Skip to content

[FEATURE]: Add LRU-K #237

@haochengxia

Description

@haochengxia

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:

  • New cache algorithm implementation

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions