Memory Hierarchy and Locality

Symptom

You replace a linked list with a std::vector and the traversal gets eight times faster. Same asymptotics, same number of comparisons, same operations executed. Eight times.

Later, you transpose a loop nest — swap the i and j order in a matrix multiply, changing nothing about what is computed — and get a 10x improvement. Later still, you switch a hash map from chaining to open addressing and get 3x with a worse theoretical collision bound.

Every one of these is invisible to the RAM model, in which memory access is $O(1)$ and all these programs are identical. The model is wrong in one specific way, and it is the way that dominates the actual runtime of essentially every real program.

Statement

This post carries a compound kind, and the two halves are genuinely separable.

The hierarchy (empirical). Memory systems are built as levels of increasing size and decreasing speed, because fast memory is expensive per bit and physically must be small. Approximate current numbers, per access:

Level	Latency	Size	Cycles
Register	0.3 ns	~1 KB	1
L1 cache	1 ns	32–64 KB	~4
L2 cache	4 ns	0.5–2 MB	~14
L3 cache	15 ns	8–64 MB	~50
DRAM	80 ns	8–512 GB	~250
NVMe SSD	50 µs	TB	~150,000

This is an observed regularity of engineering economics and physics, not a theorem. The numbers move; the ratios and the shape do not.

Locality (empirical). Real programs exhibit temporal locality (a referenced item is likely to be referenced again soon) and spatial locality (items near a referenced item are likely to be referenced soon). Caches work because of this, and it is a property of programs people write, not a law.

The cache-oblivious optimality theorem (Frigo, Leiserson, Prokop, Ramachandran, 1999). In the ideal-cache model with cache size $M$ and block size $B$, there exist algorithms that achieve asymptotically optimal cache complexity without knowing $M$ or $B$, and being optimal for one $(M,B)$ pair makes them optimal at every level of a multi-level hierarchy simultaneously.

The first two are observations. The third is proved.

Argument

Why the hierarchy is not going away. The gap is structural. Processor speeds improved roughly 50% per year for decades while DRAM latency improved about 7% per year, and the divergence — the “memory wall” — is why a modern core spends much of its time waiting. Even at the speed of light, 80 ns is about 24 metres of round trip, and a large fast memory cannot be physically close to the core everywhere at once. Caches are the physical consequence of the fact that capacity requires area and area requires distance.

The external-memory model, which is what replaces $O(1)$ access. Count cache misses, not operations. Memory moves in blocks of $B$ elements; the cache holds $M/B$ blocks. An algorithm’s cache complexity $Q(n; M, B)$ is the number of block transfers.

Scanning $n$ contiguous elements costs $Q = n/B$, because each block transfer brings $B$ useful elements. Following $n$ pointers in random order costs $Q = n$. That factor of $B$ — typically 8 to 16 for 8-byte elements in a 64-byte line — is most of your list-versus-vector measurement, with the rest coming from prefetching, which works only when the access pattern is predictable.

The lower bound for sorting in this model is

Notice what changed from the comparison-sort bound. $\Omega(n \log n)$ counts comparisons and is correct; this counts transfers, and the base of the logarithm is $M/B$ rather than 2. The two bounds do not conflict — they measure different resources, and which one predicts your runtime depends on whether your data fits in cache. That is the entire relationship between this post and the comparison-sort bound: the asymptotic count is real, and the constant is what you pay.

Matrix multiply, where the analysis is concrete. Multiply two $n \times n$ matrices with the naive triple loop, row-major layout, $n$ large enough that a row does not fit in cache. The inner loop walks $B$ down a column, and each access to $B[k][j]$ touches a new cache line. Cache complexity: $\Theta(n^3)$ misses.

Now tile it. Choose tile size $t$ with $3t^2 \le M$, so three tiles fit in cache at once, and multiply tile-by-tile. Each tile multiply costs $\Theta(t^2/B)$ misses to load and does $t^3$ work. There are $(n/t)^3$ tile multiplies, so

using $t = \Theta(\sqrt M)$. Compared with $\Theta(n^3)$, that is an improvement of $\Theta(B\sqrt M)$ — for $B = 8$ and $M = 32$ KB, a factor in the hundreds. Nothing about the arithmetic changed. The same multiplications happen in a different order. This bound is also optimal, by the Hong–Kung red-blue pebble argument.

The cache-oblivious trick. The tiled version needs $M$. That is a problem in practice: you must tune per machine, and a hierarchy has three or four different $M$ values so one tiling cannot be right for all of them.

Recursive divide-and-conquer solves both. Split each matrix into four quadrants and recurse:

multiply(A, B, C, n):
    if n small: base case
    else: split into quadrants, 8 recursive multiplies of size n/2

The recursion passes through every scale on its way down. At some level of the recursion the subproblem happens to fit in L1; at a higher level, one fits in L2; at a higher level still, one fits in L3. The algorithm never mentions any of these sizes and is optimal at all of them at once. Analysing the recurrence with the base case “subproblem fits in $M$” gives exactly $\Theta(n^3/(B\sqrt M))$ — matching the tuned tiled version.

That is the theorem half of this post, and it is a genuine surprise: knowing the cache parameters is worth only a constant factor, and one algorithm can be simultaneously optimal for a hierarchy it knows nothing about. Van Emde Boas layout for search trees and funnelsort for sorting are the other two canonical instances.

Reading the symptoms back off the model.

• List versus vector. Pointer chasing is $Q = n$; scanning is $Q = n/B$. The factor of 8 is the block size doing exactly what the model says.
• Loop interchange. ikj order makes the inner loop stride contiguously through both B and C; ijk strides through B by $n$. Same arithmetic, different $Q$ by a factor of $B$.
• Open addressing versus chaining. Chaining follows a pointer per probe; open addressing probes within the same cache line. A worse probe-count bound and a better transfer count, and the transfer count is what the clock measures.
• Struct-of-arrays versus array-of-structs. If you touch one field of a struct across many elements, AoS wastes most of every line. SoA is the same data with $Q$ divided by the ratio of struct size to field size, which is why every columnar database and every ECS game engine is laid out this way.

Forbids

Predicting runtime from operation counts alone. Two algorithms with identical $\Theta$ can differ by an order of magnitude, and the difference is not “constant factors” in the vague sense but a specific, computable transfer count.

Treating memory access as unit cost when the data exceeds cache. The RAM model is an approximation valid inside one level of the hierarchy and nowhere else.

Comparing data structures without their layout. A “linked list” and an “array” are the same abstract sequence and different physical objects, and the physical object is what runs.

Assuming an algorithm tuned for one machine’s cache is tuned for another’s. Unless it is cache-oblivious, in which case the theorem says it is.

Does not forbid

It does not make asymptotic analysis obsolete, and treating it as though it does is the most common over-correction. $\Theta$ still decides the outcome at scale: an $O(n^2)$ algorithm with perfect locality loses to $O(n \log n)$ with poor locality at large enough $n$, every time. “Cache-friendly bubble sort” is not a real position, and the honest statement is that constants decide when asymptotics tie, which at practical sizes is often.

It does not mean linked lists are always wrong. They win when you splice frequently, when elements are large, when you need stable references, or when the list is short enough to be resident anyway. The Linux kernel’s intrusive lists are correct engineering, not a locality mistake, because the objects are already in cache for other reasons and the alternative would require moving them.

It does not mean you must hand-tile. The cache-oblivious result exists precisely so that you do not: recursion gets you within a constant of tuned code, portably. FFTW’s runtime planner and BLIS’s tuned kernels are the opposite choice, and they win the last factor of two, which matters only when you are writing the library rather than using it.

It does not make big-O wrong about sorting. The $\Omega(n \log n)$ comparison bound is untouched. The external-memory bound counts a different resource, and both hold simultaneously.

It does not require you to know your cache sizes to benefit. Contiguity, struct packing, and recursive subdivision are all wins without a single measurement of $M$ or $B$.

Boundary

• The ideal-cache model assumes optimal replacement and full associativity. Real caches are set-associative with LRU approximations, which costs a constant factor and occasionally much more via conflict misses on power-of-two strides.
• Prefetchers change the game for predictable strides. A sequential access pattern may cost far less than $n/B$ latency even though it costs $n/B$ transfers, because the transfers overlap.
• NUMA adds a level the model does not name. Remote-socket DRAM is another factor of two, and it is a placement problem rather than a locality problem.
• Bandwidth, not latency, binds streaming workloads. The model counts transfers; when you are saturating DRAM bandwidth, the count is the cost, but when you are latency-bound, concurrency and memory-level parallelism decide.
• Multi-threaded sharing breaks the analysis. False sharing — two cores writing different variables in one line — is a cache effect with no analogue in the single-threaded model and can make a parallel program slower than serial.

The two things to keep separate: the hierarchy is an observation about how machines are built, and cache-obliviousness is a theorem about how to be optimal on all of them at once without asking which one you are on.

Read next