python lru_cache: Efficient Memoization

When a function is called repeatedly with the same arguments, recomputing the result wastes time. The functools.lru_cache decorator stores results keyed by arguments, returning cached values on repeated calls. This is a direct way to add memoization to pure functions without external dependencies.

What python lru_cache Does

The decorator wraps a function with a cache that maps call arguments to return values. On each call, it computes a hash of the arguments, checks the cache, and returns the stored result if present. Otherwise it executes the function and stores the result before returning.

from functools import lru_cache

@lru_cache(maxsize=128)
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

The first call with a given n runs the function; subsequent calls with the same n hit the cache. This reduces the time complexity of recursive algorithms like Fibonacci from exponential to linear, at the cost of memory for stored results.

Parameters: maxsize and typed

The maxsize parameter controls how many results are kept. When the cache reaches that limit, the least recently used entry is evicted. Setting maxsize=None creates an unbounded cache, which can grow without limit and should be used only when the number of distinct arguments is small and known.

The typed parameter, when True, separates results for arguments of different types. For example, 1 and 1.0 are considered distinct keys when typed=True, even though they compare equal. This matters when the function's behavior depends on the exact type, such as when using isinstance internally.

@lru_cache(maxsize=10, typed=True)
def parse(value):
    return int(value)

With typed=True, calls with parse(1) and parse(1.0) produce separate cache entries, which can be useful when the function returns different types or handles numeric types differently.

How Cache Eviction Works

The cache maintains an order based on recency of access. Every time a cached result is retrieved, that entry is moved to the most-recently-used position. When a new entry is added and the cache is full, the least-recently-used entry is removed. This ensures that frequently accessed results stay available while rarely used ones are discarded.

This eviction policy is appropriate when recent usage predicts future usage. If the working set of arguments changes over time, the LRU policy adapts automatically. For a fixed set of arguments, an unbounded cache avoids eviction overhead but may consume more memory.

Handling Unhashable Arguments

The cache key is derived from a hash of the arguments, so all arguments must be hashable. Mutable objects like lists, dictionaries, and sets are not hashable and will raise a TypeError when passed to a function decorated with lru_cache. This is a common pitfall.

@lru_cache(maxsize=32)
def process(items):
    return sum(items)

process([1, 2, 3])  # TypeError: unhashable type: 'list'

To work around this, convert mutable arguments to an immutable form before calling the function. For example, use a tuple instead of a list, or a frozenset instead of a set. If the argument is a custom object, ensure it implements __hash__ and __eq__ appropriately.

Using lru_cache with Methods

Applying lru_cache directly to a method stores the cache on the function object, not per instance. This means the cache is shared across all instances of the class, and the self argument is included in the cache key. If the method's result depends on instance state, the cache will be invalid because self is hashable by default (using id), but two distinct instances with the same state will have different keys.

A better pattern is to use lru_cache on a static method or to manually manage the cache per instance. For methods that depend only on arguments and not on instance state, you can place the cache on the method itself, but be aware that the cache persists for the lifetime of the class.

class Calculator:
    @staticmethod
    @lru_cache(maxsize=64)
    def square(x):
        return x * x

Here, square is a static method, so self is not part of the cache key. If you need per-instance caching, consider storing a dictionary in self and checking it manually, or use a separate cache keyed by (id(self), args) with careful cleanup.

Thread Safety and Concurrency

The lru_cache decorator is thread-safe in CPython because the cache operations are protected by an internal lock. Multiple threads can call the decorated function concurrently without corrupting the cache. However, the function body itself is not serialized; if the underlying function has side effects or is not thread-safe, concurrent calls may still race.

For pure functions, this means you can safely use lru_cache in multi-threaded code without additional locking. The lock is held only during cache lookup and insertion, not during the function execution. This reduces contention but means the same argument may be computed more than once if two threads miss the cache simultaneously. This is usually acceptable for expensive pure functions.

Memory and Performance Considerations

Every cached result occupies memory until evicted. The maxsize parameter directly bounds memory usage, but choosing the right value depends on the number of distinct arguments and the size of each result. A large maxsize can lead to high memory consumption if results are large objects.

Caching also adds overhead for cache lookup and hashing. For functions that are very fast, the overhead may dominate and negate the benefit. Measure the function's execution time and the expected call frequency before applying lru_cache. If the function is simple and called infrequently, caching may not be worth the memory cost.

Another subtlety is that the cache holds strong references to arguments and results. This can prevent garbage collection of objects that would otherwise be freed. For long-lived caches with mutable or large objects, consider using a weak reference cache or manually clearing the cache with cache_clear() when appropriate.

lru_cache also exposes cache_info() for monitoring hits, misses, and current size. This is useful for tuning maxsize in production. For example, you can log the cache info periodically to see if the cache is thrashing or underutilized.

@lru_cache(maxsize=128)
def compute(x):
    return x * 2

compute(1)
compute(1)
print(compute.cache_info())  # CacheInfo(hits=1, misses=1, maxsize=128, currsize=1)

Use this data to adjust the cache size based on actual usage patterns rather than guessing.