Branch Prediction and Speculation

The CPU's Crystal Ball

Modern CPUs don't execute instructions one at a time. They use a technique called pipelining—breaking each instruction into stages (fetch, decode, execute, write-back) and overlapping them, like an assembly line in a factory. A modern Intel or AMD core can have 15–25 pipeline stages and may be executing parts of 100+ instructions simultaneously.

But what happens when the CPU hits a conditional branch—an if statement, a loop condition, a switch case?

if (user.is_premium) {
    // Path A: Apply premium discount
} else {
    // Path B: Apply standard pricing
}

The CPU doesn't know the value of user.is_premium yet—that data might still be coming from cache or RAM. But it can't just wait, or the entire pipeline stalls. With a 20-stage pipeline, a stall means 20 wasted cycles.

So, it guesses.

It uses a Branch Predictor—a sophisticated piece of hardware that maintains a history table of recent branch outcomes. If this particular if statement has been true 99 out of the last 100 times, the predictor guesses true again and starts executing Path A immediately, speculatively. The CPU fetches, decodes, and begins executing Path A instructions before it even knows the branch condition.

• If it guessed right (predicted correctly): The speculative work is valid. The pipeline never stalled. Massive speedup.
• If it guessed wrong (misprediction): The CPU must flush all the speculative work from the pipeline, discard the results, and restart down the correct path. This costs ~15–25 cycles depending on pipeline depth.

Modern branch predictors are remarkably accurate—often 95–99% correct for typical code. But when branches are truly random (50/50 probability), the predictor is wrong half the time, and the misprediction penalty adds up fast.

The Sorted Array Example

A famous example: summing all values greater than 128 in an array of random integers (0–255). If the array is sorted, the branch predictor sees a long run of "not taken" followed by a long run of "taken"—easy to predict. If the array is unsorted, every element is a coin flip. The sorted version can be 5–6x faster, even though the same number of additions are performed, purely because of branch prediction accuracy.

The hardware-sympathetic fix for unpredictable branches is to eliminate them entirely using branchless programming—replacing if statements with arithmetic or bitwise operations that compute both paths and select the result without branching. For example:

// Branchy (prediction-dependent):
if (value > 128) sum += value;

// Branchless (prediction-independent):
sum += (value > 128) * value;
// The compiler often emits a conditional move (cmov) instruction,
// which reads both paths but selects the result without branching.

The branchless version has predictable, constant performance regardless of data distribution. It trades a potential branch misprediction penalty for a guaranteed (but small) cost of computing both paths.

Key Point: Branch prediction matters most in tight inner loops that execute millions or billions of times. For typical application code with complex business logic, branch mispredictions are rarely the bottleneck. But for data processing pipelines, parsers, codecs, and database query engines, branchless techniques can yield significant speedups. Use perf stat -e branch-misses,branches to measure your misprediction rate before optimizing—premature branchless optimization produces unreadable code for negligible gain.