The previous post ended with two numbers: a chain of dependent additions runs at exactly one per cycle, but when the additions are independent, the same CPU core does almost 3 per cycle. The program is still written one line at a time. So where does the CPU find parallel work?
This post answers that, then moves on to the biggest problem of modern CPUs: they compute far faster than memory can deliver data. The route: pipelines and out-of-order execution, branch prediction (and why sorting an array can make a loop 11 times faster), the memory wall and cache levels, cache lines and locality, then what it all means for the code you write every day, including Python.
Every number in this post was measured on a real machine, in C (clang, -O2) and Python 3.12, single-threaded, each measurement the best of 3 runs. Cache sizes and latencies differ between CPU families; what's worth looking at is the shape of the numbers.
Pipelines, and many instructions at once
The previous post split an instruction into four steps: fetch, decode, execute, write back. The CPU doesn't finish one instruction before starting the next; it arranges them into a pipeline, like an assembly line: every cycle, each station does one step for a different instruction.
cycle: 1 2 3 4 5 6
instruction 1: fetch decode execute write
instruction 2: fetch decode execute write
instruction 3: fetch decode execute write
Real CPUs have much longer pipelines (more than a dozen stations) and wider ones: every cycle they fetch and decode several instructions at once, and have several execution units (several adders, multipliers, memory readers) working in parallel. That's why the four independent chains of additions in the previous post ran at 2.9 per cycle.
But instructions in a program usually depend on each other: x = a + b then y = x * 2 means the multiplication has to wait for the addition. To avoid standing around, a modern CPU looks ahead hundreds of instructions, finds those whose data is ready, and runs them early, out of program order (out-of-order execution). Results are still "published" in the right order, so from the program's side everything looks sequential. Inside, it isn't.
Branch prediction
The pipeline has a problem with if statements. To keep the pipeline full, the CPU has to fetch the next instruction right now, before knowing whether the if condition is true or false, because that condition is still several stations back. It can't wait. So it guesses: the branch predictor remembers which way each if went before and in what pattern, then guesses this time. The CPU carries on down the guessed path. If the guess is right, nothing is lost. If it's wrong, all the work done down the wrong path is thrown away, and the pipeline has to refill from the start.
The classic experiment: sum the numbers greater than or equal to 128 in an array of a million random numbers from 0 to 255. Run it twice: once with the array as it is, once after sorting it. Same numbers, same loop, same result:
static long run(const int *data) {
long sum = 0;
for (int rep = 0; rep < 50; rep++)
for (int i = 0; i < N; i++)
if (data[i] >= 128) { sum += data[i]; __asm__ volatile(""); } // a real branch the CPU has to guess
return sum;
}
(The empty __asm__ volatile("") keeps the if as a real branch. Without it, the compiler is clever enough to replace the if with a branch-free select instruction, and the measurement comes out as 0.)
| Array | Per element |
|---|---|
| Random order | 2.43 ns |
| Sorted | 0.22 ns |
11 times faster, just from the order. With the sorted array, the first half is all numbers below 128 and the second half all above: the if goes the same way hundreds of thousands of times in a row, and the predictor is almost never wrong. With the random array, there's no pattern to learn, so about half the guesses are wrong. Working backwards: each wrong guess costs about (2.43 − 0.22) ÷ 0.5 ≈ 4.4 ns, or about 20 cycles thrown away.
Guessing and running ahead has a dark side too. In 2018, the Spectre vulnerability showed that work the CPU does down a mispredicted path, even though it's "thrown away", still leaves traces in the cache, and a malicious program can measure those traces to read data it shouldn't. Performance and security sometimes pull in opposite directions.
The memory wall
An addition takes one cycle. What about fetching the two numbers to add from memory?
To measure the true latency of memory, use pointer chasing: an array where each slot holds the position of the next slot to read, arranged into one random cycle through every slot. Each read has to wait for the previous one to finish before knowing where to read, so the CPU can't read ahead or overlap, and the measured time is exactly the latency of one read.
size_t *next = malloc(n * sizeof(size_t));
for (size_t i = 0; i < n; i++) next[i] = i;
for (size_t i = n - 1; i > 0; i--) { // Sattolo's shuffle: one big random cycle through every slot
size_t j = (size_t)rand() % i, t = next[i]; next[i] = next[j]; next[j] = t;
}
size_t p = 0;
for (size_t i = 0; i < steps; i++) p = next[p]; // each load needs the previous one's result
Varying the array size from 4 KiB to 128 MiB:
| Data | Per read | About how many cycles |
|---|---|---|
| 4 KiB – 128 KiB | 0.87 ns | ~4 |
| 256 KiB | 1.96 ns | ~9 |
| 1 MiB | 2.92 ns | ~13 |
| 4 MiB | 5.95 ns | ~27 |
| 16 MiB | 8.42 ns | ~38 |
| 32 MiB | 34.8 ns | ~160 |
| 64 MiB | 58.9 ns | ~270 |
| 128 MiB | 72.9 ns | ~330 |
The numbers don't rise smoothly; they rise in steps, and each step is a level of memory:
- Up to 128 KiB: the L1 cache, right next to the execution units, about 4 cycles.
- 256 KiB to 16 MiB: the L2 cache (and the CPU's other buffers), from 9 to almost 40 cycles.
- 32 MiB and up: real RAM, about 330 cycles at 128 MiB.
One read from RAM costs as much as over 300 additions. The CPU computes much faster than memory, and that gap is called the memory wall. Caches are how the CPU lives with it: small but very fast memories right on the chip, holding data just used and data that looks about to be used. A large part of a modern chip's area is cache, not arithmetic. If you've read part 3 of the LLM series, this is the same wall that made language-model text generation wait on memory rather than on computation.
Cache lines and locality
Caches don't store single bytes. They store cache lines: blocks of neighbouring bytes, read from RAM all at once. On this machine a line is 128 bytes (sysctl hw.cachelinesize); on most x86 CPUs it's 64 bytes. Reading a 4-byte integer means pulling the 128 bytes around it into the cache. If the program goes on to use the neighbouring bytes, they're already there. If not, the rest is wasted.
On top of that, CPUs have prefetchers: when they see a program reading neighbouring addresses one after another, they pull the next lines into the cache before they're asked for.
Both mechanisms reward one habit: read data in the order it sits in memory. The experiment: sum every element of a 4,096 × 4,096 matrix of integers (64 MiB). In C, a matrix is stored row after row, so walking by rows goes through neighbouring bytes, while walking by columns jumps 4,096 × 4 = 16 KiB at every step:
for (int a = 0; a < N; a++)
for (int b = 0; b < N; b++)
sum += order == 0 ? m[(size_t)a * N + b] // rows: neighbours in memory
: m[(size_t)b * N + a]; // columns: 16 KiB apart
| Default | Vectorization off | |
|---|---|---|
| By rows | 3 ms | 4 ms |
| By columns | 42 ms | 41 ms |
The same 16.7 million additions, the same result, 10 times slower. By columns, each read lands in a different cache line, uses only 4 of its 128 bytes, and the prefetcher can't guess the jump. The "vectorization off" column is there to make sure the gap comes from the cache: by default, the compiler also uses SIMD instructions (one instruction adding several numbers at once) for the row loop, but with them off, the gap is just the same.
Python doesn't escape it
You might think Python is too far from the hardware to be affected. Try it: build a list of 2 million big integers, then a second list holding exactly the same objects in shuffled order. Sum both:
import random, timeit
n = 2_000_000
a = [i * 3 + 1000 for i in range(n)] # big ints: each one a separate object, created one after another
b = a[:]; random.seed(0); random.shuffle(b) # the same objects, visited in random memory order
for name, xs in (("creation order", a), ("shuffled", b)):
t = min(timeit.repeat(lambda: sum(xs), number=3, repeat=3)) / 3
print(f"{name:15} {t*1000:6.1f} ms ({t/n*1e9:.1f} ns per element)")
| Time | Per element | |
|---|---|---|
| In creation order | 2.8 ms | 1.4 ns |
| Shuffled | 21.4 ms | 10.7 ns |
The same numbers, the same total, 7.6 times slower. The reason: a Python list doesn't hold numbers, it holds pointers to integer objects (previous post: 28 bytes or more each) scattered across the heap. Objects created one after another happen to sit next to each other in memory, so going in creation order walks through memory contiguously. Shuffling the list makes every element a jump to a random place, just like the pointer-chasing experiment above.
This is also one reason NumPy is fast: a NumPy array holds its numbers side by side in one block of memory, with no pointers and no separate object for each number.
What it means for code
- Contiguous data beats scattered data. Arrays are usually faster than linked lists or trees, even where complexity theory says the opposite for some operations, because every node of a linked list is another chance to miss the cache.
- Walk in memory order. For matrices, the outer loop over rows and the inner loop over columns (in C, and NumPy by default); for records with many fields, consider storing each field as its own array if a loop only reads one field.
- Keep the "hot" data small. What fits in L1 or L2 is tens of times faster than what has to come from RAM.
- Hard-to-predict branches are expensive. In a hot loop, an
ifthat goes either way at random can cost more than the actual work; sorting the data, or rewriting it without a branch, can pay off. - Measure before optimizing. Every number above required "holding the compiler back" to measure at all; compilers and CPUs already do a lot of optimizing on their own, and intuition is easily wrong.
Summary
| Concept | What it really is |
|---|---|
| Pipeline | Each station does one step for a different instruction; one instruction comes out per cycle |
| Superscalar | Several execution units in parallel: ~2.9 additions per cycle when independent |
| Out-of-order execution | Look ahead hundreds of instructions, run whichever has its data ready |
| Branch prediction | Guess an if's direction to keep the pipeline full; a wrong guess costs ~20 cycles |
| The memory wall | L1 ~4 cycles, L2 ~9–40, RAM ~330 |
| Cache line | Reads come in 128-byte blocks (64 bytes on most x86) |
| Locality | Read in memory order: rows are 10 times faster than columns |
| Python | Lists hold pointers; shuffling the order makes a sum 7.6 times slower |
This post treated "memory" as a simple row of addresses. It isn't: every program sees its own address space, a 1 GB malloc may not use a single byte of RAM, and the addresses a program uses have to be translated into real ones on every read. Next post: the stack, the heap, and virtual memory.