3 ms·
> 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 f
by 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 agoYou 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 agoWhen 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 agoExactly. 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 agoThe 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.
- scotty79 3y agoIt's rude to new customers when restaurant is already full of paying customers. It's unrelated to the new customers and in that sense unfair to them. But it's related to how successful is the restaurant at the moment. Fairness is not the goal. Success of the restaurant is. Objects near the tail are the people who occupy the table but keep ordering new dishes. Objects near the head are people who ordered just one thing and now they are politely asked to leave so new, potentially more generous customers can be accomodated. If restaurant is more full, new customers have less time to justify their continued occupation of the table by ordering again, but it's fine because it allowes more of the older customers with repeated orders to be served again and again. There is potential problem with the algorithm if there's very little space left for new items so they are never retained so hand never moves to head. Probaby you could refine the algorithm by moving hand to tail when it gets closer to head than some fixed value, finetuned to the production load. Or just occasionally move hand to tail every n inputs on average (also finetuned).