How a CPU Guesses What You'll Do Next

A colleague once showed me a benchmark where sorting an array before summing a filtered subset of it made the whole program run several times faster, even though sorting is extra work that should, on paper, only slow things down. Nothing about the arithmetic changed. The only thing that changed was how predictable the branch inside the loop became to the CPU, and that one variable was worth a bigger speed difference than most algorithmic improvements I’ve made in actual production code. Once you understand why, you stop treating CPU performance as a black box and start recognising when your own code is accidentally fighting the hardware.

Modern CPUs don’t execute your program’s instructions one at a time in the order you wrote them, waiting patiently at each if statement to find out which way it goes before deciding what to fetch next. That would leave the enormously expensive execution units inside the chip idle for the ten or twenty clock cycles it takes to resolve a comparison, every single time your code branches — and code branches constantly. Instead, the CPU guesses which way the branch will go, based on the branch’s history, and starts executing instructions down that guessed path immediately, before it actually knows if the guess is correct. Get the guess right, which happens the vast majority of the time in real code, and you’ve hidden the entire delay. Get it wrong, and the CPU has to discard everything it speculatively computed and start over down the correct path — a real cost, but one that’s rare enough, on well-predicted code, that guessing wins on average by a wide margin.

Why the pipeline needs a guess at all

A modern CPU core processes instructions in a pipeline with many overlapping stages — fetch, decode, execute, and several more depending on the architecture — so that while one instruction is being executed, the next several are already being fetched and decoded behind it, keeping every stage of the pipeline busy simultaneously rather than idle. That overlap is where most of a modern CPU’s raw throughput actually comes from. A conditional branch breaks the assumption the pipeline depends on, because “fetch the next instruction” requires knowing which of two possible next instructions is the right one, and that answer depends on a comparison that hasn’t finished executing yet, several pipeline stages further along.

Stall the pipeline until every branch resolves and you throw away most of the benefit of pipelining in the first place, on a modern chip with a pipeline ten or more stages deep. So the CPU doesn’t stall. It predicts, using dedicated hardware — a branch predictor, physically separate silicon from the arithmetic units — that tracks the recent history of how a given branch (identified by its instruction address) has resolved, and bets that the pattern will continue. Simple loops that run to completion almost always take the “loop again” branch and only rarely take the “exit” branch, so a predictor that just remembers “this branch was taken last time, predict taken again” gets the overwhelming majority of loop iterations right, which is precisely the pattern most real code actually exhibits.

The predictor is more than a coin flip

“Remember what happened last time” is the simplest possible predictor, but real branch predictors are considerably more sophisticated, because plenty of real branches follow patterns more complex than “always taken” or “always not taken.” A common building block is the two-bit saturating counter: rather than flipping its prediction the instant a branch behaves differently once, it counts through four states — strongly taken, weakly taken, weakly not-taken, strongly not-taken — and only flips its actual prediction after two consecutive misses in the same direction. That small amount of hysteresis matters enormously in practice, because it stops a single anomalous iteration inside an otherwise-predictable loop (an edge case hit once in ten thousand iterations) from derailing the prediction for every iteration around it.

Beyond that, modern high-end CPUs use two-level adaptive predictors that track a pattern across several recent branches together rather than one branch’s history in isolation, which lets them correctly predict branches whose outcome depends on the outcome of a different, earlier branch — genuinely common in real code, where an if inside a loop often correlates with a condition checked a few lines earlier. Some chips add a separate specialised predictor purely for loop-closing branches, since “how many times will this loop run” is a distinct, very common and very learnable pattern worth dedicating silicon to on its own. None of this changes the fundamental trade being made — guess now, verify later, discard on failure — it just makes the guesses considerably better than a naive coin flip would manage, which is exactly why the sorted-versus-unsorted benchmark above shows such a dramatic gap: modern predictors are good enough that “genuinely unpredictable” data is the rare, painful case rather than the default one.

What “speculative execution” really does

Once the predictor makes its guess, the CPU doesn’t just sit on the guess — it commits to it, fetching, decoding and executing instructions down the predicted path immediately, writing their results into temporary buffers rather than permanent architectural state. This is speculative execution: real work, genuinely performed by the execution units, on a path the CPU isn’t yet certain is correct. When the actual branch condition finally resolves, one of two things happens. If the guess was right, the speculatively computed results get “retired” — committed to real, visible state — and the CPU has effectively gotten several instructions’ worth of work done for free, hidden entirely behind the latency of resolving the branch. If the guess was wrong, everything computed down the wrong path gets flushed, discarded as if it never happened, and the pipeline restarts down the actually-correct path, at the cost of however many cycles the misprediction wasted refilling the pipeline from scratch.

1
2
3
4
5
6
7

// classic branch-prediction demo: same arithmetic, radically different speed
// depending on whether `data` is sorted first

for (int i = 0; i < n; i++) {
    if (data[i] >= threshold)   // predictable if data is sorted; random otherwise
        sum += data[i];
}

Run that loop over unsorted data with a roughly 50/50 split around the threshold and the branch predictor is guessing close to a coin flip on every iteration, because there’s no pattern in “greater than or less than the threshold” for the predictor’s history table to latch onto — mispredicting close to half the time, and paying the pipeline-flush cost on every miss. Sort the same data first and the branch becomes almost perfectly predictable: a long run of “not taken,” followed by a long run of “taken,” which is exactly the pattern a branch predictor is built to recognise and exploit. The arithmetic performed is identical either way. The difference — several times the wall-clock speed on real hardware, in benchmarks I’ve reproduced myself — comes entirely from how much of that speculative work the CPU gets to keep versus how much it has to throw away and redo.

Why this became a security problem, not just a performance one

For a couple of decades this was purely an optimisation, invisible to software except as a performance quirk worth knowing about. Spectre, disclosed in 2018, showed it wasn’t just a performance quirk: speculative execution can be coaxed into reading memory a program shouldn’t have access to, and even though the CPU correctly discards the speculative result once it realises the branch was mispredicted, the act of speculatively touching that memory leaves a measurable side effect behind — specifically, it pulls the touched memory address into the CPU’s cache, which changes how quickly that address can be read afterwards.

An attacker who can time memory reads precisely enough can distinguish “was recently pulled into cache” from “wasn’t,” and by training a branch predictor to speculatively execute a snippet of victim code that reads secret data and then, based on that secret, touches one of several different memory addresses, the attacker can recover the secret’s value one bit at a time purely by measuring cache-timing differences afterwards — without ever directly reading the protected memory itself, because the CPU obediently discarded the actual read as required. The trick is entirely in the side effect the discarded speculation left behind, not in the CPU ever handing over data it wasn’t supposed to hand over.

This is the reason Spectre mitigations are so architecturally invasive and so costly to performance — patches for it work by deliberately limiting speculation across trust boundaries (disabling certain predictor behaviours when switching between kernel and user code, or between different processes), which is precisely giving back some of the performance speculation exists to provide, in exchange for closing the side channel. It’s also why this class of exploit keeps resurfacing in new variants years after the original disclosure: the fundamental tension between “guess ahead for speed” and “guessing ahead can leak information through timing” is baked into how every modern high-performance CPU pipeline works, and closing it fully would mean giving up the speculation that makes these chips fast in the first place — which nobody building performance-competitive silicon is willing to do, so the industry ships targeted mitigations for each new variant instead of removing speculation itself.

Troubleshooting: recognising a misprediction problem in your own code

The signature of branch-misprediction cost in a profiler is a hot loop whose instruction count looks entirely reasonable but whose wall-clock time is disproportionately high relative to that instruction count — perf stat on Linux will show this directly via the branch-misses counter, and a high ratio of branch misses to total branches on a hot loop is close to a direct diagnosis. Tools that expose CPU performance counters (perf, Intel VTune, or the built-in profiling most modern IDEs wrap around them) will point at exactly this metric once you know to look for it, rather than the plain instruction or cycle counts most people check first.

The practical fixes fall into a small set of well-known patterns: sort or bucket data before branching over it, as in the example above, when the branch’s outcome is what you’re testing for repeatedly. Replace unpredictable branches with branchless arithmetic where practical — a conditional-move or a bitwise select computed from a boolean mask instead of an if, which the compiler will often generate automatically once optimisation flags are turned on, but which sometimes needs an explicit nudge in genuinely hot, unpredictable code paths. And, where the unpredictability is inherent to the problem rather than an artefact of data layout, accept that the branch will mispredict regularly and focus optimisation effort elsewhere in the hot path, because no amount of code restructuring makes a genuinely 50/50 unpredictable branch predictable — that’s not a bug in your code, it’s the shape of the problem itself. This is the same category of low-level hardware behaviour that shows up when reasoning about what floating-point arithmetic is doing behind your back or what a compiler actually does to your code before it ever reaches the silicon — performance-sensitive code lives at the intersection of all three, and understanding one genuinely helps with the others.

Is it worth thinking about

For the overwhelming majority of code, no — modern branch predictors are extraordinarily good, correctly guessing well over 95% of branches in typical code without you ever needing to think about it, and premature branchless rewrites usually cost more in readability than they save in cycles. But for the specific hot loops that a profiler has already flagged as disproportionately expensive relative to their instruction count, understanding that a CPU is placing a bet on every single branch, and paying a real, measurable penalty when that bet loses, turns a mysterious performance cliff into a concrete, fixable property of your data’s layout.