In practice I think cache eviction policies have trended to optimizing _memory_ usage. Storing two pointers per cache entry for LRU on 64-bit CPUs uses 16 bytes

In practice I think cache eviction policies have trended to optimizing _memory_ usage. Storing two pointers per cache entry for LRU on 64-bit CPUs uses 16 bytes of data per entry - which adds up quickly! Especially if you're storing e.g. a like count (so an int64 or float per cache value). This approach to LFU has an even higher overhead. There's a few cool alternatives. The first and most obvious - use a good dense hash table implementation! For eviction strategies: a random eviction strategy actually does pretty well in the general case and requires no extra memory - great if you're caching an int32->int32 mapping and the cost of recomputing isn't astronomical. You can also use try the CLOCK algorithm which just requires 1 bit of storage per cache entry. From an abstract perspective, all page replacement algorithms can also be used as cache eviction policies. There's a whole list of these at https://en.wikipedia.org/wiki/Page_replacement_algorithm#Page_replacement_algorithms https://en.wikipedia.org/wiki/Page_replacement_algorithm#Pag... .