Branch Prediction and CPU Pipelines: Why Sorted Data Is Faster

One if in the middle of a hot loop can cost 20 cycles per iteration on a modern CPU, while a byte-identical if in a different data pattern costs one. Nothing about the source changed — the data changed, and with it the CPU's ability to guess which way the branch goes. Branch prediction is not a CPU feature you can ignore; it's the mechanism that decides whether your hottest branch costs a cycle or twenty, and it is the same mechanism that made Spectre possible. Here's what the machine actually does.

The pipeline makes branches expensive

Modern CPUs don't execute instructions one at a time; they execute five or more at once in a pipeline: fetch, decode, execute, memory, writeback. The pipeline only works if the fetcher knows which instruction comes next. A branch makes that a guess: fetch the taken path, the fall-through path, or wait? Waiting costs one cycle per pipeline stage (empty pipeline = stall), and for a 15-stage pipeline that's ~15 cycles of nothing. That waiting is the worst case; the CPU would rather gamble than wait.

The BTB: how the CPU guesses

The branch target buffer (BTB) is the guesser. It's a small cache, indexed by the branch instruction's address, storing what the branch did recently: its direction (taken or not) and, if taken, its target address. The CPU also keeps a 1–2 bit history per branch, so a branch that alternates taken, not, taken, not can be predicted correctly. The guess costs a few cycles of work; the misprediction costs a full pipeline drain plus refetch from the wrong path. That asymmetry — cheap guess, expensive miss — is the entire economics of branch prediction.

Sorted vs unsorted: the 10x if

This is the classic experiment, and it's real:

int sum = 0;
for (int i = 0; i < N; i++)
    if (data[i] >= 128) sum += data[i];

With unsorted data, the branch is a coin flip: every iteration is a gamble, and the CPU mispredicts roughly half the time — a ~15–20 cycle penalty on roughly half of all iterations, in the worst case an order of magnitude slower than the sorted run. With sorted data, the branch settles into not taken, not taken, …, taken, taken, … — a perfectly predictable pattern the BTB follows flawlessly, so the branch effectively costs nothing.

// The branchless version — one comparison, no data-dependent jump
sum += (data[i] >= 128) * data[i];   // compiler often turns this into cmov

The fix isn't sorting your data. It's knowing that data-dependent control flow is data-dependent performance: the same binary, the same loop, and a different input order can flip your runtime by 10x. Profile-guided optimization (PGO) exists largely to tell the compiler what the BTB already knows about your data.

Speculative execution: committing to the guess

Prediction doesn't stop at fetching — the CPU goes further and executes the guessed path before the branch is resolved, keeping the results in rename registers and a reorder buffer so they can be discarded or committed at resolution. A correct guess hides the branch's latency completely. A wrong guess discards the speculative results and replays the correct path — the result is still correct (the CPU never commits a wrong result), but the cost is the drain. Speculation is what makes modern CPUs fast and what makes them leak: see below.

__builtin_expect: telling the compiler what the CPU guesses

__builtin_expect(expr, 1) (and the likely()/unlikely() macros wrapping it) doesn't change the CPU's prediction at all — it changes what the compiler does with the branch:

if (__builtin_expect(rc != 0, 0)) {   /* cold error path, moved out of line */
    handle_error(rc);
}

The compiler lays out the hot path in sequence and moves the cold path to a separate block at the end of the function. That improves instruction-cache locality and the CPU's static-prediction fallback for never-seen branches. It's worth doing in cold/rare paths (error handling, config checks), and noise in paths where the BTB already has history — the hardware's data beats your annotation.

Spectre: when speculation leaks

Speculative execution has a side channel: a speculative load still touches the cache, even when the speculation is later discarded. Spectre variant 1 exploits exactly that — train the predictor with a legal branch, then use the speculation window to read data outside the bounds check, and time the cache to exfiltrate it. The mitigations are mechanical: retpolines replace indirect branches with a return-sequence that the CPU won't speculatively execute, IBRS/IBPB and LFENCE fences constrain speculation, and compilers insert serialization or rewrite array accesses. These are not theoretical — they're the reason many binaries run a few percent slower on patched hardware, and the reason your codebase's -mretpoline flags exist.

Predictable branches are nearly free; unpredictable ones cost 20 cycles; and speculation turned the cost of guessing into a security model. Sorted data, branchless code, and likely() are all just ways of being kind to a guesser that controls your performance.