Cache Replacement Algorithm Comparison

This project implements and compares three cache replacement algorithms:

• ARC (Adaptive Replacement Cache)
• LRU (Least Recently Used)
• LFU (Least Frequently Used)

Implementation Details

The project contains the following key components:

• cache.hpp: Base interface for all cache implementations
• arc_cache.hpp: Implementation of the ARC algorithm
• lru_cache.hpp: Implementation of the LRU algorithm
• lfu_cache.hpp: Implementation of the LFU algorithm
• test_cache.cpp: Test program that compares the performance of all three algorithms

Implementation

C++ Version

The C++ implementation is header-only and can be easily integrated into your project. The main implementation is in arc_cache.hpp.

Key features:

• Template-based implementation for flexibility
• Header-only for easy integration
• Efficient memory management
• Thread-safe operations

Python Version

A Python implementation is also available in the python_version directory, which includes a comparison script to evaluate ARC against other caching algorithms (LRU, LFU).

Key features:

• Comparative analysis with LRU and LFU
• Visual performance metrics
• Multiple access pattern tests
• Automated performance reporting

Building and Running

To compile the test program:

g++ -std=c++17 test_cache.cpp -o test_cache

To run the tests:

./test_cache

Usage

C++ Version

#include"arc_cache.hpp"// Create an ARC cache with size 1000
ARCache<int, int> cache(1000);
// Add or update items
cache.put(key, value);
// Get itemsauto value = cache.get(key);

Python Version

# Navigate to python_version directorycd python_version
# Create and activate virtual environment (Windows)
python -m venv venv
venv\Scripts\activate
# Install dependencies
pip install -r requirements.txt
# Run the comparison script
python compare_caches.py

The Python script will:

1. Compare ARC with LRU and LFU caches
2. Test different access patterns:
   • Random access
   • Locality-based access
   • Periodic access
   • Zipfian distribution
3. Generate performance metrics showing:
   • Hit rates for each algorithm
   • Performance comparison with ARC
   • Summary statistics
4. Plot the results in cache_comparison.png

Example output:

=== Cache Performance Comparison ===
Pattern Type Cache Type Hit Rate Time (s) vs ARC Performance
---------------------------------------------------------------------------
Random LRU 9.89% 0.027 -0.08% ↑ ARC Better
LFU 9.92% 0.048 -0.05% ↑ ARC Better
ARC 9.97% 0.082 ...
=== Summary of ARC Performance ===
Total scenarios where ARC performs better: 6/8 (75.0%)
Breakdown by pattern:
Random : ARC better in 2/2 cases (100.0%)
Locality : ARC better in 2/2 cases (100.0%)
Periodic : Equal performance in all cases
Zipfian : ARC better in 2/2 cases (100.0%)

Test Results

The test program generates a mixed workload that includes:

1. Frequently accessed items
2. Recently accessed items
3. Random access patterns

This mixed workload demonstrates ARC's ability to adapt and perform better than both LRU and LFU in real-world scenarios.

Example output:

Testing cache performance with:
Cache size: 100
Data range: 1000
Access pattern length: 10000
Hit rates:
ARC: 13.26%
LRU: 5.77%
LFU: 12.90%

Why ARC Performs Better

ARC (Adaptive Replacement Cache) outperforms traditional algorithms because:

1. It dynamically balances between recency and frequency
2. It maintains ghost lists to track recently evicted items
3. It automatically adapts its policy based on the workload pattern

Requirements

• C++17 or later
• A C++ compiler (e.g., g++, clang++)
• Python 3.7 or later (for Python version)

References

• Nimrod Megiddo and Dharmendra S. Modha, "ARC: A Self-Tuning, Low Overhead Replacement Cache"