|
One way to think about this is that there is a single queue, but that new items are added three-quarters of the way in. When an item is accessed, it is promoted to the quartile point two back from its current position. I think that makes it clearer that it is essentially a less aggressive LRU; being less aggressive shifts its focus to a longer timescale. It also lets you think about other ways to tweak LRU; what if instead of promoting an item to a particular quarter point, you just moved it up N places in the list? If you set N to three eighths of cache size, that would be roughly equivalent to S4LRU, but with a smoother response. You could then think about varying N according to where the item starts in the list (making it tougher to climb to the very top, say), or according to some other property of the item (making it easier for small items to climb, say). Another way to think about this is that it is 4Q-LRU, but with items that fall off the higher queues being demoted to lower queues, rather than being evicted: http://www.vldb.org/conf/1994/P439.PDF It'd be interesting to see a comparison between SnLRU, nQ-LRU, and ARC. The comparisons to FIFO, LFU, and LRU in the paper really only serve to establish that SnLRU is interesting, not that it is a great algorithm. |