functools.lru_cache

The @lru_cache decorator provides memoization with a Least Recently Used eviction policy. It caches function results and automatically removes the oldest entries when the cache reaches its size limit.

from functools import lru_cache

---

Basic Usage

from functools import lru_cache

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

# Without cache: exponential time O(2^n)
# With cache: linear time O(n)
print(fibonacci(100))  # Instant!

---

maxsize Options

The maxsize parameter controls cache behavior:

from functools import lru_cache

# maxsize=128 (default) — LRU eviction when full
@lru_cache(maxsize=128)
def func1(x):
    return x ** 2

# maxsize=None — unlimited cache, never evicts
@lru_cache(maxsize=None)
def func2(x):
    return x ** 2

# maxsize=0 — no caching (useful for testing)
@lru_cache(maxsize=0)
def func3(x):
    return x ** 2

# Without parentheses (Python 3.8+) — uses default maxsize=128
@lru_cache
def func4(x):
    return x ** 2

How LRU Eviction Works

@lru_cache(maxsize=3)
def process(x):
    print(f"  Computing {x}")
    return x ** 2

process(1)  # Computing 1 → cache: [1]
process(2)  # Computing 2 → cache: [1, 2]
process(3)  # Computing 3 → cache: [1, 2, 3]
process(1)  # Cache hit    → cache: [2, 3, 1] (1 moved to end)
process(4)  # Computing 4  → cache: [3, 1, 4] (2 evicted — least recently used)
process(2)  # Computing 2  → cache: [1, 4, 2] (3 evicted)

---

Cache Management Methods

Every decorated function gains three methods:

cache_info()

from functools import lru_cache

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

square(1)
square(2)
square(1)  # Cache hit
square(3)

info = square.cache_info()
print(info)
# CacheInfo(hits=1, misses=3, maxsize=128, currsize=3)

print(info.hits)      # 1  — number of cache hits
print(info.misses)    # 3  — number of cache misses
print(info.maxsize)   # 128 — maximum cache size
print(info.currsize)  # 3  — current number of cached entries

cache_clear()

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

compute(1)
compute(2)
print(compute.cache_info().currsize)  # 2

compute.cache_clear()
print(compute.cache_info().currsize)  # 0

cache_parameters() (Python 3.9+)

@lru_cache(maxsize=256, typed=True)
def func(x):
    return x ** 2

print(func.cache_parameters())
# {'maxsize': 256, 'typed': True}

---

typed Parameter

By default, arguments of different types that compare equal share cache entries:

from functools import lru_cache

@lru_cache(maxsize=128)
def compute(x):
    print(f"  Computing {x} ({type(x).__name__})")
    return x * 2

compute(3)    # Computing 3 (int)
compute(3.0)  # No output — cache hit! (3 == 3.0)

With typed=True, different types get separate entries:

@lru_cache(maxsize=128, typed=True)
def compute(x):
    print(f"  Computing {x} ({type(x).__name__})")
    return x * 2

compute(3)    # Computing 3 (int)
compute(3.0)  # Computing 3.0 (float) — separate entry

---

Argument Requirements

Must Be Hashable

All arguments must be hashable because lru_cache uses them as dictionary keys:

@lru_cache
def process(data):
    return sum(data)

# Works: hashable types
process((1, 2, 3))        # tuple — OK
process("hello")          # str — OK
process(frozenset({1}))   # frozenset — OK

# Fails: unhashable types
# process([1, 2, 3])      # TypeError: unhashable type: 'list'
# process({1, 2, 3})      # TypeError: unhashable type: 'set'
# process({'a': 1})       # TypeError: unhashable type: 'dict'

Converting Unhashable Arguments

from functools import lru_cache

# Strategy 1: Wrapper that converts to tuple
def process_list(items):
    return _process(tuple(items))

@lru_cache(maxsize=128)
def _process(items):
    return sum(items)

# Strategy 2: Convert dict to frozenset of items
def process_dict(d):
    return _process_dict(frozenset(d.items()))

@lru_cache(maxsize=128)
def _process_dict(items):
    return dict(items)

---

Practical Examples

Recursive Dynamic Programming

from functools import lru_cache

@lru_cache(maxsize=None)
def coin_change(amount, coins):
    """Minimum coins needed for amount."""
    if amount == 0:
        return 0
    if amount < 0:
        return float('inf')

    return 1 + min(
        coin_change(amount - coin, coins)
        for coin in coins
    )

coins = (1, 5, 10, 25)
print(coin_change(67, coins))  # 7

Expensive Computation

from functools import lru_cache

@lru_cache(maxsize=1000)
def expensive_query(user_id, date):
    """Cache database results for repeated queries."""
    return fetch_from_database(user_id, date)

# First call: hits database
result1 = expensive_query("user_123", "2024-01-01")

# Second call: returns cached result
result2 = expensive_query("user_123", "2024-01-01")

Web API Response Caching

from functools import lru_cache
import json

@lru_cache(maxsize=256)
def get_exchange_rate(base, target):
    """Cache exchange rates (limited domain)."""
    response = requests.get(f"https://api.example.com/rate/{base}/{target}")
    return response.json()['rate']

# Avoids repeated API calls for same currency pair
rate = get_exchange_rate("USD", "EUR")

Recursive String Operations

from functools import lru_cache

@lru_cache(maxsize=None)
def edit_distance(s1, s2):
    """Levenshtein distance between two strings."""
    if not s1:
        return len(s2)
    if not s2:
        return len(s1)

    if s1[0] == s2[0]:
        return edit_distance(s1[1:], s2[1:])

    return 1 + min(
        edit_distance(s1[1:], s2),      # delete
        edit_distance(s1, s2[1:]),      # insert
        edit_distance(s1[1:], s2[1:])   # replace
    )

print(edit_distance("kitten", "sitting"))  # 3

---

lru_cache vs cache

Feature	@lru_cache	@cache
Python version	3.2+	3.9+
Cache size	Configurable (default 128)	Unlimited
Eviction	LRU (Least Recently Used)	Never
Memory	Bounded	Grows forever
typed parameter	Yes	No
Use case	Large/unknown domains	Small domains, recursive

from functools import lru_cache, cache

# Equivalent:
@cache
def func1(x): ...

@lru_cache(maxsize=None)
def func2(x): ...

Decision guide:

• Use @cache for recursive algorithms with bounded input (fibonacci, DP)
• Use @lru_cache(maxsize=N) for functions with large/unbounded input domains
• Use @lru_cache(maxsize=None) as a pre-3.9 equivalent of @cache

---

Memory Considerations

Monitoring Cache Size

@lru_cache(maxsize=1000)
def process(x):
    return x ** 2

for i in range(5000):
    process(i)

info = process.cache_info()
print(f"Size: {info.currsize}/{info.maxsize}")  # Size: 1000/1000
print(f"Hit rate: {info.hits / (info.hits + info.misses):.1%}")

Tuning maxsize

# Too small: many evictions, low hit rate
@lru_cache(maxsize=10)
def func(x): ...

# Too large: wastes memory
@lru_cache(maxsize=1_000_000)
def func(x): ...

# Strategy: monitor hit rate and adjust
# Good hit rate (>80%) → maxsize is adequate
# Low hit rate (<50%) → increase maxsize or rethink caching

Clearing Cache for Long-Running Processes

@lru_cache(maxsize=1000)
def compute(x):
    return expensive_operation(x)

def process_batch(items):
    results = [compute(item) for item in items]
    # Clear cache between batches to free memory
    compute.cache_clear()
    return results

---

Thread Safety

lru_cache is thread-safe. The underlying dictionary is protected by a lock:

from functools import lru_cache
from concurrent.futures import ThreadPoolExecutor

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

# Safe to call from multiple threads
with ThreadPoolExecutor(max_workers=4) as executor:
    results = list(executor.map(compute, range(100)))

However, the decorated function itself may still have race conditions if it has side effects.

---

Common Pitfalls

Caching Functions with Side Effects

@lru_cache
def log_and_compute(x):
    print(f"Computing {x}")  # Side effect: only executes on cache miss
    return x ** 2

log_and_compute(5)  # "Computing 5" — printed
log_and_compute(5)  # Nothing printed — cached result returned

Methods and self

class MyClass:
    @lru_cache(maxsize=128)  # Caution: self is part of the cache key
    def compute(self, x):
        return x ** 2

# Each instance has separate cache entries
# AND instances are kept alive by cache references!

Solution: use __hash__ carefully or prefer cached_property for instance methods.

Mutable Default State

# The cache does NOT detect changes to external state
data = [1, 2, 3]

@lru_cache
def process(index):
    return data[index]  # Caches based on index, not data contents

process(0)      # Returns 1
data[0] = 999
process(0)      # Still returns 1 (cached!)

---

Implementation Details

• Uses a doubly-linked list for O(1) LRU operations
• Uses a dictionary for O(1) lookups
• Cache key is (args, kwargs) converted to a hashable form
• maxsize should be a power of 2 for best performance (internal hash table sizing)

# Optimal maxsize values
@lru_cache(maxsize=64)    # 2^6
@lru_cache(maxsize=128)   # 2^7 (default)
@lru_cache(maxsize=256)   # 2^8
@lru_cache(maxsize=1024)  # 2^10

---

Summary

Feature	Details
Import	from functools import lru_cache
Python version	3.2+
Default maxsize	128
Eviction policy	Least Recently Used
Arguments	Must be hashable
Thread safe	Yes
Methods	.cache_info(), .cache_clear(), .cache_parameters()

Key Takeaways:

• @lru_cache provides bounded memoization with automatic LRU eviction
• Set maxsize based on expected input domain (power of 2 is optimal)
• Monitor hit rate with cache_info() to tune maxsize
• Use typed=True when int and float arguments need separate cache entries
• Arguments must be hashable — convert lists to tuples, dicts to frozensets
• Thread-safe but beware of side effects in the cached function
• For unlimited caching, use @cache (Python 3.9+) or @lru_cache(maxsize=None)