Misprediction: What a Wrong Guess Costs
When the predictor is wrong, everything fetched and executed down the wrong path is discarded and the pipeline refills from the correct address. The cost is not the discarded work — it is the emptiness afterwards, and it scales with how deep the pipeline is.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
Squash and refill
When the branch resolves and the prediction was wrong, the machine must undo the speculation. Instructions from the wrong path are marked invalid and their results discarded — critically, they must not have been allowed to modify architectural state, which is exactly what the in-order retirement of The Reorder Buffer and Precise State guarantees.
Then fetch restarts at the correct address, and the pipeline is empty behind it. The penalty is the time to refill: roughly the number of stages between fetch and the point where instructions begin producing results. On a deep out-of-order core this is substantial — considerably more than the five-stage model suggests.
Note what is *not* the cost. The discarded work is largely free: those execution units would otherwise have been idle. The cost is the gap afterwards, when the machine has nothing to do because the pipeline is empty. This is why the penalty tracks pipeline depth rather than how much speculative work was thrown away.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
| I1 BNE r1, r2, elsewhere | I | I | E | M | W | |||
| I2 (wrong path — squashed) | I | I | ||||||
| I3 (wrong path — squashed) | I | |||||||
| I4 (correct path) | I | I | E | M | W |
The cost in context
A single mispredict is a fixed penalty. Whether it matters depends entirely on how often it happens relative to the useful work between branches. A loop body of two hundred instructions absorbs an occasional mispredict easily; a loop body of five instructions with a coin-flip branch is dominated by it.
That ratio is the practical rule: mispredict cost matters in proportion to how small the loop body is and how random the branch is. It explains why filtering loops over random data are the canonical bad case — tiny body, data-dependent branch, executed millions of times.
It also explains why the fix is usually data-shaped rather than code-shaped. Making the branch predictable removes the penalty entirely, whereas making the loop body cheaper leaves it untouched. Optimising the body of a mispredict-dominated loop is the classic wasted afternoon.
| Situation | Impact | Reasoning |
|---|---|---|
| Large loop body, predictable branch | Negligible | Rare miss amortised over lots of work |
| Large loop body, random branch | Moderate | Penalty paid often but diluted by the body |
| Small loop body, predictable branch | Negligible | Prediction succeeds; branch is nearly free |
| Small loop body, random branch | Dominant | Penalty exceeds the useful work per iteration |
| Indirect call, varying target | Often dominant | Target mispredicts and the call body is usually small |
The sorted-array result
The best-known demonstration: a loop that conditionally accumulates elements above a threshold runs substantially faster over sorted input than over the same elements shuffled. Identical instructions, identical element count, identical arithmetic. The only difference is that sorted data makes the branch predictable, so the mispredicts disappear.
It is worth being precise about what this does and does not show. It shows that data shape drives front-end behaviour, and that the effect can exceed everything else in a small loop. It does not show that you should sort your data before every conditional — the sort itself costs, and the win only materialises when the pass is repeated or large enough to amortise it.
It is also the clearest available argument against reasoning about performance from source code alone. Two runs of the same binary, same input size, same instruction count, differing several-fold. Nothing in the program text distinguishes them; the difference lives entirely in a predictor the language does not expose (Why Reading the Source Cannot Tell You the Cost).
1data = random_values(N); // values in [0, 256)2 3// Pass A: shuffled input4sum = 0;5for (rep = 0; rep < REPS; rep++)6 for (i = 0; i < N; i++)7 if (data[i] >= 128) sum += data[i]; // ~50/50, unpredictable8 9sort(data);10 11// Pass B: identical loop, sorted input12sum = 0;13for (rep = 0; rep < REPS; rep++)14 for (i = 0; i < N; i++)15 if (data[i] >= 128) sum += data[i]; // long runs, predictable16 17// Same instructions. Same element count. Same arithmetic.18// The measurable difference is branch mispredictions.19// The size of the gap is machine-specific — measure it.Key points
- A misprediction discards wrong-path work and refills the pipeline; the penalty is the refill gap, not the discarded work.
- The penalty scales with pipeline depth, so deeper and faster-clocked cores pay more per miss.
- Impact depends on the ratio of penalty to useful work per branch — small bodies with random branches are the bad case.
- The fix is usually to change the data so the branch becomes predictable, not to make the loop body cheaper.
- Speculative work is discarded before it can affect architectural state, which is what makes speculation safe for correctness.
Progressive depth
Overview
The CPU guessed which way a branch would go, guessed wrong, and has to throw away the work it did on the wrong path and start fetching from the right one. The cost is the time the pipeline spends empty while it refills.
Practical
Whether this matters depends on the ratio of the penalty to the useful work per branch. A large loop body absorbs occasional mispredicts; a five-instruction body with a coin-flip branch is dominated by them. The fix is almost always to make the branch predictable rather than to optimise the body.
Advanced
The penalty scales with pipeline depth, which is why deeper high-frequency designs invest so heavily in prediction accuracy. On an out-of-order core the machine may also have to unwind rename state and reclaim resources allocated to squashed instructions, so recovery is not purely a fetch redirect.
Internals
Speculative execution is safe architecturally because results are committed only at retirement, in program order. It is not safe *microarchitecturally*: wrong-path instructions can still allocate cache lines and train predictors, leaving state an attacker can observe through timing. That gap between architectural invisibility and microarchitectural visibility is the whole substrate of speculative side-channel attacks (Side Channels: When Performance Optimisations Leak, Spectre and Meltdown: When Speculation Crossed a Boundary).
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Branch → resolution: the condition is evaluated and compared with the prediction made cycles earlier.
- 2Mismatch → squash: every instruction fetched after the branch is invalidated; none has been allowed to retire.
- 3Squash → fetch redirect: the front end restarts fetching from the correct target address.
- 4Refill → idle cycles: the pipeline is empty behind the redirect, so no instruction completes until it refills.
- 5Predictor → update: the true outcome is recorded so future predictions for this branch improve.
- • "The discarded work is the cost" — the discarded work was mostly free; the empty pipeline afterwards is the cost.
- • "A faster CPU will fix this" — a higher-frequency, deeper-pipelined CPU generally pays *more* per mispredict.
- • "The loop body is slow" — in a mispredict-dominated loop, optimising the body changes nothing measurable.
Consequences, controls and cost
- • Small hot loops with data-dependent branches can run several times slower than their instruction count implies.
- • Polymorphic call sites in hot paths cost far more than the indirection itself.
- • Preprocessing data to create predictability can be a net win despite its own cost.
- • Make the branch predictable by reshaping the data — sorting, partitioning, or grouping by outcome.
- • Hoist or specialise so the unpredictable decision happens once instead of per iteration.
- • Remove the branch only if the guarded work is trivial ([[branchless-code]]); if it guards expensive work, keep it.
- • Confirm with counters first — a mispredict-dominated loop and a memory-bound loop look identical from source.
- • Read branch misses per instruction; correlate with the specific loop via sampling on the branch-miss event.
- • Run the same code on sorted versus shuffled data — the difference isolates prediction from everything else.
- • Compare against a branchless variant as a diagnostic even if you do not ship it: a large improvement confirms the branch is the cost.
- • Data reshaping costs time, memory and sometimes ordering guarantees the rest of the program relied on.
- • Branch removal always does both sides of the work, which is a loss when the guarded path is expensive.
- • Any of these tunings can regress on a different microarchitecture with a different penalty or a better predictor.
Scope
§224 — what these claims are specific to.
- MICROARCH-SPECIFICPenalty magnitude tracks pipeline depth and is unpublished on most designs. A shallow in-order core may pay a handful of cycles where a deep speculative core pays several times that.
- SIMPLIFIEDThe pipeline diagram shows resolution at EX in a five-stage model. Real cores resolve later and speculate further ahead, so both the amount of squashed work and the refill gap are larger.