FIFO · policybook

FIFO evicts the key that arrived first. It does not care how often or how recently a key has been used: position in the queue is fixed at insertion, and entries leave in the order they came in. It is the simplest cache policy that works at all, and it is here mainly as the floor: a policy that cannot beat FIFO is not earning its complexity.

When to use it

When eviction must be predictable: a key’s lifetime is exactly one full pass of the queue, regardless of traffic.
When a hit must be as cheap as physically possible. FIFO touches no shared state on a hit, so readers need no lock and no atomic write at all. LRU needs both to reorder its list.
As the baseline in a benchmark, to see what a policy’s cleverness is buying.
On workloads with no reuse to exploit, a pure streaming scan, where every policy degrades to the same thing and FIFO gets there with the least work.

When not to use it

On any workload with a hot working set. FIFO evicts a key that is being read constantly simply because it has been around a while, and the next access faults it straight back in.
As a general-purpose cache. On the canonical Zipf trace it loses several points of hit rate to LRU for no saving that matters at that scale.
When a scan passes through. FIFO caches the entire scan and flushes the working set to do it, the same failure as LRU, with none of LRU’s upside.
If you are reaching for FIFO because it is lock-free on hits, look at SIEVE or S3-FIFO first: both keep that property and add one bit of reuse information, which is most of what LRU gives you.

How it works

A circular buffer of resident keys and two integers. Insertion writes at the tail. Eviction reads the head. Hits do nothing at all.

onAccess(key, hit):
    if hit: return                  # the whole policy
    slots[(head + length) % size] = key
    length += 1

evict():
    key = slots[head]
    head = (head + 1) % size
    length -= 1
    return key

Parameters

Complexity

O(1) time for both access and eviction, with no data-dependent branches on the hit path. O(n) space: one key slot per entry and nothing else: no per-entry metadata, no links, no counters. That makes FIFO the cheapest policy here in both memory and hit cost.

C memory: 8.0 bytes per entry at capacity 1000, measured with pb_cache_fifo.memory_bytes: exactly the 8-byte key, with the struct itself rounding to nothing at scale. For comparison, LRU costs 46.8 and LFU 74.8.

Because a hit is a no-op, FIFO needs no synchronisation on reads. This is its one genuine operational advantage over LRU and worth remembering.

Source

Folklore. FIFO queues predate caching as a discipline.

Related: LRU is FIFO plus “move to front on hit”. SIEVE and S3-FIFO are FIFO queues with a single reuse bit, which recovers most of LRU’s hit rate while keeping FIFO’s cheap hits.

Notes

No patents. No variants worth naming: FIFO’s whole appeal is that there is nothing to configure.

FIFO is sometimes confused with LRU by people who have only seen the eviction end of both. They differ solely in what happens on a hit, and that difference is what the distinguishing vector in vectors.json pins down.