08 - Caching in Python with LRU

The goal of cache is to improve speed on the cost of memory. The cache is a widespreaded technique in computer science. There are many ways to apply it, but the classical one involves in applying the least recently used principle, which says that you are more likely to reuse something in the near future that you just aksed for.

Cache policies

Caches have limited space, thus we need to make decisions about what to store and what remove from it. This is called the cache policy.

• FIFO: First In First Out
• LIFO: Last In First Out
• LRU: Least recently used
• MRU: Most recently used
• LFU: Least frequently used

Data	Creation Time	Last Time Used	# Fetches
A	120	30	10
B	110	20	2
C	100	70	15
D	80	5	8
E	50	10	10

Considering the data above, here are the Data to be removed according to each policy:

• FIFO: A
• LIFO: E
• LRU: C (Last use was 70 seconds ago)
• MRU: D (Fetched 5 seconds ago)
• LFU: B (2 fetches only)

The lru_cache decorator

Internally, the decorator creates a dictionary having the function arguments as keys. Therefore, a cache hit means that we are calling the function with the same arguments used sometime before. The values of the dictionary are, of course, the values returned by the function.

Restrictions

• All function arguments decorated with lru_cache must be hashable.
• Distinct argument order is considered a different key. Watch out for keyword arguments.

Decorator arguments

You can specify the size of the cache being used by passing it as a parameter for the decorator.

from functools import lru_cache

@lru_cache(maxsize=10)
def fibonacci(n):
    pass

Info

The lru_cache implementation is thread safe!

Primer on decorators

Decorators are wrappers around functions. We use decorators whenever we need to execute something just before a function call, just after or both.

def my_decorator(func):
    @wraps(func)
    def wrapper(*args, **kwargs):
        execute_before()
        result = func(*args, **kwargs)
        execute_after()

        return result

    return wrapper

@my_decorator
def my_decorated_function():
    pass

The line in which we write @my_decorator is expected to be parsed as a function that receives a function as parameter and returns another function. In other words:

• @my_decorator -> some_func
• some_func(my_decorated_func: function) -> wrapper_func(args,*kwargs)

No matter what I write after the @, it should be parsed into a function that expects one single argument.

Well, in order to pass parameters to the decorator itself, I can wrap the decorator yet in another function.

def my_decorator(name):
    def _decorator(func):
        @wraps(func)
        def wrapper(*args, **kwargs):
            print(name)
            execute_before()
            result = func(*args, **kwargs)
            execute_after()

            return result

        return wrapper

    return _decorator

@my_decorator("Python")
def my_decorated_function():
    pass

Notice that my_decorator("Python") returns _decorator, which is a single argument function.

LRU cache + expiration time policy

def lru_cache_expiration(duration_in_seconds, maxsize=128):
    def _decorator(func):
        func = lru_cache(maxsize=maxsize)(func)
        func.lifetime = timedelta(seconds=duration_in_seconds)
        func.expiration = datetime.utcnow() + func.lifetime

        @wraps(func)
        def wrapper(*args, **kwargs):
            if datetime.utcnow() < func.expiration:
                func.cache_clear()
                func.expiration = datetime.utcnow() + func.lifetime

            return func(*args, **kargs)

        return wrapper

    return _decorator

@lru_cache_expiration(duration=10)
def my_decorated_function():
    pass

Exercise

• Cache x Memoization x Dynamic Programming
• Explore the lru_cache implementation. The python version is in functools. The C version is in _functools.