Branch Prediction

A modern CPU doesn’t execute one instruction at a time and wait to see what happens — it runs a deep, multi-stage assembly line called a pipeline, fetching, decoding, and beginning execution on several instructions simultaneously, each at a different stage of completion. That design only works if the pipeline stays full, and roughly one in every three to five instructions in real code is a branch — an if-statement, a loop condition, a function-pointer call — whose outcome the CPU can’t actually know until the branch itself finishes executing, several pipeline stages later. Rather than stall the entire pipeline waiting for that answer, the processor guesses which way the branch will go, keeps fetching and speculatively executing instructions down that guessed path, and only finds out later whether the guess was right. Branch prediction is the name for that guess, and it is one of the single largest contributors to how fast modern CPUs actually run real-world code — and, as the 2018 disclosure of Spectre proved, one of the most consequential security assumptions baked into decades of processor design.

Why Guessing Beats Waiting

A pipelined CPU breaks instruction processing into discrete stages — commonly something like fetch, decode, execute, memory access, and writeback — with a different instruction occupying each stage at any given clock cycle, the same way a car factory assembly line has a different vehicle at each station simultaneously rather than building one car start-to-finish before starting the next. The problem a conditional branch creates is that the fetch stage needs to know which instruction comes next, and for a branch, that answer depends on a comparison result the execute stage won’t produce for several more cycles.

   Without prediction: pipeline stalls waiting for the branch

   Cycle:    1     2     3     4     5     6     7
   Fetch:  [CMP] [ ? ]  ...   ...   ...   ...   ...
   Decode:       [CMP] [ ? ]  ...   ...   ...   ...
   Execute:            [CMP] [ ? ]  ...   ...   ...
                              ↑
                     branch result known here —
                     only NOW can fetch resume,
                     several cycles wasted

   With prediction: pipeline keeps moving on a guess

   Cycle:    1     2     3     4     5     6     7
   Fetch:  [CMP] [X+1] [X+2] [X+3] [X+4] [X+5] [X+6]
   Decode:       [CMP] [X+1] [X+2] [X+3] [X+4] [X+5]
   Execute:            [CMP] [X+1] [X+2] [X+3] [X+4]
                              ↑
                     if guess was right, zero cycles lost;
                     if wrong, everything after CMP is discarded

Stalling the pipeline until every branch resolves would be correct but catastrophically slow — on a deeply pipelined superscalar processor, that’s the exact penalty a misprediction already pays, commonly cited in the range of 10 to 20-plus cycles on modern x86-64 hardware (documented figures put Skylake around 16–17 cycles, Ice Lake around 17–21, and AMD’s Zen 1/2 generation around 19). Paying that penalty on literally every branch, correct or not, would gut throughput; paying it only on the roughly 1-to-5 percent of branches a good predictor actually gets wrong is a dramatically better trade.

How the CPU Actually Guesses

The simplest possible branch predictor — always predict “taken,” or always predict based on the direction the branch went last time — works better than no prediction at all, but real predictors track history explicitly and update their guess as they learn a branch’s actual behavior over repeated executions. A widely used building block is the two-bit saturating counter: rather than flipping its prediction the instant a single branch outcome disagrees with it, the counter requires two consecutive mispredictions in the same direction before it changes its mind, which adds hysteresis and prevents a predictor from being whipsawed by one-off outliers in an otherwise consistent pattern.

Modern high-performance predictors go considerably further, tracking not just a single branch’s own history but correlating it against the recent history of other nearby branches — the intuition being that real code frequently has branches whose outcomes are correlated (an if (x > 0) check right after a loop that already established something about x, for example). Tournament predictors take this a step further still, running multiple prediction strategies in parallel and dynamically selecting whichever strategy has been most accurate recently, effectively letting the CPU adapt its guessing method to the specific pattern of branches a given piece of running code exhibits.

Predicting the branch’s direction (taken or not-taken) is only half the problem — the CPU also needs to know where to fetch from next, which for an indirect or computed branch (like a virtual function call or a switch statement compiled into a jump table) isn’t even a fixed address. This is handled by a Branch Target Buffer (BTB), a small, fast cache that stores the addresses of recently executed branch instructions alongside the target addresses they actually jumped to, letting the CPU look up “last time I hit this branch, where did it go” and start fetching from that predicted target immediately, without waiting to decode the branch instruction fully first.

The payoff for all this machinery is substantial: well-tuned modern predictors correctly guess the outcome of a branch somewhere in the 90s of a percent of the time on typical code, and pushing that accuracy even a percentage point higher translates directly into fewer expensive pipeline flushes across the astronomical number of branches a running program executes.

The Cost of Being Wrong

When a prediction turns out wrong, everything the CPU speculatively fetched, decoded, and began executing down the guessed path has to be thrown away — a pipeline flush. The processor discards all that in-flight speculative work, resets its internal state back to the last known-correct point (the branch instruction itself), and restarts fetching down the now-known-correct path. Because a modern superscalar CPU can have dozens of instructions in flight simultaneously across a deep pipeline, a mispredicted branch doesn’t just cost one wasted cycle — it costs the full depth of everything that had already entered the pipeline behind the bad guess, which is exactly where that 10-to-20-plus-cycle penalty figure comes from.

Modern out-of-order processors add a further wrinkle: instructions don’t necessarily complete in the order they were fetched, so the CPU maintains a reorder buffer that tracks the correct program order and only commits results to visible, permanent state once it’s certain they were on the correct path — which is precisely the mechanism that makes a clean rollback after a misprediction possible in the first place. Speculatively executed instructions can compute results, even touch the cache and memory subsystem, entirely provisionally; the reorder buffer is what lets the CPU cleanly discard all of that provisional work as if it had never happened, once a misprediction is detected.

This is why branch-heavy, data-dependent code (an if-statement whose outcome depends on essentially random input data, as opposed to a loop counter with an obviously repeating pattern) is disproportionately expensive on modern hardware compared to code with the same instruction count but more predictable control flow — the raw instruction count is the same, but the misprediction rate, and therefore the number of expensive pipeline flushes, is not.

1
2
3
4
5
6
7
8
9

/* Classic real-world example: sorting the array before this loop
   can make it run several times faster on the same hardware,
   purely by making the branch more predictable — same data,
   same comparisons, same instruction count either way. */
for (int i = 0; i < n; i++) {
    if (data[i] >= threshold)   /* unpredictable if data[] is random;
                                    highly predictable if data[] is sorted */
        sum += data[i];
}

Spectre: When the Guess Itself Becomes the Leak

For over two decades, branch prediction was treated purely as a performance optimization with no security implications, on the reasoning that a misprediction’s speculatively executed instructions get architecturally discarded — their results never become visible to software, so what’s the harm in guessing wrong sometimes? The Spectre vulnerability, publicly disclosed in January 2018, showed that reasoning was incomplete: while a misprediction’s speculative results are indeed discarded at the architectural level, they leave measurable microarchitectural side effects behind — specifically, changes to what’s present in the CPU’s cache — and those side effects survive the rollback even though the speculative computation itself did not.

The attack works in three stages. First, an attacker deliberately mistrains a victim process’s branch predictor by repeatedly executing a branch in a way that teaches the predictor a specific, exploitable pattern — for instance, training a bounds-check branch to reliably predict “in bounds” by repeatedly calling it with valid, in-bounds values. Second, the attacker triggers the victim code with an actual out-of-bounds value; because the predictor has been trained to expect “in bounds,” the CPU speculatively executes the supposedly safe path anyway, momentarily reading memory it should never have accessed, before the branch resolves and the CPU discovers the misprediction. Third, and this is the actual leak: before the pipeline flush cleans up the architectural state, the speculative code can use the illicitly-read secret data to influence which cache line gets touched — for example, indexing into a large array using the secret byte as an index. The pipeline flush erases the register values and any direct output of that speculative execution, but it does not undo the fact that a specific cache line got pulled into the cache. The attacker then simply times access to each possible cache line: whichever one now returns suspiciously fast reveals it was the one loaded during speculation, and from that the attacker can back out the secret byte value one bit at a time.

   1. Attacker mistrains branch predictor
      (repeated in-bounds calls teach the CPU to expect "safe")
                        │
                        ▼
   2. Attacker triggers victim with an out-of-bounds value
      CPU speculatively executes the "safe" path anyway,
      reads forbidden memory before the branch resolves
                        │
                        ▼
   3. Speculative code uses the secret to index into an array,
      pulling one specific cache line into the CPU cache
                        │
                        ▼
   4. Branch resolves as mispredicted → pipeline flush
      (register results discarded — but the cache line stays!)
                        │
                        ▼
   5. Attacker times access to each possible array index;
      the fast one reveals which cache line got loaded,
      leaking the secret byte via cache-timing side channel

This pattern — using speculative execution to transiently access data the code shouldn’t reach, then exfiltrating it through a cache-timing side channel rather than through any value the program ever architecturally returns — is what makes Spectre and its many subsequent variants so difficult to fully close. The vulnerability isn’t a bug in any specific branch predictor’s logic; it’s a consequence of speculative execution as a performance technique interacting with cache timing as an observable side channel, present across processors from Intel, AMD, and ARM used in essentially the entire modern computing installed base.

Honest Trade-offs

• Mitigations cost real performance, and there’s no way around that tension. Software and microcode mitigations for Spectre-class vulnerabilities — retpolines, indirect branch restricted speculation, and similar techniques — work by deliberately limiting or slowing speculative execution in specific risky patterns, which directly gives back some of the performance speculation was added to gain in the first place; published benchmarks after the original 2018 disclosures showed measurable slowdowns on affected workloads, particularly ones with heavy indirect branching or frequent system calls.
• Predictable code really is faster code, and that’s not a micro-optimization myth. The sorted-versus-unsorted array example above is a well-known, easily reproducible demonstration that identical instruction counts can execute at meaningfully different speeds purely as a function of branch predictability — a real, measurable effect, not a folklore claim.
• Perfect prediction is neither achievable nor infinite in value. Genuinely data-dependent branches (based on effectively random input) have a theoretical prediction ceiling no amount of predictor sophistication can beat, and chasing marginal accuracy gains on such branches trades transistor budget and power against a benefit that’s fundamentally capped by the entropy of the data itself.
• The Spectre class of vulnerabilities isn’t fully closed, and likely can’t be with current architectures. New variants and refinements have continued to surface well after the original 2018 disclosure, because the root cause — speculative execution’s side effects being observable through cache timing — is architecturally load-bearing for modern CPU performance, not an isolated defect that a single patch eliminates.
• Bigger predictors help, but with sharply diminishing returns. Doubling a pattern-history table’s size or adding another level of correlation captures more branch history and catches more exploitable patterns, but real workloads have a finite amount of learnable structure in their branch behavior; past a certain table size, the extra silicon and power spent chasing residual mispredictions buys less accuracy than the same budget would buy elsewhere on the chip, which is why predictor tables have grown steadily rather than explosively across CPU generations.

Verdict

Branch prediction exists because stalling a deep, multi-stage pipeline on every single conditional branch would waste far more performance than an educated guess, even a wrong one, ever costs — and modern predictors are good enough, correct on the large majority of branches in typical code, that the strategy pays for itself many times over despite the real 10-to-20-plus-cycle penalty a misprediction incurs. What decades of hardware design treated as a purely internal performance detail turned out, in 2018, to also be a security boundary: the same speculative execution that makes modern CPUs fast leaves cache-timing fingerprints behind even when its results are architecturally discarded, and Spectre is the demonstration that those fingerprints are enough to read data an attacker was never supposed to see. The performance gain from branch prediction was never in question; what changed permanently in 2018 was the understanding that “discarded” and “invisible” are not the same guarantee.

Sources

• Medium — Branch Prediction: Tackling Pipeline Stalls for Performance
• John Farrier — Branch Prediction: The Definitive Guide for High-Performance C++
• Johnny’s Software Lab — How Branches Influence the Performance of Your Code
• Abhik Sarkar — CPU Pipelines & Branch Prediction in Processors
• Lenovo — Pipeline Flush: The CPU Reset That Boosts Accuracy
• arXiv — Spectre Attacks: Exploiting Speculative Execution
• Wikipedia — Spectre (Security Vulnerability)
• Medium — SPECTRE: Exploiting Speculative Execution, Technical Analysis