Caches & locality

The speed gap

A modern CPU can do several billion operations a second. Main memory (RAM) hasn’t kept up: fetching one value from RAM takes about 100 nanoseconds, which is long enough for the CPU to run several hundred instructions. If the CPU waited on RAM for every value, it would spend nearly all its time doing nothing. The fix is caches: small, very fast memories built into the CPU chip that keep copies of recently used data. There are usually three levels, each bigger and slower than the one before: | Where | Typical size | Latency | Cycles at ~4 GHz | Register | a few hundred bytes | ~0 | 0 | L1 cache | 32–64 KiB per core | ~1 ns | ~4 | L2 cache | 0.5–2 MiB per core | ~3–4 ns | ~12–14 | L3 cache | tens of MiB, shared | ~10–20 ns | ~40–70 | RAM | gigabytes | ~80–100 ns | ~300–400 When the CPU needs a value it checks L1 first, then L2, then L3, and only then goes to RAM. Finding the data in a cache is a hit; having to look further is a miss. A program that mostly hits L1 can run many times faster than one that keeps missing all the way to RAM, even if both do exactly the same calculations. An analogy: L1 is the papers on your desk, L2 is your desk drawer, L3 is the filing cabinet in your office, and RAM is an archive in another building.

Cache lines: memory moves in chunks

Caches don’t copy single bytes. They copy fixed-size blocks called cache lines: 64 bytes on x86-64 and most ARM chips. Read one byte, and the whole 64-byte line containing it gets copied into the cache. That’s a gift if your next reads are nearby, because they’re already in cache and nearly free. Reading a list of u32 values from start to end, one miss brings in 16 numbers at once. On top of that, the CPU has a prefetcher that watches your access pattern. When it sees you walking forward through memory, it starts fetching the next lines before you ask for them.

Locality: the rule for fast code

Programs run fast when they have good locality:

Spatial locality: after using some data, you use the data stored right next to it. Walking through an array in order is the perfect example.
Temporal locality: you use the same data again soon, while it’s still in cache. A small lookup table used inside a hot loop stays cached. Linked lists are the classic bad example. Each node is a separate allocation, so the nodes can be anywhere in memory. Following next pointers jumps around unpredictably: each hop may miss the cache, and the prefetcher can’t guess where the next node is. Walking a million-element array is typically far faster than walking a million-node linked list, even though both are “O(n)” on paper.

Traversal order

A 2D array is still stored as one long row of memory. [R][C]T stores row 0 completely, then row 1, and so on. This is called row-major order. So:

Walking row by row (inner loop over the columns) touches memory in order. Every byte of every cache line gets used.
Walking column by column (inner loop over the rows) jumps a whole row ahead at each step. With 1024 u32 columns that’s 4 KiB per step, so every access lands on a different cache line, and by the time you come back for the next column those lines may already have been pushed out.

var grid: [1024][1024]u32 = undefined; // 4 MiB: keep it global, not on the stack

fn rowMajor() void {
    for (&grid) |*row| {
        for (row) |*cell| cell.* += 1; // walks contiguous memory
    }
}

fn columnMajor() void {
    for (0..1024) |c| {
        for (0..1024) |r| grid[r][c] += 1; // jumps 4 KiB per step
    }
}

Both functions do exactly the same work. On big arrays the column-major version is often several times slower, purely because of the order in which it touches memory.

Array of structs vs struct of arrays

Say you’re writing a particle system:

const Particle = struct {
    x: f32, y: f32, z: f32,
    vx: f32, vy: f32, vz: f32,
    color: u32,
    alive: bool,
};
var particles: [10_000]Particle = undefined;

This is an array of structs (AoS). If a loop only checks alive, each 64-byte cache line brings in whole particles, and you use just one bool from each; the rest is wasted. A struct of arrays (SoA) stores each field in its own array: all the x values together, all the alive flags together. Now a loop over alive reads nothing but tightly packed alive flags. Game engines and databases use this layout a lot. Zig’s std.MultiArrayList stores items this way while still letting you append and read whole items like a normal list.

Each CPU core has its own L1 and L2 caches. When one core writes to a cache line, the copies of that line in other cores’ caches have to be thrown out. If two threads write to different variables that happen to sit on the same 64-byte line, the line keeps bouncing between cores, even though the threads never touch each other’s data. This is false sharing, and it can make multithreaded code slower than single-threaded. The fix is to give each thread’s frequently written data its own cache line, for example with align(std.atomic.cache_line).

Recap

RAM is roughly 100× slower than L1 cache; caches keep recently used data close to the CPU.
Memory moves in 64-byte cache lines, so nearby data comes along for free.
Good locality (walking in order, reusing data) is fast. Chasing pointers around memory is slow.
Walk 2D arrays row by row. Consider struct-of-arrays when loops only use a few fields.
False sharing: threads writing different variables on one cache line slow each other down.