Caches and the Memory Hierarchy

1. What is it?#

A hierarchy of progressively larger and slower memories, arranged so that frequently used data sits close to the compute units.

             size          latency      bandwidth
Registers    ~1 KB/core    0 cycles     enormous
L1 cache     32-48 KB      4-5 cyc      ~1 TB/s per core
L2 cache     1-2 MB        12-20 cyc    ~500 GB/s
L3 cache     32-320 MB     40-70 cyc    ~200 GB/s (shared)
DRAM         128 GB-2 TB   200-400 cyc  ~300-500 GB/s (whole socket)
NVMe SSD     1-100 TB      ~100 µs      ~3-14 GB/s
Network      ∞             ~100 µs-ms   1-400 Gb/s

Each level is roughly 10x bigger and 5-10x slower. The same structure appears on the GPU (registers → shared memory → L2 → HBM), and understanding it on the CPU makes the GPU version obvious.

2. Why does it exist?#

Because fast memory is expensive and physically small, and slow memory is cheap and large. A cache is a bet that programs exhibit locality:

• Temporal locality: if you used it, you’ll use it again soon.
• Spatial locality: if you used address X, you’ll use X+1 soon.

Both bets pay off for most code. They pay off spectacularly for tiled matrix multiplication and catastrophically badly for random access into a 100 GB embedding table.

3. Simple analogy#

Your desk, your bookshelf, the library, the national archive.

Desk (L1): three books, instant access. Bookshelf (L2/L3): fifty books, a few seconds. Library (DRAM): everything, a twenty-minute walk. Archive (disk): a day’s wait.

The trick to working fast is not walking faster; it is arranging your work so that what you need next is already on the desk. That rearrangement — tiling, blocking, changing data layout — is the whole of cache optimization.

4. Tiny example#

Row-major vs column-major traversal — the canonical demonstration:

// cache.go — touch every element of the same matrix along rows, then down columns.
package main

import (
	"fmt"
	"time"
)

func main() {
	const N = 8000
	A := make([]float32, N*N) // row-major: element (i, j) lives at A[i*N+j]
	for i := range A {
		A[i] = 1
	}

	t0 := time.Now()
	for i := 0; i < N; i++ {
		for j := 0; j < N; j++ {
			A[i*N+j] += 1 // walks along a row: CONTIGUOUS
		}
	}
	row := time.Since(t0)

	t0 = time.Now()
	for j := 0; j < N; j++ {
		for i := 0; i < N; i++ {
			A[i*N+j] += 1 // walks down a column: STRIDE = N*4 bytes
		}
	}
	col := time.Since(t0)

	fmt.Printf("row %v   col %v   ratio %.1fx\n",
		row.Round(time.Millisecond), col.Round(time.Millisecond), float64(col)/float64(row))
}

Typical: columns are 3-10x slower. Why?

Cache line = 64 bytes = 16 floats.

Row traversal:   read A[i,0] → the line brings A[i,0..15] → next 15 reads are FREE
                 useful bytes per line: 64/64 = 100%

Column traversal: read A[0,j] → the line brings A[0,j..j+15], of which you use 4 bytes
                  next read A[1,j] is 32 KB away → different line, likely a miss
                  useful bytes per line: 4/64 = 6.25%

You are moving 16x more memory than you need. No amount of CPU speed fixes that.

Direct relevance to inference: this is exactly why tensor layout matters (Section IV.07), why a stray .transpose() before a kernel can cost you dearly, and why KV cache layout ([batch, head, seq, dim] vs [batch, seq, head, dim]) is a real engineering decision.

5. Technical explanation#

Cache lines and associativity#

Memory moves in cache lines of 64 bytes (128 on some ARM). You never load one byte; you load a line.

Caches are set-associative: an address maps to a set (determined by middle address bits) and can live in any of N ways within it. L1 is typically 8-way, L2 16-way, L3 12-16 way.

Failure mode worth knowing: conflict misses. If your stride happens to be a multiple of (sets × line_size), every access maps to the same set and you thrash an 8-way cache with 9 streams. Symptom: performance collapses at power-of-two array dimensions. Fix: pad your leading dimension (e.g. allocate a [N][N+8] array). This is why library GEMMs pad and why hidden sizes in models are sometimes offset from powers of two.

The three C’s of cache misses#

Compulsory  first-ever access to the data. Unavoidable (but prefetchable).
Capacity    the working set exceeds cache size. Fix: tile/block.
Conflict    too many streams map to the same set. Fix: pad, change layout.

Prefetching#

Hardware detects sequential and constant-stride patterns and fetches ahead. It handles:

• forward/backward sequential — yes
• constant stride within a page — usually
• pointer chasing (linked lists, trees) — no
• random access — no

Implication for inference: array-of-structs traversal and hash lookups defeat the prefetcher. Tokenizer trie lookups and embedding gathers are inherently prefetch-hostile, which is why they cost far more than their instruction count suggests.

Tiling — the fundamental technique#

Naive matmul on an N×N problem reads B’s columns repeatedly:

for i in range(N):
  for j in range(N):
    for k in range(N):
      C[i][j] += A[i][k] * B[k][j]

B is re-read N times → N³ memory accesses for N³ FLOPs → intensity ~0.25

Tiled matmul:

for ii in range(0, N, T):
  for jj in range(0, N, T):
    for kk in range(0, N, T):
      # 3 T×T tiles fit in cache; do T³ FLOPs on 3T² bytes
      multiply_tile(A[ii:ii+T, kk:kk+T], B[kk:kk+T, jj:jj+T], C[ii:ii+T, jj:jj+T])

intensity ≈ T/6 — increases linearly with tile size

Choose T so that 3·T²·bytes ≤ cache_size. For 32 KB L1 and FP32: T ≈ 52, so T=48 or 32.

This exact idea, one level down, is FlashAttention. Tiles in GPU shared memory instead of CPU L1; the same arithmetic-intensity argument; the same payoff. If you understand this example, Section VII.10 will feel inevitable rather than clever.

6. Under the hood#

Measuring cache behavior:

perf stat -e L1-dcache-loads,L1-dcache-load-misses,\
LLC-loads,LLC-load-misses,cycle_activity.stalls_l3_miss ./your_program

Interpreting:

• L1 miss rate > 10% → poor spatial locality; check layout and stride.
• LLC miss rate > 30% with high LLC-loads → working set exceeds L3; you’re DRAM-bound.
• stalls_l3_miss a large fraction of cycles → definitively memory-bound.

A quick, portable proxy is the pointer-chase latency test: allocate arrays of increasing size, chase a random permutation of pointers, and plot ns/access vs size. You will see clear plateaus at each cache level — that plot is your machine’s memory hierarchy, measured.

7. Performance implications#

For inference specifically:

8. Production implications#

• Layout decisions are performance decisions. Choose KV cache layout to make the attention kernel’s access pattern contiguous (Section V.10).
• Struct-of-arrays beats array-of-structs for anything you iterate over in the hot path (scheduler request lists, block tables).
• Watch for power-of-two conflict misses when you pick tile or block sizes.
• Huge pages reduce TLB pressure for large model buffers — see file 06.
• Keep the scheduler’s data structures small and flat. At batch 256 with per-step bookkeeping, a dictionary of Python objects per sequence is measurable.

9. Common mistakes#

Optimizing arithmetic while ignoring layout. A “faster” algorithm with worse locality is slower.

Assuming the compiler tiles for you. It sometimes does; for anything nontrivial, it doesn’t. Use a library (BLAS, oneDNN) rather than hand-rolling.

Using power-of-two leading dimensions without thinking. Pad if you see conflict misses.

Ignoring cache when choosing batch shapes on CPU. A batch that overflows L2 per-thread is much slower per item.

Believing cache misses are the only memory issue. TLB misses (file 06) and NUMA (file 03) are separate and equally capable of halving your performance.

10. Hands-on exercise#

A. Measure your hierarchy. Write the pointer-chase benchmark: for sizes from 4 KB to 512 MB, chase a random permutation and report ns/access. Plot on a log-x axis. Identify L1, L2, L3, and DRAM plateaus. Compare to lscpu. Save to numbers.md.

B. Row vs column. Run the example in section 4 with N = 1000, 4000, 8000 and 16384. Explain why the ratio changes with size, and why a power of two is the worst case.

C. Tiling. Implement naive and tiled matmul in C (or Numba) for N=1024. Sweep tile size T ∈ {8,16,32,48,64,128}. Plot GFLOP/s vs T. Where is the peak and does it match your L1 size?

D. Conflict misses. Time a matmul with leading dimension 1024 vs 1032. Explain any difference using perf stat.

11. Interview questions#

1. What is a cache line, and why does traversal order change performance by 10x?
2. Explain the three C’s of cache misses and the fix for each.
3. What is tiling, and how does it change arithmetic intensity? Derive the relationship.
4. How is FlashAttention the same idea as cache tiling?
5. Which parts of an LLM serving stack are cache-hostile, and why?
6. What is a conflict miss and how do you diagnose one?

12. Further reading#

• [FUNDAMENTAL] Drepper, “What Every Programmer Should Know About Memory,” parts 2-3, 5
• [FUNDAMENTAL] Hennessy & Patterson, Appendix B
• [ESTABLISHED] Goto & van de Geijn, “Anatomy of High-Performance Matrix Multiplication” (2008)
• Next: 03 — RAM, DRAM, and NUMA