LRU cache in Python (Simple Examples)

Often, speed & high performance come into our mind when we hear the term cache. In general, cache memory boosts the transfer speed when the RAM interacts with the processor via register memory.

Now, to augment the processing and performance in a Python application to make it more responsive, the caching technique has become of of the most influential techniques.

Caching is a performance-boosting method; when used precisely, can bring a notable difference by making the application faster while reducing the load on computing resources.

This tutorial will give you a complete walkthrough of the use of LRU (Least recently used) Cache that Python’s functools module brings to cache the result of your program’s functions using LRU strategies.

 

 

What is an LRU cache?

LRU stands for “Least Recently Used,” which enables programmers to discard or scrap the least recently used items first so that the program can utilize the computing resources for other new tasks or high-end tasks.

This is a technique used in organizing memory utilization and works in a First In First Out (FIFO) format.

This technique leverages the potential of cache (one of the fastest primary memory) and considers the size (number of page-frames the system’s cache can hold at once).

The LRU algorithm keeps track of what items got used when. The LRU caching scheme then helps in removing the least recently used frame as the cache becomes maximum.

The algorithm then references a new page to take more tasks. The LRU cache uses two different terms:

• Page hit: If the process finds the necessary page in the main memory, it is a page hit.
• Page fault: If the process does not find the necessary page in the main memory, it is a page fault.

A Least Recently Used (LRU) Cache also acts as a data structure to organize tasks in order of use, letting the program quickly determine which item hasn’t been utilized or operated for the longest time.

 

When to use LRU caching

LRU Caching is the optimization technique one should use while developing an application that responds quickly to every user interaction.

That way, the app can also enhance the user experience. LRU cache will keep track of the most recently used or most frequently accessed resources of the app and reduce load-time or unnecessary memory and other computational resources.

Let us take a real-life scenario where you are creating a fact-reading app. The app fetches the latest facts and information from different API-rendered sources.

As the end-user navigates through the list, your app leverages lazy loading & downloads the fact-based articles and displays the headlines along with the head link.

Imagine a situation where your user will move back and forth between a couple of facts/article headings.

Unless you are caching the data already loaded on your screen, your app would have to fetch the same fact/content every time through API calls.

That will not just make your app slow, but your users’ system sluggish. It might also put additional pressure on the server hosting your app’s articles.

 

Implement LRU cache in Python

Python’s standard library implements a decorator and comes with a module that helps cache the functions’ output through Least Recently Used (LRU) strategy.

The concept behind Least Recently Used strategy is that if your program has not accessed any program element in a while, it won’t probably be any time soon.

So, to leverage the LRU caching strategy, your program will simply get rid of the item used a long time ago, probably when the cache got full.

Here is a diagram showing how a new item replaces an old one that was not used for quite a long time.

We can use the @LRUCache decorator and the time module to explain how the task gets cached after a fixed time frame.

Here is a code snippet showing the simple way to utilize @LRUCache.

import time
class Node:  
    # Representing the nodes as n
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None
        self.prev = None
class LRUCache:
    cach_lim = None
    # When the DEBUG flag is set to TRUE, it will execute the code block
    DEBUG = False
    def __init__(self, func):
        self.func=func
        self.cache={}
        self.head=Node(0, 0)
        self.tail=Node(0, 0)
        self.head.next=self.tail
        self.tail.prev=self.head
    def __call__(self, *argu, **kwargs):
        if argu in self.cache:
            self.llist(argu)
            if self.DEBUG == True:
                return f'Task Cached.... {argu} \n {self.cache[argu]} \n Cache: {self.cache}'
            return self.cache[argu]
        # The given cache keeps on moving.
        if self.cach_lim is not None:
            if len(self.cache) > self.cach_lim:
                n = self.head.next
                self._remove(n)
                del self.cache[n.key]
        # Compute and cache and node to see whether 
        # the following element is present or not 
        # based on the given input.
        result = self.func(*argu, **kwargs)
        self.cache[argu] = result
        node = Node(argu, result)
        self._add(node)
        if self.DEBUG == True:
            return f'{result}\nCache: {self.cache}'
        return result
    # Remove from double linked-list - Node.
    def _remove(self, node):
        p = node.prev
        n = node.next
        p.next = n
        n.prev = p
    # Add to double linked-list - Node.
    def _add(self, node):
        p = self.tail.prev
        p.next = node
        self.tail.prev = node
        node.prev = p
        node.next = self.tail
    # Over here the result task is being done 
    def llist(self, argu):
        current = self.head
        while True:
            if current.key == argu:
                node = current
                self._remove(node)
                self._add(node)
                if self.DEBUG == True:
                    del self.cache[node.key]  
                    self.cache[node.key] = node.val 
                break
            else:
                current = current.next
LRUCache.DEBUG = True
# its DEFAULT test limit is set to NONE.
LRUCache.cach_lim = 3
@LRUCache
def exec_func(numb):
    print(f'Computing...{numb}')
    time.sleep(2)
    return numb
print(f'\n The function: exec_func called')
print('\n', exec_func(1))
print('\n', exec_func(2))
print('\n', exec_func(3))
print('\n', exec_func(4))
print('\n', exec_func(1))
print('\n', exec_func(2))
print('\n', exec_func(5))
print('\n', exec_func(1))
print('\n', exec_func(2))
print('\n', exec_func(3))
print('\n', exec_func(4))
print('\n', exec_func(5))

Output

 

How long does LRU cache live?

The @lru_cache decorator will put out existing entries only when there isn’t any space to store new listed tasks. But if there is sufficient space, the cache entries will live forever and never get refreshed.

That is why the LRU cache process lives till the app is on, or you can say the code is running.

To make the processing time more efficient, you can configure the LRU cache utilization strategy depending on your network bandwidth and computing power.

That way, your script will recover the tasks from the cache either once or twice before hitting again.

 

Turn off LRU cache

It is not possible to completely turn off or disable the LRU cache from inside the decorated function in a program run.

However, there is a way to simplify the code by accessing it directly (through a user-defined function) via the __wrapped__ attribute.

We must know that the original underlying function remains accessible through the __wrapped__ attribute.

Therefore to introspect and for bypassing the cache as if its operations got turned off, we can rewrap the function with a different cache.

from functools import lru_cache
@lru_cache()
def karlFunc(argu):
    return argu * 2
def cache(argu, use_a_cache = False):
    if use_a_cache is False:
        return karlFunc.__wrapped__(argu)
    return karlFunc(argu)
print(cache(10, use_a_cache=True))    # cache miss will occur
print(cache(10, use_a_cache=True))    # cache hit will occur
print(cache(10, use_a_cache=False))   # bypass the cache => partially turning off
print(cache(20, use_a_cache=False))   # bypass the cache => partially turning off
print(karlFunc.cache_info())

Output

 

How big LRU cache should be?

The @lru_cache decorator in Python offers a “maxsize” attribute for defining the maximum number of entries it can hold before the cache starts withdrawing old and unused items.

By default, the “maxsize” attribute is set to 128. But in case, you set this attribute to “None”, the cache will expand indefinitely, and no entries will get evicted.

import functools
@functools.lru_cache(maxsize = 128)
def check(numb):
  if numb < 2:
    return 1
  return check(numb-1) + check(numb-2)
print(check(10))

Output

However, there are various strategies one can use to expel tasks/items from the cache & conserve it from extending from the maximum size. The five most prominent techniques are:

1.	First-In/First-Out (FIFO)	This technique helps in removing the oldest item of all the entries.	All the newer entries are most likely to get reused.
2.	Last-In/First-Out (LIFO)	This technique helps in removing the latest item of all the entries.	All the older entries are most likely to get reused.
3.	Least Recently Used (LRU)	This technique helps in removing the least recently used entry.	All the recently used entries are most likely to get reused.
4.	Most Recently Used (MRU)	This technique helps in removing the most recently used entry.	All the least recently used entries get reused.
5.	Least Frequently Used (LFU)	This technique helps in removing the least often used or accessed entry.	All the entries with a lot of cache hits get reused.

 

Clear LRU cache

Although LRU Cache in Python enabled maximum speed for the app, making it more responsive, there are particular initiatives we have to take to deliver this technique more productively.
We can use the cache_clear() method after using the cache for clearing or invalidating the cache.

In other words, we have to execute cache_clear() on our user-defined function that has been decorated.

import functools
@functools.lru_cache(maxsize = None)
#initially maxsize is set to None
def capacity(numb): 
    if numb < 2: 
        return numb 
    return capacity(numb - 1) + capacity(numb - 2)
capacity(30)
#Before Clearing the cache
print(capacity.cache_info())
capacity.cache_clear()
#After Clearing the cache
print(capacity.cache_info())

Output

 

LRU cache using dictionary

We can create and implement the LRU cache solution using a Python dictionary. In this program, instead of requesting the fact/content directly to the server, every time it can download the fact that is there in the link.

You can create your dictionary program in such a way that it can check whether the program comprises the content in the cache. If not, it can go back to the server and request the fact/content.

In this program, we have used one content link to show you how the cache will respond once it has it.

Here is a code snippet showing what the caching technique might look like. Also, you have to install the requests library to make it work.

import requests
cache = dict()
def get_facts_ServerOn(link):
    print("Extracting the fact from the server.... ")
    response = requests.get(link)
    return response.text
def grab_fact(link):
    print("Getting the fact .... ")
    if link not in cache:
        cache[link] = get_facts_ServerOn(link)
    return cache[link]
grab_fact("https://likegeeks.com/python-deque//")
grab_fact("https://likegeeks.com/python-deque/")

Output

 

LRU cache to disk

As we have seen in the previous example, we can store web pages in the cache to load them faster to access in the future; the same goes with disk files as well.

Web browsers and internet-facing apps are not the only programs where you can use LRU cache.

They can be used everywhere, such as apps on servers and desktop applications that frequently use portions of a file from the disk.

For apps that run on the system independently, fetching content from a cache makes the app more responsive.

When you want to get something more often from the disk to the main memory, LRU caching strategy can speed up your program.

 

LRU cache memory leak

A memory leak occurs when the programmer creates and leverages memory in the heap, but forgets to delete or erase it from that allocated memory after the task gets completed.

The consequence of a memory leak is it might reduce the computer’s or app’s performance by lowering the amount of available memory for utilization.

Even things might worsen if too much available memory gets occupied or allocated under one app or task. It might make the system or app stops working correctly.

Such memory leaks can happen with the caching process also. So, you should clear the cache after every successful LRU cache utilization.

 

Lru_cache vs. Memoize

The memoize method is the technique that allows optimizing a Python function by caching the output depending on the parameters it supplies.

Once your program memoizes a function passed within it, the output computation will get performed only once for each set of parameters you call with it.

Now, on every call, it will quickly retrieve the remembered result from a cache rather than computing the function again and again on every call.

Whereas, LRU caching enables you to discard or scrap the least recently used items first so that the program can utilize the computing resources for other new tasks or processes.

This is a technique used in organizing memory utilization and works in a First In First Out (FIFO) format.

Although both these techniques help optimize the code and make the app work more responsively, the LRU cache manages the content within the cache memory from repeated calling & discards the least recently used content from the cache.

While the memoize technique remembers the result of a function it has already executed & used whenever the program sees the same function.

Memoize leverages the cache memory but is not responsible for managing it implicitly.

 

LRU_cache Performance

LRU Cache performance does not get impacted much when it comes to optimizing small-sized tasks for caching.

The performance effect is seen largely when your LRU_cache size grows bigger. The computation time will decrease as the cache size grows large.

Let us consider an example of the Fibonacci series done recursively. If we write the code in a simple format, the code looks like this:

import sys
def fibo(numb):
    if numb < 2:
        return numb
    else:
        return fibo(numb - 2) + fibo(numb - 1)
no = int(sys.argv[1])
print([fibo(x) for x in range(no)])

Output
Command-line input given is: 6.

For smaller input values, it will not impact much on the processing. But if we provide a larger number to the command-line argument, you will see it impacts the processing. Let’s take a practical look at it. The code remains the same:

Output
Command-line input given is: 40.

Here the given input is 40 which will take more iteration and as we all know recursion takes time because it has to push into the stack and then pops all the calculated results back from the stack. So, if you check the time taken for this program to execute will be:

Now, let us use the LRU cache to optimize the code.

import sys
from functools import lru_cache
@lru_cache(maxsize=64)
def fibo(numb):
    if numb < 2:
        return numb
    else:
        return fibo(numb - 2) + fibo(numb - 1)
no = int(sys.argv[1])
print([fibo(x) for x in range(no)])
print(fibo.cache_info()) #checking for effectiveness

Output

Whether you run this code in your system’s interpreter or any online interpreter, you will see that implementing the LRU cache will boost the result. You can notice a significant difference while running the previous code and this later one.

Also, if you capture the optimization level of the code, you will see a significant improvement in the performance with respect to time.

 

Conclusion

I hope this tutorial has given a crisp idea on the various aspects of caching and optimizing the programming performance through LRU cache in Python.

We have discussed how to implement LRU cache and what are its ways to implement. We have also experimented with techniques like clearing cache and turning it down for some time.

Finally, we have gone through the approaches to identify the various factors to enhance the performance of the program using the LRU cache decorator.

Caching has become an essential optimization technique to optimize the performance of the app by managing the cache system that our program utilizes.

It has become the fundamental step towards utilizing the memory and executing the program at its best case.