[6keZbCECT2uB]

I glanced through the paper and didn't see a comparison to TinyLfu. Unfortunately, it seems to be a misleading name which would make one think it was simply an LFU algorithm. The description in caffeine seems to indicate that it's more of an LRU algorithm with an LFU admission heuristic.

If the overhead of the cache itself is significant, as in kernel virtual memory management. A clock based algorithm is usually preferable which uses an array to approximate node based structures. ARC and LIRS have CAR and CLOCK-Pro respectively to simulate them. CAR is vulnerable to re-use distances near the boundary of the cache size. [1] CLOCK-Pro is widely used, notably in Linux VM. [1] https://www.slideshare.net/huliang64/clockpro

[NovaX]

Naming aside, the structure is <LRU | LFU filter | LRU>. The latest version of that is adaptive, where the front LRU may grow or shrink based on the workload. This allows the cache to mimic LRU for recency-skewed workloads (e.g. job queues) and LFU for frequency-skewed ones (e.g. loops). In a stress test, ARC and LIRS had 20% hit rate, Caffeine has 39.6%, and Optimal is 40.3%.

https://user-images.githubusercontent.com/378614/52891655-29...