"Cachetools" has become a cornerstone of Python cacheing libraries, but it has a few issues:
1) LFUCache - Mountingly slow insertion times when the cache is full. When the cache is full and a new item is inserted, the cache automatically handles eviction of the least frequently used item. Under the hood, cachetools uses a
`Collections.Counter` object as it's interface to track item usage frequencies. When an item is evicted, Cachetools calls the `Counter.most_common()` API to retrieve the least frequently used item. This method creates a copy of the original underlying dictionary and sorts it by-key. Python uses `Timsort`, so this is a O(n*logn) operation plus copy overhead. When the cache is large, this results in concerningly slow insertion times. With a cache size of 16384, median insertion times are ~0.6 microseconds (1e-6). When the cache is full, P90 and P99 insertion times are 540 and 600 microseconds (1e-6), a ~90,000% and ~100,000% increase from the median, respectively.
To solve this, `cacheing` implements an LFUCache API with O(1) insertions, deletions, and gets using a doubly linked list in the backend. This reduced P90 and P99 insertion times by ~45,000% and ~50,000%, respectively.
2) TTLCache - This is a great time aware cache implementation. The issue is that it exclusively offers a global time-to-live binding for each item in the cache. If you have a use case requiring variable, per-key time-to-lives, this API will not work for you.
By using a sorted linked list and binary search insertions, the `cacheing.VTTLCache` provides variable, per-key time-to-lives.
"Cachetools" has become a cornerstone of Python cacheing libraries, but it has a few issues:
1) LFUCache - Mountingly slow insertion times when the cache is full. When the cache is full and a new item is inserted, the cache automatically handles eviction of the least frequently used item. Under the hood, cachetools uses a `Collections.Counter` object as it's interface to track item usage frequencies. When an item is evicted, Cachetools calls the `Counter.most_common()` API to retrieve the least frequently used item. This method creates a copy of the original underlying dictionary and sorts it by-key. Python uses `Timsort`, so this is a O(n*logn) operation plus copy overhead. When the cache is large, this results in concerningly slow insertion times. With a cache size of 16384, median insertion times are ~0.6 microseconds (1e-6). When the cache is full, P90 and P99 insertion times are 540 and 600 microseconds (1e-6), a ~90,000% and ~100,000% increase from the median, respectively.
To solve this, `cacheing` implements an LFUCache API with O(1) insertions, deletions, and gets using a doubly linked list in the backend. This reduced P90 and P99 insertion times by ~45,000% and ~50,000%, respectively.
2) TTLCache - This is a great time aware cache implementation. The issue is that it exclusively offers a global time-to-live binding for each item in the cache. If you have a use case requiring variable, per-key time-to-lives, this API will not work for you.
By using a sorted linked list and binary search insertions, the `cacheing.VTTLCache` provides variable, per-key time-to-lives.
The full project can be viewed here, along with relevant benchmark statistics: https://github.com/breid48/cacheing