Memoization with functools: cache vs lru_cache

Memoization with functools: cache vs lru_cache

Memoization is an optimization technique central to top-down dynamic programming, where expensive function call results are cached and reused to avoid redundant computations. In Python 3.12+, the functools module provides two primary decorators for implementing memoization: @functools.cache for unbounded caching and @functools.lru_cache for bounded caching with least-recently-used (LRU) eviction. This section defines these decorators, contrasts their functionality, and demonstrates their application through idiomatic code examples, performance analysis, and debugging strategies, enabling readers to select the appropriate tool based on problem constraints such as input space size and memory management needs.

Definition and Core Functionality

The functools.cache decorator, introduced in Python 3.9, provides an unbounded cache without eviction, automating memoization by storing all unique argument combinations indefinitely. It is defined as a decorator that wraps a function, returning a callable with the same signature but enhanced caching behavior. In contrast, functools.lru_cache implements a bounded cache configurable via the maxsize parameter, defaulting to 128, which evicts the least-recently-used entries when the cache exceeds this limit, thereby managing memory usage in long-running applications. Both decorators require arguments to be hashable—a property ensuring objects can serve as dictionary keys, typically met by immutable types like tuples, strings, or dataclasses with frozen=True. Additionally, lru_cache supports a typed parameter; when set to True, it creates distinct cache entries for arguments of different types, preventing collisions between, for example, integer 3 and float 3.0. The cache_info() method, available on functions decorated with either @cache or @lru_cache, returns a named tuple with fields for hits, misses, maxsize, and currsize, facilitating hit rate calculation as hits / (hits + misses) and debugging cache performance.

Examples Demonstrating Usage and Integration

To illustrate practical application, consider the Fibonacci sequence, a classic example where naive recursion has exponential time complexity O(2^n). Using @cache, time reduces to O(n) after caching, with O(n) space for the recursion stack and cache storage. The following code examples, written exclusively in Python 3.12+ with strict type hints, demonstrate this and other scenarios, adhering to idiomatic practices by preferring @cache or @lru_cache over manual memoization dictionaries.

from functools import cache, lru_cache
from dataclasses import dataclass
from typing import Tuple
import tracemalloc

# Example 1: @cache vs @lru_cache for Fibonacci
@cache
def fib_cache(n: int) -> int:
    """Fibonacci using @cache, O(n) time after caching, O(n) space."""
    if n <= 1:
        return n
    return fib_cache(n - 1) + fib_cache(n - 2)

@lru_cache(maxsize=128)
def fib_lru(n: int) -> int:
    """Fibonacci using @lru_cache with bounded size, O(n) time, bounded memory."""
    if n <= 1:
        return n
    return fib_lru(n - 1) + fib_lru(n - 2)

# Example 2: Cache info and hit rate calculation
print(f"Cache info for fib_cache: {fib_cache.cache_info()}")
hits, misses, _, _ = fib_cache.cache_info()
hit_rate = hits / (hits + misses) if (hits + misses) > 0 else 0.0
print(f"Hit rate: {hit_rate:.2f}")

# Example 3: Dataclass key with frozen=True
@dataclass(frozen=True)
class StateKey:
    x: int
    y: int

@cache
def compute_with_key(key: StateKey) -> int:
    """Function using dataclass as hashable key."""
    return key.x + key.y

# Example 4: Memory profiling with tracemalloc
def profile_memory() -> None:
    tracemalloc.start()
    for i in range(1000):
        fib_cache(i % 50)  # Simulate calls with @cache
    current, peak = tracemalloc.get_traced_memory()
    print(f"@cache memory: current={current}, peak={peak}")
    tracemalloc.stop()
    tracemalloc.start()
    for i in range(1000):
        fib_lru(i % 50)  # Simulate calls with @lru_cache
    current, peak = tracemalloc.get_traced_memory()
    print(f"@lru_cache memory: current={current}, peak={peak}")
    tracemalloc.stop()

# Example 5: typed=True demonstration
@lru_cache(maxsize=128, typed=True)
def typed_func(arg: int | float) -> str:
    """Separate caches for int and float due to typed=True."""
    return f"Type: {type(arg).__name__}"

# Naive approach: Global dict (anti-pattern)
cache_dict: dict[Tuple[int, int], int] = {}
def fib_naive_dict(n: int) -> int:
    if n <= 1:
        return n
    if n in cache_dict:
        return cache_dict[n]
    result = fib_naive_dict(n - 1) + fib_naive_dict(n - 2)
    cache_dict[n] = result
    return result

# Refactor to idiomatic using @cache
@cache
def fib_idiomatic(n: int) -> int:
    """Idiomatic refactor, clearer and less error-prone."""
    if n <= 1:
        return n
    return fib_idiomatic(n - 1) + fib_idiomatic(n - 2)

These examples integrate all provided primary materials, showcasing the transition from naive implementations to idiomatic Python, while incorporating dataclasses for structured keys and tracemalloc for memory profiling to verify bounded versus unbounded growth.

Performance Comparison and Eviction Behavior

The functional differences between @cache and @lru_cache are summarized in the following performance comparison table, which highlights trade-offs in eviction policy, memory usage, and suitability for various use cases.

Aspect	@cache	@lru_cache
Eviction Policy	None (unbounded)	Least-Recently-Used (bounded)
Maxsize	Implicitly None	Configurable (e.g., maxsize=128)
Memory Usage	Unbounded, grows with unique calls	Bounded, evicts old entries when full
Time Complexity per Call	O(1) after caching	O(1) after caching, with O(1) eviction overhead
Space Complexity	O(n) where n is unique argument count	O(maxsize) bounded
Use Case	Small, finite input spaces or short-lived caches	Large input spaces, long-running applications
Thread Safety	Not thread-safe by default	Not thread-safe by default
Cache Info Available	Yes, via cache_info()	Yes, via cache_info()
typed Parameter Support	No (always untyped)	Yes, typed=True for type distinction

This table underscores that @cache is optimal for scenarios with limited, predictable input ranges, while @lru_cache excels in environments requiring memory management, such as long-running servers or applications processing large or infinite data streams.

Type Annotations and Structural Considerations

Type annotations for caching decorators enhance code clarity and type safety. The @cache decorator has a signature akin to def cache(func: Callable[..., T]) -> Callable[..., T], returning a wrapped function with identical type parameters. For @lru_cache, the signature includes optional parameters: def lru_cache(maxsize: int | None = 128, typed: bool = False) -> Callable[[Callable[..., T]], Callable[..., T]]. When caching multi-argument functions, tuples serve as hashable keys, e.g., Tuple[int, int] for state in problems like longest common subsequence. Dataclasses with frozen=True, such as StateKey in the examples, automatically generate __hash__ and __eq__ methods, ensuring compatibility with caching decorators. The return type of cache_info() is a named tuple with fields hits: int, misses: int, maxsize: int | None, and currsize: int, facilitating performance monitoring.

Complexity Analysis and Algorithmic Impact

Caching fundamentally alters the time and space complexity of recursive algorithms. Without caching, naive recursion for Fibonacci exhibits O(2^n) time complexity due to exponential recomputation. With @cache or @lru_cache, time reduces to O(n) after initial caching, as each unique argument is computed once and stored, leading to O(1) average lookup time per subsequent call. Space complexity diverges: @cache requires O(u) memory, where u is the count of unique argument combinations, potentially unbounded; @lru_cache bounds this to O(maxsize), evicting entries when the limit is exceeded. Recursion stack space remains O(n) for deep calls, independent of caching. Memory profiling overhead with tracemalloc is negligible, adding O(1) per allocation, while eviction in @lru_cache operates in O(1) time per removal.

Anti-Patterns and Corrective Measures

Common anti-patterns in memoization can undermine code reliability and performance. The following list identifies these pitfalls and aligns corrective actions with idiomatic Python practices:

1. Using global dictionaries for memoization: Error-prone due to manual key management and lack of bounds. Fix: Replace with @cache or @lru_cache.
2. Mutable default arguments in cached functions: Can cause shared state and incorrect caching. Fix: Use None with conditional initialization, e.g., def func(arg: list[int] | None = None) -> int: if arg is None: arg = [].
3. Ignoring hashability of arguments: Leads to TypeError if unhashable types like lists are used as keys. Fix: Convert to immutable types such as tuples.
4. Not using cache_info() for debugging: Misses insights into hit rates and performance. Fix: Regularly call cache_info() and monitor metrics.
5. Overusing @cache on large input spaces: Risks memory blow-up. Fix: Switch to @lru_cache with an appropriate maxsize.
6. Manual index loops in caching logic: Reduces readability. Fix: Employ iterators, enumerate, or tuple unpacking.
7. Skipping type hints: Compromises type safety and maintainability. Fix: Adhere to strict type annotations as per style guide rules.

These corrections emphasize the shift from naive, Java-style implementations to Pythonic solutions that leverage built-in decorators and modern typing features.

Production Gotchas and Mitigation Strategies

Deploying caching decorators in production environments introduces challenges that require proactive management. Key gotchas include:

1. Memory blow-up with @cache: Unbounded growth can trigger out-of-memory errors in long-running applications. Mitigation: Use @lru_cache with a configured maxsize or implement periodic cache clearing.
2. Thread-unsafety: Neither @cache nor @lru_cache are thread-safe by default; concurrent modifications may cause race conditions. Mitigation: Employ threading locks or atomic operations for synchronization.
3. Hash computation overhead: Complex keys, such as large dataclasses, can slow caching due to expensive __hash__ methods. Mitigation: Optimize __hash__ implementations or use simpler key structures.
4. Version compatibility: @cache is available only in Python 3.9+; using it in older versions results in errors. Mitigation: Verify Python version or utilize backports like functools.lru_cache(maxsize=None) as a substitute.
5. Static analyzer issues: Tools like mypy may flag caching decorators without precise type hints. Mitigation: Ensure function signatures are fully annotated with generics and protocols where applicable.
6. Cache invalidation challenges: Cached results may become stale if external data changes. Mitigation: Implement invalidation strategies, such as time-to-live (TTL) caches or manual cache clearing.
7. State evolution: Caching decorators do not handle mutable state changes in arguments. Mitigation: Use immutable arguments or clear the cache upon state updates.

Addressing these issues ensures robust, scalable caching in real-world scenarios, balancing performance gains with system stability.

Conclusion and Verification through Memory Profiling

Selecting between @cache and @lru_cache hinges on problem constraints: @cache suits small, finite input spaces where memory growth is acceptable, while @lru_cache is preferable for large or unbounded inputs, leveraging LRU eviction to cap memory usage. Verification involves profiling memory with tools like tracemalloc, as demonstrated in the examples, to compare unbounded growth under @cache versus bounded behavior with @lru_cache. By integrating type-safe code, monitoring cache statistics via cache_info(), and avoiding anti-patterns, developers can harness memoization effectively within dynamic programming frameworks, ensuring optimal performance and maintainability in Python 3.12+ applications.