cache-arena

A benchmark harness for JavaScript and TypeScript caches. It measures the two things that actually matter about a cache, on the workloads that actually stress one, and reports them the way the literature does, so you can put any cache on the same axes as every other and show the result rather than assert it.

Two axes, kept separate on purpose:

• Hit ratio as a function of cache size (the miss-ratio curve, MRC), with size expressed as a fraction of the workload's footprint and Belady's OPT as the optimal ceiling. This axis is deterministic: a simulation, not a timing, so it is exactly reproducible.
• Throughput (ops/sec) with warmup, repeated trials, and a 95% confidence interval. This axis is noisy, and is treated as such.

The "arena" is the point: a cache means little measured alone. cache-arena lines the contenders up against each other and against OPT, on identical seeded workloads, and reports the standings.

It is deliberately not tied to any one cache. It ships reference implementations of the standard policies, adapters for the popular npm caches, and a bring-your-own-cache interface.

Status: early. The core (workloads, reference policies, adapters, OPT, MRC and throughput) is here and validated; real-trace ingestion, SVG charts, and the full CLI are landing next.

Install

npm install cache-arena

cache-arena has zero runtime dependencies. Competitor caches are loaded lazily, so you install only the ones you want to benchmark.

Quick start

import {
  standardWorkloads,
  referencePolicies,
  competitors,
  missRatioCurves,
} from "cache-arena";

const workloads = standardWorkloads(); // Zipf sweep, scan, loop, shift, two-pool
const { subjects } = await competitors(); // whichever npm caches are installed

const result = missRatioCurves({
  subjects: [...referencePolicies(), ...subjects],
  workloads,
  includeOpt: true, // add the Belady optimal line
});

Each result.cells entry is { workload, subject, fraction, size, hitRatio }: hit ratio for one cache, on one workload, at one cache size (a fraction of that workload's distinct-key footprint).

Concepts

• Workload: a reference stream of keys plus its footprint (distinct keys). The synthetic generators are seeded, so a run is identical on any machine. standardWorkloads(seed) (or --seed n) re-draws the whole suite at another seed, to confirm a ranking holds rather than being a lucky draw.
• Subject: a named cache under test. make(capacity) returns a fresh cache behind a uniform { has, get, set } surface.
• Fraction-of-footprint sizing: a hit ratio is meaningless without the ratio of cache size to working set, so sizes are set as fractions of each workload's footprint (the convention S3-FIFO and SIEVE report at, 0.1% and 10%).
• OPT: Belady's offline optimal, the minimum miss ratio achievable on a trace at a given size. The line every real policy is measured against.

Reference policies

Correct, readable implementations, useful as benchmark baselines and as documentation of what each algorithm is:

FIFO, LRU, LFU, Random, CLOCK, SIEVE (NSDI'24), and S3-FIFO (SOSP'23). W-TinyLFU is intentionally not reimplemented here: benchmark a real one (koffein, or the transitory package) through an adapter.

Bring your own cache

import { adapter } from "cache-arena";

const mine = adapter({
  name: "my-cache",
  policy: "custom",
  make: (capacity) => new MyCache(capacity), // needs get / set / has
  // miss: null,   // if your cache signals a miss with something other than undefined
});

Roadmap

• [x] Synthetic workloads, reference policies, competitor adapters, OPT, MRC, throughput
• [x] Real-trace ingestion (newline keys, CSV key column)
• [x] SVG charts (MRC curves + OPT, throughput bars) and markdown report output
• [x] CLI (cache-arena bench / list), with --seed for robustness runs
• [ ] A config file for the CLI
• [ ] More policies (ARC, LIRS)

Methodology and credits

The design follows the standard cache-evaluation methodology (miss-ratio curves, fraction-of-footprint sizing, Belady's optimal, separated efficiency and throughput axes, seeded and repeated). Reference algorithms and their sources:

• L. A. Belady, "A Study of Replacement Algorithms for a Virtual-Storage Computer," IBM Systems Journal 5(2), 1966 (OPT).
• J. Yang et al., "FIFO queues are all you need for cache eviction," SOSP 2023 (S3-FIFO).
• Y. Zhang et al., "SIEVE is Simpler than LRU," NSDI 2024 (SIEVE).
• N. Megiddo, D. Modha, "ARC," FAST 2003; G. Einziger et al., "TinyLFU," ACM ToS 2017; and the trace-driven tradition of ARC/LIRS and the libCacheSim / Caffeine simulators.

License

MIT (c) David Estevez