Branch prediction
A Socratic walk-through of branch prediction — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why can a processor finish work faster by guessing the outcome of a test before it knows the answer?
A program reaches an if. Until the condition is evaluated the machine cannot know which instruction comes next — and yet processors do not wait. They pick a direction, run down it, and throw the work away if they picked wrong.
Guessing plus occasional wholesale waste beats waiting for the answer. That sounds like paying twice. So either waiting costs far more than it appears to, or being wrong costs far less. Which is it?
Reasoning it through
REASONING #Both, and the second is the surprising half.
Start with why waiting costs anything. A processor is an assembly line: fetch, decode, schedule, execute, write back, each several stages deep, so a modern core has many instructions part-finished at any moment. The branch's condition is computed deep in the line; the address of the next instruction to fetch is needed at the very front of it. Those points are many cycles apart, and no engineering closes the gap, because the gap is the pipeline.
So a machine that waits stops fetching until the branch resolves, and the line drains. How often? In ordinary general-purpose code something like one instruction in five is a branch — a figure I recall as a rough characteristic of such code, not a measurement. A stall of pipeline-depth cycles every five instructions is barely a pipelined processor at all.
Now the other half. Suppose the machine guesses wrong. It fetched and part-executed instructions from the wrong path and must discard them and restart the front end — but those cycles are exactly the cycles it would have spent stalled anyway. The wrong guess costs about what not guessing would have cost. Being right is nearly free, and being wrong is nearly free of extra cost, so any accuracy above zero is profit.
Does that argue for a coin flip? The arithmetic says otherwise, loudly. Take a scenario — illustrative round numbers, not any chip's. One instruction in five is a branch, a misprediction costs 15 cycles of refill, and the machine retires 4 instructions per cycle when nothing goes wrong, which is 0.25 cycles per instruction. Extra cycles per instruction are branch density × miss rate × penalty.
- Coin flip, 50 percent wrong: 0.2 × 0.5 × 15 = 1.5 extra. Total 1.75 cycles per instruction, about 0.57 instructions per cycle — roughly a seventh of what the machine can do.
- 5 percent wrong: 0.2 × 0.05 × 15 = 0.15. Total 0.40, giving 2.5 per cycle, about 62 percent of peak.
- 1 percent wrong: 0.2 × 0.01 × 15 = 0.03. Total 0.28, giving about 3.57, about 89 percent of peak.
Sit with the last two. Four percentage points of accuracy bought 43 percent more throughput, while the coin flip is nearly worthless. Almost the whole value of prediction lives in the final few percent, which is why processors spend a startling amount of silicon on it. And a deeper, wider machine raises both the penalty and the count of instructions discarded, so the payoff for accuracy rises with the ambition of the design. That relationship is the durable fact, not any particular predictor.
Why is such accuracy attainable? Because control flow is not random. A loop's back-edge is taken every iteration but the last; an error check is essentially never taken; a branch on a flag set earlier is determined by the earlier branch. Predictability is an empirical property of real programs — the same kind of claim as locality of reference is for caches, and just as defeasible by a program written to break it.
So real predictors do not guess "taken"; they learn. The base scheme keeps a table of small saturating counters indexed by branch address, so one anomalous outcome nudges a confident prediction rather than flipping it — exactly right for a loop that exits once per thousand iterations. A global history register then records the recent taken/not-taken pattern and is hashed with the branch address, so a branch correlated with earlier ones gets a separate entry per context. Modern designs keep several tagged tables indexed with geometrically increasing history lengths.
The falsification test. Take a loop that examines each element of a large array and does work when the value exceeds a threshold. Run it on the same data twice, shuffled and sorted. Instruction count, memory footprint and access pattern are identical; the only difference is that sorting turns one data-dependent branch into a long run of taken followed by a long run of not-taken, which any history-based predictor learns immediately. The prediction is a large runtime gap, with the branch-misprediction counter moving in step. The refuting observation is a null result, or a gap with no matching change in that counter — either would put the cost somewhere else, most likely the memory system.
The analogy
THE ANALOGY #Think of a cook who starts the most likely order the moment a regular sits down, before the ticket reaches the pass. Right guess, and the plate goes out immediately. Wrong, and the half-made dish is scraped — but the cook has lost only time that would have been spent standing still.
the scraped dish wastes ingredients, whereas mispredicted instructions consume no material at all — and the cook keeps no record of who orders what, whereas the record is the whole art of a predictor.
Clarifying the model
THE MODEL #Two neighbours to place, and one correction.
Caching, elsewhere in this collection, exploits locality in the stream of addresses a program touches. Branch prediction exploits regularity in the stream of control decisions. The fixed point of difference is what each does with the wait: a cache shortens it, a predictor refuses to have one, proceeding without the answer and reconciling later.
Speculative decoding is the closer relative and the same bargain in different clothing: something cheap proposes, something expensive verifies, and a wrong proposal is discarded rather than allowed to change the result. What differs is the cost of a rejection. There, a rejected draft token throws away work the large model would have done anyway. Here, a misprediction throws away a pipeline's worth of instructions — and the deeper the machine, the more that is.
The correction matters. "Wrong work is discarded with no effect" is true architecturally: registers and memory end up as if the mispredicted path never ran. It is false microarchitecturally. Speculative instructions leave traces — cache lines fetched, timings changed — and Spectre-class attacks exist because those traces survive the rollback.
A picture of it
THE PICTURE #How to readTime runs downward. The front end must choose an address long before the back end can resolve the condition, so it asks the predictor, which answers from a record of what this branch did before. The gap between the third and fourth messages is the whole opportunity: many cycles of work done on an unconfirmed assumption. The two branches at the bottom are the only outcomes — above the divider nothing is lost; below it the work is discarded, the record corrected, and fetching restarts. The cost of the lower path is the height of that gap.
What became clearer
WHAT CLEARED #Waiting is expensive because the branch resolves deep in a long pipeline while the next address is needed at its head, and branches are frequent. Guessing is cheap because a wrong guess costs about what waiting would have cost anyway, so speculation pays at any accuracy above zero. But the value is not spread evenly: a coin flip recovers almost nothing, and the last few points of accuracy are worth tens of percent of throughput. The durable constraint is pipeline depth against control-flow regularity; every specific predictor is a passing answer to a permanent question.
Where to go next
ONWARD #- Why an indirect branch through a function pointer or virtual call is a harder problem than a conditional one.
Key terms
TERMS #| Term | What it means |
|---|---|
| Misprediction penalty | the cycles lost discarding speculative work and refilling the front end after a wrong guess. |
| Saturating counter | a small counter that must be pushed repeatedly before it changes its prediction. |
Every term the collection defines is gathered in the glossary.