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.

It'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).

You're still on a mistaken program whereby because items are inserted at the leftmost slot of the array, that slot is the head. And so the rightmost slot is the tail.

This is not so. The tail of the buffer is the Hand pointer, and it behaves like a circular buffer tail.

This is at odds with the fixed head.

Your full versus empty analysis is flawed, because once the cache warms up, which takes only one cycle, it stays permanently full. At each subsequent cache miss, one item is evicted and one item is inserted. One in, one out. There is no tide-like ebb and flow between empty and full. That is just rhetoric which is not anchored to anything that is real in the algorithm.

Items that are booted out are identified at the circular buffer tail. But, oddly, the new ones are inserted at the physical top of the circular buffer's linear implementation which bears no relation to the circularity.

In a circular buffer, the linear indices have no special meaning.

So it is like a code smell, but for algorithms.

You can look at this cache as circular buffer. But in this interpretation there is not one pointer into that buffer, but two. Insertion pointer and eviction pointer. Their location in memory is irrelevant. What matters is that eviction pointer moves while insertion point doesn't.

Those two pointers split the circular buffer inti two parts. The part after insertion pointer but before eviction pointer you could call staging. It's a space where items that have not yet been considered for eviction are held. When an item gets evicted items in this staging space are moved one spot towards eviction pointer so that under insertion pointer a free space appears which is filled by the newly inserted item.

As items are considered for eviction and rejected (because they had visited status) eviction pointer moves closer and closer to insertion pointer shrinking the staging area. So the new items have less and less time to acquire visited status before the eviction pointer reaches them. This is what's unfair. That the chances of item getting visited and spared from eviction is lower for the items that arrive when staging is small.

This is somewhat alleviated by the fact that after eviction pointer in its motion reaches stationary insertion pointer it passes it so the staging area grows from almost nothing to the full size of the circular buffer. The items which had a bad luck to arrive when the staging is small, if they are repeated, have a later chance to arrive again when staging is large and then have a lot of time to earn visted status and avoid eviction the next time they are considered.

What you are advocating for is that insertion pointer should move too, either to keep fixed distance from the eviction pointer or to keep explicitly randomized distance. Those are of course valid choices when you design your cache algorithm. But the author(s) of this one went with another method. They reduce the distance between insertion and eviction pointer by one only after item is considered for eviction but rejected (because it got visited status since the time it was inserted or considered for eviction the previous time). Once the distance between insertion and eviction point reaches small enough value (for example zero) they increase the distance to be maximum possible (to the size of the circular buffer).

You don't see a reason for this choice and I'm telling you that the reason is that 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.

So it might be a good strategy to dedicate larger part of the buffer to those items in times when they are abundant in the input rather than fixed part or random part as you propose.

To address your concern that new items are inserted at the physical top of circular buffer implementation ... It doesn't matter. Insertion pointer could be placed at any spot in the buffer. You can randomize its initial (and ultimate since its not moving) placement and it would change nothing in the performance of the algorithm (after the buffer is initially filled). This cache could be implemented as circular linked list with two pointers into it.

Do you understand all that? Because I'm not sure if I can explain it any more clearly.

> 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.

> 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.

> its still better than

* is not worse than