Improve LFUCache performance

[tkem]

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.

[tkem]

According to this there is already an improved LFUCache implementation available which may be compatible.

[tkem]

@breid48: Want to get on board and provide a PR for LFUCache?

[breid48]

@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?

[tkem]

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)?

[breid48]

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).

Link

[tkem]

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.