Which Eviction Algorithm Is Best for Your Workload in libCacheSim: S3‑FIFO vs. Sieve vs. LRU

Use LRU for strong temporal locality, S3‑FIFO for bursty two-phase access patterns, and Sieve for sparse workloads with many one‑time requests.

libCacheSim is a high-performance caching simulator that ships with a family of replacement policies, each optimized for distinct workload characteristics. Choosing between S3‑FIFO, Sieve, and LRU requires understanding their internal mechanics—how they track object popularity, what metadata they store, and how they handle eviction. This guide breaks down the implementation details found in the source code to help you select the optimal algorithm for your specific trace or production workload.

LRU: Classic Recency-Based Eviction

The Least Recently Used (LRU) algorithm remains the baseline for cache replacement when temporal locality dominates your workload.

In libCacheSim/cache/eviction/LRU.c, the implementation relies on a doubly‑linked list managed via LRU_params_t.q_head and q_tail (source: LRU.c lines 49‑57). Every cached object is a node in this list; on a hit, the node moves to the head (move_obj_to_head), while eviction always removes the tail. This guarantees O(1) complexity for get, insert, and evict operations, with a memory overhead of just two pointers per object.

LRU excels when recently accessed objects are likely to be requested again soon—typical of web‑page caching or database buffer pools. However, the per‑object metadata requirement can become expensive when the working set contains millions of unique items.

S3‑FIFO: Adaptive Two‑Level FIFO with Ghost Cache

S3‑FIFO (S3FIFOd) targets bursty workloads where a small set of extremely hot objects appears suddenly, followed by a larger set of moderately popular items.

The implementation in libCacheSim/cache/eviction/S3FIFOd.c (source: S3FIFOd.c lines 74‑86) divides the cache into three logical structures:

• small_fifo – A fast FIFO that aggressively admits new objects.
• ghost_fifo – Records metadata for objects recently evicted from small_fifo (used only for statistics).
• main_fifo – A larger FIFO holding the bulk of cached data, whose type is configurable (FIFO, Clock, Sieve, or LRU).

Dynamic sizing occurs via S3FIFOd_update_fifo_size() (lines 192‑200), which adjusts the small_fifo capacity based on the ratio of hits in the ghost FIFO versus hits in the main FIFO. This adaptive behavior prevents the fast FIFO from monopolizing cache space during traffic bursts. The algorithm maintains O(1) complexity while adding only constant bookkeeping overhead.

Sieve: Lazy Promotion via Probabilistic Filtering

Sieve is designed for sparse‑access traces containing massive numbers of one‑time requests, where storing every object in the cache would waste space.

Implemented in libCacheSim/cache/eviction/Sieve.c (source: Sieve.c lines 45‑55), Sieve uses a counting Bloom filter (minimalIncrementCBF_init()) tracked via Sieve_obj_params_t.sieve. The filter records approximate access frequencies using only a few kilobytes of memory regardless of cache size. An object is promoted to the actual cache only after its access count exceeds a configurable threshold (default 2), filtering out the "long tail" of cold objects.

This makes Sieve ideal for log‑analysis pipelines, object‑storage workloads, or any scenario where metadata memory must remain minimal despite a huge distinct object count.

When to Choose Which Algorithm

Workload Characteristic	Recommended Policy	Rationale
Strong temporal locality (repeated recent access)	LRU	Directly evicts oldest entries, keeping recently used objects cached.
Two‑phase burst pattern (short hot burst + moderate background)	S3‑FIFO	Fast small_fifo captures bursts while adaptive sizing prevents starvation.
Highly skewed with many one‑time accesses	Sieve	Bloom filter excludes cold objects without allocating per‑object metadata.
Severe metadata memory constraints	Sieve	Filter size is independent of object count.
Hybrid needs (FIFO speed + lazy promotion)	S3‑FIFO with main_fifo_type=Sieve	Combines burst handling with probabilistic filtering (configured via lines 124‑136 in S3FIFOd.c).

Benchmarking with the Test Harness

Before deploying in production, validate your choice using the built‑in test harness in test/test_evictionAlgo.c (source: lines 178‑429). This utility runs your trace against each algorithm and prints hit‑rate, miss‑rate, and memory consumption statistics.

# Compare all policies on your trace

./test_evictionAlgo mytrace.bin

Programmatic Usage and Tuning

All three policies expose a uniform C API through the cache_t struct defined in include/libCacheSim/cache.h (source: cache.h lines 50‑65).

Basic C Implementation

#include "libCacheSim.h"
#include <stdio.h>

int main(void) {
    common_cache_params_t cp = {
        .cache_size = 32LL << 30, 
        .consider_obj_metadata = true
    };
    
    // Initialize LRU (no parameters needed)
    cache_t *cache = LRU_init(cp, NULL);
    
    // Or initialize S3-FIFO with custom ratio
    // cache_t *cache = S3FIFOd_init(cp, "fifo-size-ratio=0.15,main-cache=Clock");
    
    // Or initialize Sieve with higher threshold
    // cache_t *cache = Sieve_init(cp, "promotion-threshold=5");

    request_t *req = new_request();
    req->obj_id = 1; 
    req->obj_size = 4096;
    
    bool hit = cache->get(cache, req);
    printf("Hit: %d\n", hit);

    cache->cache_free(cache);
    free_request(req);
    return 0;
}

Command‑Line Interface

The cachesim binary (mapping defined in bin/cachesim/cache_init.h, line 72) accepts algorithm names and key‑value parameters parsed by scripts/utils/cachesim_utils.py (source: lines 182‑236):

# LRU simulation

cachesim MINI mytrace.bin LRU

# S3-FIFO with 10% small fifo and Clock main cache

cachesim MINI mytrace.bin S3FIFOd fifo-size-ratio=0.10,main-cache=Clock

# Sieve requiring 5 accesses before promotion

cachesim MINI mytrace.bin Sieve promotion-threshold=5

Summary

• LRU provides predictable, low‑overhead recency tracking for workloads with strong temporal locality, implemented via doubly‑linked lists in LRU.c.
• S3‑FIFO adapts dynamically to bursty traffic using a two‑level FIFO plus ghost cache structure in S3FIFOd.c, making it ideal for CDN edge or SSD front‑end caches.
• Sieve minimizes metadata memory using a counting Bloom filter in Sieve.c, excelling at sparse workloads with many unique, rarely‑repeated objects.
• All policies support O(1) operations and expose identical function pointers (get, insert, evict) through cache_t, allowing drop‑in replacement during experimentation.

Frequently Asked Questions

How do I know if my workload has the bursty patterns that favor S3‑FIFO?

Analyze your trace for two‑phase access patterns: a sudden spike of requests for a small object set followed by sustained traffic across a larger set. If your hit rate with LRU drops significantly during these spikes while the working set grows, S3‑FIFO’s adaptive small_fifo sizing (adjusted via S3FIFOd_update_fifo_size) will likely outperform static policies.

Can I combine Sieve’s filtering with S3‑FIFO’s burst handling?

Yes. Set main_fifo_type="sieve" when initializing S3‑FIFO (see the initialization logic at lines 124‑136 in S3FIFOd.c). This configures the main FIFO to use Sieve’s lazy promotion while retaining the fast small_fifo for immediate burst absorption.

What is the memory overhead difference between the three algorithms?

LRU requires two pointers per cached object. S3‑FIFO adds three FIFO structures plus two tiny eviction trackers, but still scales linearly with cache size. Sieve uses a fixed‑size counting Bloom filter (typically a few KB) regardless of how many distinct objects appear in the trace, making it the most memory‑efficient for large‑scale simulations.

How do I programmatically compare all three algorithms on the same trace?

Use the test_evictionAlgo.c harness located in the test/ directory. It loads your binary trace once and runs it against LRU, S3‑FIFO, and Sieve sequentially, reporting hit rates and CPU time for direct comparison. Compile with gcc test/test_evictionAlgo.c -lCacheSim after building the library via CMakeLists.txt.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}