The pipeline, out-of-order execution and branch prediction

A modern core is not a machine that runs one instruction at a time. It fetches and decodes several instructions per cycle, renames their registers to remove false dependencies, puts them in a large window (the reorder buffer, a few hundred entries on current cores), and executes each one as soon as its inputs are ready, on one of several execution units: multiple integer ALUs, load and store units, floating-point and vector units. Results are then retired in program order, so the program sees sequential behaviour.

So the speed of a loop is limited not by how many instructions it has, but by how much of it can run at the same time. That depends on dependencies: an instruction that needs the result of another must wait for it.

double sum = 0;
for (double x : v) sum += x;            // each add needs the previous sum

Every addition depends on the one before. A floating-point add takes about four cycles of latency, so this loop runs at best one add per four cycles, however many adders the core has. The core sits mostly idle: the chain, not the throughput, is the bottleneck.

double s0 = 0, s1 = 0, s2 = 0, s3 = 0;
std::size_t i = 0;
for (; i + 4 <= v.size(); i += 4) { s0 += v[i]; s1 += v[i+1]; s2 += v[i+2]; s3 += v[i+3]; }
for (; i < v.size(); ++i) s0 += v[i];
double sum = (s0 + s1) + (s2 + s3);

Four independent chains let four additions be in flight at once. That is the answer to the question: instruction-level parallelism. The compiler will not do this transformation for floating point by default, because floating-point addition is not associative and the result may differ in the last bits (Module 10); with integers, or with -ffast-math's reassociation, it often does it and vectorises too.

The same principle explains why pointer chasing is slow (each load depends on the previous one) and why interleaving two independent lookups can be almost twice as fast as doing them one after the other.

Module 1 introduced mispredictions. The predictors behind them are remarkably good: modern designs combine the history of the branch itself with the recent history of other branches, and learn patterns such as "taken every third time" or "taken if the previous branch was not taken". Loops with a fixed trip count, error checks, and type dispatch with a stable pattern predict almost perfectly.

What they cannot learn is data that is genuinely random. The cost of each miss is the depth of the pipeline that must be refilled, around fifteen to twenty cycles, plus the work that was in flight down the wrong path.

Practical habits:

• Make data predictable where you can: process messages grouped by type, or sorted, rather than interleaved.
• Replace unpredictable branches with arithmetic or selection when both sides are cheap.
• Check the branch-miss counter before and after (Module 8): if misses did not fall, the branch was not the problem.

The core also speculates on memory: it may execute a load before an earlier store whose address is not yet known, guessing they do not overlap, and replay if wrong. And it keeps executing past a cache miss, finding other independent work in its window. A long-latency miss that blocks the window from moving on is what finally stalls it. This is why independent misses overlap (memory-level parallelism) and dependent ones do not.

• Shorten dependency chains in hot loops: multiple accumulators, tree reductions, independent lookups interleaved.
• Keep branches predictable or remove them.
• Avoid long chains of dependent loads; lay data out so addresses can be computed in advance.
• Keep hot loops small enough for the micro-op cache and free of calls the compiler cannot inline.