Branch Prediction
Branch prediction guesses control flow before it resolves, keeping pipelines full; mispredictions flush the pipeline at 15 to 20 cycles each, making data layout and branch order performance-visible.
Definition
Modern CPUs speculate past branches by predicting their outcome and target. A correct prediction costs nothing; a misprediction flushes the speculative work and restarts, costing tens of cycles. Predictors learn history per branch, so code that sorts or organizes data into predictable patterns runs dramatically faster than logically identical but random-order code.
Context and scope
Explains why sorted-input loops outperform unsorted ones, why branchless arithmetic wins in hot paths, and why virtual dispatch shows cost beyond cache misses.
Common misconceptions
- Branch prediction only matters in tight numeric loops — mispredict costs appear in parsers, dispatch tables, and validation code too
- Compiler flags fix branch behavior — data layout drives global history predictors; code shape alone does not dominate
- Misprediction cost is one or two cycles — flush cost is tens of cycles, comparable to an L1 miss penalty
Anti-patterns
- Sorting data only for algorithmic reasons and missing the branch-predictability speedup as a bonus — or vice versa, assuming sort is the algorithmic win
- Branching on unpredictable booleans in hot loops instead of arithmetic or table lookups
- Optimizing cold code for branch behavior and adding unreadable branchless constructs for negligible gain
Related concepts
Authoritative source
What it is
Pipelines execute dozens of instructions in flight. A branch would stall that until resolved; instead, the predictor guesses and the machine charges ahead speculatively. Wrong guesses discard the work.
How it works
Predictors track per-branch history and global patterns, achieving over 95 percent accuracy on structured code. Data-dependent branches — if data[i] > threshold — inherit the data distribution: sorted input makes them nearly monotonic; random input makes them coin flips. Branchless forms — masks, conditional moves, table indexing — remove the branch entirely.
When to care
Hot loops with data-dependent conditionals, parsers switching on input, and dispatch-heavy interpreters. Restructuring to branchless or partitioning data by branch outcome yields order-of-magnitude swings in classic demonstrations.
Pitfalls
Branchless code is harder to read and not always faster: it forces both paths to compute. Speculation interacts with security — Spectre-class attacks leak via speculative execution, which is why prediction behavior is also a security surface. Profile before restructuring; predictors already handle most structured code well.