Introduction

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.

Try the Predictor

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.

<!-- Branch prediction demo: 2-bit saturating counter simulating a loop branch -->
<div class="container">
  <div class="panel left-panel">
    <h3>2-Bit Saturating Counter</h3>
    <div class="state-machine" id="state-machine">
      <div class="state" id="s0" title="Strongly Not Taken — predicts not-taken">Strongly Not Taken</div>
      <div class="state" id="s1" title="Weakly Not Taken — predicts not-taken">Weakly Not Taken</div>
      <div class="state" id="s2" title="Weakly Taken — predicts taken">Weakly Taken</div>
      <div class="state" id="s3" title="Strongly Taken — predicts taken">Strongly Taken</div>
    </div>
    <p class="state-label" id="state-label">Current state: <strong id="state-name">Weakly Not Taken</strong></p>
    <p class="pred-label">Next prediction: <strong id="pred-text">Not Taken</strong></p>
  </div>
  <div class="panel right-panel">
    <h3>Loop Branch Simulation</h3>
    <div class="loop-vis" id="loop-vis">
      <div class="iter-row header-row">
        <span class="col-iter">#</span>
        <span class="col-outcome">Outcome</span>
        <span class="col-pred">Predicted</span>
        <span class="col-hit">Hit?</span>
      </div>
    </div>
    <div class="counters">
      <span>Hits: <strong id="hits">0</strong></span>
      <span>Misses: <strong id="misses">0</strong></span>
      <span>Accuracy: <strong id="accuracy">—</strong></span>
    </div>
    <div class="status" id="status"></div>
  </div>
</div>
<div class="controls">
  <button id="btn-step" type="button">Run one iteration</button>
  <button id="btn-run" type="button">Run all</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<p class="footnote">A real gshare predictor XORs the program counter with a global history register, then looks up a 2-bit counter in a large table — sharing history across correlated branches.</p>

/* Layout: two-panel card + state machine circles + iteration log table */
* { 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; }

/* State machine circles — 4 states in a 2x2 grid */
.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; }

/* Scrollable iteration log */
.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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// 2-bit saturating counter branch predictor
// States: 0=strongly-not-taken, 1=weakly-not-taken, 2=weakly-taken, 3=strongly-taken
// On taken: increment (max 3). On not-taken: decrement (min 0).
// Predict taken when state >= 2, not-taken when state < 2.

const STATES = ['snt', 'wnt', 'wt', 'st'];
const STATE_LABELS = {
  snt: 'Strongly Not Taken',
  wnt: 'Weakly Not Taken',
  wt: 'Weakly Taken',
  st: 'Strongly Taken'
};

// Loop pattern: N-1 'taken' + 1 'not-taken' (the loop exit)
// First N-1 iterations: branch taken (loop continues). Last iteration: branch not taken (loop exits).
const LOOP_ITERS = 8;
const pattern = [];
for (let i = 0; i < LOOP_ITERS; i++) {
  pattern.push(i < LOOP_ITERS - 1 ? 'taken' : 'not-taken');
}

let stateIdx = 1; // Start at weakly-not-taken so the first iteration is a mispredict
let iter = 0;
let hits = 0;
let misses = 0;
let running = false;

function prediction(si) {
  // Predict taken if state >= 2 (weakly-taken or strongly-taken)
  return si >= 2 ? 'taken' : 'not-taken';
}

function predLabel(p) {
  return p === 'taken' ? 'Taken' : 'Not Taken';
}

function outcomeLabel(o) {
  return o === 'taken' ? 'Taken' : 'Not Taken';
}

function nextState(si, outcome) {
  // Saturating counter: clamp between 0 and 3
  if (outcome === 'taken') return Math.min(si + 1, 3);
  return Math.max(si - 1, 0);
}

function updateStateMachine(newSi, wasHit) {
  STATES.forEach((s, i) => {
    const el = document.getElementById('s' + i);
    el.className = 'state' + (i === newSi ? (wasHit === false ? ' mispredict' : ' active') : '');
  });
  document.getElementById('state-name').textContent = STATE_LABELS[STATES[newSi]];
  document.getElementById('pred-text').textContent = predLabel(prediction(newSi));
}

function addRow(i, outcome, pred, hit) {
  const vis = document.getElementById('loop-vis');
  const row = document.createElement('div');
  row.className = 'iter-row ' + (hit ? 'hit' : 'miss');
  row.innerHTML =
    '<span class="col-iter">' + (i + 1) + '</span>' +
    '<span class="col-outcome">' + outcomeLabel(outcome) + '</span>' +
    '<span class="col-pred">' + predLabel(pred) + '</span>' +
    '<span class="col-hit">' + (hit ? '✓' : '✗') + '</span>';
  vis.appendChild(row);
  vis.scrollTop = vis.scrollHeight;
}

function updateCounters() {
  document.getElementById('hits').textContent = hits;
  document.getElementById('misses').textContent = misses;
  const total = hits + misses;
  document.getElementById('accuracy').textContent =
    total === 0 ? '—' : (Math.round(hits / total * 1000) / 10) + '%';
}

function setStatus(msg, cls) {
  const el = document.getElementById('status');
  el.textContent = msg;
  el.className = 'status ' + (cls || '');
}

function step() {
  if (iter >= pattern.length) return;
  const outcome = pattern[iter];
  const pred = prediction(stateIdx);
  const hit = pred === outcome;
  if (hit) hits++; else misses++;
  const prevSi = stateIdx;
  stateIdx = nextState(stateIdx, outcome);
  addRow(iter, outcome, pred, hit);
  updateStateMachine(stateIdx, hit);
  updateCounters();
  if (!hit) {
    setStatus(i18nFmt('Iteration %iter%: mispredict! Counter adjusts.', { iter: iter + 1 }), 'bad');
  } else {
    setStatus(i18nFmt('Iteration %iter%: correct prediction.', { iter: iter + 1 }), 'ok');
  }
  iter++;
  if (iter >= pattern.length) {
    document.getElementById('btn-step').disabled = true;
    document.getElementById('btn-run').disabled = true;
    const acc = Math.round(hits / (hits + misses) * 1000) / 10;
    setStatus(i18nFmt('Done — %hits% hits, %misses% misses (%acc% accuracy).', { hits: hits, misses: misses, acc: acc }), hits > misses ? 'ok' : '');
  }
}

function runAll() {
  document.getElementById('btn-step').disabled = true;
  document.getElementById('btn-run').disabled = true;
  // Step through remaining iterations one at a time with 300ms delay
  const interval = setInterval(() => {
    if (iter >= pattern.length) { clearInterval(interval); return; }
    step();
  }, 300);
}

function reset() {
  stateIdx = 1;
  iter = 0;
  hits = 0;
  misses = 0;
  // Remove previous iteration rows, keep header
  const vis = document.getElementById('loop-vis');
  const rows = vis.querySelectorAll('.iter-row:not(.header-row)');
  rows.forEach(r => r.remove());
  vis.scrollTop = 0;
  updateStateMachine(stateIdx, true);
  updateCounters();
  setStatus('');
  document.getElementById('btn-step').disabled = false;
  document.getElementById('btn-run').disabled = false;
}

document.getElementById('btn-step').addEventListener('click', step);
document.getElementById('btn-run').addEventListener('click', runAll);
document.getElementById('btn-reset').addEventListener('click', reset);

// Initialize display on load
updateStateMachine(stateIdx, true);
updateCounters();
Result
Console

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.

How Predictors Work

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 nn 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,…,1282, 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×109×0.01×15=4.5×1083 \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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/branch-prediction/Content licensed under CC BY-NC 4.0.