SIEVE is Simpler than LRU

• PDF
• Website
• Authors:
  • Yazhuo Zhang
  • Juncheng Yang
  • Yao Yue
  • Ymir Vigfusson
  • K. V. Rashmi

Notes

The authors show that SIEVE can be achieved with a minor adjustment to LRU and/or FIFO (typically under an hour of work) and gain much better cache eviction.

SIEVE requires up to 40% and 24% fewer instructions than LRU and FIFO, respectively

They also claim that SIEVE can be used as a good caching base to build more complex caches on top of. SIEVE is not universally better than LRU, and performed worse in a few cases, such as in presence of scans¹

Footnotes

1. See Why Aren’t We SIEVE-ing? for a potential solution ↩