5 ms·

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 cas

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.

Karellen 3y ago
The one problem with LRU that I always remember is one John Carmack one wrote about with an LRU cache for items that were always accessed in the same order (objects to be rendered, in z-order?), which happened to be slightly bigger than the frequently-accessed set... until the day it wasn't. And performance suddenly dropped off a massive cliff. 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.
- tankenmate 3y ago
  This is the "scan resistance" pathology mentioned in the article. And the scratch slot is a (very simple) form of generational caching; i.e. generational LRU or multi-generational LRU [0]. [0] https://lwn.net/Articles/856931/ https://lwn.net/Articles/856931/
- ahoka 3y ago
  I think one can use random eviction to avoid any kind of pattern changing the average performance.
xxs 3y ago
LRU is expensive in a way that it doesn't scale (thread/core wise). What I do is probabilistic eviction, e.g. take randomly 17 items - evict the lowest three (need some algorithm for scoring). What I tend to use for scoring is 'access count', 'last access time', 'creation time', and perhaps creation costs (e.g. latency), plus a scoring formula. In that regard - such eviction can be implemented "entirely" concurrently.
- mgaunard 3y ago
  I don't understand how it doesn't scale; on a hit you just move a node to the front, which is just a few pointers to update (prev next, next prev, front prev, front, current prev, current next). If you have multiple threads, then presumably you should think how to serialize access to your shared resource anyway.
  - xxs 3y ago
    You need locking; locking does not scale. >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.
    - NovaX 3y ago
      Locking does not mean blocking. If you don't block the readers on the LRU reordering then it scales very well. That's a trick that's been in my production systems for 14 years now, and pretty much everywhere in Java land, that scales to over 900M reads/s on my laptop. Instead of probabilistic eviction you can use probabilistic reordering, e.g. via lossy sampling of the hits. The main benefit over sampled eviction or clock policies is that it is easier to use more robust and constant time algorithms.

Karellen 3y ago

The one problem with LRU that I always remember is one John Carmack one wrote about with an LRU cache for items that were always accessed in the same order (objects to be rendered, in z-order?), which happened to be slightly bigger than the frequently-accessed set... until the day it wasn't. And performance suddenly dropped off a massive cliff. 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.

tankenmate 3y ago
This is the "scan resistance" pathology mentioned in the article. And the scratch slot is a (very simple) form of generational caching; i.e. generational LRU or multi-generational LRU [0]. [0] https://lwn.net/Articles/856931/ https://lwn.net/Articles/856931/
ahoka 3y ago
I think one can use random eviction to avoid any kind of pattern changing the average performance.

xxs 3y ago

LRU is expensive in a way that it doesn't scale (thread/core wise). What I do is probabilistic eviction, e.g. take randomly 17 items - evict the lowest three (need some algorithm for scoring). What I tend to use for scoring is 'access count', 'last access time', 'creation time', and perhaps creation costs (e.g. latency), plus a scoring formula. In that regard - such eviction can be implemented "entirely" concurrently.

mgaunard 3y ago
I don't understand how it doesn't scale; on a hit you just move a node to the front, which is just a few pointers to update (prev next, next prev, front prev, front, current prev, current next). If you have multiple threads, then presumably you should think how to serialize access to your shared resource anyway.
- xxs 3y ago
  You need locking; locking does not scale. >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.
  - NovaX 3y ago
    Locking does not mean blocking. If you don't block the readers on the LRU reordering then it scales very well. That's a trick that's been in my production systems for 14 years now, and pretty much everywhere in Java land, that scales to over 900M reads/s on my laptop. Instead of probabilistic eviction you can use probabilistic reordering, e.g. via lossy sampling of the hits. The main benefit over sampled eviction or clock policies is that it is easier to use more robust and constant time algorithms.