1.6 — The Memory Hierarchy

The 1.5 trace quietly cheated. It said the ALU gets 5 and 7 from registers instantly, and it does — but a real program's data lives in memory, and memory is agonizingly slow compared to the CPU. This single gap — the CPU can compute far faster than memory can feed it — is the most important performance fact in all of computing. It shapes how caches are built, why some code runs 10× faster than logically-identical code, and why "cache-friendly" is a phrase every serious engineer respects. This chapter builds the pyramid of storage that hides the gap.

1. The gap — why memory can't keep up

A modern CPU core executes an instruction in a fraction of a nanosecond. Reading from main memory (RAM) takes roughly 100 nanoseconds — hundreds of times longer. If the CPU had to wait for RAM on every access, it would spend nearly all its time idle, and that 3 GHz clock would be a lie. To feel the scale, here is the standard "latency numbers every engineer should know," rescaled so one CPU cycle = one second:

Access	Real latency	If 1 cycle = 1 second
CPU register	~0.3 ns	1 second
L1 cache	~1 ns	~3 seconds
L2 cache	~4 ns	~13 seconds
L3 cache	~15 ns	~50 seconds
Main memory (RAM)	~100 ns	~5 minutes
SSD (flash)	~100 µs	~4 days
Spinning hard disk	~10 ms	~1 year
Network round trip (same datacenter)	~0.5 ms	~2 weeks

Read that column again. To a CPU, waiting for RAM is like you waiting five minutes; waiting for a disk is like waiting a year. The entire architecture of memory exists to avoid these waits — and this table (you'll estimate with it again in Part 10.12) is why. The reason memory is slow isn't laziness; it's physics and economics: fast memory is expensive and physically large per bit, so you can't have much of it close to the core.

2. The pyramid — trading size for speed

The solution is a memory hierarchy: several layers of storage, each larger and slower than the one above, with the CPU keeping the data it's using now in the small fast layers and everything else in the big slow ones.

Figure 1 — The memory hierarchy. Each level down is ~10× larger and ~10× slower. The CPU works at the top; the machinery's whole job is to keep the data you need as high up as possible.

Two technologies underlie it. SRAM (static RAM) is fast but bulky — each bit is a little cross-coupled latch (the SR loop from 1.2, roughly six transistors) that holds its value as long as it has power. It's what caches are made of: fast, but you get few bits per square millimeter. DRAM (dynamic RAM) stores each bit as charge in a single tiny capacitor — one transistor, one capacitor — so it packs far more bits per area (cheap, dense), but the charge leaks away and must be refreshed thousands of times per second (hence "dynamic"), and it's slower. That trade — SRAM fast-and-small vs DRAM dense-and-slow — is exactly why the hierarchy has layers: caches are SRAM, main memory is DRAM.

3. The cache — betting on locality

Between the CPU and RAM sit the caches (L1, L2, L3 — Level 1 closest and smallest, L3 largest and shared between cores). A cache is a small, fast SRAM store that keeps copies of recently- and soon-to-be-used data. When the CPU needs an address, it checks the cache first: a cache hit (data present) is answered in a few cycles; a cache miss forces the slow trip to RAM. The whole performance game is maximizing hits.

Why does keeping "recently used" data even work? Because real programs exhibit locality of reference, in two flavors:

• Temporal locality: if you used an address, you'll likely use it again soon (a loop counter, a frequently-called function). So: keep recently-used data around.
• Spatial locality: if you used an address, you'll likely use nearby addresses soon (the next array element, the next struct field). So: when you fetch one byte, fetch its neighbors too.

Spatial locality is why caches don't store single bytes — they move data in fixed blocks called cache lines, typically 64 bytes. Touch one byte and its 63 neighbors come along for free. This one fact drives an enormous amount of real-world performance, as we're about to see.

4. Why "cache-friendly" code is faster — the same logic, 10× the speed

Here is the lesson that turns this chapter from theory into a raise. Consider summing every element of a large 2-D array (a grid of rows and columns) stored in row-major order — meaning each row's elements sit contiguously in memory, then the next row. Two loops, identical arithmetic:

// Version A — walk along rows (memory order)
for (int r = 0; r < N; r++)
    for (int c = 0; c < N; c++)
        total += grid[r][c];

// Version B — walk down columns (jumping across memory)
for (int c = 0; c < N; c++)
    for (int r = 0; r < N; r++)
        total += grid[r][c];

They compute the same sum. Version A can be several times faster. Why?

First, a piece of notation you'll need: big-O

You're about to see the phrase "same big-O." Big-O notation is the standard shorthand for how the running time of an algorithm grows as its input grows — deliberately ignoring constant factors and hardware, so it describes the shape of the growth, not the actual seconds.

Read O(n) as "order n": if you double the amount of data (n), the work roughly doubles — a straight-line relationship, like scanning every item in a list once. O(n^2) means doubling the data quadruples the work (e.g. comparing every item against every other item) — it grows painfully fast. O(\log n) means the work grows very slowly — doubling the data adds only one extra step (like repeatedly halving a search range); this is the "cheap" shape you want for large data. O(1) means constant — the work doesn't grow with the data at all (like reading one array element by its index, no matter how big the array).

The point of ignoring constants is to compare algorithms independently of machine speed: an O(n^2) algorithm will eventually lose to an O(n) one on large enough data, no matter how fast the computer. The catch — and it's exactly this chapter's lesson — is that "ignoring constants" hides the 100× difference between a cache hit and a cache miss. Chapter 4.1 develops big-O properly with the mathematics; this working definition is all you need here.

Version A walks memory sequentially: it touches grid[r][0], and because a 64-byte cache line loaded its neighbors, the next 15 or so elements (grid[r][1], [2], …) are already in cache — a burst of hits per single miss. Version B walks down a column, so consecutive accesses are N elements apart in memory — each one likely on a different cache line, so nearly every access is a cache miss and a slow trip to RAM. Same instructions, same big-O complexity — but A respects spatial locality and B fights it. The CPU didn't change; the memory access pattern did. This is why "know your data layout" is a performance superpower, and why contiguous data versus pointer-chasing — and iteration order — are not academic concerns; they can dominate runtime. (A pointer is simply a value that holds a memory address — it doesn't contain data, it tells you where the data lives, like a street address rather than the house. "Pointer-chasing" means the data is scattered and each item stores the address of the next, so you must fetch one item to learn where the next one is — the classic linked list, built properly in Chapter 4.7. Since each address is unpredictable, the cache can't prefetch ahead, and every hop risks a miss.)

5. Coherence — when cores disagree (MESI)

One more wrinkle, and it's the seed of an entire field. Modern CPUs have multiple cores, each with its own L1/L2 cache. Now imagine core 1 and core 2 both cache the same variable x = 5. Core 1 changes it to 6 in its own cache. Core 2's cache still says 5. They disagree about reality — a cache coherence problem — and if unmanaged, one core would compute with stale data.

Hardware solves this with a coherence protocol, the classic being MESI, which tags every cache line with one of four states — Modified (I changed it, I'm the only owner), Exclusive (only I have it, unchanged), Shared (several caches have identical copies), Invalid (my copy is stale, don't use it). The cores snoop on each other: when core 1 writes x, it broadcasts that intent, and core 2's copy is marked Invalid, forcing it to re-fetch the fresh value. This keeps the caches consistent automatically — but at a cost: that coordination traffic is real, and when many cores hammer the same cache line, they can grind each other to a halt (false sharing — two unrelated variables that happen to share one 64-byte line, ping-ponging between cores).

Sit with what just happened: two agents, each with a local copy of shared data, must agree on the truth as it changes. That is exactly the problem distributed systems face across machines in Part 10 — replication, consistency, invalidation. The CPU solves it in hardware across millimeters; a distributed database solves the same puzzle in software across continents. The vocabulary you're learning here — shared vs exclusive, invalidation, staleness — is the same vocabulary you'll use to reason about a globally-replicated database. Same problem, different scale.

6. The expert lens

Big-O isn't the whole story; the constant hidden in "one memory access" varies 1000×. Two algorithms with identical asymptotic complexity can differ enormously in practice because one is cache-friendly and the other isn't. An O(n) scan of a contiguous array routinely beats an O(n) walk of a pointer-linked structure of the same length, because the array streams through cache lines while the linked list chases pointers to random addresses, missing constantly. This is why, for modern hardware, a std::vector/ArrayList often outperforms a linked list even for operations the linked list is "supposed" to win — the constant factor from locality dominates. Never reason about performance from big-O alone; reason about memory access patterns.

The hierarchy is fractal — the same idea repeats at every scale. CPU cache hides RAM latency; RAM (as a page cache) hides disk latency; a Redis cache (Part 7) hides database latency; a CDN (Part 13) hides origin-server latency across the planet. Every one is the same pattern — a small fast layer holding hot data in front of a big slow layer, betting on locality, and facing the same hard question: invalidation (when is the cached copy stale?). Phil Karlton's famous quip, "there are only two hard things in computer science: cache invalidation and naming things," is about this, and it will haunt you from L1 to global CDNs.

Mechanical sympathy. The best performance engineers have what's called mechanical sympathy — they write code aware of how the machine underneath actually behaves: they keep hot data small and contiguous, iterate in memory order, and avoid pointer-chasing in tight loops. They're not micro-optimizing blindly; they're respecting the hierarchy you just learned. You now have the model to join them.

Next chapter: we've built the machine from physics up — switches, gates, memory, the CPU, the storage that feeds it. 1.7 rises from how machines compute to what can be computed at all — the theory of computation, the limits no faster chip can ever break.

Recall

• The CPU is hundreds of times faster than main memory; hiding that gap is the central performance problem. Latency scales dramatically — to a CPU, RAM ≈ 5 minutes, disk ≈ 1 year (rescaled).
• The memory hierarchy stacks registers → L1/L2/L3 cache (SRAM, fast/small) → RAM (DRAM, dense/slow) → disk, each ~10× bigger and slower.
• Caches work because of locality: temporal (reuse soon) and spatial (neighbors soon). Data moves in 64-byte cache lines, so touching one byte prefetches its neighbors.
• Iterating in memory order (respecting spatial locality) can be several× faster than logically-identical code that jumps across memory — access pattern dominates, not big-O alone.
• Multi-core caches can disagree; MESI (Modified/Exclusive/Shared/Invalid) keeps them coherent via invalidation — the same shared-data problem distributed systems face across machines (Part 10).

Self-test: Why is there a hierarchy instead of one big fast memory? What are the two kinds of locality? Why can column-order and row-order iteration of the same array differ several-fold in speed? What problem does MESI solve, and where does that same problem reappear at larger scale?

Quiz Bank

FoundationalWhy do computers use a memory hierarchy instead of one large, fast memory?

Because fast memory (SRAM) is expensive and physically large per bit, so you can only afford a little of it near the core, while cheap dense memory (DRAM) and storage are slower. A memory hierarchy gives the illusion of large-and-fast: keep the data in active use in the small fast layers (caches) and everything else in the big slow layers, exploiting locality so most accesses hit the fast layers.

FoundationalWhat is the difference between SRAM and DRAM, and where is each used?

SRAM stores each bit in a ~6-transistor latch — fast and stable while powered, but low density and costly; used for CPU caches. DRAM stores each bit as charge on a single tiny capacitor (one transistor) — very dense and cheap, but the charge leaks so it must be periodically refreshed, and it's slower; used for main memory (RAM). The density-vs-speed trade is exactly why the hierarchy has layers.

AppliedWhat are temporal and spatial locality, and how does the cache exploit each?

Temporal locality: recently accessed data is likely accessed again soon — the cache exploits it by keeping recently-used data. Spatial locality: data near a recent access is likely accessed soon — the cache exploits it by fetching a whole cache line (typically 64 bytes) at once, so neighbors come pre-loaded. Programs have locality because of loops, sequential data structures, and struct field access — which is why caching works at all.

AppliedWhy can iterating a 2-D array row-by-row be much faster than column-by-column, given identical work?

For a row-major array, row elements are contiguous in memory. Row-order iteration accesses sequential addresses, so each 64-byte cache line fetch serves many subsequent accesses (mostly hits) — it respects spatial locality. Column-order iteration jumps N elements between accesses, landing on a different cache line almost every time (mostly misses, each a slow RAM trip). Same instructions and same big-O, but the memory access pattern differs, and misses dominate runtime.

InterviewWhat is cache coherence, and what does MESI do?

In a multi-core CPU each core has private caches, so the same memory address can be cached in several places; if one core writes it, the others hold stale copies — the cache coherence problem. MESI tags each cache line Modified / Exclusive / Shared / Invalid and has cores snoop each other's memory traffic: a write invalidates other copies (→ Invalid), forcing a re-fetch of fresh data. This keeps caches consistent automatically, at the cost of coordination traffic (and pitfalls like false sharing).

InterviewWhy might an array outperform a linked list even for a simple traversal, despite both being O(n)?

Big-O ignores the constant factor, and here it's dominated by locality. An array is contiguous, so traversal streams through cache lines with mostly hits (great spatial locality). A linked list scatters nodes across memory, so each next pointer chases a likely-uncached address — a cache miss per node, each ~100× slower than a hit. So the array's traversal has a far smaller constant, often winning decisively on real hardware. Lesson: reason about memory access patterns, not just asymptotic complexity.

StaffA hot multithreaded counter array shows terrible scaling — adding cores makes it slower. Using this chapter, name the likely cause and the fix.

Likely false sharing. If each thread updates its own counter but several counters sit within the same 64-byte cache line, then every write by any thread marks that whole line Modified and Invalidates it in all other cores' caches (MESI), so the line ping-pongs between cores' caches on every update — coherence traffic serializes what should be independent work, and more cores make it worse. Fix: pad/align each thread's counter to its own cache line (e.g. 64-byte alignment) so unrelated counters no longer share a line; or aggregate per-thread locals and combine at the end. The general principle: on multicore, what memory layout shares a cache line is a correctness-adjacent performance concern.

Flashcards

FlashApprox latency: L1 vs RAM vs disk

L1 ~1 ns, RAM ~100 ns, SSD ~100 µs, spinning disk ~10 ms. (Rescaled: RAM ≈ 5 min, disk ≈ 1 year.)

FlashSRAM vs DRAM

SRAM: fast, ~6 transistors/bit, used for caches. DRAM: dense/cheap, 1 transistor + capacitor, needs refresh, used for main memory.

FlashTwo kinds of locality

Temporal (reuse the same data soon) and spatial (use nearby data soon).

FlashCache line size and why it matters

Typically 64 bytes; touching one byte loads its neighbors, exploiting spatial locality.

FlashMESI states

Modified, Exclusive, Shared, Invalid — cache-line states keeping multi-core caches coherent.

FlashThe two hard problems (Karlton)

Cache invalidation and naming things — invalidation recurs at every layer from L1 to CDNs.

Scenario Drill

DrillA service reads user profiles from a database on every request and is slow under load. You add a Redis cache in front. Map every decision you now face back to concepts from this chapter.

Adding Redis is building another level of the memory hierarchy: a small fast layer (cache) in front of a big slow one (database), betting on locality — hot profiles get re-requested (temporal locality), so most reads become cache hits and skip the slow DB trip, exactly as L1 sits in front of RAM. The decisions mirror the hardware ones: (1) hit rate is everything — if requests don't have locality, the cache just adds a hop; (2) eviction — the cache is smaller than the DB, so you need a replacement policy (LRU echoes "keep recently used," i.e. temporal locality); (3) invalidation — the hardest part, identical to MESI's job: when a profile is updated in the DB, the cached copy is now stale (the "Invalid" state), so you must invalidate or expire it, or serve wrong data; (4) coherence across instances — multiple app servers with their own local caches face the multi-core disagreement problem at datacenter scale. The whole design is the L1↔RAM relationship, re-implemented in software one level up — which is why understanding the CPU cache makes you better at system design (Parts 7 and 10 formalize this).