LRU caches

Adding a cache is one of the few changes that can make a program faster without changing what it computes, which is why it gets reached for early and configured late. The two decisions that matter are made when you add it — what counts as the same call, and what happens when the cache is full — and both are easy to get wrong in ways that show up as a low hit rate or a process that grows all week.

What least-recently-used actually orders#

The ordering is by last access, not by age. An entry added an hour ago and read a second ago is newer, as far as the cache is concerned, than one added a minute ago and untouched since. Every read moves an entry to the front, and eviction always takes from the back, so what leaves is whatever has gone longest without being wanted.

That rule encodes a bet about the workload, and Python’s documentation states it rather than leaving it implicit: an LRU cache works best when the most recent calls are the best predictors of upcoming calls. When that holds — a handful of popular items, most traffic landing on them — the cache is nearly free. When it does not, the same mechanism turns against you: a workload that walks steadily through a wide key space evicts each entry shortly before it would next have been needed, so you carry the cost of the cache and collect almost none of the benefit.

The key is the whole argument list#

A memoising cache has to decide when two calls are the same call, and it does so mechanically, from the arguments as they arrived. Python’s implementation builds a dictionary key out of them, which brings one requirement with it that the documentation states directly: the positional and keyword arguments must be hashable. That is the same condition every hash table rests on, surfacing here as a rule about arguments. Pass a list where a tuple would do and the call does not fail to cache, it fails outright.

The subtler consequence is that identical intent can produce different keys. The documentation gives the case exactly: f(a=1, b=2) and f(b=2, a=1) differ in keyword order and may end up as two separate entries. Nothing is broken — both return the right answer — and the cache is simply doing twice the work and holding twice the memory for one logical result. It is invisible in review, because both call sites look correct, and it is the reason cache_info exists: hits and misses side by side will show the problem that reading the code will not.

A cache that never forgets#

The dangerous setting is the one that removes the limit. Python’s documentation notes that with maxsize set to None the eviction feature is disabled and the cache can grow without bound, and it names the reason the limit exists at all: to assure the cache does not grow without bound on long-running processes such as web servers. An unbounded cache keyed on something with unbounded variety — a user id, a request path, a timestamp — is not a cache. It is a structure the program still references and never releases, which is the one category of leak a garbage collector cannot see.

The other failure is caching something that goes stale. A cache decides when to forget an entry by how recently it was used, and that has nothing to do with whether the underlying answer is still correct. Cache a lookup against data somebody else can change and the freshness of a result now depends on how popular it is — the most requested entries are the ones held longest, so the hottest keys serve the most out-of-date answers. Where correctness has a time limit, the eviction rule is the wrong tool for enforcing it, and the fix is an explicit invalidation rather than a smaller cache.