# Branch Prediction: Why Sorted Data Runs Faster

> The same loop over the same data runs 5x faster when the array is sorted. The instructions are identical. The difference is a gambler inside your CPU that's either winning or losing.

URL: https://harshith.in/blog/branch-prediction-and-pipelines/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: performance, hardware, systems

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.