Why Repeated Calculations Hurt Performance

I often run into functions that recalculate the same values over and over. Whether it is Fibonacci numbers, binomial coefficients, or the result of a complex lookup, the same inputs keep returning the same outputs. Without any caching, the CPU spends cycles recomputing, and the call stack can grow deep enough to cause stack‑overflows or unacceptable latency in a service.

The classic answer to this problem is **memoization** – store the result of a function the first time it is called and return the stored value on subsequent calls. Python ships with a ready‑made memoizer in the standard library: functools.lru_cache. It is tiny, thread‑safe, and can be dropped onto an existing recursive routine with a single decorator.

Enter `lru_cache` – The Built‑in Memoizer

`lru_cache` implements an LRU (Least Recently Used) cache. When the cache reaches its size limit it evicts the least‑recently accessed entry, keeping memory usage bounded while still giving you O(1) lookup for hot values. The decorator works on any hashable arguments, which covers the vast majority of pure functions you will encounter in day‑to‑day code.

Using it is as simple as adding a line:

from functools import lru_cache

@lru_cache(maxsize=128)
def expensive_computation(x: int, y: int) -> int:
    """Perform a heavy calculation.

    In a real scenario this might query a remote API,
    parse a large file, or solve a recursive problem.
    """
    # Simulate work
    result = 0
    for i in range(x * y):
        result += i
    return result

The first call with a given pair of arguments will compute the result and store it. Later calls with the same pair hit the cache and return instantly. The cache is thread‑safe, so you can safely decorate a function that is called from multiple greenlets or OS threads.

A Practical Example: Fibonacci with Caching

Let’s look at the classic Fibonacci sequence. A naïve recursive implementation has exponential time complexity because it recomputes the same sub‑problems many times.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n: int) -> int:
    """Return the n‑th Fibonacci number.

    The decorator ensures each value is calculated only once.
    """
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

# Now this runs in linear time and constant extra space per distinct n.
for i in range(10, 30):
    print(i, fib(i))

Without the cache, the program would take seconds or minutes for n ≈ 30. With the cache, the same loop completes in a few milliseconds. The `maxsize=None` argument tells the cache to grow without bound – useful when the domain of inputs is known to be small and finite.

Real‑World Scenario: Binomial Coefficients in Data Science

In a data‑science pipeline I once built, we needed to compute binomial coefficients C(n, k) for many pairs while training a probabilistic model. The formula involves a factorial calculation that quickly becomes expensive for n > 30. By decorating a pure function with lru_cache, we turned a heavy routine into a lookup.

from functools import lru_cache
import math

@lru_cache(maxsize=1024)
def binomial(n: int, k: int) -> int:
    """Calculate C(n, k) using the multiplicative formula.

    The function is deterministic and hashable on its arguments,
    making it an ideal candidate for caching.
    """
    if k < 0 or k > n:
        return 0
    # Use symmetry to reduce calls
    k = min(k, n - k)
    result = 1
    for i in range(1, k + 1):
        result = result * (n - k + i) // i
    return result

# Later in the pipeline:
for n in range(50, 70):
    for k in range(n + 1):
        val = binomial(n, k)
        # feed val into model training...

Because the cache lives for the duration of the program, subsequent training runs (or even interactive exploration) benefit from the stored values, shaving minutes off each execution.

Fine‑Tuning Your Cache

`lru_cache` exposes a few knobs that are worth knowing:

  • maxsize – limits the number of entries. Use a finite value when the input space is large but only a few values are hot. Set to None for unlimited growth.
  • typed – if True, arguments of different types are cached separately. Useful when you want to distinguish 1 (int) from 1.0 (float).
  • cache_info() – returns a named tuple with hits, misses, maxsize, currsize. Helpful for monitoring cache effectiveness.

Here is a quick example of inspecting the cache:

@lru_cache(maxsize=8, typed=True)
def greet(name: str, formal: bool) -> str:
    return "Dr. " + name if formal else "Hi, " + name

print(greet("Alice", False))   # cache miss
print(greet("Alice", False))   # cache hit
print(greet.cache_info())      # CacheInfo(hits=1, misses=1, maxsize=8, currsize=1)
\n

Thread safety note: The cache is implemented with a lock, so you can safely decorate a function that is called from multiple threads without additional synchronization.

When to Use – And When Not To

Memoization shines when:

  1. The function is **pure** – same inputs always produce the same output and there are no side effects.
  2. Inputs are **hashable** – typical for numbers, strings, tuples of immutables.
  3. You have **repeated sub‑problems**, such as recursive algorithms, combinatorial calculations, or repeated remote lookups.

Avoid caching when:

  • The function has **mutable arguments** – they cannot be stored in a dict.
  • The result is **large** and you risk blowing memory – consider a bounded maxsize or an external store.
  • You need **strict LRU behavior** with custom eviction policies – `lru_cache` is a good default but not a full‑featured cache server.

In those edge cases you might reach for a dedicated caching library like cachetools or a Redis backend.

Putting It All Together – A Small Utility

Below is a tiny utility I keep in a utils.py module. It wraps any pure function with a cached version, exposing the underlying cache info for debugging.

from functools import lru_cache
from typing import Callable, Any, Dict, Tuple

class CachedFunction:
    """A simple wrapper that adds an LRU cache to a callable.

    This can be handy for ad‑hoc memoization without cluttering the
    original function definition with decorators.
    """
    def __init__(self, func: Callable[..., Any]):
        self._func = func
        self._cache: Dict[Tuple[Any, ...], Any] = {}
        self._hits = self._misses = 0

    def __call__(self, *args: Any) -> Any:
        key = args
        if key in self._cache:
            self._hits += 1
            return self._cache[key]
        self._misses += 1
        result = self._func(*args)
        self._cache[key] = result
        return result

    def cache_info(self) -> Tuple[int, int, int]:
        return self._hits, self._misses, len(self._cache)

    def clear(self) -> None:
        self._cache.clear()
        self._hits = self._misses = 0

# Example usage:
my_cached_sqrt = CachedFunction(lambda x: int(x ** 0.5))
print(my_cached_sqrt(9))   # 3, miss
print(my_cached_sqrt(9))   # 3, hit
print(my_cached_sqrt.cache_info())  # (1, 1, 1)

Even though `lru_cache` already does most of this, the wrapper demonstrates how you can extract the pattern into a reusable component when you need custom statistics or integration with other tooling.

Wrap‑Up

Memoization is a timeless technique, and `functools.lru_cache` gives you a production‑ready implementation that requires almost no boilerplate. By decorating pure functions with it you instantly gain O(1) lookups for repeated calls, which translates into faster response times and lower CPU usage. Remember to pick an appropriate maxsize, watch cache hits versus misses, and respect the hashability of arguments. When those conditions line up, `lru_cache` becomes the silent workhorse that lets you focus on solving the problem rather than recomputing the same answer over and over.

Next time you spot a recursive routine that feels slow, drop a `@lru_cache` decorator on it and see the difference. You might be surprised how much simpler your code becomes.