CPU Caches

L1/L2/L3 caches exist because a load from DRAM costs ~60–80 ns - a few hundred cycles waiting. They sit close to the core, so their latency is far lower - the price is capacity. That limitation pushes the hardware into eviction and prefetch heuristics, and pushes code toward being efficient in locality, not just algorithmically correct.

The hierarchy

Rough numbers for a modern x86-64 desktop core — exact values differ per CPU, the orders of magnitude are what matter:

Level	Size	Latency	Shared?
L1d	32–48 KB	~4 cycles, ~1 ns	per core
L2	0.5–2 MB	~14 cycles, 4 ns	per core
L3	8–64 MB	~40 cycles, 15 ns	all cores
DRAM	GBs	~200+ cycles, 60-80 ns	everything

Each level is generally larger and slower than the one above it. A load checks L1 first, then L2, then L3, then goes to memory. There is a separate L1i for instructions, so a tight loop's code and its data don't evict each other.

The practical consequence: an L1 hit and a trip to DRAM can differ by roughly 50–100x in latency. Two programs doing the identical number of operations can therefore differ significantly in wall time purely because of where their data is in the memory hierarchy.

Cache lines

Memory doesn't move between levels one byte at a time. It moves in fixed blocks called cache lines — 64 bytes on x86-64 and most ARM (128 bytes on Apple silicon).

Reading a single int pulls in the whole 64-byte line containing it. So the next 15 ints cost almost nothing, and a single byte that is 100 bytes away costs a full miss. Every performance property below falls out of this one fact.

getconf LEVEL1_DCACHE_LINESIZE prints the real value on the machine.

Locality

Two kinds, both worth optimising for:

Temporal — the same address is used again soon, so it is likely still cached.
Spatial — nearby addresses are used soon, so they may already be in the same cache line.

Hardware also has a prefetcher: it detects sequential access patterns and pulls the next lines in before they're asked for. Linear scans are very cache-friendly while random pointer chasing defeats it completely.

What this means in code

Traversal order

Simple one - C stores 2D arrays row-major — m[i][j] and m[i][j+1] are adjacent in memory:

// fast: walks memory in order, one miss per 16 ints, prefetcher keeps up
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        sum += m[i][j];

// slow: jumps N*4 bytes each step, a fresh cache line every iteration
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        sum += m[i][j];

Same operations, same result, and for a large N the second version can be several times slower. Loop order is a cache decision.

Arrays beat linked structures

A linked list is a pointer chase: each next dereference is potentially a cold line, and the address isn't known until the previous load completes, so the CPU can't overlap the misses either.

This is why std::vector usually beats std::list, why Go slices beat linked lists, and why linear search over a small array often beats a hash map or tree — asymptotics lose to constants when the constant is 100 cycles. A binary search over 10k sorted elements does ~14 random-ish accesses; a linear scan touches 625 lines but sequentially, with the prefetcher helping.

This is why std::vector usually beats std::list, why Go slices often beat linked lists, and why linear search over a small array can beat a hash map or tree despite worse asymptotic complexity. For example, a binary search over 10k sorted elements does ~14 accesses, but those accesses may have poor locality; a linear scan touches ~625 cache lines sequentially, allowing hardware prefetching to help.

Struct layout

Fields used together should sit together, while cold fields can be kept elsewhere:

struct Entity {
    float x, y;
    char name[48];
    time_t created_at;
};

If the struct occupies 64 bytes, iterating over 100k entities to update positions reads roughly 6.4 MB of cache-line data while using only 0.8 MB of position data. Splitting the hot fields into their own arrays — an array of structs (AoS) to struct of arrays (SoA) transformation — can reduce the amount of memory touched by the hot loop by roughly 8x.

Field order matters too: struct fields may require padding for alignment, so arranging fields carefully can reduce the size of each element. Fewer bytes per element means more elements fit in each cache line.

Padding for the opposite reason

Two variables written by two different threads that land on the same line will ping-pong that line between cores even though nothing is actually shared — false sharing, covered in atomic operations. The fix is the inverse of everything above: deliberately pad the per-thread data out to a full cache line.

Associativity and conflict misses

A line can't go just anywhere. The cache is divided into sets, and an address maps to exactly one set by its middle bits; an "8-way" cache holds 8 lines per set. If a loop touches 9 addresses that all map to the same set, they evict each other constantly even though the cache is 99% empty — a conflict miss.

Because the set is picked from address bits, this happens with power-of-two strides. Walking a 1024 x 1024 float matrix by column means every access is exactly 4096 bytes apart, which is the pathological case. The standard fix is padding the row to 1025 — a wrong-looking dimension that makes the code faster. Sizing a hot buffer to N + 1 instead of a round power of two is a cheap thing to try when a benchmark is inexplicably bad.

Measuring

Cache effects are invisible in the source, so guessing is unreliable — measure:

perf stat -e cache-references,cache-misses,L1-dcache-load-misses ./prog
perf stat -e LLC-load-misses ./prog        # last-level misses = actual RAM trips
valgrind --tool=cachegrind ./prog          # per-line miss attribution, slow but exact
lscpu | grep -i cache                      # what the machine actually has

A miss rate that's a few percent is normal; double-digit LLC misses in a hot loop is the signal to look at layout and access order.

The thing to keep: caches reward code that touches memory in order and in bulk, and punish code that hops. Most "optimisations" that turn out to matter are just rearrangements that respect that.

Glossary

Cache line

The block of memory a CPU cache moves and tracks as one unit, 64 bytes on x86-64. Loading one byte loads its entire line.

Conflict miss

A miss caused by too many actively used addresses mapping to the same cache set, evicting each other while the rest of the cache sits unused. Distinct from a capacity miss, where the data genuinely doesn't fit.

Eviction policy

The rule a cache uses to choose which cache line to discard when a cache set is full and a new line has to be loaded. The goal is to remove a line that is unlikely to be needed soon.

Prefetcher

Hardware that detects access patterns, such as sequential access, and loads upcoming cache lines before the program requests them, helping to hide cache-miss latency.