Take an array of random bytes, sum only the values ≥ 128, and time it. Now sort the array first and run the identical loop. On most machines the sorted version is 4–6× faster. Same instructions, same data, same total work. This is the most famous performance puzzle on the internet, and its answer — the branch predictor — explains a whole family of “why is this slow” mysteries.

Pipelines: The CPU Is an Assembly Line

A CPU doesn’t finish one instruction before starting the next. It runs an assembly line: while one instruction executes, the next is being decoded, and the one after that is being fetched. Modern pipelines are 15–20 stages deep and 4–8 instructions wide — at any instant, over a hundred instructions are in flight in various stages of completion.

An assembly line only works if you know what’s coming down the belt. A conditional branch is a fork in the road: the next instruction is either the loop body or the instruction after the loop, and the CPU won’t know which until the comparison executes — 15+ stages from the front of the pipe. Waiting would mean draining the line at every branch, and real code branches every 5–10 instructions. So the CPU doesn’t wait. It guesses.

The Predictor

The branch predictor is a table of counters and histories that tracks, per branch, which way it usually goes and in what pattern. Modern predictors (TAGE-family) are shockingly good: they learn loop trip counts, alternating patterns, and correlations between nearby branches, hitting 95–99% accuracy on typical code.

When the guess is right, the branch is free — the pipeline never hiccups. When it’s wrong, everything fetched after the branch is garbage. The pipeline is flushed and restarted from the correct target: 15–20 cycles of work, thrown away.

Now the sorted-array puzzle solves itself:

text
   random data:   T F F T T F T F ...   predictor is wrong ~50% of the time
                                        → ~10 wasted cycles per element

   sorted data:   F F F F ... T T T T   wrong exactly once, at the boundary
                                        → free everywhere else

Making Branches Disappear

You can’t sort your data every time, but you can often remove the branch. The compare-and-add can become arithmetic:

c
/* branchy */
if (data[i] >= 128) sum += data[i];

/* branchless: the comparison result (0 or 1) becomes a mask */
int keep = -(data[i] >= 128);      /* 0x00000000 or 0xFFFFFFFF */
sum += data[i] & keep;

The branchless version does slightly more work per element and wins big on random data because it never mispredicts. Compilers do this themselves when they can — x = c ? a : b often compiles to a cmov (conditional move) instead of a jump — but they’re conservative, because branchless is slower on predictable data (you always pay for both sides). GCC and Clang decide based on heuristics; when they guess wrong, __builtin_expect or profile-guided optimization feeds them better information.

The same idea at larger scale: replace if-chains with lookup tables, partition data so each loop handles one case (all-true then all-false), and hoist invariant conditions out of loops — the predictor learns fast, but no prediction beats no branch.

Measuring, Not Guessing

bash
perf stat -e branches,branch-misses ./a.out

Typical code sits at 1–5% miss rate. A hot loop at 15%+ miss rate is leaving a multiple of its runtime on the table, and the fix is usually one of: sort/partition the data, go branchless, or restructure the condition. perf record -e branch-misses localizes it to the exact branch.

One caveat worth knowing: branch mispredictions are also a security story — Spectre-class attacks work by deliberately training the predictor and observing what speculatively executed code leaves behind in the cache. The predictor is shared microarchitectural state, and that’s exactly why it leaks.

Takeaways

  • Pipelines keep 100+ instructions in flight; branches threaten to stall the line, so the CPU predicts and speculates past them.
  • A correct prediction is free; a miss costs 15–20 cycles of flushed work.
  • Predictors learn patterns, not randomness: sorted/partitioned data is fast, random decisions are slow.
  • Branchless code (masks, cmov, tables) trades a little extra work for immunity — a win only when the branch was unpredictable.
  • perf stat -e branch-misses turns this from folklore into a number.