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

> Discover the best eviction algorithm for your workload in libCacheSim. Compare S3-FIFO, Sieve, and LRU to optimize cache performance and reduce misses.

- Repository: [Juncheng Yang/libcachesim](https://github.com/1a1a11a/libcachesim)
- Tags: best-practices
- Published: 2026-02-23

---

**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`](https://github.com/1a1a11a/libcachesim/blob/main/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](https://github.com/1a1a11a/libcachesim/blob/develop/libCacheSim/cache/eviction/LRU.c#L49-L57)). 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`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/cache/eviction/S3FIFOd.c) (source: [S3FIFOd.c lines 74‑86](https://github.com/1a1a11a/libcachesim/blob/develop/libCacheSim/cache/eviction/S3FIFOd.c#L74-L86)) 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`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/cache/eviction/Sieve.c) (source: [Sieve.c lines 45‑55](https://github.com/1a1a11a/libcachesim/blob/develop/libCacheSim/cache/eviction/Sieve.c#L45-L55)), 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`](https://github.com/1a1a11a/libcachesim/blob/main/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`](https://github.com/1a1a11a/libcachesim/blob/main/test/test_evictionAlgo.c) (source: [lines 178‑429](https://github.com/1a1a11a/libcachesim/blob/develop/test/test_evictionAlgo.c#L178-L429)). This utility runs your trace against each algorithm and prints hit‑rate, miss‑rate, and memory consumption statistics.

```bash

# 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`](https://github.com/1a1a11a/libcachesim/blob/main/include/libCacheSim/cache.h) (source: [cache.h lines 50‑65](https://github.com/1a1a11a/libcachesim/blob/develop/libCacheSim/include/libCacheSim/cache.h#L50-L65)).

### Basic C Implementation

```c
#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`](https://github.com/1a1a11a/libcachesim/blob/main/bin/cachesim/cache_init.h), line 72) accepts algorithm names and key‑value parameters parsed by [`scripts/utils/cachesim_utils.py`](https://github.com/1a1a11a/libcachesim/blob/main/scripts/utils/cachesim_utils.py) (source: [lines 182‑236](https://github.com/1a1a11a/libcachesim/blob/develop/scripts/utils/cachesim_utils.py#L182-L236)):

```bash

# 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`](https://github.com/1a1a11a/libcachesim/blob/main/LRU.c).
- **S3‑FIFO** adapts dynamically to bursty traffic using a two‑level FIFO plus ghost cache structure in [`S3FIFOd.c`](https://github.com/1a1a11a/libcachesim/blob/main/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`](https://github.com/1a1a11a/libcachesim/blob/main/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`](https://github.com/1a1a11a/libcachesim/blob/main/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`](https://github.com/1a1a11a/libcachesim/blob/main/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`](https://github.com/1a1a11a/libcachesim/blob/main/CMakeLists.txt).