The Memory Hierarchy
One big fast memory is not buildable at a price anyone would pay, so machines are built as a stack of progressively larger, slower, cheaper memories that pretend to be one. The gaps between the levels are enormous, and nothing in your source code tells you which level you just hit.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
Why not just build one big fast memory?
Because speed, capacity and cost pull against each other in the physical design. Fast storage is built from more transistors per bit, sits physically closer to the execution units, and is wired for low latency rather than density. All three of those make it expensive per byte and limit how much of it can fit near the core. Slow storage inverts every one of those trade-offs.
The engineering answer is not to pick a point on that curve but to have all of them at once, arranged so that the small fast ones hold whatever is being used right now. That only works because real programs are not random: they reuse the same data and they touch neighbouring addresses, which is exactly what Spatial Locality and Temporal Locality name. A hierarchy is a bet on that regularity, and it is a bet that pays off for most code and fails badly for some.
The scale below is the single most useful picture in this domain. Read it as ratios, not times. The absolute numbers depend on the chip, the clock, the memory controller, the DIMM and the load on the machine — but the *shape*, and the fact that each step down costs several times the one above, holds broadly across machines you are likely to meet.
The ratios transfer; the numbers do not
It is tempting to memorise a table of nanoseconds. Resist it. Cache sizes, cache latencies and DRAM timings differ between vendors, between generations from the same vendor, between a laptop part and a server part, and between an idle machine and a loaded one. A number you memorise is a number that will be wrong on the next machine you touch.
What does transfer is the structure: there are several levels, each is several times slower than the one above, the last-level cache is usually shared while L1 is not, and leaving the chip for DRAM is a step change rather than an increment. Those facts let you reason correctly about a machine you have never measured — and then you measure, because §224 applies to you as much as to this page.
The table below is the honest version of "what should I actually assume". Note how little is safely universal. This is why the lessons in this module talk about mechanisms and ratios and hand you to The CPU Counts Itself for the specifics of your machine.
| Property | Safe to assume | Must be measured |
|---|---|---|
| Number of cache levels | At least two; commonly three | Whether there is an L4 or an on-package memory tier |
| L1 sharing | Private to a core (often split instruction/data) | Whether sibling hardware threads share it — they usually do |
| Last-level sharing | Usually shared across some group of cores | Which cores share which slice, and how that maps to NUMA: Not All Memory Is Equally Far nodes |
| Relative gaps | Each level costs several times the one above | The actual multipliers on your part |
| Line size | One fixed size per level, typically 64 bytes today | The real value — read it from the OS rather than assuming |
| Replacement policy | Something approximating recency | Nothing. Vendors do not document it; see Cache Replacement: LRU Is the Idea, Not the Implementation |
Where the hierarchy shows up in ordinary code
You do not need to write unusual code to be affected by this. The two loops below perform the same number of additions on the same data, and differ only in the order they visit it. On a row-major array the first walks memory in order; the second strides across it, taking a fresh line for nearly every element and reusing almost nothing.
The instruction counts are effectively identical. The runtimes are not, and the gap widens as the array grows past each cache level — which is the tell that you are looking at a memory effect and not an arithmetic one. That widening is worth internalising: a memory problem gets *relatively worse* with size, while a compute problem scales smoothly.
The point is not that you should always traverse in row order. It is that "same operations, same count" stopped being a sufficient argument the moment the hierarchy existed. When two implementations with equal complexity perform differently, the memory hierarchy is the first place to look, and Busy Is Not the Same as Working is how you confirm it.
1for (col = 0; col < N; col++)2 for (row = 0; row < N; row++)3 sum += a[row][col];4 5// Each step jumps N elements forward in memory.6// Once N is large, every access is a different line.7// The line that arrives brings 15 neighbours you never use.1for (row = 0; row < N; row++)2 for (col = 0; col < N; col++)3 sum += a[row][col];4 5// Consecutive steps are adjacent in memory.6// One line fetch serves many iterations.7// The prefetcher recognises the stride and runs ahead.Identical arithmetic, identical instruction count, different memory order. The first version pays a fetch per element; the second amortises one fetch across everything sharing the line, and lets Prefetching: The Hardware Guesses What You Will Read Next hide even that. This is the whole module in one example.
Key points
- The hierarchy exists because fast, large and cheap cannot be satisfied at once — so machines have all of them and move data between them.
- The gaps are large: a DRAM access costs on the order of a hundred times an L1 hit, and leaving the chip is a step change rather than an increment.
- Ratios and structure transfer between machines; absolute latencies and sizes do not, and memorising them will mislead you.
- Nothing in your source distinguishes a register hit from a DRAM trip — which is exactly why memory effects feel like magic.
- A performance gap that widens as the data grows is a memory-hierarchy signature, not an algorithmic one.
Progressive depth
Overview
Machines have several memories of increasing size and decreasing speed, arranged so the small fast ones hold what is being used now. Reading arr[i] might be answered by any of them, and the difference between the best and worst case is enormous.
Practical
Assume roughly: L1 a few times a register, L2 a few times L1, L3 a few times L2, and DRAM a large multiple again. Aim to keep hot data small enough to stay in a level, and traverse it in layout order. When two equal-complexity implementations differ in speed, check placement before arithmetic.
Advanced
The hierarchy is not a simple ladder. Lines are installed at multiple levels on the way back, caches may be inclusive or exclusive of one another, the last level is shared and therefore contended, and several misses can be in flight simultaneously so their latencies partly overlap (Misses That Overlap Are Nearly Free). A single "DRAM latency" number ignores all of this.
Internals
Each level maintains tags, state bits and a replacement approximation; misses allocate line-fill buffers that themselves limit outstanding requests; the memory controller reorders and batches requests to respect DRAM row activation and refresh timing. Coherence traffic from other cores shares the same interconnect, so a "memory" cost is partly a *sharing* cost — which is why Cache Coherence: Why Shared Memory Works At All belongs to performance and not only to correctness.
Where the Data Is
Change an input and watch which number moves — and which one refuses to.
The exact ratios vary by machine and the absolute times vary far more, which is why none are shown. What is stable enough to build intuition on is the shape: each level is several times the one above, and the gap between the last cache level and memory is the one that decides most program performance.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Core → L1: the load unit presents an address; on a hit the data returns in a handful of cycles and execution continues.
- 2L1 → L2: on a miss L1 forwards the request to L2, and the requesting instruction waits unless the core can find independent work.
- 3L2 → L3: another miss walks out to the shared last-level cache, now competing with other cores for capacity and bandwidth.
- 4L3 → memory controller: a last-level miss leaves the chip. The controller queues the request against DRAM timing constraints.
- 5DRAM → core: the line is returned and installed at each level on the way back, so the next access to any byte in it is a hit.
- • "L1 is faster than RAM" stated as the whole lesson — true, uninformative, and it does not tell you what to change.
- • Treating a published latency table as applying to your machine, then building a cost model on numbers that are wrong by a factor of two.
- • Concluding a loop is compute-bound because the CPU shows 100% utilisation; a core stalled on memory is still counted as busy (Busy Is Not the Same as Working).
- • Assuming more cache always helps — a streaming workload with no reuse gets nothing from a larger cache (Three Kinds of Miss, Three Different Fixes).
Consequences, controls and cost
- • Programs with equal instruction counts can differ by an order of magnitude in runtime purely through data placement.
- • Performance degrades in steps rather than smoothly as a working set grows past each cache level.
- • Optimising arithmetic in a memory-bound loop produces no measurable improvement, which reads as "the optimisation did nothing".
- • Benchmarks that fit in cache report numbers the production workload will never see — see [[microbenchmarking-pitfalls]].
- • Shrink the working set so more of it fits in a level — smaller types, fewer fields, denser encodings ([[working-set]]).
- • Traverse in the order the data is laid out, so each fetched line is fully used ([[spatial-locality]]).
- • Restructure the algorithm to reuse data while it is still resident, rather than streaming past it repeatedly ([[matrix-tiling]]).
- • Choose layouts that put the fields you actually touch together ([[aos-vs-soa]]).
- • Measure which level you are missing in before optimising for any of them — the fix differs per level.
- • Read the actual cache sizes and line size from the OS rather than assuming: on Linux, `lscpu` or `/sys/devices/system/cpu/cpu0/cache/`.
- • Sweep a working set across sizes and plot time per element; the cliffs mark your cache capacities on this machine.
- • Sample cache-miss counters per level and compare miss counts against loads retired to get a miss rate, not just a count.
- • Compare the same benchmark at a size that fits in L2 against one that does not — the ratio is your local penalty.
- • Watch whether the gap between two implementations widens with input size: widening implicates memory, flat implicates arithmetic.
- • Restructuring for locality usually costs readability, and sometimes costs an abstraction the rest of the codebase relies on.
- • Shrinking data to fit a level can mean lossy encodings, more unpacking work, or types that are awkward in the source language.
- • Cache-conscious layouts are tuned to a machine profile; the tuning can be wrong on the next generation, so it needs re-measuring rather than trusting.
Scope
§224 — what these claims are specific to.
- GENERALThe multi-level structure holds across essentially all contemporary general-purpose CPUs; the level count, sizes and inclusivity policy differ by vendor and generation
- SIMPLIFIEDThe cost scale omits store buffers, line-fill buffers, memory-level parallelism and the fact that several misses can be outstanding at once — see Misses That Overlap Are Nearly Free
Misconceptions
Apply it
Where the rest of this lives
Which level answers a read is decided largely by how the runtime laid the object out and where the allocator put it — neither of which appears in your source.