🎓 A1Learner
🔍

Python Caching With lru_cache

Caching stores a result so a later call can reuse it.

Plain recursion repeats the work

The counter counts every call the plain function makes.

calls = 0

def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))
print(calls)

Remember an answer by hand

A dict makes a fine first cache. Its keys are inputs, and its values are stored answers.

cache = {}


def square(n):
    if n in cache:
        return cache[n]
    result = n * n
    cache[n] = result
    return result


print(square(4))
print(square(4))
print(cache)

Let lru_cache do the remembering

The letters LRU stand for least recently used. The second call with 4 prints no working line, because its answer is cached.

from functools import lru_cache


@lru_cache
def square(n):
    print("Working out", n)
    return n * n


print(square(4))
print(square(4))
print(square(5))

Read the cache statistics

A hit means the answer came from the cache. A miss means the function ran, and currsize counts stored answers.

from functools import lru_cache


@lru_cache
def square(n):
    return n * n


square(2)
square(2)
square(3)
square(2)
print(square.cache_info())

Only hashable inputs can be keys

A list cannot be a dict key. So a cached function refuses a list argument.

from functools import lru_cache


@lru_cache
def total(numbers):
    return sum(numbers)


try:
    print(total([1, 2]))
except TypeError as error:
    print("TypeError:", error)

Example

from functools import lru_cache


plain_calls = 0


def fib(n):
    global plain_calls
    plain_calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)


cached_runs = 0


@lru_cache
def fib_fast(n):
    global cached_runs
    cached_runs += 1
    if n < 2:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)


print("Plain result:", fib(10))
print("Plain calls:", plain_calls)
print("Cached result:", fib_fast(10))
print("Cached body runs:", cached_runs)
print(fib_fast.cache_info())

Key points

  • Memoisation: storing a result so a later call can reuse it
  • Cache: the store where past results wait for reuse
  • Use a dict to build a small cache by hand
  • Use functools.lru_cache to add caching with one decorator line
  • Use cache_info() to see hits, misses, and the cache size
  • Pure function: it always gives the same answer for the same inputs
  • Hashable: a value that can serve as a dict key

In this example, fib uses plain recursion with no cache. It needs 177 calls to reach the answer 55. The cached fib_fast stores each answer it works out. Its body runs only 11 times, once for each number from 0 to 10. Both versions print the same result, 55. The cache_info line reports 11 misses and 8 hits. A miss is a body run, and a hit is a reused answer.

Note

When the cache is full, lru_cache drops the least recently used result, unless maxsize is None.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

When is it safe to cache a function's results?