The experiments are interesting but they never explained what the strategies are. It's OK for LRU and FIFO but certainly not for 2-random!
Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
11–20 of 44 posts
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#12Note that LFU does not have the same limits and will adapt to access patterns that are pathological for LRU like circular accesses. LRU is an approximation of LFU based on the idea that last access time is related to the future access frequency of an object. The pathological cases where LRU fails and random eviction is better is related to the fact that such access patterns violate such premise. LFU does not have such limits because it attempts to measure the actual access frequency (smoothed by time) of an object, and uses that as prediction of the future frequency.
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#13An 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...
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#14Caffeine, a caching library for Java, has a nice write-up on more advanced cache eviction strategies. https://github.com/ben-manes/caffeine/wiki/Efficiency
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#15> 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…
>>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.
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#16> 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…
>>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.
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#17An 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...
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
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#18Worth 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
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#19> 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 speed.
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#20Interesting read, but I wish he'd explain how 2-random and LRU differ better. In a nutshell, LRU tracks the time when a cache item was last accessed and always discards the oldest item. 2-random also tracks the age of all cache items, but when discarding picks two random items and discards the oldest of those two.
It doesn't discard the oldest item, it discards the item that was least recently used/accessed (LRU, like the name says). To see the difference more clearly, note that the oldest item can in fact be the most recently used one.