Branch Prediction

Why branch prediction matters

• Pipeline depth. Modern Intel and AMD pipelines are 14-20 stages deep. Without prediction, every branch stalls the pipeline waiting for the condition to evaluate — losing 15+ cycles per branch. With ~20% of all instructions being branches, that would cap IPC (instructions per cycle) below 1; predictors are why we get IPC of 4-8 on modern cores.
• Tight loops. Loop back-edges are nearly always taken; the predictor learns this in 1-2 iterations and sustains 99%+ accuracy. Mostly-predictable loops are why CPUs achieve their advertised peak throughput.
• Profile-guided optimization (PGO). Compilers like GCC, Clang, MSVC use runtime branch profiles to lay out code so the likely branch falls through, packing hot code densely in I-cache and aligning branches favorably for the predictor.
• Branchless code. When prediction fails (e.g. random/data-dependent conditions), branchless equivalents using cmov, masks, or min/max avoid the misprediction penalty even at the cost of always doing both arms of the conditional.
• JIT compilers. V8, HotSpot, .NET emit branch prediction-aware code, including type guards that trade an occasional misprediction (deopt) for the common-case speed.
• Security. Spectre, Meltdown, and successors weaponize speculative execution to leak microarchitectural state. Mitigations (retpoline, IBPB, IBRS) cost 5-30% on syscall-heavy workloads.

How a modern predictor works

A current Intel/AMD predictor combines several mechanisms in parallel:

• BTB (Branch Target Buffer). Cache of recently-encountered branch instructions and their targets. Hit means the CPU knows where to fetch from before decoding the branch instruction. Sized 2K-8K entries.
• Direction predictor. Predicts taken/not-taken. Modern designs use TAGE: multiple tables tagged with different history-length hashes, the longest matching tag wins. Captures both short-range and long-range branch correlations.
• Indirect branch predictor. For computed jumps (vtable, switch tables, function pointers), a separate target-prediction structure indexed by recent history.
• Return Stack Buffer (RSB). Mini hardware stack tracking call/return pairs; predicts return targets without consulting the BTB.
• Loop predictor. Recognizes simple loops (e.g. for i in 0..100) and predicts the exit branch correctly on the final iteration.

The end-to-end accuracy on SPECint 2017 reaches 97-99% for loops and structured code, dropping to 90-95% on hash-table walks and indirect-call-heavy OOP code.

Anatomy of a misprediction

A misprediction unfolds as follows:

1. Branch fetched. Predictor guesses NOT TAKEN. Pipeline fetches sequential instructions speculatively.
2. Speculative instructions decode, dispatch, execute out-of-order. Some commit, some buffered in reorder buffer (ROB).
3. 10-20 cycles later, the branch resolves: it WAS taken.
4. Pipeline is flushed: ROB drained, register renaming reset, fetched instructions discarded.
5. Fetch redirected to the correct branch target. Pipeline refills (15-20 cycles to a fully-issued state).

Net cost: 15-20 cycles of useful work lost per misprediction. At a 3 GHz clock that's 5-7 nanoseconds — equivalent to an L2 cache hit. Frequent mispredictions tank IPC: a workload mispredicting 5% of branches with 15-cycle penalty effectively pays 0.75 cycles per branch instruction, halving observed throughput.

The famous sorted-array example

The Stack Overflow question "Why is processing a sorted array faster than an unsorted array?" (2012, 1.5M views) demonstrated branch prediction's impact:

// Unsorted array, random values 0..255
int sum = 0;
for (int i = 0; i < ARRAYSIZE; ++i) {
    if (data[i] > 128) sum += data[i];
}

With unsorted data, data[i] > 128 is true ~50% of the time at random positions. The predictor's accuracy plummets to 50%; every other iteration eats a 15-cycle penalty. Measured: ~11 seconds for 100M iterations on an Intel i7 of that era.

Sort the array first: now the branch is taken for the first half, not-taken for the second half. The predictor learns each segment in 2 iterations and stays correct. Measured: ~1.9 seconds — a 5.7× speedup. The instructions executed are identical; only the branch outcome pattern changes.

Branchless alternatives

When data is genuinely unpredictable, branchless code avoids the penalty:

// Branchless: always compute, mask via comparison
int t = (data[i] - 128) >> 31;  // 0 if >=128, -1 otherwise
sum += data[i] & ~t;

No conditional jump — the CPU pipeline never has to predict. On the unsorted benchmark, branchless is ~2.0 seconds, comparable to the sorted version. The trade-off: branchless does both "halves" of work always; for highly imbalanced or predictable branches, branchful + good prediction is faster because skipped work stays skipped.

Measurement tools

• Linux perf. perf stat -e branch-misses,branches reports miss rate. perf record -e branch-misses samples mispredicting PCs for source-level attribution.
• Intel VTune. Microarchitecture Exploration analysis breaks down "Bad Speculation" as a top-level bottleneck category.
• AMD μProf. Equivalent to VTune for AMD CPUs.
• Apple Instruments. CPU Counters template exposes branch_mispred events.
• llvm-mca / uica.uops.info. Static analysis of expected branch behavior in tight loops.

A first-cut diagnostic: branch miss rate >1% of total branches indicates either intrinsic data unpredictability or insufficient predictor warmup; >5% is a serious bottleneck worth restructuring code for.

Common misconceptions

• "Modern CPUs predict perfectly." 99% accuracy still means a misprediction every 100 branches; with 20% branch density, that's one penalty every 500 instructions. On a 4-IPC core, that's 6-7 ns of stall per ~150 ns of work. Far from invisible.
• "Spectre is fully fixed." Mitigations exist for known variants but new speculative side channels keep appearing (Branch History Injection 2022, Inception 2023). The fundamental tension between speculation and isolation remains unresolved.
• "Branchless is always faster." Only when prediction would have failed. For highly predictable branches, branchful code skips the unused arm entirely; branchless always evaluates both. Profile before refactoring.
• "likely/unlikely macros directly improve runtime." They mostly improve I-cache layout and rarely-taken-path attribution; on modern x86 the dynamic predictor learns the same information from the first few executions. Their effect is real but small (typically 1-3% on hot code, more on cold paths).
• "Switch statements always use a jump table." Modern compilers prefer binary-search trees of comparisons for sparse switches and small jump tables for dense ones, plus they sometimes lay out cases by frequency from PGO. Indirect-jump prediction is harder than direct-branch prediction; misprediction rates 5-15% are common on virtual dispatch.
• "You don't have to think about branches in high-level languages." JIT compilers (HotSpot, V8, .NET) emit branchful machine code with the same prediction behavior. A poorly-laid-out conditional in JavaScript still pays misprediction penalties.

Design implications

• Sort before scan when downstream code branches on values.
• Use branchless idioms — min, max, abs, bit tricks — for hot loops with unpredictable conditions.
• Hoist predicates out of loops when possible; one branch per loop is better than per-iteration.
• Group similar work together. Polymorphic dispatch on heterogeneous lists devastates indirect predictors.
• Exploit PGO/BOLT/Propeller to align branches and lay out hot code densely in I-cache.
• Tolerate misprediction on cold paths (error handling, logging) — readability wins.