Branch Prediction and Out-of-Order Execution Explained

Branch prediction and out-of-order execution are two techniques modern CPUs use to keep their internal pipelines full despite the fact that real code is full of conditional jumps and instructions that depend on slow, unpredictable operations like memory loads. Both exist to solve the same underlying problem — a pipelined CPU wants to work on many instructions at once, but real programs keep interrupting that flow — and both are largely invisible to the software running on top of them.

The pipelining problem they solve

A modern CPU doesn’t execute one instruction, finish it, then start the next. It pipelines: while one instruction is being decoded, another is being fetched, another is executing, and another is writing back its result, all in the same clock cycle, at different stages. This only works smoothly if the CPU knows in advance which instructions are coming next.

An if statement breaks that assumption. The CPU can’t know whether the branch will be taken until the condition is actually evaluated — but evaluating it might itself depend on a value that hasn’t finished loading from memory yet. If the pipeline simply stalled and waited every time it hit a branch, most of its parallelism would go to waste.

Branch prediction: guessing which way a branch goes

Branch prediction is exactly what it sounds like: the CPU guesses which direction a conditional branch will go, and starts fetching and executing instructions along that guessed path before the condition is actually resolved. Predictors range from simple (assume a branch behaves the same way it did last time) to sophisticated pattern-history tables that track a branch’s recent history and correlate it with other nearby branches, learning patterns like “this loop’s exit branch is almost always not-taken until the last iteration.”

When the prediction is right — and modern predictors are right the overwhelming majority of the time for typical code — the CPU has effectively hidden the latency of resolving the branch, having already done useful work along the correct path. When it’s wrong, everything speculatively executed down the wrong path has to be discarded, and the pipeline has to restart from the correct instruction — a misprediction penalty that costs many cycles, roughly proportional to how deep the pipeline is. This is why branch-heavy code with unpredictable patterns (data-dependent branches over effectively random data, for instance) tends to run slower than branch-light code doing comparable work, even at identical clock speeds.

Out-of-order execution: not waiting for the slow thing

Out-of-order execution addresses a related but distinct problem: instructions often depend on results that aren’t ready yet, most commonly a value still being fetched from main memory or a slower cache level. Rather than stalling the entire pipeline until that value arrives, an out-of-order CPU scans ahead in the instruction stream for other, independent instructions that don’t depend on the stalled value, and executes those instead, in whatever order their operands become ready — hence “out of order.” Results are still committed and made visible in the original program order at the end (this is what keeps the CPU’s behavior correct from the program’s point of view), but the internal execution order can differ substantially from how the instructions were written.

This is the mechanism that lets a single CPU core extract meaningful instruction-level parallelism out of ordinary sequential code, without the programmer or compiler doing anything special — it’s a property of the hardware, not something exposed in an instruction set.

How the two work together

Branch prediction and out-of-order execution compound: a mispredicted branch doesn’t just waste the instructions fetched down the wrong path, it also wastes whatever out-of-order scheduling and speculative work was built up around them, since all of that has to be flushed and restarted too. Conversely, a well-predicted branch lets the out-of-order engine keep working confidently on instructions well beyond the branch, since it can trust the guessed path enough to build real computation on top of it before confirmation arrives.

This combination is also the root cause behind the Spectre class of hardware vulnerabilities, where speculative execution down a mispredicted (and in that case, deliberately mistrained) path can leave observable side effects in the cache even after the speculative work is discarded, letting an attacker infer data that was never supposed to be readable. It’s a good illustration of how deeply these performance mechanisms are baked into how a modern CPU behaves, security included.

Why this matters beyond CPU design

You don’t control branch prediction or instruction scheduling directly, but you can write code that’s friendlier to them:

• Predictable branches beat unpredictable ones. Sorting data before branching on it, or restructuring a hot loop to avoid a data-dependent branch entirely, can measurably speed up hot paths, because the predictor has an easier pattern to learn.
• Independent work parallelizes better under the hood. Code with fewer artificial dependencies between nearby instructions gives the out-of-order engine more freedom to reorder around a stall.
• None of this shows up in Big O notation. Two algorithms with identical asymptotic complexity can have very different real-world performance purely because of how branch-friendly or cache-friendly they are — a reminder that algorithmic complexity and constant-factor performance are separate concerns.

The takeaway

Branch prediction guesses which way a conditional branch will go and starts executing down that path before the CPU actually knows, hiding the latency of resolving the branch when the guess is right. Out-of-order execution reorders independent instructions around slow dependencies like memory loads, so the pipeline keeps working instead of stalling. Together they’re a large part of why single-core performance improved for decades even as clock speeds plateaued, and they’re a good example of hardware doing enormous, invisible work to make ordinary sequential code run fast.