Improve LFUCache performance
tkem opened this issue · 6 comments
According to this two-year old gist, LFUCache performance seems to lack behind other cache variants.
Since nobody else seems to have noticed, I guess LFUCache is not in widespread use. However, it is a sane caching strategy, and improvements (instead of dropping it altogether) would be welcome.
According to this there is already an improved LFUCache implementation available which may be compatible.
@breid48: Want to get on board and provide a PR for
LFUCache?
I'd be willing to submit a proposal. However, this will involve tearing out all of the existing LFUCache code in favour of a different design (namely, DLL).
Is this something that you would be interested in?
I'm happy with replacing LFUCache implementation with something completely different, as long as it still fits with the rest of cachetools. So could you please elaborate a little on the design (pardon my ignorance, but "DLL" doesn't ring any bells with me in this context)?
Doubly linked list. The design will loosely follow the design proposed in this paper:
Ketan Shah, Anirban Mitra, and Dhruv Matani, An O(1) algorithm for implementing the LFU cache eviction scheme, (August 16, 2010).
Sorry, I should have guessed that 😜
Sure, feel free to use whatever implementation you see fit - lists, dicts, sets, whatever, as long as it doesn't introduce any new dependencies.