Problem Description:
The libCacheSim library aims to be a comprehensive cache simulation tool for research. While an interface for LRU-K exists at libCacheSim/cache/eviction/cpp/LRU_K.cpp, the implementation is missing. This limits the library's ability to simulate and benchmark against this foundational algorithm, which is crucial for understanding advanced cache policies like 2Q and ARC.
Solution:
Implement the complete and functional LRU-K eviction algorithm in LRU_K.cpp, ensuring it correctly tracks and evicts based on the K-th last access time.
Feature Category:
Use Case:
Enables researchers to:
- Directly compare new algorithms against LRU-K.
- Study the impact of the 'K' parameter on cache performance.
- Understand the evolution of modern cache algorithms from LRU-K's principles.
- Reproduce academic results.
Alternatives Considered:
Currently, users must implement LRU-K externally. An internal implementation enhances libCacheSim's completeness and utility for research, providing direct K-parameter tuning not fully covered by 2Q.
Implementation Considerations:
- Efficiently store and retrieve K-th last access timestamps (e.g., using
std::unordered_map with std::list or std::set for history).
- Ensure
K is configurable.
- Handle pages with fewer than K accesses.
- Integrate with existing
EvictionPolicy interface.
Additional Context:
LRU-K (O'Neil, O'Neil, Weikum, 1993) is a seminal algorithm that introduced history-based eviction to address scan resistance. Its inclusion is vital for a research-oriented simulation library.
Problem Description:
The
libCacheSimlibrary aims to be a comprehensive cache simulation tool for research. While an interface for LRU-K exists atlibCacheSim/cache/eviction/cpp/LRU_K.cpp, the implementation is missing. This limits the library's ability to simulate and benchmark against this foundational algorithm, which is crucial for understanding advanced cache policies like 2Q and ARC.Solution:
Implement the complete and functional LRU-K eviction algorithm in
LRU_K.cpp, ensuring it correctly tracks and evicts based on the K-th last access time.Feature Category:
Use Case:
Enables researchers to:
Alternatives Considered:
Currently, users must implement LRU-K externally. An internal implementation enhances
libCacheSim's completeness and utility for research, providing direct K-parameter tuning not fully covered by 2Q.Implementation Considerations:
std::unordered_mapwithstd::listorstd::setfor history).Kis configurable.EvictionPolicyinterface.Additional Context:
LRU-K (O'Neil, O'Neil, Weikum, 1993) is a seminal algorithm that introduced history-based eviction to address scan resistance. Its inclusion is vital for a research-oriented simulation library.