Lazy Promotion on top of FIFO

FIFO is Better than LRU: the Power of Lazy Promotion and Quick Demotion

Interesting article about the efficiency of cache eviction algorithms. LRU is usually used because it makes sense to evict the last accessed object, but, counter-intuitively, FIFO may actually be better. LRU uses a doubly-linked list, and every access requires to update six pointers guarded by locks. FIFO doesn’t need to do this, but it trades this gain in efficiency with a higher miss ratio.

The article then goes on to explain improvements that make FIFO more efficient:

• lazy promotion: when an object is about to be evicted, promote it to the top of the list if it has been accessed recently
• quick demotion: if an object is not accessed soon after insertion, evict it early, rather than waiting for it to get to the end of the list