A tiny LRU cache, from scratch

Python gives you an LRU cache for free:

from functools import lru_cache

@lru_cache(maxsize=256)
def expensive(x: int) -> int:
    ...

That’s the right answer in production. But “least recently used” is one of those ideas that feels obvious until you try to implement it, so let’s build one — partly for fun, mostly because the implementation is a beautiful use of a data structure you already know.

The trick is the dict

Since Python 3.7, dictionaries preserve insertion order. That’s the whole trick. An LRU cache needs two operations to be fast:

• Look up a key, and mark it as recently used.
• Evict the oldest key when the cache is full.

An ordered dict gives you both. “Mark as recently used” is just delete and re-insert — the key moves to the end. “Evict the oldest” is pop the first key. Both are O(1).

class LRUCache:
    def __init__(self, maxsize: int = 256):
        self.maxsize = maxsize
        self._data: dict = {}

    def get(self, key):
        if key not in self._data:
            raise KeyError(key)
        value = self._data.pop(key)   # remove...
        self._data[key] = value       # ...and re-insert at the end
        return value

    def put(self, key, value) -> None:
        if key in self._data:
            self._data.pop(key)
        elif len(self._data) >= self.maxsize:
            oldest = next(iter(self._data))
            del self._data[oldest]
        self._data[key] = value

Twenty lines. The recently-used order is the dict’s insertion order; we never store it separately, so it can never go stale.

Why the real one is different

CPython’s lru_cache is implemented in C with a doubly linked list threaded through the hash table entries, plus a lock for thread safety. The linked list avoids the pop-and-reinsert dance — it just splices nodes. Same idea, fewer allocations.

The best way to appreciate a standard library function is to write a worse version of it yourself.

If you want homework: add a hits / misses counter and a cache_info() method, then compare your numbers against the real decorator on the same workload. They should match exactly — and if they don’t, finding out why is where the actual learning is.