CPU and memory: the machine is a guessing machine

Why does it matter more how predictable your code is than how much work it does?

A memory system with a calculator attached

In Storage media the main force was Cause 0 (stability vs. mutability). Here it mostly disappears. SRAM and DRAM are on the low-barrier end of the dial: nothing wears out. What takes its place is Cause 1, distance, and one physical law:

Two consequences produce everything else in this article:

1. CPUs became ~200× faster than DRAM over three decades (the "memory wall"): CPU speed grew ~50% per year, DRAM latency only ~7%, compounding from about 1986 until CPU clock growth stalled around 2005. The machine you program is a memory system with a calculator attached, not the opposite.
2. Every fix for this gap is a prediction. Caches predict you will reuse data. Prefetchers predict your next address. Branch predictors predict which way an if goes. Speculation predicts results before they are computed. A modern CPU is a guessing machine. Your speed depends on how predictable your code is, not how much work it does.

In Storage media the key question was "which axis absorbed the cost?" Here it is "how predictable is this?"

Cache hierarchy, line size and locality

A cache is a small fast memory holding copies of recently used data from a bigger, slower memory.

Each level gives ~4× more latency for 10–30× more capacity. Nobody designed a neat pyramid; the pyramid is what physics gives you when you ask for both fast and big.

The cache line: Cause 2 in miniature

Memory is not moved byte by byte. The CPU moves it in blocks called cache lines of 64 bytes. The cost of tags, address decoding and the DRAM burst is spread over a block of bits — the same ladder as the flash erase block, only at nanosecond scale. And it has the same consequence: if your access size does not match the line size, you get amplification. Touch 4 bytes, pay for 64: a read amplification of 16×.

Locality: two bets

• Spatial locality: if you touch this address, you will probably touch its neighbors soon (arrays read in order).
• Temporal locality: if you touched this just now, you will probably touch it again soon (loop counters, hot tables).

Hardware prefetchers watch your access pattern, detect a stride, and load data before you ask. So sequential access does not only amortize cost; it hides latency completely. This is why walking a 2-D array row by row (when it is stored row by row) can be 5–10× faster than column by column, for exactly the same arithmetic:

// 'a' is stored row by row: a[i][j] is next to a[i][j+1] in memory.
long sum = 0;

// FAST: reads memory in the order it is stored. One 64-byte line serves 16 ints.
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        sum += a[i][j];

// SLOW: jumps N*4 bytes between reads. Every read loads a new cache line.
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        sum += a[i][j];

The number that changes how you think

DRAM latency ≈ 200–400 clock cycles. A modern core can finish about 4 instructions per cycle. So one cache miss wastes about 1,000 instruction slots. You are not optimizing the number of instructions. You are optimizing the number of cache misses.

Cache misses dominate scans

A scan reads a lot of data and does little work per item (sum a column, filter rows). Arithmetic per byte is ~1 operation, so the memory system sets the limit and the arithmetic units wait. Latency can be hidden with concurrency (below). Bandwidth cannot.

The first-principles case for columnar storage

Row layout stores each record's fields together: [id, name, age, city, … 20 columns …], then the next record. A query needs one column (SUM(age)). Every 64-byte line you load holds one useful value and ~19 unwanted columns. You waste ~95% of every line: ~20× read amplification.

Column layout stores all age values together. Now every byte in every line is useful: amplification → 1. The prefetcher works (pure sequential access). Compression also works better, because one column holds similar values.

Parquet exists because of cache lines, before it exists because of disks. (The layouts themselves, and what each costs, are storage layout's.) (This is the answer to Meera's slow scan: her events were stored as rows.)

Memory-level parallelism: Little's Law again

A core can have ~10–16 cache misses in progress at once (limited by line-fill buffers, the hardware slots that track them). So

Pointer chasing (following a linked list or tree, where each item's address is inside the previous item) forces misses to happen one after another: concurrency stays at 1. That is why linked lists are terrible and arrays are fine: same instruction count, very different achievable concurrency.

This is the same equation as NVMe queue depth in Storage media. The prefetcher's job is to raise the concurrency term for you. It can only do that when your pattern is predictable.

False sharing

When several cores each keep a copy of a cache line, hardware must keep the copies consistent (cache coherence). When one core writes to a line, the other cores' copies are invalidated (marked stale) and must be loaded again. Coherence works per line, not per byte, because tracking per byte would need 64× more bookkeeping (Cause 2 again).

So if two cores write different variables that sit in the same 64-byte line, the hardware treats it as a fight over the same data. The line bounces back and forth between the cores. There is no logical sharing, but you pay the full cost of sharing: ~100 ns per bounce instead of ~1 ns, and more cores make it worse.

// Each thread increments its own counter. It looks perfectly parallel.
long counts[NUM_THREADS];      // 8 longs fit in ONE 64-byte line → 8 threads fight over it

void* worker(void* arg) {
    int id = (int)(long)arg;
    for (long i = 0; i < 100000000; i++) counts[id]++;
}

// Fix 1: pad each counter to its own cache line (spend space to buy time).
struct { long value; char pad[56]; } counts[NUM_THREADS];   // 8 + 56 = 64 bytes

// Fix 2 (usually better): count in a local variable, write once at the end.
long local = 0;
for (long i = 0; i < 100000000; i++) local++;
counts[id] = local;

(Some CPUs prefetch lines in pairs, so padding to 128 bytes is sometimes needed.)

This is the one place where pure hardware gives negative scaling: more threads make the program slower. It is the hardware form of the β (coherency) term of the Universal Scalability Law in Performance laws. This was Meera's first odd finding: eight counters sharing one line.