Out-of-Order Execution
You wrote A, B, C. If B is waiting on a cache miss, the machine will run C first — and then hand you a result indistinguishable from having run them in order. This is the lesson where "the CPU executes my code line by line" stops being a useful model.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
The window, not the line
A modern core does not fetch one instruction, run it and move on. It fetches a block, decodes it into internal operations, and drops those into a scheduling window. Every cycle, the scheduler looks across that whole window and picks operations whose inputs are already available and whose required execution port is free. Program order is an input to that decision only insofar as it defines the dependencies.
The consequence is that a long-latency operation does not stop the machine — it stops *the operations that need its result*. In the trace below, B loads from memory and misses cache. In an in-order machine everything behind B waits. In an out-of-order machine, C and D do not depend on B, so they issue and complete while B is still outstanding. Only E, which consumes B's value, has to wait.
This is why "how many instructions does this loop execute" is such a weak predictor of speed. The scheduler is trying to keep every port busy every cycle; whether it succeeds depends on whether you gave it independent work to find. That framing — the machine is hunting for parallelism inside your single thread — is the whole subject of Instruction-Level Parallelism.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
| A r1 = r2 + r3 | i | e | d | |||||
| B r4 = load [r9] | i | e | w | w | w | w | d | |
| C r5 = r6 * r7 | i | e | d | |||||
| D r8 = r5 + 1 | i | e | d | |||||
| E r10 = r4 + r8 | w | w | w | i | e |
What actually guarantees correctness
If operations complete in a scrambled order, something has to restore the illusion. That something is in-order retirement. Completed results are held in a buffer rather than written straight to architectural registers and memory; the machine retires them strictly in program order, and only at retirement does a result become part of the state the ISA describes. The mechanism is the subject of The Reorder Buffer and Precise State.
This split gives you a precise definition worth carrying around: execution is when the work happens, retirement is when it counts. Everything between the two is speculative in the broad sense — it can still be discarded. If instruction B raises a page fault, every operation after it that already executed is thrown away, and the fault is reported as though nothing past B had run at all. That property is called a *precise exception*, and it is why debuggers, signal handlers and try/catch work at all on a machine that reorders aggressively.
Note carefully what is *not* guaranteed. In-order retirement preserves the illusion for the thread doing the executing. It says nothing about what a different core observes about the order of your memory operations — that is a separate mechanism with separate rules, and it is why Why Your Loads and Stores Happen Out of Order and Memory Barriers: Ordering, Not Flushing exist as topics at all. Single-threaded code gets its illusion for free; multi-threaded code has to ask for it.
| Execution order | Retirement order | |
|---|---|---|
| Determined by | Operand readiness and port availability | Program order, always |
| Visible to this thread | No | Yes — this *is* the architectural state |
| Visible to another core | Only via memory, under the memory model | Only via memory, under the memory model |
| Can be discarded | Yes — misprediction, fault, or exception | No, by definition |
| Reordered relative to source | Freely, subject to dependencies | Never |
What it changes about how you read your own code
The practical shift is from counting operations to looking for chains. Both loops below perform the same number of additions over the same data. The first threads every addition through one accumulator, so each iteration cannot start until the previous one finished — a chain as long as the array, each link paying the full latency of an add. The second keeps four partial sums, giving the scheduler four independent chains to interleave, and the adds overlap.
On a machine with more than one add port and pipelined addition, that difference can be substantial — and nothing in the source suggests it. The instruction counts are identical; the compiler cannot make the transformation for floating point without permission, because reassociating floating-point addition changes the result (Why 0.1 + 0.2 Is Not 0.2 + 0.1's Problem). The programmer has to know the machine is looking for independent work and give it some.
The general habit: when a loop is slower than its arithmetic suggests, ask what the longest dependency chain through one iteration is, and whether the loop body can be split into chains that do not touch each other. That question is worked properly in Dependency Graphs: The Real Shape of Your Code.
1sum = 02for i in 0..n:3 sum = sum + a[i] # each add waits for the previous add4 5# chain length: n adds, each paying full add latency6# the scheduler has nothing independent to overlap1s0 = s1 = s2 = s3 = 02for i in 0..n step 4:3 s0 = s0 + a[i+0] # four chains, none waiting on another4 s1 = s1 + a[i+1]5 s2 = s2 + a[i+2]6 s3 = s3 + a[i+3]7sum = s0 + s1 + s2 + s38 9# same instruction count, four times the available parallelismIdentical work, identical instruction count. The second version differs only in that consecutive additions are independent, so the out-of-order scheduler can have several in flight at once instead of serialising on one register. For floating point this is a semantic change — the sums are grouped differently — which is exactly why the compiler will not do it unless you allow reassociation.
Key points
- The machine holds a window of pending operations and issues each one when its inputs are ready, not when its turn arrives in program order.
- A long-latency operation stalls only its dependents, not the instructions behind it in the source.
- In-order retirement is what preserves the illusion: execution is when work happens, retirement is when it counts.
- Precise exceptions fall out of in-order retirement — everything after a faulting instruction is discarded as if it never ran.
- The limit on such a machine is the dependency graph, not the instruction count.
Progressive depth
Overview
The CPU keeps many instructions in flight and starts each one when its inputs are ready rather than when its turn comes. It still finishes them, officially, in the order you wrote — so your results are unaffected and only your timing changes.
Practical
Optimise the dependency chain, not the instruction count. If a loop threads everything through one accumulator or one pointer, the machine has nothing to overlap and you are paying full latency per step. Splitting into independent chains is often the single highest-leverage change to a hot arithmetic loop.
Advanced
The window is a finite resource and fills up. A single long-latency miss at the head of the reorder buffer eventually blocks retirement, and once the buffer is full the front end stalls even though ports are idle. This is why one badly-placed cache miss can cost far more than its own latency, and why memory-level parallelism (Misses That Overlap Are Nearly Free) matters as much as memory latency.
Internals
Renaming removes write-after-write and write-after-read hazards by mapping architectural names onto a larger physical register file, leaving only true data dependencies to constrain the scheduler (Register Renaming). Loads may issue speculatively before earlier stores have computed their addresses; if a store later proves to alias, the load and everything depending on it is squashed and replayed. Memory disambiguation of this kind is one of the more expensive predictors in a modern core, and it is entirely MICROARCH-SPECIFIC.
Out-of-Order Scheduler
Change an input and watch which number moves — and which one refuses to.
Everything waits for the instruction ahead of it, so the cache miss stalls the whole machine even though two of these instructions need nothing from it. Switch to out-of-order and watch the total drop without a single instruction getting faster.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Front end → decoder: a fetched block is decoded into internal operations, which may be more or fewer than the instructions you wrote.
- 2Decoder → rename: architectural register names are mapped onto a larger physical file, removing reuse-induced false dependencies (Register Renaming).
- 3Rename → scheduler window: operations wait here, tracked by which operands they still need.
- 4Scheduler → execution port: every cycle, ready operations are issued to whichever units are free — this is where program order stops mattering.
- 5Execution → reorder buffer → retire: results are buffered, then committed strictly in program order, making them architecturally visible.
- • "The CPU executes one instruction at a time, in order." It executes many at once, out of order, and only *retires* in order.
- • "Fewer instructions is always faster." A shorter dependency chain usually beats a shorter instruction sequence.
- • "Out-of-order execution means my results can come out in the wrong order." Within a thread it cannot; retirement guarantees that.
- • "The profiler blamed this line, so this line is slow." Stall attribution is approximate — look for the load that missed, not the instruction that was retiring.
- • "If it reorders freely, my locks are unsafe." Locks work because of memory ordering rules and barriers, which are a separate mechanism from this one.
Consequences, controls and cost
- • Adding independent work to a memory-stalled loop can cost close to nothing, because the machine had idle ports anyway.
- • Restructuring a loop to break one long dependency chain into several short ones can speed it up without changing the instruction count.
- • Profilers attribute stall time imprecisely: the instruction blamed is often the one retiring when the stall cleared, not the load that caused it.
- • Single-threaded code never observes the reordering; multi-threaded code can, through memory, which is why a separate memory model exists.
- • Microbenchmarks that measure a single dependent chain measure *latency*; ones that measure independent work measure *throughput*. They give different answers for the same instruction.
- • Break long dependency chains — multiple accumulators, unrolling, reassociating where semantics allow — so the scheduler has independent work to find.
- • Reduce the latency of the chain itself: fewer indirections, cheaper operations, and data that is already in cache.
- • Give the machine memory-level parallelism: several independent loads in flight beat one pointer chase ([[memory-level-parallelism]], [[pointer-chasing]]).
- • Avoid mistaking instruction count for cost when optimising; count chain length instead.
- • For floating point, decide explicitly whether reassociation is acceptable — the compiler will not assume it is.
- • Compare a dependent-chain microbenchmark against an independent-work one for the same operation: the gap is the latency-versus-throughput difference the scheduler exploits.
- • Read IPC ([[ipc]]) alongside stall counters — high stalls with low IPC means the window is full of operations waiting on something.
- • Use counters that attribute cycles to stall reasons (backend-bound versus frontend-bound categories) rather than reasoning from source position.
- • Unroll a loop with independent accumulators and re-measure; if the time drops with identical instruction counts, you were chain-limited.
- • Cross-check with [[performance-counters]] on the real target machine — window size and port mix differ enough between cores that a result on one says little about another.
- • Manual chain-breaking costs readability and can change floating-point results; it is worth doing only where measurement showed a chain-limited loop.
- • Unrolling increases code size, which pressures the instruction cache ([[instruction-cache]]) and can hurt a loop that was not chain-limited.
- • The hardware machinery itself is expensive in area and power, which is why small cores implement narrower windows or none at all.
- • Reasoning about the window is inherently machine-specific; a tuning decision that helps on one core can be neutral or negative on another.
Scope
§224 — what these claims are specific to.
- MICROARCH-SPECIFICWindow size, issue width and port mix differ by generation and by core type. Big performance cores hold hundreds of operations in flight; small efficiency cores hold far fewer, and some embedded cores execute strictly in order with none of this machinery.
- SIMPLIFIEDThe pipeline trace shows issue/execute/wait/done only. Real cores add fetch, decode, rename, dispatch, several scheduler queues and a retirement stage, and split instructions into micro-operations that do not map one-to-one onto what you wrote.
Misconceptions
Where the rest of this lives
In-order retirement makes reordering invisible to the thread doing it, but not to other threads observing through memory. The rules for what another thread may see are a correctness question rather than a performance one, and belong with concurrency reasoning.
The instruction stream the scheduler sees has already been rearranged once by the compiler, under the language's as-if rule. Two independent layers of reordering sit between your source and the execution units.