Branch Prediction: Guessing Well Enough to Matter
The CPU has to supply a fetch address before it knows the branch outcome, so it predicts one from history. Modern predictors are accurate enough that well-behaved code pays essentially nothing for its branches — which is exactly why the badly-behaved cases stand out so sharply.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
Prediction from history
The simplest useful idea: remember what this branch did last time and guess it will do the same. That alone handles loop back-edges extremely well — a loop running a thousand iterations is taken 999 times and not-taken once, so a last-time predictor is right 99.9% of the time.
Real predictors go considerably further, correlating outcomes with recent branch history so they can learn patterns rather than just a most-recent value. A branch that alternates, or one whose outcome correlates with an earlier branch, can be predicted well by a scheme that considers history rather than only the branch's own last result.
Indirect branches need a target rather than a direction, so they use a separate structure remembering recent destinations per call site. Returns get their own mechanism — a small stack that pairs each call with its return address, which is why returns predict almost perfectly despite being indirect.
| Branch behaviour | Predictability | Why |
|---|---|---|
| Loop back-edge, many iterations | Excellent | Taken almost every time; one miss on exit |
| Condition constant for the whole run | Excellent | Always the same outcome |
| Outcome in long runs (sorted data) | Very good | Only the transitions between runs mispredict |
| Short repeating pattern | Good | History-based schemes learn the pattern |
| Outcome correlated with an earlier branch | Good | Global history captures the correlation |
| Outcome genuinely random per iteration | Impossible | There is no pattern to learn — chance is the ceiling |
Why prediction is so accurate in practice
Most branches in real programs are not decisions in any interesting sense. They are loop conditions, bounds checks that always pass, null checks that always fail, error paths never taken, and feature flags fixed for the process lifetime. All of those are trivially predictable, and modern predictors get them right nearly always.
This has a design consequence people often find surprising: adding a cheap, predictable branch to avoid expensive work is almost always a win. A bounds check costs essentially nothing when it always passes. A guard clause that skips a costly path is close to free when it is usually taken. The reflex to remove branches for performance is generally wrong.
The mirror image is that the small minority of unpredictable branches can dominate. A single data-dependent branch in an inner loop over random data can cost more than everything else in the loop combined, and it will not appear in a profile as anything other than "this loop is slow".
Making branches predictable
The most effective technique is to change the *data* rather than the code. Sorting or partitioning input so that a branch's outcome comes in long runs converts a random branch into a highly predictable one. On a large enough dataset processed repeatedly, the sort pays for itself several times over — a genuinely counter-intuitive result that measures well.
The second technique is to hoist. A condition that does not change within a loop should be evaluated outside it, even at the cost of duplicating the loop body. This converts one unpredictable branch per iteration into one branch total.
The third is to accept the branch and stop optimising it. If the outcome is genuinely random and the guarded work is substantial, the branch is doing its job: skipping work. Removing it via Branchless Code: A Trade, Not an Upgrade means always doing both sides, which is only a win when the guarded work is trivial. Measure before assuming which regime you are in.
1for (i = 0; i < n; i++) {2 if (config.use_fast_path) // loop-invariant, but the3 fast(data[i]); // branch is still executed4 else // n times5 slow(data[i]);6}1if (config.use_fast_path) {2 for (i = 0; i < n; i++) fast(data[i]);3} else {4 for (i = 0; i < n; i++) slow(data[i]);5}6// One branch total instead of n. Also lets the compiler7// optimise each loop body without the other in the way.The original branch was already highly predictable, so the direct branch saving is modest. The larger win is that each specialised loop can now be optimised — and possibly vectorised (Auto-Vectorization: Verify, Do Not Assume) — without a conditional in the body. Compilers often perform this transformation themselves; the point is understanding why it helps when they do not.
Key points
- Predictors guess direction and target from history, supplying a fetch address before the condition is evaluated.
- Most real-program branches are highly predictable: loop conditions, checks that always pass, paths never taken.
- Adding a predictable branch to skip expensive work is usually a win, not a cost.
- Only genuinely pattern-free outcomes are unpredictable — and those can dominate a loop.
- Changing the data to create runs is often more effective than changing the code.
Branch Predictor Lab
Change an input and watch which number moves — and which one refuses to.
Real predictors are far more sophisticated — they correlate across branches and keep long histories. This one is the classic teaching model, and it already shows the shape: patterns are learnable, randomness is not.
The predictor is learning but still paying. Each miss costs a full pipeline refill, and that cost scales with pipeline depth.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Branch address → predictor lookup: the front end indexes history structures using the branch's address and recent global history.
- 2History → predicted direction: the predictor supplies taken or not-taken before the condition has been evaluated.
- 3Indirect branch → target buffer: for indirect transfers, a separate structure supplies a predicted destination address.
- 4Prediction → speculative fetch: the front end continues fetching and executing down the predicted path.
- 5Resolution → predictor update: the actual outcome updates the history so future predictions improve.
- • "Fewer branches is faster code" — predictable branches are free and often save far more work than they cost.
- • "The predictor will learn my pattern eventually" — only if there is a pattern; randomness has no learnable structure.
- • "Branch-miss rate is low so branches are fine" — a low overall rate can hide one catastrophic branch in a hot loop; look per-site.
Consequences, controls and cost
- • Well-structured code pays essentially nothing for its branches, which is why branch counts are a poor performance proxy.
- • A single unpredictable branch in a hot loop can cost more than the rest of the loop combined.
- • Sorting input before a branch-heavy pass can reduce total time despite the sort's own cost.
- • Reshape the data so branch outcomes come in runs — sorting or partitioning is the highest-leverage change.
- • Hoist loop-invariant conditions out of loops, specialising the body for each case.
- • Devirtualise or de-polymorphise hot indirect call sites so target prediction succeeds.
- • Leave predictable branches alone; removing them is a common and usually counterproductive reflex.
- • Read branch instructions and branch misses together; the ratio is the accuracy, and per-site attribution is what identifies the culprit.
- • Compare runtime on sorted versus shuffled input for the same code — the difference is almost entirely prediction.
- • Use sampling with branch-miss as the sampling event, where supported, to locate the specific branch rather than the loop.
- • Sorting for predictability costs time and memory and only wins at sufficient scale or reuse.
- • Hoisting conditions duplicates loop bodies, increasing code size and instruction-cache pressure.
- • Any tuning aimed at predictor behaviour is fragile, because predictor internals are unpublished and change between generations.
Scope
§224 — what these claims are specific to.
- MICROARCH-SPECIFICPredictor structures, capacities and algorithms are proprietary and differ per generation. Only the history-based principle and the impossibility of predicting randomness are general.
- GENERALThat prediction is required by pipelining, and that accuracy determines whether branches are free or expensive, holds on every speculating processor.