How does functools.lru_cache work internally?

It pairs a dict with a circular doubly linked list. The dict maps each call key to a link node, giving O(1) lookup; the linked list orders nodes by recency, giving O(1) move-to-front on a hit and O(1) eviction of the oldest. Each node is a 4-element list [PREV, NEXT, KEY, RESULT], and a sentinel "root" node closes the ring. On a hit the node is unhooked and spliced in just before the root (the most-recently-used position); on a miss when the cache is full, the oldest node (root.NEXT) is reused in place to hold the new key and result, so nothing is allocated or freed on the hot path.

Is functools.lru_cache thread-safe?

Yes, for the bounded cache. The size-limited wrapper does all of its linked-list surgery inside a single RLock, because — as the source comment says — "linkedlist updates aren't threadsafe." The unbounded (maxsize=None) path uses no lock and relies on individual dict operations being atomic under the GIL. What lru_cache does NOT do is single-flight: if two threads miss on the same key at the same moment, both run the wrapped function, because the lock is released while the user function runs. It is thread-safe, not deduplicating.

What happens if two threads call an lru_cache-wrapped function with the same missing key at once?

The wrapped function runs twice. Both threads build the key, take the lock, see a miss, and release the lock before calling the user function — so both compute concurrently. When they re-acquire the lock to store their results, the first inserts the link and the second hits the guard "if key in cache: pass," which detects that the key was added while the lock was released and simply returns its own already-computed value. The cache ends with one entry, but the expensive function ran twice. lru_cache is honest about this: it protects the data structure, not the computation.

Why does lru_cache reuse the oldest node instead of allocating a new one?

To avoid churn on the hot path. When the cache is full, evicting the oldest and inserting a new key would mean freeing one node and allocating another on every miss. Instead the code repurposes the oldest link (root.NEXT) as the new root and writes the new key/result into the old root — the same nodes are recycled in a ring of fixed size. The source is careful to keep references to the outgoing key and result during the swap so their reference counts do not hit zero mid-update, which would let arbitrary __del__ code run while the links are in an inconsistent state.

How does lru_cache build the cache key from arguments?

With _make_key, which flattens the positional args, a separator, and the keyword items into one flat tuple — "flat as possible rather than a nested structure that would take more memory." If typed=True it also appends the argument types so f(3) and f(3.0) cache separately. As a fast path, a single int or str argument is used directly as the key with no wrapper. Otherwise the tuple is wrapped in _HashedSeq, a list subclass that caches its own hash so the key is hashed only once even though the miss path looks it up several times.

functools.lru_cache, Line by Line

The canonical interview prompt — build a thread-safe LRU cache with O(1) get and put — answered in production Python. Walk the real functools.py: the flattened key, the circular doubly linked list, the pointer surgery that moves a hit to the front, the reuse-the-oldest-node eviction trick, and the one RLock that keeps it all consistent.

Code walk · Languages & Runtimes. The source ↗

A free, interactive, animated visual explainer of functools.lru_cache, Line by Line — built to be understood, not skimmed.

Questions

How does functools.lru_cache work internally?: It pairs a dict with a circular doubly linked list. The dict maps each call key to a link node, giving O(1) lookup; the linked list orders nodes by recency, giving O(1) move-to-front on a hit and O(1) eviction of the oldest. Each node is a 4-element list [PREV, NEXT, KEY, RESULT], and a sentinel "root" node closes the ring. On a hit the node is unhooked and spliced in just before the root (the most-recently-used position); on a miss when the cache is full, the oldest node (root.NEXT) is reused in place to hold the new key and result, so nothing is allocated or freed on the hot path.
Is functools.lru_cache thread-safe?: Yes, for the bounded cache. The size-limited wrapper does all of its linked-list surgery inside a single RLock, because — as the source comment says — "linkedlist updates aren't threadsafe." The unbounded (maxsize=None) path uses no lock and relies on individual dict operations being atomic under the GIL. What lru_cache does NOT do is single-flight: if two threads miss on the same key at the same moment, both run the wrapped function, because the lock is released while the user function runs. It is thread-safe, not deduplicating.
What happens if two threads call an lru_cache-wrapped function with the same missing key at once?: The wrapped function runs twice. Both threads build the key, take the lock, see a miss, and release the lock before calling the user function — so both compute concurrently. When they re-acquire the lock to store their results, the first inserts the link and the second hits the guard "if key in cache: pass," which detects that the key was added while the lock was released and simply returns its own already-computed value. The cache ends with one entry, but the expensive function ran twice. lru_cache is honest about this: it protects the data structure, not the computation.
Why does lru_cache reuse the oldest node instead of allocating a new one?: To avoid churn on the hot path. When the cache is full, evicting the oldest and inserting a new key would mean freeing one node and allocating another on every miss. Instead the code repurposes the oldest link (root.NEXT) as the new root and writes the new key/result into the old root — the same nodes are recycled in a ring of fixed size. The source is careful to keep references to the outgoing key and result during the swap so their reference counts do not hit zero mid-update, which would let arbitrary __del__ code run while the links are in an inconsistent state.
How does lru_cache build the cache key from arguments?: With _make_key, which flattens the positional args, a separator, and the keyword items into one flat tuple — "flat as possible rather than a nested structure that would take more memory." If typed=True it also appends the argument types so f(3) and f(3.0) cache separately. As a fast path, a single int or str argument is used directly as the key with no wrapper. Otherwise the tuple is wrapped in _HashedSeq, a list subclass that caches its own hash so the key is hashed only once even though the miss path looks it up several times.

functools.lru_cache, Line by Line

Questions

Related explainers