LRU makes sense to me, so that is what I use.
The fact that some algos outperform it on some distributions (which might or might not be relevant to the use cases I might face) isn't good enough to convince me to switch.
The fact that some algos outperform it on some distributions (which might or might not be relevant to the use cases I might face) isn't good enough to convince me to switch.
The problem, it turned out, was that iterating through the same frequently accessed set of items, 1...N, in the same order every time, with an LRU cache of size N-1, would put items 1...N-1 in the cache, and then on the very last step evict item 1 (because it was the oldest) to put in item N. The next time round, when item 1 was not in the cache, it would evict item 2 (the oldest) to make way for item 1. And then evict item 3 to make way for item 2, evict 4 for 3, etc..., until finally evicting item 1 (again) to make way for item N. And do the same on the next iteration.
IIRC, he solved it by switching one of the cache slots as a "scratch" slot for the current iteration, so the last few items in the set would only overwrite each other, and items 1...C-1 would remain in the cache for the next iteration (where C is the size of the cache).
It is an unusual use case, to be sure, and not a reason to avoid LRU caches in general. Most users are unlikely to hit it. But it's useful considering as an example of how edge cases can pop up in places you might not have been expecting. It also shows you don't necessarily need to completely switch algorithms if you hit a pathological case - just tweaking how the cache works slightly (LRU to LRU-plus-scratch-slot) can sometimes get you back to 95% of where you were, which might be good enough.
In that regard - such eviction can be implemented "entirely" concurrently.
If you have multiple threads, then presumably you should think how to serialize access to your shared resource anyway.
>presumably you should think how to serialize access to your shared resource anyway.
I'd call that 'false'. The shared resource is the LRU Map in that case. The one w/ prob. eviction can be implemented (as in has been implemented) w/o a global lock (per the Map, which the LRU requires it). Prob. eviction can be implemented entirely lock free for that matter.
Locks offer no forward grantees, and don't scale. The changes of the lock state require the coherency traffic between the cores. Reads scale very well, writes don't.
Overall any data structure that requires a lock per the entire structure, especially on the read path -> bad, doesn't scale. Like I've said it's possible to have a Map w/o locks both on the reading/writing paths.