Two caches hold three items each. One gets four hits; the other gets two.
The entire workload fits on one line: ABCABDABCDAB. Each letter requests a fictional object, and both caches start empty. A hit means the object is already present; a miss means it must be brought in. The only difference is the eviction rule. This tiny trace lets us inspect every decision without pretending to measure a real computer’s speed.
A cache is a prediction made with limited space.
Remembering everything would avoid the argument
There are four possible objects but only three slots. The first requests for A, B and C miss because the cache is empty. After those requests, all three slots are occupied. When D arrives, a resident must leave. The interesting question is not whether to remember, but which part of the past is worth keeping.
The model treats all objects as equally sized and every miss as the same kind of event. It does not attach download times, storage prices or retrieval costs. Real caches often face unequal objects and unequal consequences, but leaving those out makes the replacement rules easier to compare on their own.
Arrival order and use order are different
First-in, first-out, or FIFO, evicts the object that entered earliest. A hit does not refresh its position in that queue. Least recently used, or LRU, evicts the object whose latest request is furthest in the past. A hit updates recency even though no new object is loaded.
After the opening ABC, the next requests are A and B. Both policies hit on them. FIFO still regards A as the oldest arrival, while LRU now regards C as the least recently used. When D comes next, FIFO removes A and LRU removes C. That single disagreement changes what happens when A and B are requested again.
The advantage has a specific cause
Across all twelve requests, LRU records four hits and FIFO two, corresponding to 33.3% and 16.7% of this trace. LRU benefits because A and B are reused soon after their earlier requests. The trace was chosen to make that distinction visible; it is not a random sample of a user’s browsing or a processor’s memory traffic.
The final four requests, C D A B, miss under both policies in the three-slot run. Recent use is helpful only when the future actually reuses what the rule protects. A stream that keeps moving through more objects than fit can defeat that expectation. This example contains both a short useful reuse pattern and a later stretch that offers no hits.
A fourth slot changes the story
The script repeats the same trace with capacities one through four. At four slots, every object can remain once loaded, so both policies produce eight hits after the four first-time misses. The earlier difference disappears because the model no longer has to evict anything. Capacity and replacement policy interact rather than offering independent guarantees.
This result is confined to a workload with four immutable keys and a permanently available slot budget. A bigger real cache might compete for memory with other work or store large objects that crowd out several small ones. A capacity chart should therefore carry the workload and object-size assumptions that make its horizontal axis meaningful.
Remembered is not always current
A cache also needs rules about when a stored result becomes stale. A perfect hit count can still serve the wrong answer if the source changed and the cache never learned about it. Expiry, validation and explicit invalidation concern correctness; replacement policy mainly concerns which available copy stays when space runs out.
None of those freshness mechanisms is modeled here. The letters name unchanging objects, and eviction only removes an object from the simulated cache. The useful takeaway is a separation of questions: what should remain, how long is it valid, and what does retrieving it cost? A recent-use rule answers the first imperfectly, not all three at once.
Further reading
Python: LRU memoization semantics ↗Python: ordered dictionaries and reordering ↗Original documentation and useful background.