How lru_cache Works in Python: A Deep Dive and Building Your Own

Caching is a powerful tool in programming to improve the performance of expensive or frequently called functions. One popular built-in caching mechanism in Python is the lru_cache decorator from the functools module. In this blog, we will explore the inner workings of lru_cache, understand its logic, and even build our custom implementation from scratch.

What is lru_cache?

The lru_cache (Least Recently Used Cache) decorator caches the results of function calls and returns the cached result when the same inputs occur again. It is useful for reducing the computation time of expensive functions that are called multiple times with the same arguments.

Let’s first understand how the lru_cache works and then build our own implementation.

How lru_cache Works in Python

The lru_cache decorator is implemented using a combination of a hash map (to store function results based on inputs) and a doubly linked list (to track the order of usage). The idea is to store the result of a function call, and when the cache reaches its size limit, the least recently used (LRU) element is removed.

• Cache Miss: If the requested result is not in the cache, the function is called, and its result is stored.
• Cache Hit: If the requested result is in the cache, the function is not called, and the cached result is returned.
• Eviction: When the cache is full, the least recently used item (the one that hasn’t been accessed for the longest time) is removed to make space for a new one.

Example Usage of lru_cache

from functools import lru_cache

@lru_cache(maxsize=3)
def expensive_function(x):
    print(f"Computing {x}")
    return x * 2
# Testing the cache
print(expensive_function(2))  # Cache miss
print(expensive_function(3))  # Cache miss
print(expensive_function(4))  # Cache miss
print(expensive_function(2))  # Cache hit, no computation
print(expensive_function(5))  # Cache miss, evicts the least recently used (3)

Output:

Computing 2
4
Computing 3
6
Computing 4
8
4
Computing 5
10

In this example, we set a maxsize of 3 for the cache. The cache will store only three results at a time, and if a new result is computed, the least recently used result is evicted.

How the Backend of lru_cache Works

At its core, the lru_cache mechanism uses a data structure called an LRU Cache. It typically consists of:

1. Hash Map (Dictionary): This stores the cache entries for fast lookups by function arguments.
2. Doubly Linked List: This maintains the order of cache entries, with the most recently used item at the front and the least recently used at the back. This allows O(1) insertions and deletions.
3. Eviction Policy: When the cache reaches its capacity, the least recently used item (the one at the back of the list) is evicted.

Here’s a visual representation:

HashMap:
--------------------------
| Key (Arguments) | Value |
--------------------------

Doubly Linked List:
[ Most Recent ] -> [ ... ] -> [ Least Recent ]

For more details -> Click on This

Building Your Own LRU Cache in Python

Let’s walk through creating a simple LRU cache from scratch using Python’s collections.OrderedDict. We’ll define a decorator that mimics the behavior of lru_cache.

Step 1: Importing Libraries

We’ll use OrderedDict to maintain the order of function calls and handle evictions when the cache size exceeds the limit.

from collections import OrderedDict

Step 2: Defining the LRU Cache

Here’s the implementation of our custom LRU cache decorator:

class LRUCache:
    def __init__(self, maxsize=128):
        self.cache = OrderedDict()
        self.maxsize = maxsize
    def __call__(self, func):
            def wrapper(*args):
                # Check if result is in cache (cache hit)
                if args in self.cache:
                    self.cache.move_to_end(args)  # Move to end to mark as recently used
                    return self.cache[args]
                
                # Compute the result (cache miss)
                result = func(*args)
                self.cache[args] = result
                # If the cache exceeds maxsize, remove the least recently used item
                if len(self.cache) > self.maxsize:
                    self.cache.popitem(last=False)  # FIFO order, remove first item (least recent)
                
                return result
            
            return wrapper

Explanation:

• OrderedDict: It stores the function results in the order of usage. We use move_to_end to mark the entry as the most recently used.
• __call__ method: This makes the class a decorator. The wrapper function checks if the result is in the cache (cache hit), otherwise, it computes the result and stores it in the cache (cache miss). If the cache size exceeds maxsize, the least recently used item is evicted using popitem(last=False).

Step 3: Using the Custom LRU Cache

Now, let’s test our custom LRUCache decorator:

@LRUCache(maxsize=3)
def expensive_computation(n):
    print(f"Computing {n}...")
    return n * 2

# Test calls
print(expensive_computation(2))  # Cache miss
print(expensive_computation(3))  # Cache miss
print(expensive_computation(4))  # Cache miss
print(expensive_computation(2))  # Cache hit
print(expensive_computation(5))  # Cache miss, evicts least recently used (3)
print(expensive_computation(3))  # Cache miss (recomputed after eviction)

Output:

Computing 2...
4
Computing 3...
6
Computing 4...
8
4
Computing 5...
10
Computing 3...
6

Here, the cache evicts the least recently used item (in this case, 3) to make space for new entries.

Key Takeaways

1. lru_cache helps in optimizing functions by caching results for repeated inputs.
2. The cache has a limit (maxsize), and once it’s full, the least recently used item is evicted.
3. We can build our custom LRUCache using a combination of a hash map (for storing results) and a doubly linked list (for managing usage order).
4. The custom implementation is simple and allows you to control how many results are stored in memory.

Conclusion

In this blog, we explored the Python lru_cache decorator and how it works under the hood. We also created our own LRUCache from scratch using Python’s OrderedDict. Understanding how lru_cache operates can help you optimize your applications by using caching wisely.