Cache Eviction Algorithms: FIFO vs LRU vs LFU vs S3-FIFO Benchmark

LRU scored exactly zero hits on one million requests. Not 0.4%, not "close to zero" — 0 out of 1,000,000, with a cache large enough to hold 90% of the working set.

The workload was a cyclic scan: walk 20,000 keys in order, then start over. FIFO returned zero too. So did LFU. Random replacement, the policy nobody writes blog posts about, hit 79.1% on the same trace.

That result is why I stopped reading about cache eviction and started measuring it. Almost every article on the topic explains the algorithms and then asserts a ranking. So I implemented FIFO, LRU, LFU and S3-FIFO from scratch in Python — no libraries — and ran each one over three access patterns, four cache sizes, and 1,000,000 requests per pattern. Random replacement and Belady's offline optimum are included as reference lines: one tells you how low the bar is, the other tells you how much headroom is left.

Across the 12 hit-rate cells, S3-FIFO had the best number in 8, LFU in 3, and random replacement in 1. No policy won everywhere, and the winning margins ranged from 0.02 percentage points to 24.

What do FIFO, LRU, LFU, and S3-FIFO actually do?

They differ in one decision: which resident key to throw away when a new one arrives. FIFO evicts the oldest insertion, LRU the least recently touched, LFU the least frequently touched, and S3-FIFO splits the cache into a small probation queue and a main queue so that one-hit wonders never reach the main queue at all.

Every implementation below is the one I benchmarked, with unit-sized objects and integer keys.

FIFO

Insertion order decides everything. A hit changes nothing, which is exactly why it is cheap.

class FIFO:
    def __init__(self, capacity):
        self.cap = capacity
        self.q = deque()
        self.live = set()

    def get(self, key):
        if key in self.live:
            return True
        if len(self.live) >= self.cap:
            self.live.discard(self.q.popleft())
        self.q.append(key)
        self.live.add(key)
        return False

LRU

A hit moves the key to the back of the queue. That single line is the whole difference from FIFO, and it costs a pointer update on every hit.

class LRU:
    def __init__(self, capacity):
        self.cap = capacity
        self.d = OrderedDict()          # hash map + doubly linked list

    def get(self, key):
        if key in self.d:
            self.d.move_to_end(key)     # this is the entire algorithm
            return True
        if len(self.d) >= self.cap:
            self.d.popitem(last=False)
        self.d[key] = None
        return False

LFU

Keys live in buckets indexed by access count, and each bucket is itself ordered by recency so ties break the LRU way. Counters never decay, which is the classic weakness: a key that was hot last Tuesday can squat in the cache forever.

class LFU:
    def __init__(self, capacity):
        self.cap = capacity
        self.freq = {}                            # key -> count
        self.buckets = defaultdict(OrderedDict)   # count -> keys, LRU order
        self.min_freq = 0

    def get(self, key):
        if key in self.freq:
            f = self.freq[key]
            del self.buckets[f][key]
            # … promote key from bucket f to bucket f+1, fix min_freq
            return True
        if len(self.freq) >= self.cap:
            victim, _ = self.buckets[self.min_freq].popitem(last=False)
            del self.freq[victim]
        # … insert key into bucket 1, min_freq = 1
        return False

S3-FIFO

S3-FIFO (Yang et al., SOSP '23) uses three FIFO queues and no linked-list surgery on hits. New keys land in a small queue S holding 10% of capacity. If a key in S is touched at least twice it graduates to the main queue M; otherwise its identifier drops into a ghost queue G that stores keys but no data. A miss that hits G skips probation and goes straight into M.

The paper calls these ideas quick demotion and lazy promotion. Quick demotion is the one that earns its keep: most keys in a real workload are requested once, and S discards them after 10% of the cache worth of traffic instead of 100%.

class S3FIFO:
    def __init__(self, capacity, small_ratio=0.10,
                 ghost_ratio=0.90, move_threshold=2):
        self.cap = capacity
        self.s_cap = max(1, int(capacity * small_ratio))
        self.m_cap = max(1, capacity - self.s_cap)
        self.g_cap = max(1, int(capacity * ghost_ratio))
        self.move_threshold = move_threshold
        self.S, self.M = deque(), deque()
        self.G = OrderedDict()   # ghost: keys only, no payload
        self.loc, self.freq = {}, {}
        self.has_evicted = False

    def _evict_small(self):
        while self.S:
            key = self.S.popleft()
            if self.freq[key] >= self.move_threshold:
                self.M.append(key)          # lazy promotion
                self.loc[key], self.freq[key] = 1, 0
                continue
            del self.loc[key], self.freq[key]
            self._ghost_add(key)            # quick demotion
            return

    def _evict_main(self):
        while self.M:
            key = self.M.popleft()
            f = self.freq[key]
            if f >= 1:                      # FIFO-reinsertion, CLOCK-style
                self.M.append(key)
                self.freq[key] = min(f, 3) - 1
                continue
            del self.loc[key], self.freq[key]
            return

    def get(self, key):
        if key in self.loc:
            f = self.freq[key]
            if f < 3:                       # 2-bit saturating counter
                self.freq[key] = f + 1
            return True
        hit_ghost = key in self.G
        if hit_ghost:
            del self.G[key]
        while len(self.loc) >= self.cap:
            self._evict()
        if hit_ghost or (not self.has_evicted and len(self.S) >= self.s_cap):
            self.M.append(key)              # ghost hit skips probation
            self.loc[key] = 1
        else:
            self.S.append(key)
            self.loc[key] = 0
        self.freq[key] = 0
        return False

This is the object-count variant, ported line by line from the reference C implementation in libCacheSim, whose defaults are small-size-ratio=0.10, ghost-size-ratio=0.90, move-to-main-threshold=2. The paper's own evaluation uses byte-sized objects on production traces; that is a different animal, and I am not claiming to reproduce it.

How was this benchmark built and how do you reproduce it?

One Python file, one fixed seed, one command, about 30 seconds. Everything ran on an Apple M5 (arm64, macOS 26.6.1) under CPython 3.9.6, single-threaded, with 1,000,000 requests per access pattern and a base seed of 20260812. There are no third-party dependencies, and reruns produce byte-identical output.

The three access patterns:

• Zipf, α = 0.9 over 100,000 keys, of which 91,217 appear in the trace. Popularity is skewed the way web and CDN traffic is skewed. Key IDs are shuffled so ID order carries no popularity signal.
• Cyclic scan, 20,000 keys visited in order, on repeat — 50 full laps. The textbook LRU pathology, included to see how bad "bad" really is.
• Mixed, 80% of requests from a Zipf-distributed hot set of 10,000 keys, 20% one-hit wonders from a scan that never repeats. This is the shape most production caches see, and its ceiling is 80% by construction — a fifth of the requests can never hit.

Cache sizes are a fraction of the distinct keys in each trace. The loop uses a different grid (10% to 90%) because a loop only gets interesting when the cache is close to the working set.

Before any numbers are printed, the script runs a correctness gate: every policy is checked for capacity violations, for hit-versus-residency agreement on every request, and against two identities — no online policy may beat Belady's offline optimum, and every policy with an infinite cache must return exactly requests - distinct_keys hits. All five pass. Two external checks back this up: Belady's loop numbers land on exactly capacity / working_set at steady state, and random replacement obeys the fixed-point equation h = e^(-(W/C)(1-h)) — at C=10,000 and W=20,000 the model predicts 20.3% and the run produced 20.4%.

Which algorithm wins on Zipf-distributed traffic?

S3-FIFO and LFU win, and they win by 7.6 to 10.9 percentage points over LRU at the two smallest cache sizes. FIFO and random replacement are indistinguishable from each other and clearly last.

Hit rate %, 1,000,000 requests, Zipf α=0.9 over 91,217 distinct keys:

Two things stand out. First, FIFO and random replacement stay within 0.11 points of each other at every size. FIFO's insertion order carries almost no information on skewed traffic — it is a coin flip with extra bookkeeping. Second, LFU is not the fossil its reputation suggests. On a stationary popularity distribution, counting is close to the right thing to do, and at 27% cache size LFU edges out S3-FIFO by 0.09 points.

The gap between the policies is really a gap in how fast they discard the tail. Skew determines how much tail there is, so I reran the 10,000-key cache at three exponents:

The result runs opposite to intuition: the flatter the distribution, the more the smart policies win. At α=0.7 S3-FIFO beats LRU by 8.6 points, at α=1.2 by 1.2. When traffic is heavily skewed the hot set is small and obvious, and any policy finds it. Quick demotion pays off precisely when the tail is fat.

When does LRU actually lose?

On a cyclic scan, and it loses completely — 0 hits out of 1,000,000, at every cache size I tested, including one holding 90% of the working set. FIFO and LFU produce the identical zero.

Hit rate %, cyclic scan over 20,000 keys, 1,000,000 requests:

The zeros are not rounding. At the 90% cache size I printed raw counts instead of percentages: FIFO 0 hits, LRU 0 hits, LFU 0 hits, out of 1,000,000. A loop evicts each key exactly one step before it is needed again, forever, and recency order is precisely the wrong order to evict in. LFU joins them because in a pure loop no key is ever hit twice, so every counter stays at 1 and LFU degenerates into LRU.

Random replacement escapes because it is not systematic. It keeps a shrinking-but-nonzero fraction of the loop by accident, and at 90% cache size that accident is worth 79.1% — better than every policy in this article and 90% of the offline optimum.

S3-FIFO's nonzero numbers deserve honesty rather than applause. I instrumented the run: at cap=2,000 the main queue ends holding exactly 1,800 keys — its full capacity — every one admitted during warm-up. Since no key is ever hit twice, nothing is promoted out of S, and M's eviction path only fires when M overflows or S runs empty. Neither happens. M freezes into a static pinned cache, and 88,200 hits is exactly 49 laps × 1,800 pinned keys. The steady-state hit rate lands on 0.9 × capacity / working_set to the decimal at three of the four sizes.

That is faithful to the reference implementation, not a bug in my port, but it means the loop column measures accidental pinning rather than scan resistance. Real traces have repeat accesses, M churns normally, and the effect disappears. The engineering conclusion is unchanged: if your workload contains a genuine loop over a set larger than your cache, no policy in this family will save you. Shard the loop or size the cache above the working set.

What happens when a scan pollutes a hot working set?

S3-FIFO wins where it is designed to win, by up to 9.9 points over LRU, and it gets within 1.4 points of the offline optimum. This is the pattern that matters most, because a hot working set plus a stream of one-hit wonders is what real caches see.

Hit rate %, 80% Zipf over 10,000 hot keys + 20% never-repeated keys, 210,220 distinct keys, ceiling 80%:

Read the 5% column carefully. S3-FIFO reaches 77.62 against a hard ceiling of 80 and an offline optimum of 78.98 — it is leaving 1.4 points on the table while LRU leaves 10.2. The small queue is doing exactly its job: one-hit wonders enter S, never get a second touch, and are demoted after consuming 10% of the cache instead of 100% of it.

Then look at the last two columns, where LFU takes both by 0.02 points. Once the cache is large enough to hold the hot set outright, admission control stops mattering and every frequency-aware policy converges on the ceiling. A 0.02-point difference is a tie, and anyone reporting it as a win is selling something.

I also swept S3-FIFO's small-queue ratio here, since 10% is a tuned constant rather than a law. At the 5% cache size the hit rate goes 78.01 / 77.62 / 76.47 / 75.18 / 72.25 for small queues of 5 / 10 / 20 / 30 / 50%. Smaller is monotonically better on this workload, and the published 10% default costs 0.4 points against a 5% queue. That default is a safe compromise across many traces, not the optimum for yours.

What does eviction cost in throughput?

FIFO and LRU run 2.0x to 2.5x faster than LFU and S3-FIFO in this implementation, which sounds decisive and usually is not. Throughput here is a property of my Python code, not of the algorithms.

Thousand operations per second, single-threaded CPython 3.9.6 on an Apple M5:

Treat these as ordering, not magnitude. A production C or Rust implementation changes all five numbers by an order of magnitude and changes their ratios too. What survives the language change is the shape of the work: LFU touches multiple dictionaries per hit, S3-FIFO's eviction path can walk several queue entries before it frees a slot, and both do more per operation than a deque append.

The argument my harness cannot settle is concurrency. LRU mutates a shared linked list on every hit, so it needs a lock on the read path — the reason production systems reach for CLOCK or sharded approximations. S3-FIFO only increments a per-object counter, one atomic operation with no list surgery. That is the scalability claim in the SOSP paper, and single-threaded numbers can neither confirm nor refute it.

Which one should you actually use?

S3-FIFO, if you are choosing today and your traffic looks anything like the mixed pattern. It led 8 of 12 hit-rate cells, it never lost to LFU by more than 0.09 points, and it beat LRU by 8.4 to 10.9 points wherever the workload had a fat tail. The implementation above is roughly 70 lines of Python and needs no locks on the read path. Its only real defeat was to random replacement on the loop, by 15.2 points — a pattern where you have a sizing problem, not a policy problem.

The more useful finding is how much of the received wisdom did not survive contact with a benchmark. FIFO is not meaningfully better than random replacement on skewed traffic — the two stayed within 0.11 points at every size. LFU is not obsolete; it won three cells and was within a rounding error in four more. Random replacement is not a joke policy; it was the best online policy in this article on the one pattern where the others returned literal zeros. And S3-FIFO's advantage narrows to nothing exactly when your cache is big enough to hold the hot set, which is the case where the decision was never going to matter.

If you take one operational habit from this, take the size question first. On both realistic patterns, every policy at the largest cache size beat every policy at the smallest, by margins no eviction algorithm came close to. Replacing LRU with S3-FIFO bought 9.9 points on the mixed pattern. Growing the same cache from 1% to 5% of the key space bought 18.9. Tune the cheap knob before the clever one.

FAQ

Is S3-FIFO always better than LRU?

No. S3-FIFO beat LRU in every cell I measured — by 0.15 to 10.9 points on the two realistic patterns, and by more on the loop, where LRU sits at zero. But the margin collapses as the cache grows past the hot working set: at 25% cache size on the mixed pattern the gap was 0.15 points. On a pure cyclic scan both are effectively useless and random replacement wins.

Why did LRU get exactly zero hits on a loop?

A cyclic scan over a working set larger than the cache evicts every key one step before it is needed again. LRU always discards the key that has waited longest, which in a loop is always the next key requested. The failure is systematic, so the hit count is exactly 0 rather than merely low.

Does LFU still make sense in 2026?

Yes, for stationary popularity distributions. LFU had the highest hit rate in 3 of my 12 cells and stayed within 1 point of S3-FIFO in most of the rest. Its real weakness is not accuracy but adaptation: counters that never decay let yesterday's hot keys squat in the cache, and my traces have no popularity shift to expose that.

What cache size should I use?

Larger than your hot working set, if you can afford it. In my mixed-pattern run, growing the cache from 1% to 5% of the key space gained S3-FIFO 18.9 points of hit rate — roughly twice what switching from LRU to S3-FIFO gained at a fixed size. Sizing dominates policy until the hot set fits.

Is random replacement a serious option?

For loop-heavy workloads, yes. Random replacement hit 79.1% on a cyclic scan where FIFO, LRU and LFU all hit exactly 0%, and it obeys a clean analytic model: h = e^(-(W/C)(1-h)). It is also lock-free and needs no metadata. On Zipf traffic it trailed S3-FIFO by 6 to 14 points, so it is a pattern-specific answer, not a general one.

How do these results compare to the SOSP '23 paper?

They agree on direction, not magnitude, and the setups differ. The paper evaluates S3-FIFO against 6,594 production traces with byte-sized objects; I ran three synthetic patterns with unit-sized objects. My numbers are my own measurements — quote them as such.

What is Belady's optimum doing in the tables?

It is the ceiling, not a candidate. Belady's MIN evicts the key whose next use is farthest in the future, which requires knowing the future, so no online cache can implement it. Its value is calibration: on the mixed pattern at 5% cache size it shows S3-FIFO's remaining headroom is 1.4 points while LRU's is 10.2.

References

• Juncheng Yang, Ziyue Qiu, Yazhuo Zhang, Yao Yue, K. V. Rashmi. FIFO queues are all you need for cache eviction. SOSP '23. doi.org/10.1145/3600006.3613147
• s3fifo.com — the authors' summary of quick demotion and lazy promotion.
• Reference S3-FIFO implementation in libCacheSim: S3FIFO.c. My Python port follows its defaults and control flow.
• L. A. Belady. A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal, 1966. The origin of the offline optimum used as the ceiling here.