Python's LRU Cache Explained in Under 5 Minutes

Least Recently Used (LRU) is a caching strategy where the most recently used results are prioritized, while the least recently used results are evicted. Python provides a straightforward way to implement an LRU cache using the functools.lru_cache decorator.

Implementing LRU in Python

The lru_cache decorator is part of Python's built-in functools module, making the setup incredibly simple.

Here’s how it works. This decorator sits on top of a function and stores its results. The maxsize parameter defines the size of the cache. In this example, it will only remember the results of the last three unique inputs.

from functools import lru_cache

@lru_cache(maxsize=3)
def compute(n):
    print(f"Computing {n}...")
    return n * 10

compute(2)
compute(3)
compute(4)
compute(2) # This will be a cache hit
compute(3) # This will be a cache hit
compute(5) # This will cause an eviction

Let's try this out. When you run the code, you'll see an output like this:

Computing 2...
Computing 3...
Computing 4...
Computing 5...

Notice how it only printed "Computing..." for new inputs. That's because once the result is in the cache, the function skips the computation and just reuses the stored value. When we called compute(5), the cache was full, so it kicked out the least recently used item, which in this case was the result for the input 3.

How It Works: Under the Hood

The LRU cache is built on two main components: a dictionary for storing the cached results and a doubly linked list to track the order in which items are accessed.

Let's visualize the process:

1. Initial State: The cache is empty.
2. compute(2): This is a cache miss. The result is stored in the dictionary, and 2 is added to the linked list, marked as the most recently used item.
3. compute(3): Another cache miss. The result is stored, and 3 is added to the list as the new most recently used item.
4. compute(2): This is a cache hit. The result is already in the dictionary. The position of 2 is moved to the end of the list, marking it as the most recently used again.
5. compute(4): A cache miss. The result is stored, and 4 is added to the list as the most recently used. The cache is now full (maxsize=3).
6. compute(5): This is a cache miss. To make space, the least recently used item, 3, is evicted from both the list and the dictionary. The new result for 5 is then stored and marked as the most recently used.

Think of it as a queue where new items join at the end, and old, unused items fall off the front. It's a simple and efficient system.

Cache Configuration and Stats

Note on maxsize: What happens if you don't define the maxsize parameter? By default, it is set to 128. However, if you set it to None, the cache can grow infinitely.

@lru_cache(maxsize=None)
def infinite_cache_compute(n):
    # ...

If you're curious about what's happening inside the cache, you can check its performance using the cache_info() function.

print(compute.cache_info())

This gives you useful stats like hits, misses, max size, and the current size of the cache.

To sum it up, the lru_cache decorator is a fantastic tool to optimize your code, especially for expensive or repetitive computations. With just a few lines, you get a powerful caching mechanism built right into your functions.