Re:Sieve is simpler than LRU
by scotty79 on Friday January 05, 2024 @07:58PM
(#38887158)
> Items can acquire visited status anywhere in the cache, to the left or right of the Hand pointer. There is no special area.
They can lose visited status only if they are between head and hand pointer. That's the special area. There's no way for item to loose their visited status if they are between hand and tail until the hand reaches head. In this sense area between hand and tail is privileged.
> If an item is inserted while the Hand is in the leftmost position, it will be evicted immediately when another not-present item is accessed.
You see the cost of small head-hand area but you don't see the benefit of large hand-tail area.
> Moreover, the algorithm doesn't allow for experimentation with randomly varying the trim distance between two arbitrary values.
In its basic form it doesn't. However I suggested that you might tweak how far from the head, the hand loops back to tail. It doesn't have to happen at exactly zero distance if you don't want to ever disadvantage new entries too much.
> .. construe a sequence of access patterns under LRU in which two items A and B appear equally frequently, yet enjoy significantly different retention times.
I see no cost of that. Cache doesn't need to be fair. It only needs to be successful. If it can serve item A from cache for 100% of the time and item B 0% of the time despite same patterns its still better than if it serves each of them 25% of time from cache.
They can lose visited status only if they are between head and hand pointer. That's the special area. There's no way for item to loose their visited status if they are between hand and tail until the hand reaches head. In this sense area between hand and tail is privileged.
> If an item is inserted while the Hand is in the leftmost position, it will be evicted immediately when another not-present item is accessed.
You see the cost of small head-hand area but you don't see the benefit of large hand-tail area.
> Moreover, the algorithm doesn't allow for experimentation with randomly varying the trim distance between two arbitrary values.
In its basic form it doesn't. However I suggested that you might tweak how far from the head, the hand loops back to tail. It doesn't have to happen at exactly zero distance if you don't want to ever disadvantage new entries too much.
> .. construe a sequence of access patterns under LRU in which two items A and B appear equally frequently, yet enjoy significantly different retention times.
I see no cost of that. Cache doesn't need to be fair. It only needs to be successful. If it can serve item A from cache for 100% of the time and item B 0% of the time despite same patterns its still better than if it serves each of them 25% of time from cache.