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 understand this, we need to know what a cycle actually is. Deep inside the CPU is a tiny electronic metronome ticking constantly, sending a pulse of electricity through the wires. This tick is the clock, and the time between one tick and the next is a single cycle. Every time the clock ticks, the CPU takes one tiny step forward in its work — like fetching an instruction, decoding it, or executing it. When you buy a 3 GHz processor, that means the clock ticks three billion times every single second. Every single action the computer takes is perfectly synchronized to this relentless heartbeat. 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 one is MESI, which labels every cache line with one of four states:

• Modified: I changed it, and I am the only owner.
• Exclusive: only I have it, and it is unchanged.
• Shared: several caches have identical copies.
• Invalid: my copy is out of date, so do not 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).

To see this in action, imagine two cores running a program. Core 1 reads x. It pulls the 64-byte cache line containing x from RAM. Since no one else has it, the line is marked Exclusive. Then, Core 2 reads x. Core 1 snoops this request and downgrades its own line to Shared, while Core 2 also gets a Shared copy. Now, Core 1 needs to change x to 6. Before it can write, it broadcasts an invalidation message. Core 2 hears this and marks its copy Invalid. Core 1 changes its state to Modified and writes the new value into its own cache. Later, when Core 2 tries to read x again, it sees its copy is Invalid, so it asks for the fresh data. Core 1 intercepts this request, pauses its own work, sends the fresh data to Core 2, and both go back to Shared. The truth is protected, but the conversation took time.

This conversation reveals a trap called false sharing. Remember that caches do not track individual variables; they track 64-byte cache lines. Imagine you have two separate variables sitting next to each other in memory: hits and misses. They are small enough to fit inside the exact same cache line.

Figure 2 — False sharing. Core 1 only cares about hits, and Core 2 only cares about misses. Because both variables sit in the same cache line, the hardware treats them as a single shared block of data.

Now, Core 1 runs a loop that constantly updates hits, and Core 2 runs a loop that constantly updates misses. They are working on completely unrelated data. But because hits and misses live in the same cache line, the hardware thinks they are sharing data. When Core 1 changes hits, MESI forces the entire cache line in Core 2 to become Invalid. Core 2 must now wait to fetch the fresh line from Core 1 just so it can update misses. When Core 2 updates misses, it invalidates Core 1's copy. The single cache line bounces violently back and forth between the two cores. This ping-pong effect brings both fast cores to a crawl, waiting on memory traffic for data they aren't even sharing. The software is logically correct, but the hardware is fighting itself.

The solution to false sharing is simple once you know how the cache works: separate the variables. You pad the data structure so that hits and misses sit in different cache lines. For example, you can insert 64 bytes of empty, unused space between them. When you do this, hits gets its own cache line, and misses gets its own cache line. Core 1 and Core 2 can now modify their respective cache lines in the Modified state forever, with zero invalidations and zero waiting.

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.

This happens because standard numbers are tiny. A normal integer is just 4 bytes, meaning 16 independent counters will pack perfectly into a single 64-byte cache line. If you give one counter to each of 16 different cores, all 16 processors are now fighting for ownership of that exact same cache line. When Core 1 updates its counter, it sends an invalidation message to the other 15 cores, forcing them to drop their copies. A fraction of a second later, Core 2 updates its counter and does the exact same thing to Core 1.

The cores spend their time shouting invalidation messages across the chip instead of doing math. The work happens one by one, serialized by the hardware. This is why adding more cores makes the program slower — you are just adding more voices to the argument.

The padding fix simply forces them apart. You change the data structure so each 4-byte counter is followed by 60 bytes of empty, unused dummy space. Now, each counter is physically 64 bytes wide. Counter 0 gets its own cache line, and Counter 1 gets the next one. Core 1 and Core 2 can now each claim their own private cache line in the Modified state and update it forever, with zero invalidation traffic and no waiting.

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 are the same as in the hardware:

1. Hit rate is everything. If requests do not repeat, the cache just adds an extra step.
2. Eviction. The cache is smaller than the database, so you need a rule for what to throw out. LRU, "keep what was used recently", is the same idea as temporal locality.
3. Invalidation, the hardest part. It is exactly MESI's job. When a profile changes in the database, the cached copy is now stale, like the "Invalid" state. So you must remove it or let it expire, or you will serve wrong data.
4. Keeping several servers in agreement. If each app server has its own local cache, they face the same disagreement problem as CPU cores, at the size of a datacenter.

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).