The overhead here in terms of space per element and amount of work while holding a mutex seems like it would only work well for some kinds of workloads. Particu

The overhead here in terms of space per element and amount of work while holding a mutex seems like it would only work well for some kinds of workloads. Particularly the design doesn't lend itself well to lock free algorithms or other techniques for reducing contention. Knowing how some real life high performance LFU caches work, I think this is optimizing the wrong thing. Look at the design of caffeine and ristretto[1] for some discussion of the tradeoffs with actual measurements. I believe both are based on TinyLFU with modifications. I don't know any serious LFU implementations that actually use a min heap and are still competitive, so the premise that LFU is commonly log N is not actually true. [1] https://dgraph.io/blog/post/introducing-ristretto-high-perf-go-cache/ https://dgraph.io/blog/post/introducing-ristretto-high-perf-...