4 ms·

> ... the closer are newly inserted items to being evicted. That's a good thing because newly inserted items didn't prove yet that they are worth keeping. The

> ... the closer are newly inserted items to being evicted. That's a good thing because newly inserted items didn't prove yet that they are worth keeping. They have less time to proove themselves but if they prove themselves they can have a long lifetime because they will remain when the hand loops back to tail. End of cache is filled with items of proven utility. New ones are unproven. Shrinking distance between head and hand reflect accumulation of proven items which leaves less space for unproven ones. Which is good. Eventually (when the space for fresh ones ends) you want to reconsider the proven ones again and this is achieved by moving hand back from head to tail. It might be unfair to new items comming in at the times when there are a lot of proven ones accumulated but it is a good strategy from the point of view of the whole process. Good solutions are not necessarily fair. > If randomization of the distance is beneficial, let that be explicit! But it's better than random. It's adaptive to how many of the items already stored were visited recently.

kazinator 3y ago
> That's a good thing because newly inserted items didn't prove yet that they are worth keeping. It isn't good that the probation is random, depending on how far left the Hand is at the time the item is inserted. Or else if it is good for that distance to be randomized, it would be good to make that random choice explicit. > It's adaptive to how many of the items already stored were visited recently. It's not adaptive whatsoever. The Hand moves left when there are cache misses, in order to find items to evict, and then wraps back to the rightmost slot. The current position of the Hand bears no relation to a newly observed cache miss, yet affects its retention.
- 1a1a11a 3y ago
  You are probably thinking of block I/O or CPU cache workloads where scans cause the miss ratio to increase. This algorithm targets web workloads where scans are not common, and the miss ratio does not change abruptly. Yes, SIEVE does not adapt to miss ratio, but it adapts to the inherent popularity in the workloads. You can see the evidence in the results.
- scotty79 3y ago
  > The Hand moves left when there are cache misses It moves only if there were cache hits. If there are only cache misses it stays at the tail so the whole cache is dedicated for new unproven entries. Once there are some cache hits then they are retained and the area shrinks. It's not random. It reacts to whether it managed to catch something valuable or not. > The current position of the Hand bears no relation to a newly observed cache miss, yet affects its retention. Yes, but it is related to recent cache hits. It sacrifices chances of new items getting retained in exchange for retaining items that were recently proven to be worth keeping.
  - kazinator 3y ago
    When there is a cache hit, the accessed item is flipped to visited state (if necessary). No eviction takes place and so the Hand stays where it is. The Hand moves when it has to scan over visited items in search of an unvisited item to evict, when there is a cache miss. The scanned items are flipped to unvisited.
    - scotty79 3y ago
      Exactly. And if there are no visited items, evictions happen at hand and hand is at tail and doesn't move. Full cache is dedicated to finding items that will repeat. They are getting the best chance they can. Once some visited items arrive they are retained and the fraction of cache dedicated to new ones shrinks, so they have less time to get visited again and avoid eviction. But this happens for the benefit of retained items. If they were already seen second time there's a chance they'll occur for the third time and more. They are worth more than fresh ones. It's unfair to new items but beneficial for the cache as a whole. When many different items are revisited hand moves and eventually reaches the head. Then the cache is full. So it's moved back to tail to see if we can evict some of the old stuff because maybe they weren't re-visted since last time we considered them for eviction. Can you see it's not random and that it's actually useful?
      - kazinator 3y ago
        The algorithm is arbitrarily unfair towards new items based on its state, which has no relation to those items. It's like being rude to customers whenever the day of year is divisible by five. Sure it's not mathematically even pseudo-random, but it's unrelated to the customers. It's effectively random to them.

kazinator 3y ago

> That's a good thing because newly inserted items didn't prove yet that they are worth keeping. It isn't good that the probation is random, depending on how far left the Hand is at the time the item is inserted. Or else if it is good for that distance to be randomized, it would be good to make that random choice explicit. > It's adaptive to how many of the items already stored were visited recently. It's not adaptive whatsoever. The Hand moves left when there are cache misses, in order to find items to evict, and then wraps back to the rightmost slot. The current position of the Hand bears no relation to a newly observed cache miss, yet affects its retention.

1a1a11a 3y ago
You are probably thinking of block I/O or CPU cache workloads where scans cause the miss ratio to increase. This algorithm targets web workloads where scans are not common, and the miss ratio does not change abruptly. Yes, SIEVE does not adapt to miss ratio, but it adapts to the inherent popularity in the workloads. You can see the evidence in the results.
scotty79 3y ago
> The Hand moves left when there are cache misses It moves only if there were cache hits. If there are only cache misses it stays at the tail so the whole cache is dedicated for new unproven entries. Once there are some cache hits then they are retained and the area shrinks. It's not random. It reacts to whether it managed to catch something valuable or not. > The current position of the Hand bears no relation to a newly observed cache miss, yet affects its retention. Yes, but it is related to recent cache hits. It sacrifices chances of new items getting retained in exchange for retaining items that were recently proven to be worth keeping.
- kazinator 3y ago
  When there is a cache hit, the accessed item is flipped to visited state (if necessary). No eviction takes place and so the Hand stays where it is. The Hand moves when it has to scan over visited items in search of an unvisited item to evict, when there is a cache miss. The scanned items are flipped to unvisited.
  - scotty79 3y ago
    Exactly. And if there are no visited items, evictions happen at hand and hand is at tail and doesn't move. Full cache is dedicated to finding items that will repeat. They are getting the best chance they can. Once some visited items arrive they are retained and the fraction of cache dedicated to new ones shrinks, so they have less time to get visited again and avoid eviction. But this happens for the benefit of retained items. If they were already seen second time there's a chance they'll occur for the third time and more. They are worth more than fresh ones. It's unfair to new items but beneficial for the cache as a whole. When many different items are revisited hand moves and eventually reaches the head. Then the cache is full. So it's moved back to tail to see if we can evict some of the old stuff because maybe they weren't re-visted since last time we considered them for eviction. Can you see it's not random and that it's actually useful?
    - kazinator 3y ago
      The algorithm is arbitrarily unfair towards new items based on its state, which has no relation to those items. It's like being rude to customers whenever the day of year is divisible by five. Sure it's not mathematically even pseudo-random, but it's unrelated to the customers. It's effectively random to them.