hesela.devLow inter-reference recency set replacement
LIRS is a cache-replacement policy that protects low inter-reference-recency blocks while retaining some evicted-block history.
Inter-reference recency (IRR) counts distinct intervening blocks between consecutive accesses; it is not elapsed time or the number of repeated requests. [2]
LIR blocks stay resident until demotion. After the LIR allocation fills, first-seen blocks enter as HIR; eviction selects from the resident HIR queue Q. [1]
Stack S tracks LIR entries and selected HIR history, including nonresident entries. Pruning removes bottom HIR entries until an LIR entry is reached; removing history from S does not itself evict a resident HIR block from Q. [1]
An access to a resident HIR block is a hit; an access to a nonresident HIR entry is still a miss and needs a fetch. If the HIR entry was already in S, it becomes LIR and the bottom LIR entry is demoted. Otherwise it remains HIR and moves to the recent end of Q. On a miss, Q supplies the victim before promotion; demotion keeps the former LIR block resident in Q. [2]
Every accessed block moves to the top of S. A resident HIR block outside S remains HIR on that access but re-enters S, so a later access before pruning can qualify it for promotion. An LIR hit at the previous bottom of S triggers pruning. [2]
CLOCK-Pro adapts the reuse-history principle to reference-bit sampling and changes its cold-page allocation dynamically. It is not the same per-access stack algorithm. [3]
Relations
- related
- Least recently used replacement, Reuse distance, CLOCK-Pro, Ghost cache entry, Cache pollution
Advantages
- A scan need not replace protected reusable blocks merely because its one-time blocks were accessed more recently. [1]
Limitations
- The fixed HIR allocation trades protected capacity against responsiveness; a setting suitable for loops can lose hits on strongly localized workloads. [3]
- Trace-simulation hit ratios do not establish present-day end-to-end latency, implementation overhead or a universal ranking. [2, 3]
- Ordinary stack pruning does not impose a fixed metadata budget: bursts of first-time references can enlarge S. A separately capped variant removes HIR history near the bottom, trading retained history for bounded metadata. [1]
Citations
- Jiang and Zhang. LIRS: An Efficient Low Inter-reference Recency Set Replacement Policy. Author-hosted TR-02-6, sections 3.1-3.3 and 5.3.
- Jiang and Zhang. Making LRU Friendly to Weak Locality Workloads. IEEE TC 54(8), 939-952 (2005), sections 1.2, 3.3 and 4.
- Jiang, Chen and Zhang. CLOCK-Pro: An Effective Improvement of the CLOCK Replacement. USENIX ATC 2005, sections 2.2, 4 and 5.
Sources & caveats
- Primary-source synthesis, not a benchmark replication or a claim about a current kernel policy. The 2002 report and 2005 extension are distinguished.