How to Compare Different Cache Algorithms Fairly in libCacheSim

libCacheSim ensures fair cache algorithm comparisons by running multiple eviction policies side-by-side on the exact same trace using a single reader instance and identical cache configurations.

libCacheSim is an open-source cache simulator designed for rigorous performance evaluation. When you need to compare different cache algorithms fairly in libCacheSim, the framework provides built-in mechanisms to eliminate confounding variables such as trace parsing differences or configuration inconsistencies.

The Fair Comparison Workflow in libCacheSim

To compare different cache algorithms fairly in libCacheSim, follow this deterministic workflow:

1. Select a single trace in supported formats (plain text, CSV, VSCsi, or Oracle-General binary).
2. Define cache sizes as absolute byte values or working-set fractions.
3. List eviction algorithms in a comma-separated string (e.g., lru,lfu,s3fifo).
4. Fix auxiliary parameters such as object size handling, metadata consideration, TTL usage, and algorithm-specific knobs via the -e flag.
5. Execute cachesim to instantiate one cache object per algorithm-size pair and receive unified miss-ratio statistics.

Why libCacheSim Comparisons Are Fair

The fairness guarantee rests on three architectural decisions implemented in the source code.

Single Trace Reader

All cache instances consume requests from a single reader_t object. In libCacheSim/bin/cachesim/cli_parser.c, the setup_reader() function opens the trace once at lines 29-33 and passes the identical request stream to every cache instance. This eliminates I/O timing variations or parsing differences between runs.

Identical Cache Parameters

The create_cache() function in libCacheSim/bin/cachesim/cache_init.h receives the same common_cache_params_t structure for every algorithm instantiation. This structure, defined in the core headers, enforces uniform cache size, hash power, TTL settings, and metadata handling across all policies being compared.

Unified Statistics Collection

The simulation core aggregates results through simulate_with_multi_caches(), declared in libCacheSim/include/libCacheSim/simulator.h at lines 40-48. Each cache object maintains a cache_stat_t structure (defined in libCacheSim/include/libCacheSim/cache.h) that tracks misses and requests. The simulator collects these statistics simultaneously, ensuring that all algorithms experience the exact same request count and termination conditions.

Practical Examples for Comparing Cache Algorithms

Command-Line Comparison

The cachesim binary provides the simplest method to compare different cache algorithms fairly in libCacheSim:

# Compare LRU, LFU and S3-FIFO on a VSCsi trace with three cache sizes

./bin/cachesim \
    data/trace.vscsi \
    vscsi \
    lru,lfu,s3fifo \
    0.001,0.01,0.1 \
    -e "window-size=0.01"

The arguments specify the trace path, format, comma-separated algorithms (parsed by parse_eviction_algo() in cli_parser.c at lines 73-87), and size fractions (converted by conv_cache_sizes() at lines 38-57). The -e flag passes algorithm-specific parameters to create_cache().

Python API Comparison

For programmatic analysis, the Python bindings maintain the same fairness guarantees:

from libcachesim import SyntheticReader, FIFO, LRU, S3FIFO

# Create a synthetic trace or use TraceReader for real files

reader = SyntheticReader(
    num_objects=1_000_000,
    num_of_req=10_000_000,
    alpha=0.8,
    dist="zipf"
)

# Instantiate caches with identical parameters

caches = [
    FIFO(cache_size=64 * 1024 * 1024),
    LRU(cache_size=64 * 1024 * 1024),
    S3FIFO(cache_size=64 * 1024 * 1024),
]

# Process the same reader through each cache

for cache in caches:
    obj_mr, byte_mr = cache.process_trace(reader)
    print(f"{cache.cache_name():<8} obj miss: {obj_mr:.4f}  byte miss: {byte_mr:.4f}")

All caches receive the same reader instance and cache_size, ensuring the comparison reflects algorithmic differences rather than configuration variance.

Low-Level C API

For custom tooling, the C API exposes the fairness mechanisms directly:

#include "libCacheSim/simulator.h"
#include "libCacheSim/cache.h"
#include "libCacheSim/reader.h"

int main(int argc, char **argv) {
    /* Open trace once */
    reader_t *reader = open_trace(argv[1], VSCSI_TRACE, NULL);
    request_t *req = new_request();

    /* Common parameters for all caches */
    common_cache_params_t cc = {
        .cache_size = 64*MiB,
        .default_ttl = 0,
        .hashpower = 24,
        .consider_obj_metadata = false
    };

    /* Create cache instances */
    cache_t *lru = LRU_init(cc, NULL);
    cache_t *lfu = LFU_init(cc, NULL);
    cache_t *s3fifo = S3FIFO_init(cc, NULL);
    cache_t *caches[] = {lru, lfu, s3fifo};

    /* Single pass: feed every cache the same request */
    while (read_one_req(reader, req) == 0) {
        for (int i = 0; i < 3; ++i)
            caches[i]->get(caches[i], req);
    }

    /* Output statistics */
    for (int i = 0; i < 3; ++i) {
        cache_stat_t *stat = caches[i]->stats;
        printf("%s miss ratio: %.4f\n", 
               caches[i]->cache_name, 
               (double)stat->n_miss / stat->n_req);
    }

    /* Cleanup */
    for (int i = 0; i < 3; ++i) caches[i]->cache_free(caches[i]);
    free_request(req);
    close_trace(reader);
    return 0;
}

This implementation mirrors the internal logic of simulate_with_multi_caches() found in libCacheSim/profiler/simulator.c.

Key Implementation Files for Fair Comparisons

Understanding these source files helps verify the fairness mechanisms when you compare different cache algorithms fairly in libCacheSim:

File	Purpose	Critical Sections
libCacheSim/bin/cachesim/cli_parser.c	Parses CLI arguments and orchestrates cache instantiation	parse_eviction_algo() (lines 73-87), conv_cache_sizes() (lines 38-57), setup_reader() (lines 29-33)
libCacheSim/bin/cachesim/cache_init.h	Maps algorithm names to init functions	create_cache() (lines 17-55), simple_algos[] table (lines 37-78)
libCacheSim/include/libCacheSim/simulator.h	Declares simulation APIs	simulate_with_multi_caches() (lines 40-48)
libCacheSim/profiler/simulator.c	Executes unified request loops	Core simulation loop (lines 250-285)
libCacheSim/include/libCacheSim/cache.h	Defines cache statistics structures	cache_stat_t definition (lines 89-106)

Checklist for Fair Cache Algorithm Comparison

Before running experiments to compare different cache algorithms fairly in libCacheSim, verify these conditions:

• Single trace source – Use one reader_t instance for all caches; do not re-open or re-parse the trace per algorithm.
• Identical cache sizes – Specify the same absolute byte count or working-set fraction for every policy.
• Consistent auxiliary options – Apply the same values for --ignore-obj-size, --consider-obj-metadata, and --use-ttl across all runs.
• Deterministic parameters – Pass fixed eviction-specific knobs (e.g., window-size for TinyLFU) via the -e flag.
• Unified execution context – Run all algorithms within a single cachesim invocation or Python process to ensure identical random seeds for stochastic policies.

Summary

To compare different cache algorithms fairly in libCacheSim, leverage the framework's built-in single-reader architecture and unified parameter system:

• The cachesim CLI and Python bindings instantiate multiple cache_t objects with identical common_cache_params_t structures.
• The setup_reader() function in cli_parser.c guarantees every algorithm processes the exact same request sequence.
• The simulate_with_multi_caches() function aggregates cache_stat_t results simultaneously, ensuring comparable miss-ratio statistics.

Frequently Asked Questions

How does libCacheSim ensure the same request order for all algorithms?

libCacheSim opens the trace file once using setup_reader() in libCacheSim/bin/cachesim/cli_parser.c (lines 29-33). This single reader_t instance feeds requests to every cache object in a loop. Because the trace is not reopened or re-parsed for each algorithm, all policies see identical request sequences in the exact same order.

Can I compare algorithms with different cache sizes in the same run?

Yes, but fairness requires that every algorithm be tested against the same set of cache sizes. The conv_cache_sizes() function in libCacheSim/bin/cachesim/cli_parser.c (lines 38-57) converts size fractions (e.g., 0.001,0.01,0.1) into absolute byte counts. The simulator then creates one cache instance per algorithm-size combination, ensuring that when you compare LRU vs LFU at size 0.01, both are operating with the identical byte capacity.

What is the role of common_cache_params_t in fair comparisons?

The common_cache_params_t structure, defined in libCacheSim/include/libCacheSim/cache.h, enforces uniform configuration across all algorithms. When create_cache() in libCacheSim/bin/cachesim/cache_init.h instantiates a cache, it passes the same cache_size, hashpower, default_ttl, and consider_obj_metadata values to every eviction policy. This structural constraint prevents configuration drift that could skew miss-ratio results.

How do I handle stochastic algorithms when comparing fairly?

For algorithms with random eviction or probabilistic admission (e.g., certain variants of FIFO with random promotion), ensure deterministic behavior by running all caches within a single cachesim invocation or Python process. The simulate_with_multi_caches() function in libCacheSim/profiler/simulator.c initializes the random seed once at startup. Because all cache objects exist in the same process context, stochastic algorithms share the same seed state, making their behavior reproducible and comparable across policies.

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