hesela.devLRFU replacement
LRFU is a block-replacement policy that combines reference frequency with recency through exponentially decaying scores.
For 0 <= lambda <= 1 and q = 2^(-lambda), each reference contributes q^(current tick - reference tick); the smallest total score is evicted. The clock advances once per block reference, not per second. Lambda = 0 gives frequency ordering, while lambda = 1 gives LRU ordering. [1]
A score and its last-reference tick suffice. On another reference after d ticks, update C to 1 + q^d C. Compare blocks at a common current tick, not by their stored scores from different times. The basic implementation initializes a fetched block's score, so history retention across eviction must be specified. [1]
Example: with two slots and requests A,A,A,B, consider C at tick 5. At q = 1/2, A scores 7/16 and B scores 1/2, so A is evicted. Comparing their stale stored values, 7/4 and 1, wrongly selects B. At q = 3/4, the aligned scores are 333/256 and 3/4, so B is evicted. These are exact constructed scores, not measured cache performance. [3]
Relations
Citations
- Lee et al. LRFU: A Spectrum of Policies that Subsumes the Least Recently Used and Least Frequently Used Policies. IEEE TC 50(12), 2001, sections 3-4.
- Hesela: exact LRFU score alignment example (JSON).
- Hesela: exact rational score calculation (Python).
Further reading
Sources & caveats
- Source review covers the base algorithm; correlated-reference masking and the optimized heap/list implementation are not reproduced. [1]
- The constructed four-reference example uses equal-size blocks, an empty initial cache and exact rational arithmetic. It is not a reproduction of the paper's workload experiments. [4]