Branch Prediction

Every line of code you write is full of if-statements. Every time the CPU hits one, it faces a fork in the road: take the branch, or skip it? The answer depends on data that hasn't been computed yet.

A naive processor would stall — freeze the pipeline, wait for the result, then continue. On a modern chip running four instructions per clock, that stall costs 10–20 cycles of wasted work. In a tight loop that runs a billion times, a few stalled cycles per iteration adds up to seconds of lost time.

The solution is branch prediction: the CPU guesses the outcome before computing it, speculatively executes the most-likely path, and discards the work if it guessed wrong. A good predictor is right more than 99% of the time, turning a potential 15-cycle penalty into a 0-cycle non-event.

Understanding branch prediction means understanding why sorting a list makes it faster to search, why Spectre and Meltdown were possible, and why a single mispredict can cost more than hundreds of correct predictions combined.

The demo below simulates a 2-bit saturating counter predictor — the simplest design that actually appears in real CPUs. A loop branch is taken most iterations and not taken at the end. Click Run one iteration and watch the predictor learn.

<!-- {{c_html_intro}} -->
<div class="container">
  <div class="panel left-panel">
    <h3>{{label_predictor}}</h3>
    <div class="state-machine" id="state-machine">
      <div class="state" id="s0" title="{{state_snt_title}}">{{state_snt}}</div>
      <div class="state" id="s1" title="{{state_wnt_title}}">{{state_wnt}}</div>
      <div class="state" id="s2" title="{{state_wt_title}}">{{state_wt}}</div>
      <div class="state" id="s3" title="{{state_st_title}}">{{state_st}}</div>
    </div>
    <p class="state-label" id="state-label">{{label_current_state}}: <strong id="state-name">{{state_wnt}}</strong></p>
    <p class="pred-label">{{label_prediction}}: <strong id="pred-text">{{pred_not_taken}}</strong></p>
  </div>
  <div class="panel right-panel">
    <h3>{{label_loop_sim}}</h3>
    <div class="loop-vis" id="loop-vis">
      <div class="iter-row header-row">
        <span class="col-iter">{{col_iter}}</span>
        <span class="col-outcome">{{col_outcome}}</span>
        <span class="col-pred">{{col_pred}}</span>
        <span class="col-hit">{{col_hit}}</span>
      </div>
    </div>
    <div class="counters">
      <span>{{label_hits}}: <strong id="hits">0</strong></span>
      <span>{{label_misses}}: <strong id="misses">0</strong></span>
      <span>{{label_accuracy}}: <strong id="accuracy">—</strong></span>
    </div>
    <div class="status" id="status"></div>
  </div>
</div>
<div class="controls">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run_all}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<p class="footnote">{{footnote_text}}</p>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
h3 { margin: 0 0 .6rem; font-size: 1rem; }
.container { display: flex; gap: .8rem; flex-wrap: wrap; }
.panel { flex: 1 1 200px; background: #f0f4f8; border-radius: 10px; padding: .8rem; }

/* {{c_state_machine_css}} */
.state-machine { display: grid; grid-template-columns: 1fr 1fr; gap: .5rem; margin-bottom: .5rem; }
.state { border: 2px solid #9aabb8; border-radius: 50%; width: 68px; height: 68px;
         display: flex; align-items: center; justify-content: center; text-align: center;
         font-size: .65rem; font-weight: 600; background: #fff; cursor: default;
         transition: background .25s, border-color .25s; padding: 4px; }
.state.active { background: #1d3557; border-color: #1d3557; color: #fff; }
.state.mispredict { background: #e63946; border-color: #c92f3c; color: #fff; }
.state-label, .pred-label { margin: .25rem 0; font-size: .85rem; }

/* {{c_loop_vis_css}} */
.loop-vis { max-height: 160px; overflow-y: auto; margin-bottom: .4rem; border-radius: 6px;
            background: #fff; border: 1px solid #cdd9e3; }
.iter-row { display: grid; grid-template-columns: 40px 1fr 1fr 40px; gap: 4px;
            padding: 3px 6px; font-size: .78rem; align-items: center; }
.header-row { background: #dde5ec; font-weight: 700; position: sticky; top: 0; }
.iter-row.hit { background: #d4edda; }
.iter-row.miss { background: #f8d7da; }
.col-hit { text-align: center; font-weight: 700; }

.counters { display: flex; gap: .8rem; font-size: .85rem; margin-bottom: .4rem; flex-wrap: wrap; }
.status { min-height: 1.3em; font-weight: 600; font-size: .9rem; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .6rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.footnote { font-size: .78rem; color: #555; margin: .5rem 0 0; line-height: 1.45; }

// Code not found

Notice how the predictor starts uncertain and converges quickly to "strongly taken." When the loop ends and the branch is not taken, one mispredict fires — then the counter adjusts. The pattern repeats on the next run. A real gshare predictor keeps a global history register of recent branch outcomes and XOR-indexes into a table of such counters, letting correlated branches share information across the program.

Branch predictors have evolved from single bits to multi-kilobyte state machines. Here is the ladder:

• 1-bit predictor: remember the last outcome — taken or not. Wrong at every loop boundary (the last iteration and the first of the next run). Accuracy: ~85%.
• 2-bit saturating counter: a four-state machine (strongly not-taken, weakly not-taken, weakly taken, strongly taken). A single mispredict doesn't flip the prediction immediately — it takes two consecutive wrong outcomes. Accuracy: ~90%.
• gshare (1992, McFarling): XOR the program counter with a global history register (GHR) of the last $n$ branch outcomes, then index into a table of 2-bit counters. Correlated branches — "the outer loop always predicts the inner loop" — share information through the history bits. Accuracy: ~95%.
• TAGE (2006, Seznec): a cascade of history tables at geometrically increasing history lengths ($2, 4, 8, \dots, 128$ bits). The longest matching history wins; shorter tables act as fallback. TAGE is the predictor inside every modern Intel, AMD and Apple Silicon chip. Accuracy: >99%.

Why does 1% failure matter? At 3 GHz with a 15-cycle penalty, one mispredict per hundred branches costs $3 \times 10^{9} \times 0.01 \times 15 = 4.5 \times 10^{8}$ wasted cycles per second — almost half a billion cycles gone.

The predictor also drives speculative execution: the CPU doesn't just predict and wait — it starts executing the predicted path immediately. On a misprediction it must roll back that speculative work, which is why branch mispredicts are so costly and why the halting problem makes perfect static prediction impossible.

Branch prediction is not an academic curiosity — it shapes every program you run:

• The sorted-array mystery: a famous Stack Overflow question asked why processing a sorted array is ~6× faster than an unsorted one. The answer is branch prediction: in sorted order, the branch if (data[i] >= 128) has a predictable pattern (all false, then all true), so zero mispredicts. Shuffled data gives ~50% mispredicts — maximum penalty.
• Spectre and Meltdown (2018): these hardware vulnerabilities exploit speculative execution driven by branch prediction. An attacker trains the predictor to speculatively execute code that reads secret memory. Even after the roll-back, traces remain in the CPU cache, leaking data through a timing side-channel. Mitigations slow down millions of servers by 5–30%.
• Compiler hints: GCC and Clang expose __builtin_expect(expr, likely_val) (and C++20's [[likely]]) so programmers annotate which branch is common. The compiler places the likely path first in memory (better cache behavior) and may restructure the branch.
• Profile-guided optimization (PGO): compilers run the program with sample inputs, record branch statistics, then recompile with those statistics driving layout decisions — effectively training the predictor offline.
• Data structures: designs like branch-free binary search (using conditional moves instead of branches) or B-trees that minimize comparisons exist partly to avoid branch mispredicts.

Branch prediction is one of the most elegant engineering compromises in computer architecture: instead of waiting for certainty, the CPU bets on the most-likely future and nearly always wins. A 2-bit counter evolving into TAGE over three decades brought accuracy from 85% to above 99%, turning a potential 15-cycle stall into an almost invisible non-event.

The same mechanism that makes your loops fly is also the surface that Spectre exploits — a reminder that every performance trick has a security shadow. Understanding the predictor means understanding both why your code is fast and why perfect isolation between programs is harder than it looks.

Next time you sort a list before processing it or reach for [[likely]], you are not just optimizing code — you are tuning a prediction engine that runs billions of times per second, and that connects all the way back to the fundamental limits explored in P vs NP and the halting problem.