Play the Cache: Why LRU Sometimes Scores Zero
Every other structure in this cluster has a right answer available to it. A search tree knows where a value belongs; a hash table knows which bucket a key hashes to. A cache does not, because the question it has to answer is which of these will I need again — and the answer lives in requests that have not arrived yet.
So every eviction policy is a guess about the future, written as a rule about the past. LRU’s guess is: what has been used recently will be used again soon. That is often right. It is sometimes catastrophically wrong, and the interesting part is seeing exactly when.
Take the decision yourself
Serve the request stream. Whenever the cache is full and something new is asked for, you pick what to drop. Your score runs against LRU on the identical stream, and against the most any policy could possibly have scored.
A cache holds a limited number of items. When something is requested that is not held and there is no room, one entry has to go — and which one you drop decides how many future requests hit. The catch is that the best choice depends on requests that have not arrived yet, so every real policy is a guess about the future dressed up as a rule about the past.
With a cache of 3 entries over 16 requests: on a repeating loop FIFO, LRU and the optimal ceiling all score 13. On mixed traffic LRU scores 7 against FIFO's 5, with 9 theoretically available. On a sequential scan — four keys cycled through a cache holding three — LRU scores 0, and so does FIFO, while the ceiling is 8. Not a bug: "evict the least recently used" is exactly the wrong rule when every key is used exactly once per lap, so LRU always throws away the entry it is about to need.
That ceiling is Belady's optimal policy, which evicts whatever is needed furthest in the future. Nobody can implement it — it requires knowing the future — so it is a measuring stick rather than an algorithm, and the gap between LRU and it is how good a guess LRU is.
Serve the request stream. When the cache is full and something new is asked for, you choose what to drop. Beat LRU. Match the ceiling if you can.
Your cache — click one to evict it
- Your hits
- 0
- LRU would have
- 0
- Ceiling
- 0
- Requests left
- 0
The same game, as values
Request stream
Cache
Final scores
Start on Mixed reuse to get the feel, then switch to Sequential scan and try to score a single hit.
Play Sequential scan and watch what happens to LRU’s bar. Four keys, a cache holding three, each key used once per lap. LRU evicts the least recently used entry — which, in a cycle, is always precisely the one about to be needed. It scores zero. Not zero because of a bug: zero because its guess is inverted on this input.
You can beat it easily once you see the trick, by refusing to evict something you know is coming soon. That is the whole lesson: you had information LRU did not, because you could see the stream printed in front of you.
The ceiling is not an algorithm
The third bar is Belady’s optimal policy: evict whatever is needed furthest in the future. It produces the highest hit count any policy could achieve, and it is unimplementable, because it requires the future.
That is why it belongs on the page. Quoting a cache’s hit rate alone tells you nothing — 80% might be superb or might be leaving half the available hits on the table. Measured against the ceiling, a policy’s quality becomes a real number.
def next_use(requests, key, after):
"""Index of the next request for `key` strictly after position `after`, or None."""
for j in range(after + 1, len(requests)):
if requests[j] == key:
return j
return None
def simulate(requests, capacity, policy):
"""Returns hits. `cache` is ordered oldest-first for FIFO and least-recent-first for LRU."""
cache, hits = [], 0
for i, key in enumerate(requests):
if key in cache:
hits += 1
if policy == "lru":
cache.remove(key)
cache.append(key) # touching a key makes it most recent
continue
if len(cache) == capacity:
if policy == "optimal":
# Belady: evict whatever is needed furthest in the future. Requires the future.
victim, furthest = cache[0], -1
for k in cache:
nxt = next_use(requests, k, i)
if nxt is None:
victim = k
break
if nxt > furthest:
victim, furthest = k, nxt
else:
victim = cache[0] # FIFO and LRU both drop the front
cache.remove(victim)
cache.append(key)
return hits
SCAN = [1, 2, 3, 4] * 4
LOOP = [1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1]
MIXED = [1, 2, 1, 3, 1, 4, 1, 2, 5, 1, 2, 3, 1, 6, 1, 2]
CAPACITY = 3
print(f"{'access pattern':<16} {'requests':>8} {'FIFO':>6} {'LRU':>6} {'optimal':>8} what it shows")
for name, seq, note in [
("repeating loop", LOOP, "working set fits: everything does well"),
("mixed reuse", MIXED, "LRU earns its reputation here"),
("sequential scan", SCAN, "LRU's pathological case"),
]:
fifo = simulate(seq, CAPACITY, "fifo")
lru = simulate(seq, CAPACITY, "lru")
best = simulate(seq, CAPACITY, "optimal")
print(f"{name:<16} {len(seq):>8} {fifo:>6} {lru:>6} {best:>8} {note}")access pattern requests FIFO LRU optimal what it shows repeating loop 16 13 13 13 working set fits: everything does well mixed reuse 16 5 7 9 LRU earns its reputation here sequential scan 16 0 0 8 LRU's pathological case
Three rows, three different lessons.
When the working set fits, the policy does not matter. All three score 13. Most caching advice is really advice about making the working set fit.
On mixed traffic LRU earns its reputation — 7 against FIFO’s 5 — and still leaves 2 hits on the table. A good heuristic, not a solved problem.
On the scan, LRU and FIFO both score zero while 8 hits were available. This is not a contrived input; it is what a full table scan does to a database buffer pool, and it is why real systems detect scans and route them around the cache rather than letting them evict everything useful.
What an LRU cache is made of
The policy needs two things at once: find a key instantly, and know the exact order of last use. Neither structure in this cluster does both, so a real LRU cache is a hash map and a doubly linked list wired together.
The list holds entries in order of use, most recent at one end. The hash map maps each key to the list node holding it. A lookup hashes the key, follows the pointer straight to the node, and splices it to the front — all constant time, none of it involving a search. Eviction takes the node at the far end, which the list can reach directly.
That is the composition worth noticing: the hash map cannot answer “what was used least recently” and the list cannot answer “where is key K”. Neither is sufficient and together they are, which is the usual shape of a real data structure.
What this page simplifies
- Hits, not latency. Hit counts are deterministic. Real value depends on how expensive a miss is, and a policy with a slightly lower hit rate but cheaper bookkeeping can win.
- No LRU variants. Real caches use approximations — CLOCK, segmented LRU, LRU-K, ARC — because exact LRU ordering costs a write on every read, which is painful under concurrency.
- Fixed capacity, uniform costs. Every entry is assumed the same size and equally expensive to fetch. Web and CPU caches are neither.
- Belady is a bound, not a suggestion. No implementation is possible. If a page ever presents it as one, it is describing something else.