3 ms·

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

> 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.
    - scotty79 3y ago
      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).
      - kazinator 3y ago
        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.

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.
  - scotty79 3y ago
    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).
    - kazinator 3y ago
      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.