Pipelines, Branch Prediction and Speculation

A modern core does not finish one instruction before starting the next. It works on dozens at once, like an assembly line, and it guesses which way every branch will go so that the line never has to wait. When the guess is right the program flies. When it is wrong, the core throws the guessed work away and starts again.

That guess is why a loop over sorted data can run several times faster than the same loop over shuffled data, with exactly the same number of steps. And in 2018 it is how the industry learned that guessing leaves footprints an attacker can read. This topic follows the line, the guess and the footprints, and prices each.

The Assembly Line

Fetching an instruction, decoding it, executing it, touching memory and writing the result back are separate jobs done by separate circuits. So while one instruction executes, the next is being decoded and the one after that fetched, the way a car factory works on many cars at once, each at a different station. The figure shows five instructions in a five-stage pipeline: at the fifth tick every stage is busy, and five instructions finish in 9 ticks instead of 25.

Real cores go much further. Current designs have pipelines on the order of 15 to 20 stages, and they can fetch, decode and start several instructions in every tick, so a single core keeps dozens, often well over a hundred, instructions in flight at once. None of this is visible to the program, which sees instructions complete one after another in the order it wrote them.

The Stall

The line only flows if every instruction has what it needs. An instruction that needs a result not yet computed, or data not yet loaded from memory, cannot proceed, and in a simple pipeline everything behind it stops too. That is a stall.

Out-of-order execution is the core's answer. It looks ahead in the instruction stream for later instructions that do not depend on the stalled one and runs those in the meantime, then puts the results back in program order. That hides short stalls, a few ticks waiting for an arithmetic result or a nearby cache. It cannot hide a trip to main memory, which costs about a hundred nanoseconds on the latency ladder in Chapter 4, a few hundred ticks, far longer than the core can find independent work to fill.

Branches and the Predictor

At an if statement, or at the end of a loop, the core does not yet know which instruction comes next: the comparison that decides it is still somewhere in the pipeline. Waiting would empty the line on every branch. So the core predicts. A branch predictor remembers the recent history of each branch and guesses from it, and the core keeps fetching and executing along the guessed path.

Modern predictors are right well over 90 percent of the time on typical code, because most branches are regular: a loop branch goes the same way thousands of times, an error check almost never fires. When a guess is wrong, the core discards every instruction it started on the wrong path and refills the line from the right one. That flush costs on the order of 15 to 20 ticks on current cores, about the depth of the pipeline.

Why Sorted Data Runs Faster

Take a loop that adds up every byte whose value is at least 128. Over random bytes the branch is a coin flip, and no predictor can beat a coin. A simple model of a predictor, one that remembers whether the branch was taken recently, guessed wrong on 50.0 percent of a million random bytes. Sort the same bytes first and the branch goes one way for the first half and the other way for the rest. The same model then guessed wrong 3 times in the million, all at the switch.

Compiled, the difference is large. On the laptop this book was written on, that loop took about 3.6 nanoseconds per byte over shuffled data and about 0.4 over sorted data, roughly nine times faster for the same count of steps. This is the effect behind a famous 2012 Stack Overflow question about why processing a sorted array is faster. In CPython 3.15 the same loop took about 24 nanoseconds per byte shuffled and 15 sorted: the effect is still there, and the interpreter's own overhead shrinks it from nine times to about one and a half. It shows most in compiled code, vectorized libraries and database engines.

Speculation and the Spectre Lesson

Executing along a guessed path is called speculative execution. Its results are held back until the guess is confirmed, and thrown away if it was wrong, so the program's visible state is never affected. But the guessed path also loads data, and that data stays in the processor's cache after the results are discarded.

In January 2018 researchers disclosed Spectre, together with a related attack called Meltdown. They showed that an attacker could steer speculation to read a secret on a path that would never really run, and then recover the secret by timing which memory had become fast to read. Spectre affected processors from Intel, AMD and ARM, because speculation is how all fast cores go fast. It is a class of attacks, not a single bug: new variants kept appearing after 2018, and the hardware and software mitigations cost performance on some workloads.

The Price of Unpredictability in Your Code

The same algorithm on data in a predictable order runs faster than on shuffled data. Branch-heavy code over random input, such as parsing, hash lookups and tree walks with random keys, pays for mispredictions on top of its step count. That is one reason a flat scan over an array can beat a tree on small inputs, which Chapter 4 measures.

It is also one reason the constant that Big-O discards, in Chapter 1, differs between two O(n) loops. Two loops with the same class and the same step count can run nine times apart because one of them branches unpredictably, and nothing in the source code says which.