Most programmers spend their careers at a comfortable altitude above the hardware. You write code, the compiler handles the translation, and somewhere beneath all that abstraction, a processor runs instructions. The details of how that happens feel irrelevant to the daily work of writing software, and for most tasks, they are.
But there are moments when those details stop being irrelevant. When your code is slower than it should be in ways that make no sense from the language level. When a loop that does half the work somehow takes the same amount of time. When adding an unrelated variable somewhere makes another part of your code faster. When multithreaded code produces results that shouldn't be possible. These things are explicable, but only if you know what the hardware is actually doing.
This is an attempt to explain what the hardware is actually doing.
The instruction set is not the machine
The first thing to get straight is the relationship between the instructions you write (or that your compiler writes on your behalf) and what the CPU physically does.
Most programmers are vaguely familiar with the idea of assembly language. x86, ARM, RISC-V. Instructions like MOV, ADD, JMP. The mental model is that these instructions are the thing the CPU executes, one at a time, in order.
That mental model was accurate for processors built before the 1990s. It has been increasingly fictional ever since.
Modern high-performance CPUs use the instruction set as a front-end interface, a compatibility layer that looks like it works the way programmers expect, while the actual execution engine underneath does something far more complicated and far more interesting. The x86 instructions your compiler produces are not executed directly. They are decoded into a different, lower-level set of operations called micro-ops, and it is those micro-ops that the execution engine actually runs. The instruction set architecture is a contract with software. The implementation behind that contract is almost entirely hidden.
Understanding what the implementation actually does requires starting with a basic model and then breaking it repeatedly until the real picture emerges.
The basic model: fetch, decode, execute
A simple processor works in a loop. It fetches the next instruction from memory, decodes it to figure out what operation it represents, and executes it. Then it moves to the next instruction and repeats. This is the classic fetch-decode-execute cycle that every computer science course covers.
The problem with this model, from a performance standpoint, is that each step takes time. Fetching from memory is slow. Decoding takes hardware. Executing takes more hardware. If you do each of these steps in strict sequence for each instruction, you spend most of your time waiting for one step to finish before the next can start.
The first major solution to this is pipelining.
Pipelining: running multiple instructions at once
A pipeline divides the fetch-decode-execute cycle into multiple stages and runs them in parallel on different instructions. While one instruction is being executed, the next is being decoded, and the one after that is being fetched. It is the assembly line applied to computation.
A simple five-stage pipeline has stages for instruction fetch, instruction decode, operand fetch, execution, and write-back of results. At any given clock cycle, five different instructions are in flight simultaneously, each at a different stage of processing. The throughput of the pipeline approaches one instruction completed per clock cycle, even though each individual instruction takes five cycles to move through all stages.
This works well when instructions flow through the pipeline without interruption. The complications arise when they cannot.
Pipeline hazards
A hazard is any situation that prevents the pipeline from advancing smoothly. There are three kinds.
A structural hazard happens when two instructions need the same hardware resource at the same time. Two instructions both needing the multiplier unit during the same clock cycle, for example. The processor has to stall one of them.
A data hazard happens when one instruction depends on the result of a previous instruction that hasn't finished executing yet. If you add two numbers and then immediately use the result in another addition, the second instruction needs a value that the first hasn't produced yet. A naive pipeline would read a stale value from the register file and produce the wrong answer.
Processors handle data hazards in a few ways. One is stalling: just hold the dependent instruction in place and wait until the value is ready. This wastes cycles. A more sophisticated approach is forwarding, also called bypassing: rather than waiting for the result to be written back to the register file and then read out again, the processor creates a direct path from the output of one execution unit to the input of another, delivering the value as soon as it is computed without the detour through the register file. Forwarding eliminates many stall cycles at the cost of more wiring in the processor.
A control hazard is the most expensive kind. It happens at branches: jumps, if statements, loops. When the processor encounters a branch instruction, it doesn't know yet which instruction comes next. It might need to jump to a completely different location in the code, or it might continue to the next sequential instruction. But the pipeline doesn't stop fetching instructions while the branch is being resolved. It has to fetch something. If it guessed wrong, it has to throw away the work it did on the incorrectly fetched instructions and start over from the right location.
Branch prediction: guessing what comes next
Branch misprediction is expensive. In a deep pipeline, the processor might have ten or twenty instructions in flight that are on the wrong path. Discovering the misprediction, flushing those instructions, and fetching from the correct location can waste fifteen or more cycles. At three gigahertz, fifteen cycles is five nanoseconds. Do that a million times a second and you've lost a significant fraction of your compute budget on wrong guesses.
Branch predictors are dedicated hardware units whose job is to guess correctly as often as possible. Modern predictors are sophisticated enough to achieve accuracy above 95 percent on typical code, sometimes above 99 percent.
The simplest predictors use static rules: always predict that backward branches are taken (because they're usually loop back-edges) and forward branches are not taken. These rules are right often enough to be useful but miss a lot of real patterns.
Better predictors maintain history tables that track the recent behavior of each branch. A two-bit saturating counter per branch remembers whether the branch was taken or not taken in recent executions and uses that to predict the next time. This handles branches that are consistently taken or not taken, and recovers from occasional exceptions without immediately flipping the prediction.
Modern processors use much more sophisticated schemes: perceptron predictors that weight multiple history bits, TAGE predictors that use tagged geometric history tables, and hybrid approaches that combine multiple prediction mechanisms and select among them based on which has been most accurate for each branch. The branch predictor in a current high-end processor is an elaborate piece of engineering that represents decades of research.
This is why branch-heavy code can be slower than it appears it should be, and why making branches more predictable is a legitimate optimization. If you have code that branches randomly, the predictor cannot learn the pattern, and you pay the misprediction penalty frequently. If you sort your data before processing it, branches that depend on data values become more predictable, and you pay that penalty rarely.
Out-of-order execution: doing work before it's asked for
Pipelining helps with the sequential flow of instructions. Out-of-order execution handles something different: the fact that even within a sequence of instructions, some can proceed while others are waiting.
Consider a sequence of instructions where the first one is a memory load, and the next few don't depend on the loaded value. A strictly in-order processor would stall on the load, waiting for memory to respond, before doing anything else. An out-of-order processor looks ahead in the instruction stream, finds instructions that don't depend on the load, and executes them while the load is still in flight.
The mechanism that makes this work is the reorder buffer. Instructions are fetched and decoded in order, then placed into a buffer that tracks them. The execution engine picks instructions from this buffer in whatever order their dependencies allow, potentially executing later instructions before earlier ones. When instructions complete, their results go back into the reorder buffer. Instructions are then retired in order, committing their results to the architectural state of the machine in the original program order.
This last part matters. From the perspective of the program, instructions happen in order. Results are visible in program order. Exceptions are handled in program order. The out-of-order execution is completely hidden behind this ordered retirement. The hardware does speculative work out of order and then presents the results as if everything happened in the sequence the programmer expected.
The depth of the reorder buffer determines how far ahead the processor can look for independent work. Processors with larger reorder buffers can keep more instructions in flight simultaneously and tolerate longer latencies from slow operations. A current high-end x86 processor might have a reorder buffer depth of 500 or more instructions.
Superscalar execution: doing multiple things simultaneously
Out-of-order execution allows the processor to find work to do while waiting. Superscalar execution allows the processor to do more than one piece of work at the same time.
A superscalar processor has multiple execution units. Multiple arithmetic logic units for integer operations, multiple floating-point units, multiple load units, multiple store units, a branch unit. In any given clock cycle, if the processor has multiple independent instructions ready to execute, it can dispatch several of them simultaneously to different execution units.
This is instruction-level parallelism, and extracting it is one of the primary jobs of a modern processor. The hardware looks at the stream of instructions, figures out which ones are independent of each other, and runs them in parallel without any intervention from the programmer or compiler.
The limit on how much parallelism can be extracted is set by the actual dependencies in the code. If every instruction depends on the result of the previous one, there is no parallelism to find. If instructions are largely independent, the processor can keep many execution units busy simultaneously. Real code sits somewhere between these extremes, and the processor's ability to find and exploit whatever parallelism exists determines a large part of its performance on that code.
The memory hierarchy: the part that changes everything
So far we've been talking as if memory access is a minor inconvenience that forwarding and out-of-order execution can mostly hide. In reality, memory is the dominant performance constraint for most programs, and understanding it is at least as important as understanding the execution pipeline.
A modern processor runs at several gigahertz. A DRAM memory access takes roughly 60 to 100 nanoseconds. At three gigahertz, one nanosecond is three clock cycles. A memory access that takes 80 nanoseconds takes 240 clock cycles. That is 240 cycles in which the processor is trying to do useful work while waiting for data that hasn't arrived yet.
Out-of-order execution can hide some of this. If there's other work to do while the memory access is in flight, the processor does it. But there's a limit to how much other work is available, constrained by the reorder buffer depth and the actual dependencies in the code. For programs that are dominated by memory accesses with not much independent work in between, the processor spends a lot of those 240 cycles doing nothing useful.
The solution is the cache hierarchy.
Caches
A cache is a small, fast memory that sits between the processor and main memory. When the processor requests data, it first checks the cache. If the data is there (a cache hit), it comes back quickly. If it's not there (a cache miss), the processor has to go to the next level of the hierarchy.
Modern processors have multiple levels of cache. L1 cache sits closest to the execution units, is very small (typically 32 to 64 kilobytes per core), and responds in three to five clock cycles. L2 cache is larger (typically 256 kilobytes to a few megabytes per core) and slower, maybe ten to fifteen cycles. L3 cache is shared among all cores on a chip, might be tens of megabytes, and takes thirty to forty cycles to access. Beyond that is main memory at hundreds of cycles.
The effectiveness of caches depends on locality. Temporal locality: if you access a memory location, you're likely to access it again soon. Spatial locality: if you access a memory location, you're likely to access nearby locations soon. Caches exploit both. Recently accessed data stays in cache. Data is fetched in cache lines (typically 64 bytes), so when you access one byte, the surrounding 63 bytes come along for free.
This is why the memory access pattern of your code matters so much. Iterating through an array sequentially is fast because you access each cache line once and then move on, and the hardware prefetcher can predict the pattern and fetch lines before they're requested. Iterating through a large array with a random access pattern is slow because every access is likely to miss the cache and require a trip to main memory.
Prefetching
Hardware prefetchers watch the pattern of memory accesses and try to predict what data will be needed next, fetching it into cache before the processor asks for it. A simple stride prefetcher detects that you're accessing memory in regular steps and prefetches ahead along that stride. More sophisticated prefetchers detect more complex patterns.
Prefetchers work well for predictable access patterns and fail for unpredictable ones. A linked list traversal, where each node contains a pointer to the next node at an address that depends on the contents of the current node, defeats most hardware prefetchers because each address is only known after the previous access completes. The processor has to wait for each pointer load to resolve before it can request the next one, with no ability to prefetch ahead.
This is one concrete reason why arrays are often faster than linked lists even for operations that should theoretically favor linked lists. Arrays have predictable access patterns that prefetchers can handle. Linked lists have pointer-chasing patterns that they cannot.
Speculative execution and what it means
Out-of-order execution and branch prediction together produce something called speculative execution: the processor executes instructions before it knows whether those instructions should execute at all.
When the branch predictor guesses that a branch is taken, the processor starts executing down the predicted path before the branch condition has been evaluated. If the prediction was correct, that work is committed and everything is fine. If it was wrong, all that work is discarded.
The processor also speculates across loads. If a load instruction is waiting for its address to be computed, and there's a later instruction that doesn't appear to depend on that load's result, the processor might execute the later instruction first. If that turns out to be valid, great. If the ordering mattered in some way the processor didn't detect, it has to replay the affected instructions.
Speculative execution is essential to extracting performance from modern hardware. It is also the source of an entire class of security vulnerabilities that were discovered starting in 2017 with Spectre and Meltdown.
The core issue is that speculative execution leaves microarchitectural traces even when its results are discarded. If speculative code brings data into cache, that data stays in cache even if the speculation is rolled back. By carefully measuring cache access times, an attacker can infer what data was loaded speculatively, including data the attacker should not have access to. The timing of a cache hit versus a cache miss is measurable, and that timing difference becomes a covert channel through which secrets can leak.
Fixing these vulnerabilities properly requires either preventing the speculation that causes them (with significant performance cost) or preventing the microarchitectural traces from being observable (which is extremely difficult to do completely). The hardware and software mitigations that have been deployed since 2017 represent an enormous engineering effort and have permanently changed how people think about the security implications of performance optimizations.
Register renaming: eliminating false dependencies
One more piece of the puzzle worth understanding is register renaming.
Programs use a limited number of architectural registers, the ones that have names in the instruction set. In x86-64, there are sixteen general-purpose integer registers. Code that does a lot of work has to reuse these registers. Register reuse creates what look like data dependencies: if instruction A writes to register R1 and instruction B later writes to the same register R1, a naive processor would think B has to wait for A because they share a register. But if B doesn't actually use A's result, this dependency is false. They could run in parallel without any correctness issue.
Register renaming eliminates this problem by mapping architectural registers to a much larger pool of physical registers. When instruction A writes to R1, it gets mapped to physical register P37. When instruction B writes to R1, it gets mapped to physical register P52. The processor tracks these mappings and uses the physical registers internally. A and B now have no register conflict and can run in parallel.
Modern processors have physical register files of 200 or more entries. This is far more than the sixteen architectural registers that code refers to. The extra registers exist to absorb the false dependencies that would otherwise prevent parallel execution. Register renaming, combined with the reorder buffer and out-of-order execution, is what allows the processor to find and exploit instruction-level parallelism even in code written without any awareness of the underlying hardware.
Putting it together: why some code is fast and some is not
With all of this in place, a few patterns become explainable.
Sequential memory access is fast because caches and prefetchers are designed for it. Random memory access is slow because every miss goes to main memory. A program whose hot path consists of sequential array iterations will run close to memory bandwidth limits. A program whose hot path consists of pointer chasing through a linked list or a tree will be limited by memory latency, with the processor spending most of its time waiting for each pointer load to resolve before it can proceed.
Branches that follow predictable patterns are cheap. Branches that are genuinely unpredictable are expensive. A branch that depends on whether a data value is positive or negative will be predictable if the data is sorted and unpredictable if it is random. Sorting data before processing it is sometimes fast not because the sorting saves computation but because it makes subsequent branches predictable.
Tight loops with lots of independent iterations are fast because the processor can keep many instances of the loop body in flight simultaneously, hiding latencies and keeping the execution units busy. Loops with tight serial dependencies between iterations are slow because each iteration cannot start until the previous one completes.
Code that thrashes the instruction cache, jumping around to many different locations, can run slower than dense straightforward code even if the scattered code does technically less work, because instruction cache misses stall the fetch stage of the pipeline.
Functions that are called very frequently benefit from staying resident in the L1 instruction cache. Code that is cold, called rarely, will have instruction cache misses when it runs. This is usually fine for cold code but means you shouldn't measure the performance of cold code and assume it represents what hot code will do.
The gap between what you write and what runs
The thing I find most interesting about all of this is how large the gap has grown between the programming model and the physical reality.
When you write a for loop, you're describing a sequential operation. The processor executes that loop with multiple iterations in flight simultaneously, with instructions from different iterations running in parallel on different execution units, with the branch predictor guessing when the loop ends before the loop condition has been evaluated, with data fetched from cache lines that arrived before they were requested. The sequential programming model is a fiction that the hardware maintains on your behalf, because the fiction is useful and the reality would be impossibly complex to program against directly.
This is mostly a good thing. The abstraction is remarkably effective and lets programmers reason about correctness without tracking the physical state of hundreds of in-flight instructions. But the abstraction leaks in performance-sensitive situations, and when it does, knowing what's underneath is the difference between debugging by intuition and debugging by understanding.
The processor is not a passive executor of your instructions. It is an aggressive, speculative, parallel machine that is constantly trying to do more work than you asked for, in an order you didn't specify, and then presenting the results as if it did exactly what you wrote. Most of the time that works perfectly. Understanding when and why it doesn't is what separates people who write fast code from people who write code and hope it's fast enough.
Top comments (0)