Cache Replacement: LRU Is the Idea, Not the Implementation
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.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
Why true LRU is not what gets built
True LRU requires a total ordering of the N ways in a set, updated on every access — including hits, which are the overwhelming majority of accesses. Maintaining that ordering means reading and rewriting per-set state constantly, in the middle of the hit path you spent all that effort keeping short. For a small number of ways it is merely expensive; as N grows the state and the update logic grow with it.
So designs implement approximations. A common family is tree-based pseudo-LRU, which keeps one bit per internal node of a binary tree over the ways: an access flips the bits along its path, and eviction walks the tree following the bits. That is N-1 bits per set instead of a full ordering, and the update is a handful of bit flips. It usually picks a recently-unused way, and sometimes it picks a way that true LRU would have kept.
Other families exist and are used. Some track re-reference intervals to predict whether a line will be reused soon, which handles streaming data better than recency alone. Some detect thrashing and deliberately retain a subset rather than cycling the whole set. Some mix policies adaptively based on which is winning. The point is not to enumerate them but to internalise that "the replacement policy" is not one thing.
| Approach | State per set | Handles well | Handles badly |
|---|---|---|---|
| True LRU | Full ordering of N ways | Recency-dominated reuse | Its own update cost; streaming data |
| Tree pseudo-LRU | N-1 bits | Most recency patterns, cheaply | Occasionally evicts what LRU would keep |
| FIFO / round-robin | One pointer | Being nearly free to implement | Ignores reuse entirely |
| Re-reference prediction | A few bits per way | Streaming and scan-resistant workloads | Extra state and tuning |
| Adaptive / hybrid | Policy selection state | Shifting between workload phases | Behaviour that is hard to predict or model |
What you may not assume
Do not write code whose correctness or performance depends on a specific eviction order. This is the §224 rule for this lesson, and it is stronger than it first appears. It rules out reasoning like "I touched A most recently so B will be evicted", and it rules out microbenchmarks that construct a precise eviction sequence and then generalise the result to other machines.
It also rules out a subtler mistake: assuming that repeatedly touching a line is enough to keep it resident. Under an adaptive or scan-resistant policy, a line may be retained or discarded for reasons that have nothing to do with your access recency — the hardware may have decided your access pattern looks like streaming and be protecting other data from it.
What you *may* rely on is the statistical shape. Reuse helps; a working set that fits tends to stay (Working Set: Why Performance Falls Off a Cliff); a working set that does not fit tends to churn regardless of policy, because no policy can retain more than capacity. Design for capacity and reuse distance, and treat the specific victim choice as noise you do not control.
| Assumption | Verdict | Why |
|---|---|---|
| Reuse within a small working set is usually rewarded | Safe | Every policy approximates recency; a set that fits stays resident under all of them |
| A working set far larger than the level will miss | Safe | No policy can retain more than capacity — this is arithmetic, not policy |
| The least-recently-used line is the one evicted | Unsafe | Real policies approximate recency and routinely evict something LRU would have kept |
| A constructed eviction sequence reproduces elsewhere | Unsafe | Policy, geometry and index hashing all differ between machines and generations |
| Touching data frequently guarantees residency | Unsafe | Scan-resistant and adaptive policies may retain other data instead, by design |
| A better policy would fix my miss rate | Usually unsafe | If the working set exceeds capacity, the policy is not what is failing |
Where the difference actually shows up
For most code the distinction between LRU and its approximations is invisible: the working set either fits or it does not, and policy is a second-order effect. The place it becomes visible is at the boundary — a working set slightly larger than a level, cycled repeatedly. Under true LRU a cyclic pattern one element too large evicts exactly the line you are about to need, every time, producing a pathological zero hit rate. Approximations sometimes get lucky here and do *better* than LRU.
The other visible case is scanning. A single pass over a large array under a naive recency policy flushes everything useful to make room for data that will never be touched again. Scan-resistant policies exist precisely to stop that, which is why a streaming workload may disturb a co-running program less than a simple model predicts.
Both of these are reasons to measure rather than model. If you are near a capacity boundary, small changes in working-set size can produce disproportionate and non-monotonic changes in hit rate, and the direction is not always the one intuition suggests.
1// ways per set = 8; hot lines mapping to this set = 92repeat many times:3 for i in 0 .. 8: // 9 lines, cycled in order4 touch(line[i])5 6// Under strict LRU: the victim is always the line7// needed next. Hit rate approaches zero even though8// the set is one line short, not empty.1// restructure so at most 8 lines are hot per set2repeat many times:3 for i in 0 .. 7: // 8 lines, fits4 touch(line[i])5 6// Now every access after the first pass hits.7// The change is one line of working set, and the8// hit rate moves from near-zero to near-total.The cliff is caused by the interaction of working set and capacity, not by the policy being bad. It is also why an approximate policy can beat true LRU here: by evicting slightly unpredictably it retains part of the cycle instead of losing all of it.
Key points
- True LRU needs a full ordering updated on every hit, which is too expensive to sit in the hit path.
- Real caches use approximations — tree pseudo-LRU, re-reference prediction, adaptive hybrids — chosen for cost.
- The specific policy is a per-design decision, often unpublished, and can differ between levels on one die.
- Never depend on eviction order; depend on working set size and reuse distance, which you can actually reason about.
- Policy is visible mainly at capacity boundaries and under scanning, where approximations sometimes beat strict LRU.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Miss → set selected: the index has already narrowed the choice to one set of N ways.
- 2Set → validity check: if any way is empty, it is used and no victim is needed.
- 3Set → replacement state: the hardware reads the few bits it maintains for this set.
- 4State → victim: those bits select a way that is probably not about to be reused, without a full ordering.
- 5Victim → eviction: a dirty line is written back, then the incoming line takes its place and the state is updated.
- • "The cache is LRU" — it approximates recency. Treating the approximation as the specification produces predictions that do not hold.
- • "My microbenchmark proves the eviction order" — it proves it on that machine, that generation, possibly that boot. It does not generalise.
- • "Touching data often keeps it cached" — under scan-resistant or adaptive policies, retention is not a simple function of your access frequency.
- • "A better policy would fix my miss rate" — if the working set exceeds capacity, no policy retains more than capacity.
Consequences, controls and cost
- • Eviction order is not reproducible across machines, so benchmarks that depend on it do not transfer.
- • Hit rate near a capacity boundary can move non-monotonically as working set changes slightly.
- • A streaming pass may disturb co-resident data less than a naive LRU model predicts, if the policy resists scans.
- • Two machines with identical capacity and associativity can produce noticeably different hit rates on the same workload.
- • Design so the hot working set fits comfortably within a level rather than sitting at its boundary ([[working-set]]).
- • Where a platform offers non-temporal or streaming hints, use them for data you know will not be reused, instead of hoping the policy notices.
- • Reduce reuse distance by blocking or tiling, so reuse happens before eviction is plausible under any policy ([[matrix-tiling]]).
- • Almost nothing else — the policy is not exposed or controllable, so measure the outcome rather than modelling the mechanism.
- • Measure hit rate as a function of working-set size and look for the cliff; its position tells you the effective capacity better than any datasheet.
- • Compare the same sweep on two different machines — divergence in cliff shape is policy and geometry differing, and is a reason not to tune to one box.
- • Watch for non-monotonic hit rate near the boundary; that is a signature of an approximate or adaptive policy.
- • Use miss counters at the specific level rather than aggregate misses, since replacement decisions at one level are invisible in the total ([[performance-counters]]).
- • Cheaper policies cost a little hit rate to save latency, area and energy on the path every access takes.
- • Adaptive policies improve average behaviour but make performance harder to model and reproduce.
- • Designing to the working set rather than to the policy is more portable but constrains data-structure choices.
Scope
§224 — what these claims are specific to.
- MICROARCH-SPECIFICReplacement policy is a per-design, frequently unpublished choice that differs between vendors, between generations, and between cache levels on the same die.
- SIMPLIFIEDDescribes policy families rather than any implementation. Real designs combine several mechanisms and may switch between them at runtime.