TopolearnHigh-traffic services rely on caches behaving predictably under concurrency.
CPython's lru_cache is implemented in C (_functools._lru_cache_wrapper), with a pure-Python fallback that documents the algorithm:
- Keys:
_make_keyflattens positional args, a marker, then keyword items into a flat tuple (with types appended iftyped=True). A single argument of type int or str is used directly as the key, a fast path. - Storage: a dict maps keys to links in a circular doubly linked list. A hit moves the link to the front; when the cache is full, a miss reuses the oldest link. Both are O(1). The unbounded variant skips the linked list entirely.
- Hashing happens once per call; arguments with expensive
__hash__make every call expensive.
Thread safety: the cache's internal structures stay consistent when used from several threads. But the wrapped function is called without holding a lock, so two threads that miss on the same key concurrently both compute the value, and the last one to finish is stored. For expensive or side-effecting computations that must run once, add a per-key lock or use a single-flight pattern.
On the free-threaded 3.13 build, the C implementation uses critical sections to protect its state; the "may compute twice" behaviour remains.
cached_property similarly has no lock since 3.12, for the same reason: the old class-wide lock serialised all instances.
Example
import threading
import time
from functools import lru_cache
calls = []
@lru_cache(maxsize=None)
def slow_square(n):
calls.append(n)
time.sleep(0.1) # simulate an expensive call
return n * n
def run_threads(fn, arg, n=3):
ts = [threading.Thread(target=fn, args=(arg,)) for _ in range(n)]
for t in ts: t.start()
for t in ts: t.join()
run_threads(slow_square, 7)
print(len(calls) > 1) # True: concurrent misses computed it again
locks, guard = {}, threading.Lock()
def once(n): # single-flight wrapper
with guard:
lock = locks.setdefault(n, threading.Lock())
with lock:
return slow_square(n)
calls.clear(); slow_square.cache_clear()
run_threads(once, 8)
print(calls) # [8]Remember
- lru_cache is a C dict plus a linked list: O(1) hits, misses and evictions
- Its state is thread-safe, but concurrent misses can call the function more than once
- Add per-key locking when a computation must happen exactly once
Watch out for
- Using lru_cache to guarantee an expensive initialisation runs only once across threads.