It would be interesting to compare the behavior of real workloads with different cache protocols. In a "real workload" the sequence of reads and writes to memory (and the cache) come from a multiplicity of independent processes functioning co-sequentially with some distribution of lifetimes of cache ownership. In many cases, the caches will be in a non-equilibrium state and behaving badly.
Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
21–30 of 44 posts
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#22> If you have a tight loop, LRU is going to be perfect as long as the loop fits in cache, but it's going to cause a miss every time if the loop doesn't fit. A random eviction policy degrades gracefully as the loop gets too big. That's the key take-away from my experience with optimizing control loops for microcontrollers with small caches. As soon as your loop is too bit, your code suddenly runs at a hundredth of the…
I am not sure I understand what you mean by the size of the "loop".
Conventional LRU uses linked-lists and when the LL no longer fits in the L1/L2 caches, you will see the performance hit you mention (given that accessing the associated LL node and reordering the list will most likely result in two cache misses).
Try libclc [1] for a compact segmented cache of n 64B containers that exactly fit a cache line, with each container having its own eviction policy. The overhead of LRU per container (of 7 data lines) is 9.14 bits/entry and the same cache line access will give you both the data lines and the LRU order.
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#23Note that Redis's LRU algorithm is randomized: https://redis.io/topics/lru-cache
> The reason why Redis does not use a true LRU implementation is because it costs more memory.
...but it sounds like it wouldn't necessarily be totally desirable to use true LRU anyhow. :-)
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#24> If you have a tight loop, LRU is going to be perfect as long as the loop fits in cache, but it's going to cause a miss every time if the loop doesn't fit. A random eviction policy degrades gracefully as the loop gets too big. That's the key take-away from my experience with optimizing control loops for microcontrollers with small caches. As soon as your loop is too bit, your code suddenly runs at a hundredth of the…
It goes beyond microcontrollers to every step up the chain. You want to optimize you system to hit the cache at every level as much as possible. The processor and its cache. The database and its cache. Web servers and their cache. Because going outside of the cache at any level usually incurs a performance hit orders of magnitude worse.
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#25> If you have a tight loop, LRU is going to be perfect as long as the loop fits in cache, but it's going to cause a miss every time if the loop doesn't fit. A random eviction policy degrades gracefully as the loop gets too big. That's the key take-away from my experience with optimizing control loops for microcontrollers with small caches. As soon as your loop is too bit, your code suddenly runs at a hundredth of the…
I am not sure I understand what you mean by the size of the "loop". Conventional LRU uses linked-lists and when the LL no longer fits in the L1/L2 caches, you will see the performance hit you mention (given that accessing the associated LL node and reordering the list will most likely result in two cache misses). Try libclc [1] for a compact segmented cache of n 64B containers that exactly fit a cache line, with each…
> Conventional LRU uses linked-lists and when the LL no longer fits in the L1/L2 caches
He refers to the LRU-like policy of the I/D cache itself.
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#26Earlier quoted context omitted.
I am not sure I understand what you mean by the size of the "loop". Conventional LRU uses linked-lists and when the LL no longer fits in the L1/L2 caches, you will see the performance hit you mention (given that accessing the associated LL node and reordering the list will most likely result in two cache misses). Try libclc [1] for a compact segmented cache of n 64B containers that exactly fit a cache line, with each…
> Conventional LRU uses linked-lists and when the LL no longer fits in the L1/L2 caches He refers to the LRU-like policy of the I/D cache itself.
Got it. Thanks for the clarification.
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#27Earlier quoted context omitted.
>>When Are Randomized Algorithms Better Than LRU? >When the access pattern is random: recently used items are not more likely to be accessed than other items. Wouldn't they perform equally well in this case? There's no advantage in LRU, but also no disadvantage if they're really unpredictably random.
A random strategy has less overhead than LRU because there is no bookkeeping.
This argument does not apply to the OP as it does not account for any bookkeeping. I think an actual answer is more complicated and will entirely depend on the definition of “random access pattern.”
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#28Worth reading http://open-zfs.org/wiki/Performance_tuning about the Adaptive Replacement Cache algorithm ( https://en.m.wikipedia.org/wiki/Adaptive_replacement_cache ) which is less vulnerable to cache flushes than LRU
The only big gain of ARC is the adaptive sizing. If you can live with static sizing you will do just as well with 2Q, which is not patented.
I haven't used a true LRU in quite a while because the coordinated bookkeeping required is as disaster on multithreaded programs. ARC and 2Q can be largely lock-free.
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#29> When Are Randomized Algorithms Better Than LRU? When the access pattern is random: recently used items are not more likely to be accessed than other items. Or worse: the access pattern is "anti-recent": items recently accessed are less likely to be accessed again than other items. This is undergraduate stuff I once had to know for exams in machine architectures and operating systems. The choice of LRU replacement i…
Even when the access pattern is not random, random can provide some benefits.
It can prevent any otherwise harmless sweep/scan of the system from completely busting your entire cache for all of the other uses.
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#30An algorithm that's more optimal than LRU on most workloads is Window TinyLFU. Some nice simulations and graphs can be found here: https://github.com/ben-manes/caffeine/wiki/Efficiency
LHD is more optimal than LFU on most workloads. It's harder to implement, but more accurately computes the actual expected value of each cache item. https://www.cs.cmu.edu/~beckmann/publications/papers/2018.ns...
The LHD paper lacks a robust analysis against different workloads. The few traces they use are either private or not considered representative workloads. For MSR, the provider (SNIA) specifically states:
"WARNING: These traces are over 10 years old! They should not be used for modern research!".
It would be much more interesting if they used the traces from ARC and LIRS, perhaps also UMass and Wikipedia. These traces are publically available and used by multiple papers from a variety of groups.
I have not seen a sampling-based policy that outperforms a policy that has tracks history outside of its working set. Since the examples specifically avoided that comparison, I suspect that it under performs in comparison. That isn't to say it isn't a useful advancement, but that a more robust analysis is needed to validate their claims.