IT Blog | A bit more about cache and the way how to implement it in Python

Cache represents a way how you can make your algorithm work faster. Basically, it is a memory that stores outputs of your algorithm for specific inputs - which outputs are cached depending on the policy. When you ask your algorithm for results, it first checks if it is stored in a cache (memory) to return without performing any computations. If this logic succeeds (information is in memory), the situation is called a cache hit. On the other hand, if the information is not in memory, it is called a cache miss.

Naturally, you intend to have the highest cache hit ratio - this is the ultimate goal. Usually, the memory size dedicated to the cache and replacement policy determines the level of success. Of course, many other aspects have an impact on performance (for example, how fast cache memory is) - but these practical factors are typically something that you cannot change from the perspective of high-level programming.

Cache replacement policies

There are many policies on how to cache your data (meaning what data you want to save in a particular context). The most crucial cache policies are LRU and MRU - there also exist other policies. The correct replacement policy is essential and depends on a concrete algorithm. Consider an example of a fast algorithm except for a few values. Then it makes sense to cache these few values even if not computed very often - it can make the algorithm run continuously quickly. Whereas if you have a different algorithm where the computation is always slow, it makes sense to cache only values computed frequently. You can find many other examples and appropriate cache policies if you search.

It is essential to notice that cache policy does not determine how to implement a cache. Instead, it always depends on a concrete situation - if you implement a cache for hardware, in some low-level programming language, or high-level one, and on what type of data is cached (is it possible to compute hash, etc.). Therefore cache policy is, technically speaking, a class defining some algorithmic problem.

Least recently used (LRU)

It is arguably the most common cache policy. This algorithm caches only values that have been used recently (and discards oldest values). Generally, most of the algorithms use values repeatedly in programming, so it makes sense to store a few newest values. As a result, this class of caches is prevalent on every level. For example, you can find LRU caches on many hardware components (like disk, on many units of CPU, GPU). In addition, almost every standard library in every popular language implements it somehow.

Most recently used (MRU)

Works in the exact opposite direction than LRU. It caches the oldest values and discards the newest ones. MRU caching class is not that widespread. However, there are some good examples when it makes sense - imagine that you deal with something that occurs periodically (or almost periodically) - it makes sense to cache the oldest value because it will occur earlier than the newest value. You can imagine the example of busses arriving at the station and the algorithm providing details related to bus number. This algorithm will likely need to access older values as the probability that the same number occurs twice in a sequence is low.

Practical usage of cache in Python language

The good news is that there is a simple way to use cache on some functions in Python. But before diving into this issue, it is vital to introduce decorators in Python.

Decorator of function/method in Python

Decorators are a helpful construct in Python. They allow you to modify the behaviour of some function or method (and also classes). User-defined decorators are typically beneficial for logging functionality or doing some pre/after-commit work.

Consider the following example (of the most complex) decorator:

def decorator_factory(argument):
    print(f"decorator_factory called with: {argument}")
    def decorator(function):
        print(f"decorator for fn: {function.__name__}")
        def wrapper(*args, **kwargs):
            print("wrapper start")
            # For example, modify parameters
            args = (args[0] + 1, args[1] + 2)
            # Call wrapped function:
            result = function(*args, **kwargs)
            print("wrapper end")
            return result
        return wrapper
    return decorator

@decorator_factory("whatever")
def some_function(x, y):
    print(f"some_function ({x}, {y})")

# Call our decorated function
some_function(2, 3)
some_function(6, 7)

# OUTPUTS:
# >>> decorator_factory called with: whatever
# >>> decorator created for fn: some_function
# >>> wrapper start
# >>> some_function (3, 5)
# >>> wrapper end
# >>> wrapper start
# >>> some_function (7, 9)
# >>> wrapper end

This example is the most complex decorator you can create. It has its parameters, and you can also modify the function behaviour (and its arguments).

As you probably already know, there are many build-in decorators in Python, as well as many decorators created in Python's libraries.

Decorator `lru_cache` in `functools` package

Decorator for function lru_cache in the functools package (this package is a system package, so you do not have to install anything) is the easy-to-use implementation of LRU cache. The decorator itself takes a few parameters. The most important one is maxsize that defines the size of the cache. It also provides some additional functionality that can be called on function (as to object) to see some statistics (cache_info) or to clean cache(cache_clear). The following example demonstrates everything you need to know:

import functools
import random  # To test if cache works

@functools.lru_cache(maxsize=128)
def some_function(attr):
    return random.randint(0, 100) * attr

print(some_function(4))  # Some random output
print(some_function(5))  # Some random output
print(some_function(4))  # Same output as above (OK)
print(some_function(5))  # Same output as above (OK)

# Print statistics
print(some_function.cache_info())
# >>> CacheInfo(hits=2, misses=2, maxsize=128, currsize=2)

# Clear cache
some_function.cache_clear()
print(some_function.cache_info())
# >>> CacheInfo(hits=0, misses=0, maxsize=128, currsize=0)
print(some_function(4))  # A totally new output

The important note is: you can use lru_cache from functools only to stand-alone functions and the static method of a class. Never to standard class methods. It is not possible to use functools lru_cache decorator for a standard method because it is related to the whole class and not to an instance. This can cause memory leaks and unexpected behaviour. Consider the following example:

import functools
import random

class SomeClass(object):
    @functools.lru_cache(maxsize=3)
    def some_method(self, argument):
        return random.randint(0, 500) * argument

obj_a = SomeClass()
print(obj_a.some_method(4))
obj_b = SomeClass()
print(obj_b.some_method(4))
print(obj_b.some_method.cache_info())
# >>> CacheInfo(hits=0, misses=2, maxsize=3, currsize=2)
# => See a problem here: currsize=2 instead of 1 !!!

As you can see in this example, attribute currsize has value 2 after a call on a totally different object. This is unexpected behaviour because you would normally expect value 1 (as you want to have cache on method related to instance but not to the whole class).

Decorator `lru_cache` in `methodtools` package

Fortunately, there is a simple fix for this memory-leaking lru_cache decorator from functools. That is to use a different library called methodtools. This library is not a system package, so you have to install it (simply using pip install methodtools). The behaviour of this function in methodtools library is exactly the same as in functools. The only difference is that it works correctly. Consider the following example:

import methodtools
import random

class SomeClass(object):
    @methodtools.lru_cache(maxsize=3)
    def some_method(self, argument):
        return random.randint(0, 500) * argument

obj_a = SomeClass()
print(obj_a.some_method(4))
obj_b = SomeClass()
print(obj_b.some_method(4))
print(obj_b.some_method.cache_info())
# >>> CacheInfo(hits=0, misses=2, maxsize=3, currsize=1)
# => Great!!! Now it works correctly.

The drawback of the methodtools library is that it contains quite a few sub-dependencies (which can sometimes cause issues).

Summary

The article presents some theory behind caching and then practical examples of caching in Python language using functools and methodtools lru_cache decorator. Caching is generally helpful for making your code run faster. Of course, it is convenient to have some support functionality on the language level. In Python, it is good to know about the unexpected behaviour of lru_cache in the functools package (memory leaks) and how to overcome it. Also, if needed, you can usually quickly implement your cache logic as well - for example, the key for dictionaries can be almost everything, so the dictionary itself can be a data structure for the cache.