Comparing the performance of a cache built using a `dict` + `__missing__` against lru_cache

cache_performance.py

"""
Comparing the performance of a cache built using a `dict` +  `__missing__` against lru_cache
"""
import time
from typing import TypeVar, Callable, Dict, Deque
from collections import deque
from functools import lru_cache

_K = TypeVar("_K")
_V = TypeVar("_V")


class FastDictCache(Dict[_K, _V]):
    """
    LRU cache implementation using dict.
    """

    def __init__(self, get_value: Callable[..., _V], size: int = 1000000) -> None:
        self._keys: Deque[_K] = deque()
        self.get_value = get_value
        self.size = size

    def __missing__(self, key: _K) -> _V:
        # Remove the oldest key when the size is exceeded.
        if len(self) > self.size:
            key_to_remove = self._keys.popleft()
            if key_to_remove in self:
                del self[key_to_remove]

        result = self.get_value(*key)
        self[key] = result
        self._keys.append(key)
        return result


# Function that we want to cache.
def func(a: int, b: int) -> int:
    return a + b


# Benchmark dict cache.
dict_cache = FastDictCache(func)

start = time.time()
for i in range(100000):
    for i in range(1000):
        result = dict_cache[1, 2]

end = time.time()
print("FastDictCache duration", end - start)


# Benchmark LRU cache.
cached_func = lru_cache(maxsize=1000000)(func)

start = time.time()
for i in range(100000):
    for i in range(1000):
        result = cached_func(1, 2)

end = time.time()
print("lru_cache duration", end - start)

# Without cache.
start = time.time()
for i in range(100000):
    for i in range(1000):
        result = func(1, 2)

end = time.time()
print("without cache duration", end - start)


# Results, Python 3.9.10, Linux

"""
(in seconds:)
FastDictCache duration 10.836893796920776
lru_cache duration 15.038449048995972
without cache duration 14.712836980819702
"""

# Results, Python 3.11.0b3

"""
(in seconds:)

FastDictCache duration 11.821012496948242
lru_cache duration 18.167968273162842
without cache duration 11.236643075942993
"""