hesela.devLeast frequently used replacement
Least frequently used replacement selects a resident entry with the lowest tracked access count, with behavior also determined by counting scope and tie-breaking.
The LFU name alone does not specify count lifetime, aging or how equal counts are ordered. In the pinned standalone implementation, insertion starts the count at one, hits increment it, and a tie evicts the most recently used candidate. [1]
The LeCaR expert in the same repository instead breaks equal-frequency ties by block identifier and can recover a previous count from eviction history. These choices can change eviction sequences even when both implementations are called LFU. [2]
The CACHEUS paper describes random tie-breaking for classic LFU. That description and the linked standalone implementation are different baseline specifications; neither should silently substitute for the other. [3] [1]
Relations
- related
- LeCaR, CACHEUS, Least recently used replacement, TinyLFU, LRFU replacement, Ghost cache entry
Citations
- Standalone LFU author implementation: count lifetime and tie-breaking; commit 1eec63ce166502be33ddd1f35bc041ed73a24f4d.
- LeCaR author implementation: evict, addToHistory, miss and adjustWeights; commit 1eec63ce166502be33ddd1f35bc041ed73a24f4d.
- Rodriguez et al. Learning Cache Replacement with CACHEUS. FAST 2021, pp. 341-354, sections 3-6.
Further reading
Sources & caveats
- Primary-paper and pinned-source comparison, not execution of either baseline. The difference does not establish which implementation produced the historical published results.