Skip to main content
Be Bitwise

Branch Prediction

CPU Pipeline & Microarchitecture · CPU Architectures track

7 min read

Part ofSystems Programming Companion, week 6

In this module

Predicting the Future

A typical program runs into a branch every 5-8 instructions. On a 15-stage pipeline, each misprediction torches roughly 15 cycles of work — every speculatively executed instruction has to be thrown away. Without branch prediction, the CPU would stall at every branch and run at a fraction of its potential. Modern predictors hit 95-99% accuracy, which is what makes speculative execution viable in the first place.

Static Prediction

The simplest strategies need zero runtime history:

  • Always not-taken: assume branches never fire and just keep fetching the next sequential instruction. Works fine for error-checking branches like if (error) handle_error() that almost never trigger.
  • Always taken: assume every branch fires. It does better than not-taken on loop-heavy code, but wastes fetches on rarely taken forward branches.
  • Backward-taken, forward-not-taken (BTFN): bet that backward branches (loops) are taken and forward branches aren't. Loops spin many times before they exit, so backward branches usually go.

Static prediction is the fallback when the dynamic predictor has nothing to go on — a cold start, or the first time it sees a branch.

Dynamic Prediction

Dynamic predictors keep a Branch History Table (BHT) that logs recent outcomes. The simplest dynamic scheme is a 2-bit saturating counter per branch:

Predict Taken in state 10 or 11 (Weakly or Strongly Taken). Predict Not Taken in 00 or 01.

The 2-bit counter needs two consecutive mispredictions to flip its prediction, which fits how loops behave. The exit iteration mispredicts once, but the counter only sags to "weakly taken" and gets the next iteration of the outer loop right.

Try it on a few patterns. Each run feeds one branch 48 outcomes, and every counter starts at 01. Start with the loop of 8 and compare the 1-bit predictor with the 2-bit counter: the 1-bit one pays twice per loop exit, the 2-bit one once. Then pick the alternating pattern and watch the 2-bit counter get every single prediction wrong, bouncing between 01 and 10. The 2-level predictor in the last button is the one the next section describes, with two bits of history.

Pattern
Predictor

The branch at the bottom of an 8-iteration loop: taken 7 times, then not taken once on exit, and the loop starts again.

0 of 48 branches
················································

Each square is one execution of the branch: T for taken, N for not taken. Green means the prediction was right, red means it missed.

Last outcome: not taken, so predict not taken.

Random outcomes are the control: nothing beats a coin flip by much, because there's no pattern to learn.

Two-Level Adaptive Predictors

Real workloads have patterns too messy for a simple loop predictor. A branch might alternate taken/not-taken, or its behaviour might be correlated with branches that came before it. Two-level predictors capture these patterns by keeping a history register of recent outcomes and using it to index into a table of counters.

This learns surprisingly intricate patterns. If a branch alternates T-N-T-N, then after seeing [T,N] the predictor looks up "TN" and predicts T. After [N,T], it looks up "NT" and predicts N. Job done.

Modern CPUs use global history — the outcomes of the last N branches from anywhere, not just the current one — combined with the branch address to index the table. That picks up correlations between different branches scattered through the program.

TAGE: The State of the Art

Most modern high-performance CPUs run TAGE — TAgged GEometric history length. TAGE keeps multiple prediction tables indexed by different history lengths (a geometric series, such as 4, 8, 16, 32, 64, 128, ...). For each branch, it consults all tables and trusts whichever table had the longest matching history. That covers both short-range patterns (loop behaviour) and long-range correlations (function-level patterns). TAGE pulls ~97-99% accuracy on most workloads.

Branch Target Buffer

Predicting whether a branch fires is only half the work. The CPU also has to figure out where the branch goes — the target address. That's the job of the Branch Target Buffer (BTB), a cache of recent branch addresses and their targets.

For direct branches, where the target is baked into the instruction, the BTB hands over the target before the instruction is even decoded. For indirect branches, where the target lives in a register, the BTB stores the most recent target — often right for predictable cases like virtual function calls.

An Indirect Branch Predictor handles indirect branches that bounce around multiple targets. It looks structurally similar to the direction predictor (indexed by history), mapping history patterns to likely target addresses. C++ virtual calls, switch tables, and return addresses all lean on this.

Speculative Execution

Branch prediction is what unlocks speculative execution: the CPU fetches, decodes, and executes instructions along the predicted path before the branch is even resolved. Speculative results sit in the reorder buffer, never touching architectural state.

If the prediction holds, results commit as normal and nothing's wasted. If the prediction is wrong — a misprediction — the CPU flushes everything speculative and restarts from the correct branch target. The price tag is the number of pipeline stages between fetch and branch resolution.

Misprediction Penalties

The misprediction penalty varies by CPU. These are approximate figures from independent microbenchmarks, since vendors rarely publish exact numbers:

  • Intel Skylake: ~15-20 cycles
  • AMD Zen 3: ~11-18 cycles
  • Apple M1: ~13-14 cycles
  • ARM Cortex-A78: ~11-13 cycles

At 4 GHz, 15 cycles is 3.75 nanoseconds. Sounds tiny — until you realise a tight loop mispredicting every 10 instructions hands half its throughput over to pipeline flushes. That's why branch-heavy code (deeply nested conditions, unpredictable data-dependent branches) drags, and why branchless programming (using cmov and friends instead of branches) can transform performance on workloads where branches are genuinely unpredictable.

You can watch this happen. The program below adds up every element of a 32,768-element array that's at least 128, first with the values in random order, then again after sorting them. The work is identical. The only difference is whether the if follows a pattern: unsorted, it's a coin flip every time; sorted, it's a long run of not-taken followed by a long run of taken, which even a 2-bit counter gets almost entirely right.

Try itRun it and compare the two times, then change >= 128 to >= 0 so the branch always goes the same way and see what happens to the gap.
C (GCC 9.2.0)

The runner compiles at -O0, which keeps the branch in place. At -O2, gcc may replace the if with a branch-free cmov or vectorise the whole loop, and the gap between sorted and unsorted can disappear, which is the whole point of branchless code.

Security Implications

Speculative execution gave us the Spectre family of vulnerabilities (disclosed in 2018). Mispredicted speculative instructions are architecturally rolled back, yes — but they leave fingerprints in microarchitectural state, mostly the cache. An attacker trains the branch predictor to mispredict, sends speculative execution wandering into memory it shouldn't touch, and the touched data drags a specific cache line in. Speculation rolls back; the cache line stays. The attacker times cache hits to pry the secret loose. Mitigations include retpolines (for indirect branches), IBRS (Indirect Branch Restricted Speculation), and STIBP (Single Thread Indirect Branch Predictors). Every one of them trades performance for security, and none of them are free.