The Cache Hierarchy and Why Locality Decides Speed

Processor speed and DRAM speed improved at very different rates for decades. Wulf and McKee named the consequence in "Hitting the Memory Wall: Implications of the Obvious", ACM SIGARCH Computer Architecture News, volume 23, issue 1, pages 20 to 24, March 1995. Their argument was arithmetic rather than speculative: if two quantities both improve exponentially at different rates, the ratio between them grows without bound, so eventually memory access dominates all execution time regardless of how fast the processor is.

That is where we have arrived. A modern core can issue several arithmetic operations per cycle, and a single DRAM access costs it hundreds of cycles of potential work.

Caches do not make DRAM faster. They exploit a statistical property of real programs to make most accesses avoid DRAM entirely. When that property holds, the machine runs near its arithmetic limit. When it does not, none of the pipeline and out-of-order machinery from the previous two lessons can save it.

Caching only works because real programs are not random. Two empirical regularities carry the whole design.

• Temporal locality. A location accessed now is likely to be accessed again soon. Loop counters, the top of the stack, a hot lookup table.
• Spatial locality. A location accessed now makes nearby locations likely to be accessed soon. Array traversal, struct fields read together, sequential instruction fetch.

These are not laws. They are properties of how people write code, and code that violates them gets no benefit from any cache. A hash table probing random slots in a large array has almost no spatial locality by construction, which is precisely why hash lookups on big tables are slower than their O(1) complexity suggests.

That gap between complexity class and measured speed is the theme of this lesson. Asymptotic analysis counts operations and assumes each costs the same. On real hardware they differ by roughly a factor of sixty.

Abstract descriptions of "fast" and "slow" memory are less useful than measurements. These are from 7-cpu.com, which publishes measured latencies for an Intel i7-6700 (Skylake) at 4.0 GHz with dual-channel DDR4-2400 CL15:

The DRAM figure is expressed as the L3 latency plus a memory-side delay, because a DRAM access must miss all three caches first. At 4.0 GHz, 51 ns is about 204 cycles, giving roughly 246 cycles in total.

So the span from L1 to DRAM is about 60x. The same site measures an Intel i7-1065G7 (Ice Lake) at 5, 13 and 42 cycles for L1, L2 and L3, with RAM at 42 cycles plus 87 ns on LPDDR4-3733, so the shape is stable across generations even as capacities change.

Caches do not track individual bytes. They operate on fixed-size blocks called cache lines, and on every x86-64 part in the table above the line is 64 bytes.

This single fact has more practical consequences than any other in this cursus.

• Reading one byte transfers 64. A program that touches one byte per 64-byte region wastes 63/64 of its memory bandwidth.
• Sequential access is close to free after the first element. Walking an int32 array pulls 16 elements per line, so 15 of every 16 accesses hit a line already present.
• Alignment matters. A structure straddling a line boundary requires two line fetches instead of one.

The rule of thumb that follows: the cost of a memory access is dominated by how many distinct cache lines you touch, not how many bytes you read. Optimising memory-bound code almost always means reducing line count, not byte count.

Traverse a 2D array of 32-bit integers, stored row-major, in each of the two possible orders.

// Row-major: consecutive j are adjacent in memory.
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        sum += a[i][j];

// Column-major: consecutive i are N*4 bytes apart.
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        sum += a[i][j];

Both execute exactly N squared additions and are identical in complexity terms. Count cache lines instead, assuming a 64-byte line and N large enough that a full row exceeds the cache:

row-major   : 16 int32 per line -> 1 miss per 16 accesses
              N^2 / 16 line fetches
column-major: stride N*4 bytes  -> every access a new line
              N^2 line fetches       (16x more)

The second version fetches sixteen times as many lines to do the same arithmetic, and each fetched line has 15/16 of its contents discarded. This is the canonical demonstration that complexity analysis and running time are different questions.

A cache must decide where in its storage a given address may be placed. The design space runs between two extremes.

• Direct mapped. Each address has exactly one legal slot. Cheap and fast to look up, but two hot addresses that map to the same slot evict each other repeatedly even when the rest of the cache is empty.
• Fully associative. A line may go anywhere. Best hit rate, but every lookup must compare against every entry, which is impractical at size.

Real caches take the middle: N-way set associative. The address selects a set, and the line may occupy any of N ways within it. From the Skylake figures above, L1 data is 8-way, L2 is 4-way, and L3 is 16-way.

The practical hazard is conflict misses. If a loop touches several arrays whose addresses differ by exactly a large power of two, they can map to the same set and evict one another despite the cache being mostly idle. It is the classic cause of a program that slows down sharply when an array dimension is rounded up to a power of two.

Hill and Smith's three-way classification is still the fastest way to diagnose a memory problem, because each cause has a different remedy. Compulsory misses are unavoidable in principle but can be overlapped by prefetching. Capacity misses mean the working set is simply too large, and the fix is to restructure the algorithm to work on cache-sized chunks. Conflict misses mean the data fits but collides, and the fix is a layout change such as padding an array dimension away from a power of two.

Capacity misses are the one class you fix by changing the algorithm rather than the layout, and matrix multiply is the standard illustration.

The naive triple loop streams an entire row and an entire column per output element. For large matrices, by the time the code returns to a row it has been evicted, so nearly every access misses.

Blocking, also called tiling, splits the iteration space so the working set fits in cache:

for (int ii = 0; ii < N; ii += B)
  for (int jj = 0; jj < N; jj += B)
    for (int kk = 0; kk < N; kk += B)
      // multiply the B x B sub-blocks; three blocks
      // of B^2 elements each stay resident
      for (int i = ii; i < ii+B; i++)
        for (int j = jj; j < jj+B; j++)
          for (int k = kk; k < kk+B; k++)
            c[i][j] += a[i][k] * b[k][j];

Choose B so that three B-by-B blocks fit comfortably in L1 or L2. The arithmetic performed is identical, so the operation count and the complexity class do not change. Only the order changes, and with it the miss rate. This is the single most important optimisation technique for dense numerical code, and it is entirely about memory.

Coherence between cores also operates on whole lines, and that creates a failure mode with no equivalent in single-threaded code.

Two threads write to two different variables that happen to occupy the same 64-byte line. Logically they share nothing. But the coherence protocol tracks lines, so each write invalidates the other core's copy, and the line ping-pongs between cores on every access.

// Pathological: both counters in one line.
struct { long a; long b; } counters;

// Fixed: force them into separate lines.
struct {
    long a;
    char pad[64 - sizeof(long)];
    long b;
} counters;

The symptom is distinctive: a parallel program that gets slower as you add threads, with no lock contention to blame. The diagnosis is that sharing is happening at a granularity the source code does not express. Note this is a performance problem only. Correctness is unaffected, and the memory ordering rules that govern what threads may observe are a separate matter handled elsewhere in the catalogue.

The practical summary, in the order worth checking when code is slower than its operation count suggests:

• Count lines, not bytes. 64 bytes move whether you asked for one byte or all of them.
• Traverse in storage order. Row-major arrays walk by row. This single change is often worth an order of magnitude.
• Keep the working set in a level. Blocking converts capacity misses into hits without changing the arithmetic.
• Watch powers of two. Strides that are large powers of two invite conflict misses; padding a dimension by one element often fixes it outright.
• Pad shared-but-independent data. Anything written by different threads belongs in different lines.

What this lesson has not answered is when memory is the limit at all. Some code genuinely is arithmetic bound and none of the above matters for it. The next lesson gives the model that tells the two apart before you spend effort optimising the wrong one.