Small fast memory, big slow memory, and one question that never goes away — what do you throw out? Your closet, your desk and your brain are all running the same algorithm.
Chapter 3 was about putting things in order. This one is about a quieter, more constant problem: there is never enough room close to you. Not in your closet, not on your desk, not on the chip. Something has to go.
The surprising part is that computer science has spent sixty years on exactly this question, has a provably perfect answer nobody can use, and has settled on a runner-up that your grandmother was probably already using on her filing cabinet.
You have a closet. It holds maybe forty things, and everything in it is one reach away. You also have an attic, a basement, a storage unit and — if you're honest — a shop down the road that stocks whatever you gave away last year. Between them, the space out there is effectively unlimited. The space in here is not.
So every object you own sits in one of two states: close and quick, or far and slow. There is no third option, and the boundary is a hard one — the closet doesn't stretch. Which means the interesting decision was never "what should I own?" It was "what deserves the reach?"
And here's the thing that makes it a genuine problem rather than a chore: the closet is always full. Not sometimes. Always, eventually. So the moment you bring in something new, you are — whether you admit it or not — deciding what leaves. Buying a jacket is an eviction.
A small fast store sitting in front of a big slow one, holding the things you're most likely to want next. That arrangement has a name in computing: it's a cache. You've been managing one your whole life.
Here's an awkward fact about hardware: memory can be fast, or it can be big, or it can be cheap. Pick roughly two. Nobody knows how to build a store that is simultaneously enormous, instant and affordable — the physics and the economics both refuse.
So the machine on your desk doesn't have a memory. It has a stack of them, each one about ten times bigger and roughly ten times slower than the one above it. A handful of registers right in the processor. A small L1 cache beside them. A larger L2 behind that. Then main memory, then the SSD, then — at the bottom — the rest of the internet.
The sleight of hand is that your program sees none of this. It asks for a byte; a byte arrives. What actually happens is that the request falls down the stack until something has it, and then that value gets copied back up — on the bet that you'll want it again shortly. Your computer feels fast not because it has fast memory, but because it has a small amount of fast memory and a very good guess about what belongs there.
Maurice Wilkes wrote this idea down in 1965, almost apologetically: since fast memory is expensive, put a little of it in front of the slow stuff and keep the popular items there. It was a workaround for a budget problem. It became the reason modern computing works at all.
Stop and notice how strange it is that caching works. You're keeping forty things out of ten thousand and expecting the next request to land in your forty. Why on earth would it?
Run the thought experiment where it doesn't. Suppose every request picked a random item, uniformly, out of the ten thousand. Then your forty-item closet hits 0.4% of the time and you walk to the attic for everything else. A cache would be a rounding error — you'd be paying for fast memory and getting nothing. No eviction policy on earth could save you, because there'd be nothing to be clever about.
Real demand isn't like that, and it isn't close. Two things are reliably true about it. First, what you just used, you tend to use again — you wore that shirt on Tuesday and you'll wear it next Tuesday; the function you called is about to be called in the loop's next iteration. Second, popularity is wildly lopsided — a handful of items soak up most of the requests while a long tail of things get touched roughly never. Your top five shirts probably outnumber the bottom thirty in wearings.
Those two facts have names — the first is temporal locality, the second is a power law (or Zipf distribution: the second-most-popular item gets about half the traffic of the first, the third about a third, and so on). But the names matter less than the consequence. Caching is not a trick that makes memory fast. It's a bet on the past predicting the future, and the world happens to be repetitive enough for the bet to pay.
The cache is full. Something new shows up. One thing has to leave. That's it — that's the entire field. Everything else about caching is plumbing; the algorithm is the answer to who gets kicked out.
Here's the cast, in roughly ascending order of thoughtfulness:
Four plausible answers, four different closets. Which is right? That's not a matter of taste — it's measurable, and there's a scoreboard below. But before we race them, we need to know what a perfect score even looks like.
Suppose you could cheat. Suppose you had tomorrow's list of everything you'll reach for, in order. What would you throw out?
The answer falls right out: throw out the thing you won't need for the longest time. If you're not touching the ski boots until December, the boots go, regardless of how recently or how often you've used them. And this isn't a heuristic that happens to work well — it is provably the best any policy can do. László Bélády proved it in 1966. No sequence of choices beats it; nothing ever will.
It also requires seeing the future, which rather limits its deployment options.
But don't file that under "useless". Bélády's policy is the yardstick. It tells you the ceiling — the hit rate that is physically available given this cache size and this request stream — so you can stop wondering whether your cache is underperforming or whether the workload is just hard. And it reframes every real policy in one line: every cache you will ever write is a guess at what Bélády would have done.
Which turns the whole question into a forecasting problem. You can't see the future, so you need a cheap proxy for "needed furthest away". And it turns out the best cheap proxy is embarrassingly simple: the recent past. Things you touched a moment ago tend to come back soon; things you haven't touched in ages tend to stay gone. Reverse time and LRU is Bélády — evict what was used furthest in the past, as a stand-in for what'll be used furthest in the future. It works because demand is bursty, and the burst you're in right now is the best evidence you have about the burst you're about to be in.
Once you know the shape, you find it everywhere — usually in places nobody calls a cache:
The best of these is a Japanese economist's filing system. Yukio Noguchi got tired of maintaining folders, and tried something that sounds like giving up: put every document in an envelope, stand them all in a row on the shelf, and after you use one, put it back at the left end. That's the whole system. No categories, no alphabet, no index, no decisions.
You may recognise it. Putting the just-used item at the front, and searching left-to-right, means the thing you never touch drifts steadily rightward until it's at the far end waiting to be thrown away. Noguchi had accidentally built LRU in cardboard — and it's not merely like a cache, it is provably well-ordered for exactly the reason LRU works: the left end is your working set, the right end is dead weight, and the sort happens as a free side effect of using the thing.
Which is a callback to Chapter 3, and a pointed one. We said there that sorting is only worth it if you'll search enough to earn back the effort — and that a lot of tidying is effort you never earn back. This is the sharper version: you often don't need to sort, because the pile sorts itself. Every time you use something, you file it, for free, by touching it. The mess on your desk has been quietly maintaining a recency order this whole time, and it's a better one than you'd get by alphabetising.
Now the part that might change how you feel about your own head.
The standard story about memory is decay. Hermann Ebbinghaus measured it in the 1880s by memorising nonsense syllables and testing himself over days, and he found a clean curve: recall drops off fast at first, then levels out. The usual reading is that memories rot — that forgetting is damage, the slow failure of the hardware.
Here's the thing about that curve, though. It has the same shape as something we've already met. Anderson and Schooler went looking at how often words appear in newspaper headlines, how often you hear a given name, how likely a piece of information is to be needed again after n days — and the environment's statistics match the forgetting curve almost exactly. Memory isn't decaying at some arbitrary rate. It's tracking the actual probability that you'll need the thing. That's not a broken cache. That's a well-tuned one.
Then there's the tip-of-the-tongue moment, which is a strange kind of failure if you think about it: you clearly have the item — you know its shape, its first letter, that it rhymes with something — you just can't pull it out. That's not the file being gone. That's the lookup taking too long. A miss in the fast store while the item sits somewhere slower.
Which brings us to the finding worth carrying around. Older adults do score worse on lookup speed, and the assumption has always been degradation. Michael Ramscar and colleagues took the tests, and instead of testing people, they tested models — they trained a system on more and more text and re-ran the cognitive tests on it as it went. The system got "worse" with age too. In exactly the human pattern. And nothing in it had degraded; the only thing that had changed was that it knew more things. Bigger cache, more items to search, longer to find any one of them. That's not decline. That's a search cost, and it's the price of a full library.
So: a seventy-year-old taking longer to produce a name is not a seventy-year-old whose memory is failing. They're running a query against a database with fifty more years of rows in it. The lookup is slower because the answer is drawn from more. And the forgetting that goes along with it isn't damage either — it's the eviction policy doing its job, keeping what you're likely to need close and letting the rest drift right, toward the end of the shelf.
Your memory isn't failing you. It's making room.
LRU is small enough to hold in your head. You need two things: a lookup that's fast, and a notion of order that a hit can reshuffle. Scala gets both for free from LinkedHashMap, which keeps insertion order — so "remove and re-insert" is a promotion to the back of the line, and the eviction victim is always head. The Haskell version keeps it pure: stamp every entry with a tick, and the victim is the minimum tick. Same policy, different bookkeeping.
Caching answered "what should be near me?" The next chapter asks a harder question about the same finite life: everything is due, the list is longer than the day, and you have to pick an order. It turns out that "which task first" has a real answer too — and that it changes completely depending on what you're trying to minimise. Choose your metric badly and you'll optimise yourself into a corner while working perfectly hard.