Branch prediction

A CPU reaches an if long before it knows which way the branch goes. Waiting would stall the pipeline, so the CPU guesses and keeps going. When the guess is right, the work is free. When it is wrong, the work is thrown away. How often the guesses are right decides how fast a loop with data-dependent ifs runs.

The big idea

Roughly one instruction in five or six is a branch. The core fetches about 15 instructions past a branch before it knows the outcome. So a branch predictor keeps a history of each branch and predicts its outcome. The core then runs speculatively down the predicted path.

• Right guess: nothing is lost.
• Wrong guess: the speculative work is discarded and the core restarts on the right path. This costs roughly 15 to 20 cycles.

Modern predictors are right more than 95% of the time on typical code. Most branches are regular. Loop conditions stay true until the last iteration, and error checks are almost always false. The trouble starts with branches that depend on random data.

Walking through it: the sorted-array benchmark

Fill an array with 32,768 random numbers from 0 to 255. Then repeatedly add up the ones that are 128 or more. The timed loop looks like this (the fill step is left out):

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

With random data, the if is a coin flip, so the predictor is wrong about half the time. Sort the array first and the branch is false for the first half and true for the second half. The predictor is almost always right.

Here are the measured results:

2012 question (older hardware):  unsorted 11.54 s, sorted 1.93 s   → about 6×
2026 Apple M-series, clang -O0:  unsorted 59 ms,    sorted 22 ms    → 59 / 22 ≈ 2.7×
2026 Apple M-series, -O1 or -O2: gap about 1.3×

The gap shrinks at -O1 because the compiler replaces the branch with a conditional select (csel on ARM, cmov on x86). It computes both results and picks one without branching. With no branch, there is nothing to mispredict.

Speculation can leak data

Speculative work is supposed to be invisible, since wrong-path results are discarded. In January 2018, the Spectre and Meltdown disclosures showed that discarded work still leaves traces in the CPU caches. An attacker can time memory accesses to read data they should not see, including kernel memory and other processes' secrets.

The fixes, especially kernel page-table isolation (KPTI) for Meltdown, made every system call and context switch more expensive. Syscall-heavy workloads saw measurable slowdowns. The performance features in this section also shape security and cloud pricing.

Common mistakes

• Benchmarking on sorted or constant data. Real input is often random, so the predictor behaves differently.
• Hand-writing branchless code without measuring. The compiler may already have done it, and your version may be slower.
• Ignoring branches in parsers and query engines. Code that switches on data values in tight loops pays this cost on every row.

Check yourself

• Why does sorting the array speed up the loop with the same arithmetic? The branch outcome becomes predictable, so the predictor is right almost every time.
• A mispredict costs about 15 to 20 cycles. Why is that a big deal in a loop over 30,000 items? Each wrong guess wastes that many cycles, and a random branch can be wrong about half the time.

Key takeaways

• Branch prediction lets the core run ahead by guessing. Wrong guesses cost about 15 to 20 cycles.
• Predictors are right over 95% of the time on regular code, but random, data-dependent branches are often wrong about half the time.
• Compilers can replace simple branches with conditional selects, which removes the mispredictions.
• Speculative execution has a security cost. Spectre and Meltdown led to mitigations that slow system calls.

Further learning

Next, see what a program needs the kernel for, and what each request costs, in system calls.

The Stack Overflow question that made this benchmark famous has the original discussion and measurements.