Cache Performance and Replacement Policies: When the Cache Is Full

Hook #

In the last course you learned what a cache is — a small fast memory that keeps hot data close, organised as direct-mapped, set-associative, or fully-associative slots. This lesson answers the question that organization raises but doesn't resolve: a cache is small, so what happens when it fills up and you need to bring in something new? Something already in the cache has to be evicted to make room. Which something you evict is the replacement policy, and it turns out to be one of the most consequential and recurring decisions in all of computing. Get it right and your hit rate stays high; get it wrong and you thrash — constantly evicting data you're about to need again. The policies you meet here (LRU, FIFO, LFU) are the same ones you'll implement by hand later for an application cache, so this is theory you'll ship.

What you'll be able to do by the end of this lesson #

• Compute hit rate and miss rate from an access trace, and explain why a small change in miss rate can mean a large change in wall-clock time (the "average memory access time" formula makes this precise).
• Explain the three main replacement policies — LRU, FIFO, LFU — and the intuition each one bets on.
• Explain why true LRU is expensive in hardware and why real caches approximate it (CLOCK / pseudo-LRU) rather than implementing it exactly.
• Name what "thrashing" is and recognise the access pattern that causes it.

A quick try before we start #

Suppose a cache holds 3 items and you access the sequence A B C A B D A B C D. Using "evict the least recently used item" (LRU), how many of those ten accesses are misses? Work it out on paper before reading — tracking the cache's contents by hand for a few accesses is the single fastest way to feel how a replacement policy behaves, and every policy in this lesson can be understood by running a short trace through it.

Why this matters here #

You will implement a cache with a replacement policy in this exact course — the "Cache Simulator in C" project is precisely this lesson made concrete. But the reach is much wider. An LRU cache is one of the most common data-structure interview questions in the industry, and it's common because it's everywhere in real systems: your database's buffer pool evicts pages by an LRU-like policy, your CDN evicts objects, your ORM's query cache, Redis's maxmemory-policy, the browser's cache — all replacement policies choosing what to keep when space runs out. Learning the policies here at the hardware level means that every one of those higher-level caches is a variation you already understand rather than a new thing to memorise.

This lesson also sharpens the performance intuition that started in the last course. There, locality was qualitative ("sequential access is faster"). Here it becomes quantitative: a formula relating hit rate, hit time, and miss penalty to the average memory access time your program actually experiences. That formula is why a 95% hit rate and a 99% hit rate can differ in performance by more than the 4-point gap suggests — because the misses, not the hits, dominate the cost.

The engineer's lens #

The idea worth internalising is that every replacement policy is a bet about the future made from the past. No policy can see what you'll access next; each one uses history as a proxy. LRU bets "what I used recently, I'll use again soon" — it's temporal locality turned into an eviction rule, and it works remarkably well because most real workloads genuinely have that shape. FIFO bets "the oldest thing has outlived its usefulness" — cheaper to implement (just a queue, no per-access bookkeeping) but blind to how often something is used. LFU bets "what I've used a lot, I'll keep using" — great for stable hot sets, terrible when the hot set shifts (it clings to yesterday's popular items). There is no universally best policy; there's only the best bet for this workload. That framing — "caching is prediction under uncertainty" — is exactly how you should think when you later choose allkeys-lru vs allkeys-lfu in a Redis config, and it's why those options exist at all.

The second lens is the gap between the ideal policy and the implementable one, which recurs constantly in systems. True LRU requires knowing the exact recency order of every item — in hardware, that's expensive bookkeeping on every single access, at nanosecond speeds. So real CPU caches don't implement true LRU; they approximate it with schemes like CLOCK (a "second chance" bit per line) or tree-based pseudo-LRU that get most of LRU's benefit for a fraction of the cost. This "the perfect algorithm is too expensive, so ship a cheap approximation that's 95% as good" pattern is one you'll meet again in page replacement (next lesson, same policies, different layer), in load balancing, in rate limiting. The engineering maturity is knowing when the approximation is good enough — almost always.

What to focus on in CS:APP §6.4-6.5 #

• The average-memory-access-time intuition (§6.4.3). You don't need to memorise the formula, but you must internalise its consequence: because a miss costs orders of magnitude more than a hit, miss rate is the lever, and small miss-rate improvements pay off disproportionately. This is why "reduce cache misses" beats "reduce instructions" for many hot loops.
• Writing cache-friendly code (§6.5). This is the practical payoff — how loop order, data layout, and access stride change your miss rate. The matrix-multiply reordering example is the canonical demonstration; work through it.
• For the policies themselves, the Wikipedia survey plus running traces by hand is enough. LRU, FIFO, and LFU are the three you must be able to simulate on paper; the rest (ARC, CLOCK, 2Q) are variations to recognise, not implement now.
• Skip on first pass: cache coherence protocols (MESI) and multi-core cache interaction. Real and important for concurrency later; not this lesson's job. Note the words and move on.

Explain it back #

Explain to a colleague why a caching system might offer both an LRU and an LFU eviction option instead of just picking the "best" one. A strong answer says there is no universal best — each policy bets on a different assumption about the access pattern (recency vs. frequency), so the right choice depends on the workload's shape. Bonus: give one workload where LFU beats LRU and one where the reverse holds.

Where this connects #

Backward: Last course's cache organization (direct-mapped/set-associative/fully-associative) and locality of reference. Replacement policy is the piece that organization left open — which line in a set to evict. The hashing-collision connection from that lesson still holds: a conflict miss is when two hot addresses fight for the same set, and the replacement policy decides who wins each round.

Forward: Lesson 2 (virtual memory) applies these exact same replacement policies one layer down — page replacement uses LRU/FIFO/LFU to decide which memory page to evict to disk. Same problem, same policies, hundred-thousand-times-larger miss penalty. And the LRU cache you build in the project here is a data structure (hash map + doubly linked list) you'll reach for in application code for the rest of your career.