Toolgeist › Developer

Cache Eviction Simulator — LRU vs LFU vs FIFO vs Belady Optimal

Four eviction policies racing on one identical access trace, plus Belady's OPT — the policy that evicts whatever is needed furthest in the future — as the provable lower bound on misses. OPT cannot be implemented because it requires knowing the future, but that is exactly what makes it useful: the gap between it and your policy is the only honest measure of how much room is left for a smarter algorithm versus how many misses are simply unavoidable. The lower bound property was verified across 60 traces, 3 capacities and 4 policies, and no online policy ever beat it.

How to use Cache Eviction Policy Simulator — LRU vs LFU vs FIFO vs Belady

  1. Pick a workload shape — skewed, cyclic scan, uniform random, or hot set plus noise.
  2. Drag the capacity slider and watch the hit rates diverge.
  3. Compare each policy against the Belady OPT bar.
  4. Read the hit-rate-versus-capacity curve to decide between a better policy and more memory.

Frequently asked questions

Why does LRU sometimes get a 0% hit rate?
Because a cyclic scan over a working set one item larger than the cache defeats it perfectly: the key LRU evicts is always precisely the one needed next. Select the cyclic scan workload with capacity 8 and you will see 0%, not merely a poor number. MRU — normally a bad idea — wins outright there. This is why database buffer pools detect sequential scans and switch strategy rather than trusting LRU blindly.
When does LFU beat LRU, and when does it fail?
LFU wins when popularity is genuinely stable, which is why it leads on the skewed workload. It fails on shifting popularity: an item that was hot once accumulates a large count and then squats in the cache long after anyone stopped wanting it. Production systems therefore use aged or windowed LFU variants rather than raw frequency counts.
What is Belady's OPT and why include something unimplementable?
It is the offline optimal policy — evict whatever will be used furthest in the future — and it is provably the minimum achievable number of misses. As a benchmark it answers the question that actually matters when tuning: if OPT is barely ahead of your policy, stop tuning and buy more cache; if the gap is wide, your policy is the bottleneck.
Why does FIFO do worse than LRU?
FIFO evicts by insertion age and never accounts for use, so an item accessed on every single request is still evicted once it becomes the oldest. LRU refreshes an item on every hit. You can see the difference directly: on the trace A B C A D with capacity 3, FIFO evicts A despite A having just been used, while LRU keeps it and evicts B.
Which policy should I actually use?
On typical skewed traffic LRU is a sound default and is cheap to implement. Reach for a frequency-aware policy when popularity is stable and long-lived, and add scan resistance when large sequential reads pass through. The genuinely important step is measuring against your own trace, because the right answer changes completely with workload shape — which is what this tool is for.
Does a bigger cache always mean more hits?
For LRU, LFU and OPT yes — they are stack algorithms, so hit rate never decreases as capacity grows, which this tool verifies. FIFO is not a stack algorithm and can genuinely get worse with more memory. Load the ‘Belady’s anomaly’ workload and set capacity to 3, then 4: FIFO goes from 9 misses to 10. That is a real phenomenon, not a bug in the simulator.

Related Developer tools

Also searched for: lru vs lfu cache · cache eviction policy comparison · belady optimal algorithm · cache hit rate simulator · why lru fails on sequential scan

Browse all 738 free tools on Toolgeist →