Caches & Memory Hierarchy
The deepest module, because this is where most real programs spend their time. Lines, locality, associativity, replacement, thrashing and prefetching — the machinery behind "why is this loop slow".
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.
A cache is not a faster memory. It is a small tagged store holding copies of recently used lines, managed entirely by hardware, betting that your program will ask for the same or nearby data again. When the bet pays it is invisible; when it fails it is also invisible, which is the problem.
The cache has no concept of your variables. It moves fixed-size blocks — typically 64 bytes today — so reading one byte fetches the 63 around it. Almost every practical memory optimisation, and one notorious concurrency bug, follows directly from that one fact.
If you touch an address, you will probably touch its neighbours soon. Hardware bets on this at every level — line size, prefetchers, DRAM row buffers — so code that walks memory in order gets most of its data effectively for free, and code that scatters pays full price for every element.
If you touched something recently, you will probably touch it again. That assumption is what makes keeping copies worthwhile at all — and it is why the size of the data you revisit, rather than the size of the data you own, determines whether a program is fast.
A miss is not an error; it is a cost, and it is the normal way data arrives. What matters is where the miss is satisfied — one level out, three levels out, or in DRAM — because those outcomes differ by more than an order of magnitude and imply completely different fixes.
Compulsory, capacity and conflict misses look identical in a counter and have almost nothing in common as problems. Prefetching helps one, blocking helps another, and layout changes help the third — so classifying the miss is what turns a measurement into a plan.
The simplest way to build a cache: every memory address has exactly one line it is allowed to occupy. Lookup becomes trivial and the hardware stays cheap — but two hot addresses that happen to share an index evict each other forever, while the rest of the cache sits empty.
Give each address a set of N possible homes instead of one. Conflicts stop being catastrophic, lookup stays affordable, and you inherit a new problem — with N candidates, something has to decide which one to evict.
A cache does not search. It slices the address into three fields — offset, index, tag — and each field's width is forced by the geometry rather than chosen. Once you can do the split, most cache behaviour stops being mysterious.
With N ways in a set, a miss requires choosing a victim. Textbooks say least-recently-used. Real hardware implements approximations that are cheaper, sometimes adaptive, generally undocumented, and different between levels on the same die.
Two ways to make a cache useless: overflow it, or arrange for everything you touch to land in one set. Both produce the same signature — a performance cliff at a specific input size or stride, where the curve falls off rather than bending.
The working set is the data a program actually touches in a window of time. Whichever level of the hierarchy it fits in determines what the program costs — and because the levels are discrete, crossing a boundary produces a step change rather than a gradual decline.
A cache miss costs far more than an instruction, so the hardware tries not to take one: it watches your access stream, predicts the next addresses and fetches them early. Predictable patterns get their data before they ask. Pointer chasing does not — which is most of the answer to why an array beats a linked list at the same complexity.