News for hackers. Stuff that matters.
Re:Sieve is simpler than LRU by kazinator on Friday January 05, 2024 @02:53PM (#38883937)
> You can look at this cache as circular buffer.

After that, you cannot "unsee" it any more.

> items that since their insertion acquired visited status at least once

> the second part of the buffer (the part starting at eviction point and ending at insertion point) is devoted exclusively to items that since their insertion acquired visited status at least once thus prooving they are worth keeping in cache.

Items can acquire visited status anywhere in the cache, to the left or right of the Hand pointer. There is no special area.

The "reaper" which ages visited items to unvisited, and which collects aged items, moves in a circle.

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. If an item is inserted while the Hand is farthest away at the rightmost slot, and not visited again, it can stay in the cache for a number of miss cycles, until the Hand goes to the top again.

That variability, as such, may be useful and good.

One problem is that it's not actually random, and it's not even a good form of pseudo-random.

I posit that input sequences exist in which two items of equal importance, A and B, are consistently treated unequally, with B enjoying much longer retention in the cache than A.

Moreover, the algorithm doesn't allow for experimentation with randomly varying the trim distance between two arbitrary values. Like say random between 4 and 8 slots in a 64 slot cache. That's a disadvantage, because for some given patterns, it prevents the optimal parameters from being discoverable.

Algorithms like LRU don't have the above weird property. While their hit rate may be good or bad depending on the locality of patterns, you cannot construe a sequence of access patterns under LRU in which two items A and B appear equally frequently, yet enjoy significantly different retention times.

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.

Re:Sieve is simpler than LRU by scotty79 on Saturday January 06, 2024 @05:49AM (#38890321)
> its still better than

* is not worse than