4 ms·

> This is for no good reason other than just luck. > When the Hand finds a victim we just replace the Hand slot with the new item, and mark it visited That wo

> This is for no good reason other than just luck. > When the Hand finds a victim we just replace the Hand slot with the new item, and mark it visited That would cause newly inserted items to take at least N (size of the cache) rounds to be evicted. Evicting cache entries early is extremely important for performance. Their algorithm means new items will have a higher chance of being evicted, and that is by design, not random chance. Here's the paper: https://yazhuozhang.com/assets/pdf/nsdi24-sieve.pdf https://yazhuozhang.com/assets/pdf/nsdi24-sieve.pdf

iainmerrick 3y ago
I was curious too so I took a look. I think this is the relevant bit: Recent work [94] shows that “lazy promotion” and “quick demotion” are two important properties of efficient cache eviction algorithms. [...] Quick demotion removes most objects quickly after they are inserted. Many previous works have discussed this idea in the context of evicting pages from a scan [16,60,67,70,75,77]. Recent work also shows that not only storage workloads but web cache workloads also benefit from quick demotion [94] because object popularity follows a power-law distribution, and many objects are unpopular. [...] [94] Juncheng Yang, Ziyue Qiu, Yazhuo Zhang, Yao Yue, and K. V. Rashmi. FIFO can be better than LRU: the power of lazy promotion and quick demotion. In The 19th Workshop on Hot Topics in Operating Systems (HotOS 23), 2023.
- kazinator 3y ago
  I read that before. Caching is predicated on locality. We put things into a cache based on the idea that something accessed once is likely to be used again, due to locality. Lazy promotion is useful in a situation in which we don't trust that the access pattern exhibits locality, nor not fully. Perhaps it exhibits locality for some data, but is widely scattered for others. For instance, an algorithm is working with numerous local variables in a loop (good locality) but the loop is also stepping through a very large set of data in memory, much larger than the cache. Moreover, items in this set are visited only once (poor/nonexistent locality). If we regard accesses with a bit of suspicion ("this might not have good locality") we can avoid those latter items from overstaying in the cache. Items in the cache that are not going to be touched again effectively shrink the cache. Like if at any given time about half our cache has such items, the cache is effectively halved. With a deterministic, fixed distance between the Hand pointer and the Insert point, which we can tune, we could empirically adjust for this. For instance we could have it so that, consistently, every new item that is not visited within 4 subsequent cache misses will be evicted. If we had a magic oracle, we would not use LRU or any of these other approaches. We would ask the oracle questions "Great Oracle, given these items in the cache, and this new one which is not in the cache, which one(s) will not be seen again, or else which one(s) will be seen again farthest into the future?" That's really what we want to know, but since oracles don't exist, we use heuristics, like the idea that the longer an item goes without being accessed, the more likely it is that it's a never-again-accessed item.
  - 1a1a11a 3y ago
    Great point! We tried the oracle (Belady MIN) and found that the oracle often does not admit new objects (<20% chance admitting new objects) in most traces. That's why we need to evict new objects quickly
kazinator 3y ago
I clearly articulated in my comment that this is one choice we could make for the distance between the Insert point and the Hand pointer. That distance is a parameter whose space can be experimentally tested. Without my proposal, there is no control over the parameter: the distance is an average, and so about half the cache size. When Hand is on the far right, a new item inserted at that time will stay in the cache long. When the Hand is far left, it may get evicted almost immediately. The only thing important for performance is a good hit ratio, however it is achieved. An evicted item is one that cannot be hit. Early eviction is not ipso facto good for performance; only with regard to some access patterns where early eviction of the right items improves retention of other items that yield good hits.
- vidarh 3y ago
  Early eviction is fine for performance if the average eviction you get is good enough that any improvement in eviction you get from a more optimal choice of distance is outweighed by the effort in picking the insertion point. You really need to measure, because this will depend on your workload, how fast your implementation is relative to the cost of a miss, what the ratio of "likely to never be requested again" to potentially long-lived objects are, etc.
  - kazinator 3y ago
    The roving Insert point is harder to implement, due to the reversed case: [ ][ ][I][ ][ ][H][ ][ ] ^^^^^^^^ `these items move right [ ][ ][H][ ][I][ ][ ][ ] ^^^^ ^^^^^^^ ^- this item moves to the top (left most slot) | `--- these items move right ` these items move right If we think about doing it in hardware, like for each set of a set-associative L1 or L2 cache, it's a hindrance.
    - 1a1a11a 3y ago
      I totally agree with you, this is not designed for hardware... and as others mentioned RRIP might be better for set-associative caches

iainmerrick 3y ago

I was curious too so I took a look. I think this is the relevant bit: Recent work [94] shows that “lazy promotion” and “quick demotion” are two important properties of efficient cache eviction algorithms. [...] Quick demotion removes most objects quickly after they are inserted. Many previous works have discussed this idea in the context of evicting pages from a scan [16,60,67,70,75,77]. Recent work also shows that not only storage workloads but web cache workloads also benefit from quick demotion [94] because object popularity follows a power-law distribution, and many objects are unpopular. [...] [94] Juncheng Yang, Ziyue Qiu, Yazhuo Zhang, Yao Yue, and K. V. Rashmi. FIFO can be better than LRU: the power of lazy promotion and quick demotion. In The 19th Workshop on Hot Topics in Operating Systems (HotOS 23), 2023.

kazinator 3y ago
I read that before. Caching is predicated on locality. We put things into a cache based on the idea that something accessed once is likely to be used again, due to locality. Lazy promotion is useful in a situation in which we don't trust that the access pattern exhibits locality, nor not fully. Perhaps it exhibits locality for some data, but is widely scattered for others. For instance, an algorithm is working with numerous local variables in a loop (good locality) but the loop is also stepping through a very large set of data in memory, much larger than the cache. Moreover, items in this set are visited only once (poor/nonexistent locality). If we regard accesses with a bit of suspicion ("this might not have good locality") we can avoid those latter items from overstaying in the cache. Items in the cache that are not going to be touched again effectively shrink the cache. Like if at any given time about half our cache has such items, the cache is effectively halved. With a deterministic, fixed distance between the Hand pointer and the Insert point, which we can tune, we could empirically adjust for this. For instance we could have it so that, consistently, every new item that is not visited within 4 subsequent cache misses will be evicted. If we had a magic oracle, we would not use LRU or any of these other approaches. We would ask the oracle questions "Great Oracle, given these items in the cache, and this new one which is not in the cache, which one(s) will not be seen again, or else which one(s) will be seen again farthest into the future?" That's really what we want to know, but since oracles don't exist, we use heuristics, like the idea that the longer an item goes without being accessed, the more likely it is that it's a never-again-accessed item.
- 1a1a11a 3y ago
  Great point! We tried the oracle (Belady MIN) and found that the oracle often does not admit new objects (<20% chance admitting new objects) in most traces. That's why we need to evict new objects quickly

kazinator 3y ago

I clearly articulated in my comment that this is one choice we could make for the distance between the Insert point and the Hand pointer. That distance is a parameter whose space can be experimentally tested. Without my proposal, there is no control over the parameter: the distance is an average, and so about half the cache size. When Hand is on the far right, a new item inserted at that time will stay in the cache long. When the Hand is far left, it may get evicted almost immediately. The only thing important for performance is a good hit ratio, however it is achieved. An evicted item is one that cannot be hit. Early eviction is not ipso facto good for performance; only with regard to some access patterns where early eviction of the right items improves retention of other items that yield good hits.

vidarh 3y ago
Early eviction is fine for performance if the average eviction you get is good enough that any improvement in eviction you get from a more optimal choice of distance is outweighed by the effort in picking the insertion point. You really need to measure, because this will depend on your workload, how fast your implementation is relative to the cost of a miss, what the ratio of "likely to never be requested again" to potentially long-lived objects are, etc.
- kazinator 3y ago
  The roving Insert point is harder to implement, due to the reversed case: [ ][ ][I][ ][ ][H][ ][ ] ^^^^^^^^ `these items move right [ ][ ][H][ ][I][ ][ ][ ] ^^^^ ^^^^^^^ ^- this item moves to the top (left most slot) | `--- these items move right ` these items move right If we think about doing it in hardware, like for each set of a set-associative L1 or L2 cache, it's a hindrance.
  - 1a1a11a 3y ago
    I totally agree with you, this is not designed for hardware... and as others mentioned RRIP might be better for set-associative caches