Memory hierarchy & caches

Scope: the module overview already introduced the latency ladder and the idea of locality in brief. This page goes one layer deeper on the mechanics underneath those numbers: what a cache line actually is, the three flavors of locality and why each pays off, and how the hardware prefetcher rides a predictable access pattern. It also covers the TLB — the extra, often-forgotten level of the hierarchy that caches address translation rather than data.

TL;DR — in 30 seconds:

• Caches move data in 64-byte cache lines, not single values — the entire reason spatial, sequential, and temporal locality all pay off.
• Each step down the hierarchy (registers→L1→L2→L3→RAM) is roughly 3–5× slower; a full RAM miss costs on the order of 500 instructions' worth of time.
• The TLB caches where things are (address translation), not what they are — a scattered, pointer-chasing structure stacks a page-walk penalty on top of the cache-miss penalty.

1. The ladder, and why each step is roughly an order of magnitude

Every level of the memory hierarchy is smaller and faster than the one below it. Each step down is roughly 3–5× slower than the step above — registers are effectively free, and a full miss all the way out to main memory costs on the order of 500 instructions' worth of time:

Level	Approx. latency	Note
Registers	~1 ns	effectively free
L1 cache	~1 ns	per-core, smallest and fastest cache
L2 cache	~4 ns	per-core or per-core-pair, larger, still fast
L3 cache	~15 ns	shared across cores on the chip
Main memory (RAM)	~65–100 ns	one full miss ≈ 500 instructions' worth of time
Disk / SSD	far slower still	not shown to scale below — orders of magnitude beyond RAM

flowchart TB
  R["Registers · ~1 ns"] --> L1["L1 · ~1 ns"]
  L1 --> L2["L2 · ~4 ns"]
  L2 --> L3["L3 · ~15 ns"]
  L3 --> RAM["RAM · ~65-100 ns<br/>one full miss ~ 500 instructions"]
  RAM --> DISK["Disk / SSD<br/>orders of magnitude slower again"]

These are the canonical order-of-magnitude figures — see "Latency Numbers Every Programmer Should Know" for the full reference table.

CPU compute speed has outpaced memory-latency improvements for decades — bandwidth kept climbing, but latency barely moved — so the entire cache hierarchy exists purely to hide that gap. This is why a cache-friendly algorithm with a worse Big-O can still beat a cache-hostile one with a better Big-O in practice: the constant factor hiding inside "one memory access" is not constant at all — it depends entirely on which level of the ladder actually answers it.

2. The cache line: memory moves in blocks, not values

Caches don't fetch a single byte or a single variable — they fetch a fixed-size block called a cache line, commonly 64 bytes on mainstream CPUs. Ask for one int, and the hardware pulls in that int plus its neighboring 60-odd bytes, whether you asked for them or not.

This has two consequences that shape everything else in this module:

• Reading one field from a struct is effectively free if a related field sits on the same line — it arrived already.
• Reading one field is not free if an unrelated field two threads both write to sits on that same line — that's the setup for false sharing, covered on the multicore page.

The cache line, not the variable, is the real unit of cost. A data structure's layout — how tightly its frequently-accessed fields pack onto shared lines — matters as much as its algorithmic complexity.

3. Locality: three flavors, one payoff

"Locality" is the umbrella term for access patterns a cache can exploit. There are three distinct flavors, and each earns its speedup a different way:

Flavor	What it means	Why it's fast
Temporal locality	You'll touch this same data again soon	It's still sitting in a fast cache level from last time — no re-fetch needed
Spatial locality	You'll touch data near this address soon	It rode along on the same cache line as something you already fetched
Sequential / striding locality	Your accesses step through memory in a predictable pattern	The hardware prefetcher can see the pattern and start fetching ahead of you (see below)

A contiguous structure — an array, an open-addressing hash table — hands the cache all three for free when you scan it: near-future elements are already loaded (spatial), the scan pattern is predictable (sequential), and hot elements get revisited from cache (temporal).

A pointer-chasing structure — a linked list, a chained hash map — gets none of them: each next pointer can land anywhere in the heap, so every hop is a fresh, unpredictable fetch. A random walk across a large heap uses roughly one word out of an entire 64-byte line before jumping away, wasting most of what the cache line delivered — which is why linear, contiguous access can outperform an equivalent pointer-chasing traversal by a wide margin on otherwise identical work.

4. The hardware prefetcher: getting ahead of a predictable pattern

Modern CPUs include a hardware prefetcher that watches recent memory accesses and, when it detects a sequential or fixed-stride pattern, speculatively loads the next cache lines before the program asks for them. By the time your loop's next iteration requests that data, it may already be sitting in L1 or L2 rather than waiting on a trip to RAM.

The prefetcher is why sequential/striding locality is its own category rather than just "spatial locality, sort of" — spatial locality is about what's already nearby; prefetching is the hardware actively predicting what you'll want next and racing to have it ready. A predictable stride (every 8th element, every row of a matrix) is prefetcher-friendly; a random-index access pattern gives the prefetcher nothing to predict, so every access pays the full latency the ladder above shows.

5. The TLB: caching where things are, not what they are

Every memory access a program makes uses a virtual address, which the CPU must translate to a physical address before it can actually fetch anything. That translation is itself a lookup — normally walking a multi-level page table in memory — so the CPU keeps a small, very fast cache of recent translations called the Translation Lookaside Buffer (TLB).

A TLB hit means the translation is already known and the access proceeds at full speed. A TLB miss means the CPU has to fall back to a page walk — one or more extra memory accesses just to find out where the data you actually wanted even lives, before it can fetch it. A pointer-chasing traversal across a large heap is doubly punished: it already defeats data-cache locality (§3), and because it touches so many distinct memory pages, it defeats the TLB too, stacking a page-walk penalty on top of the cache-miss penalty.

flowchart LR
  V["Virtual address<br/>(what your code uses)"] --> TLB{"In TLB?"}
  TLB -->|hit| P["Physical address<br/>— fetch proceeds"]
  TLB -->|miss| WALK["Page walk<br/>(extra memory access(es)<br/>to find the mapping)"]
  WALK --> P

This is the hierarchy's easy-to-forget extra dimension: the ladder in §1 caches data; the TLB caches addresses. A layout that's cache-friendly for data can still suffer if it's spread across far more distinct memory pages than it needs to be.

6. How this connects

• This extends the module overview's five-part mental model — §1 here is the same latency ladder, §3–§4 fill in why locality works instead of just stating that it does, and §5 adds the TLB dimension the overview didn't have room for.
• Cache lines (§2) are the exact mechanism the multicore page's false sharing section depends on — two unrelated variables landing on one line is only a problem because the cache moves data by the line, not the variable.
• Contiguous-vs-pointer-chasing (§3) is the concrete, checkable version of the module's exercise: estimate the relative cost of walking a large linked list versus an equivalent array using this ladder.

Common gotchas

• Judging performance by Big-O alone. Fix: also weigh cache-friendliness — a cache-hostile O(log n) lookup can lose to a cache-friendly O(n) scan, since a single miss costs roughly 500 instructions' worth of time.
• Forgetting the TLB when reasoning about pointer-chasing structures. Fix: remember a scattered traversal pays two separate penalties — a cache miss and, because it spans many distinct memory pages, a page-walk penalty from the TLB.
• Treating spatial and sequential/striding locality as the same thing. Fix: spatial locality is about what's already nearby on the same line; sequential/striding locality is specifically what lets the hardware prefetcher predict and preload ahead — a random-but-nearby pattern gets one but not the other.

Check yourself — why is reading one struct field sometimes 'free', depending on which field you touch first?

Because the cache fetches the whole 64-byte line containing that field, not just the field itself — a related field on the same line arrives as a side effect of that fetch, regardless of access order.

Check yourself — a traversal touches thousands of scattered heap addresses. What two separate penalties does it pay, beyond the raw cache misses?

It defeats the hardware prefetcher (no predictable stride to follow), and because it spans many distinct memory pages, it also defeats the TLB — stacking a page-walk penalty on top of the cache-miss penalty.

You can defend this when you can state the latency ladder in order and say roughly how much slower each step is than the one above it; explain why a cache fetches a whole 64-byte line instead of one value, and what that implies for struct layout; name the three flavors of locality and give a concrete data-structure example of each; and explain what a TLB miss costs beyond the data-cache miss it usually travels with.