Complete Guide to Caching in Python
When repeated function calls are made with the same argument, this causes the computation to be repeated. Memoization is useful in such scenarios where the results of function calls can be ‘saved' for future use. This results in time savings and code optimization as code becomes less computationally expensive. Caching is a more general term used to refer to storing of any data.
This article will touch on the different caching strategies, caching considerations, and how to enable and implement different types of caching for your scripts (using Python package and your implementation)!
Table of Contents
Types of Caching
There are several strategies for caching based on your needs, such as:
- Least Recently Used (LRU): removes least recently used data, the most common type of caching
- Least Frequently Used (LFU): removes least frequently used data
- First-In-First-Out (FIFO): removes the oldest data
- Last-In-First-Out (LIFO): removes the newest data
- Most Recently Used (MRU): removes most recently used data
- Random Replacement (RR): removes randomly selected data
Caching Considerations
When using caching in your applications, you should consider the memory footprint of the cache as it is storing additional information. If you are deciding between different implementations, in terms of architecture and data structures, there are a few timing considerations such as:
- Access time: For arguments that have been computed before, results should be accessed quickly in
O(1)time - Insertion time: For new arguments, data should be inserted into the cache, preferably in
O(1)time (depending on implementation, some may takeO(n)time, choose wisely!) - Deletion time: In the case when the cache is full, data will need to be removed according to the caching strategy. Deletion involves identifying the data to be deleted and subsequently removing them from memory
1 – Least Recently Used (LRU) Caching
Implemented by adding a decorator to your Python function
How it works: It uses a dictionary and a doubly linked list. In the dictionary, the key-value pairs are the supplied arguments and the entries in the doubly linked list. This allows the results to be quickly referenced given the supplied arguments (O(1) access time). Since arguments can be stored as a dictionary key, they must be hashable.
In the doubly linked list, function results are stored in the entries. Entries are sorted according to their recency and can reference their immediate previous and next entries. This allows entries to be easily inserted or reordered and for quick identification and deletion of the least recent entry if the cache is full.
Python">from functools import lru_cache
@lru_cache
def fibonacci(n: int) -> int:
return n if n < 2 else fibonacci(n - 1) + fibonacci(n - 2)Advanced Usage
LRU caching can be enhanced by implementing the following features:
- Maximum cache size with
maxsizeargument - Unlimited cache size with
maxsize=Noneargument orfunctools.cache. This means that data will never be deleted, which can lead to timing improvement at the expense of memory footprint. - Retrieve caching information on the number of hits and misses using
.cache_info(). Cache statistics allow us to evaluate how efficiently the cache is being accessed - Add expiration time with
cachetools.TTLCache - Linking cache with CPU memory usage instead of cache size
# 1. Maximum cache size
@lru_cache(maxsize=1024)
def fibonacci(n: int) -> int:
return n if n < 2 else fibonacci(n - 1) + fibonacci(n - 2)
# 2. Unlimited cache size
@lru_cache(maxsize=None)
def fibonacci(n: int) -> int:
return n if n < 2 else fibonacci(n - 1) + fibonacci(n - 2)
from functools import cache
@cache
def fibonacci(n: int) -> int:
return n if n < 2 else fibonacci(n - 1) + fibonacci(n - 2)
# 3. Retrieve caching information
fibonacci.cache_info()
# 4. Add expiration time (requires pip install cachetools)
from cachetools import cached, TTLCache
@cached(cache=TTLCache(maxsize=100, ttl=60*60*5), info=True)
def fibonacci(n: int) -> int:
return n if n < 2 else fibonacci(n - 1) + fibonacci(n - 2)Note: Other Python packages implement caching such as fastcache but they are not as popular or commonly used as
functools.lru_cache
2 – Least Frequently Used (LFU) Caching
Implemented by maintaining a cache dictionary and a frequency dictionary
Many implementations of LFU caching can be found online, including cachedtools with usage similar to LRU caching in the previous section. There can be various implementations for LFU caching using Hash Map, Singly Linked List, or Doubly Linked List.
I find maintaining two dictionaries the most optimal way, considering the access, insertion, and deletion time. Memory usage can be improved further by the use of hashing.
How it works: It uses 2 dictionaries. In the cache dictionary, the key is the supplied arguments and the value is a tuple of the function results and frequency. This allows quick retrieval of the function results (O(1) access time!) and frequency (to be used for accessing frequency dictionary).
In the frequency dictionary, the key is the frequency and the value is a list of supplied arguments. Storing the list of supplied arguments allows quick identification of the least frequently used argument and subsequent eviction of the argument and result from both dictionaries. Deque can be used instead of a list for quicker access, insertion, and deletion time.
Caveat: In LFU caching, it is biased against recent entries as newer entries may not have as high frequency as the existing entries – making it hard to evict the older entries even if they are being accessed less frequently
from collections import defaultdict, deque
from typing import Any, Deque, Dict, Tuple
class LFUCache:
def __init__(self, maxsize: int | None = None):
"""
Args:
maxsize (int | None): Capacity of cache size, defaults to None
"""
if maxsize and maxsize < 0:
maxsize = 0
self.maxsize = maxsize
self.cache_dict: Dict[Any, Tuple[Any, int]] = {}
self.freq_dict: Dict[int, Deque[Any]] = defaultdict(lambda: deque([]))
self.hits, self.misses, self.curr_size = 0, 0, 0
def cache_info(self) -> Dict[str, int | None]:
"""Report cache statistics"""
return dict(
hits=self.hits,
misses=self.misses,
maxsize=self.maxsize,
currsize=self.curr_size,
)
def cache_clear(self) -> None:
"""Clear the cache and cache statistics"""
self.cache_dict = {}
self.freq_dict = defaultdict(lambda: deque([]))
self.hits, self.misses, self.curr_size = 0, 0, 0
def update(self, key: Any, value: Any) -> None:
"""Update frequency of key in cache and frequency dictionary.
Removes key in frequency dictionary if necessary.
Args:
key (Any): Argument to function
value (Any): Result of function
"""
_, freq = self.cache_dict[key]
self.cache_dict[key] = (value, freq + 1)
self.freq_dict[freq].remove(key)
self.freq_dict[freq + 1].append(key)
if not len(self.freq_dict[freq]):
del self.freq_dict[freq]
def get(self, key: Any) -> Any:
"""Get value by key. Updates the hits and misses statistics.
Args:
key (Any): Argument to function
Returns:
(Any)
"""
if key in self.cache_dict:
self.hits += 1
value, _ = self.cache_dict[key]
self.update(key, value)
return value
self.misses += 1
raise KeyError(f"{key} does not exist in cache.")
def put(self, key: Any, value: Any) -> None:
"""Put value by key into cache and frequency dictionary.
Check the capacity of the cache and delete the key-value if necessary.
Args:
key (Any): Argument to function
value (Any): Result of function
"""
if key in self.cache_dict:
self.update(key, value)
else:
self.cache_dict[key] = (value, 1)
self.freq_dict[1].append(key)
self.curr_size += 1
if self.maxsize is not None and self.curr_size > self.maxsize:
remove_key = self.freq_dict[min(self.freq_dict)].popleft()
del self.cache_dict[remove_key]
self.curr_size -= 1The code snippet above is adapted from here, with some tweaks.
To use the LFU cache as a decorator, we can wrap the LFUCache class and use it similarly to functools.lru_cache. This can be done as such:
from functools import wraps
from typing import Callable
def lfu_cache(maxsize: int | None = None) -> Any:
cache = LFUCache(maxsize)
def decorator(func: Callable[..., Any]) -> Any:
@wraps(func)
def wrapper(*args, **kwargs) -> Callable[..., Any]:
key = hash(*args, **kwargs)
try:
result = cache.get(key)
return result
except KeyError:
result = func(*args, **kwargs)
cache.put(key, result)
return result
wrapper.cache = cache
wrapper.cache_info = cache.cache_info
wrapper.cache_clear = cache.cache_clear
return wrapper
return decorator
# Usage
@lfu_cache(maxsize=1024)
def fibonacci(n: int) -> int:
return n if n < 2 else fibonacci(n - 1) + fibonacci(n - 2)
fibonacci.cache_info()3 – First-In-First-Out (FIFO) / Last-In-First-Out (LIFO) Cache
Implemented by maintaining an ordered dictionary
How it works: It uses an ordered dictionary where the key-value pairs are the supplied arguments and the function results. The dictionary is sorted chronologically according to when the supplied arguments were first called.
This allows the results to be quickly referenced given the supplied arguments (O(1) access time), and entries can be removed from the front or the back depending on the caching strategy (O(1) insertion and deletion time). Implementation can be done using cachedtools with usage similar to LRU caching in the previous section. To illustrate this:
# Requires pip install cachetools
from cachetools import cached, FIFOCache
@cached(cache=FIFOCache(maxsize=100), info=True)
def fibonacci(n: int) -> int:
return n if n < 2 else fibonacci(n - 1) + fibonacci(n - 2)
# Retrieve caching information
fibonacci.cache_info()Hope you have understood more about caching, types of caching strategies and their considerations, and implementations using Python libraries, or your implementation!
Related Links
- LRU Documentation: https://docs.python.org/3/library/functools.html
- LFU Article: https://www.tutorialspoint.com/lfu-cache-in-python
cachetoolsOfficial GitHub: https://github.com/tkem/cachetools
