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), measured in five separate processes with the arms interleaved inside each, reporting the spread within a run and the spread between runs as two separate figures. This axis is an estimate and is treated as one: two caches are ranked only when every replicate agreed on which was faster.

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.

What this is

If the words above went past you, here is the situation this exists for.

A cache is a small box you keep answers in so you do not pay for them twice. It is small on purpose, so it fills up, so every arrival forces an eviction. The rule deciding what gets thrown out is the eviction policy, and two caches of identical size running different policies can differ by a factor of two in how often they save you a database round trip. Choosing between them is therefore a real engineering decision and not a matter of taste.

The problem is that it is nearly impossible to choose from the outside. Every cache library's README reports numbers from its own benchmark, on its own workload, at its own sizing, and those numbers are not comparable with anybody else's. Worse, two of the ways they routinely differ are invisible in the headline figure: a cache that quietly holds twice its nominal entry count will win any comparison made by entry count, and a cache measured on uniform traffic will look identical to one measured on skewed traffic even though real traffic is skewed.

A harness is the instrument, not the finding. This package holds the workloads, the sizing rules, the measurement protocol and the reference policies, so that any cache can be put on the same axes as any other. Two ideas do most of the work:

• Size by fraction of footprint, and equalize occupancy by measuring it. A cache is interesting at 1% of the working set and boring at 200%, so the axis is the ratio. Before anything is timed, every subject is driven until its resident set stops growing and the harness reads off how many entries it really holds per entry of capacity asked for; each one is then sized down by its own measured factor. That check caught a popular library holding twice what its capacity argument suggested, and later caught an adapter in this very panel holding 1.36x while declaring 1.0.

  The factor is measured at the capacity being benchmarked, because it is not a constant of the cache. transitory holds 1.36 entries per entry when asked for 11 and 1.01 when asked for 4,262: the overshoot is generation rounding, so it shrinks as the capacity grows. A single number taken from a small probe and applied across the panel is a real correction pointed at the wrong sizes, and it costs its subject about three points of hit ratio at the wide end.

  This equalizes entries, not bytes. There is no byte instrument here, and per-entry overhead differs enough between libraries that the two are not the same claim; every report prints the measured occupancy table so you can see exactly what was held equal.

• Compare against Belady's OPT. OPT is the policy that evicts whatever will be requested furthest in the future. It requires knowing the future, so it is unimplementable and it is exactly what you want: the ceiling nobody can beat. "72% hit ratio" means little. "72% where the ceiling is 74%" means you are done optimizing.

It does not have an opinion about which cache should win. It is a neutral spin-off of a cache I wrote, and it stays neutral on purpose, because a benchmark whose default configuration favors the benchmark author's product is an advertisement.

Status: early, and specific about it. Workloads, reference policies, adapters, OPT, MRC, throughput, real-trace ingestion, SVG charts and the full CLI are all here. The efficiency axis is deterministic: a miss ratio is a function of the trace and the policy, and a second run reproduces it exactly. The throughput axis is an estimate and now carries the apparatus an estimate needs: five separate processes by default, both dispersions reported side by side, and two caches ranked only when every replicate agreed on the direction. Pairs the replicates split are printed as unordered, which is a result and not a gap.

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).

Command line

The package ships a CLI, and for most people it is the whole product. It runs the standard suite across the reference policies and whatever competitor caches are installed in the current project, then writes a markdown report with SVG charts.

npx cache-arena list      # workloads, reference policies, installed caches
npx cache-arena bench     # the whole suite, into ./cache-arena-report

bench is the default command, so bare cache-arena does the same thing. The report is BENCHMARKS.md: a method section carrying the measured occupancy table, one efficiency chart and table per workload with OPT pinned above the standings, and the throughput table. --json writes the raw cells beside it.

| flag | what it does | | --- | --- | | -o, --out <dir> | output directory (default cache-arena-report) | | --workloads a,b | only these standard workloads | | --seed <n> | re-draw the synthetic suite at seed n (default 0) | | --fractions 0.01,0.1 | sizes as fractions of footprint (default 0.001,0.005,0.01,0.05,0.1,0.25, floored at 10 entries) | | --trace <path[,path]> | add real trace files as workloads | | --trace-format, --trace-column, --trace-header, --trace-limit | how to read them | | --trials <n>, --warmup <n>, --tput-fraction <f> | timing protocol per process (defaults 10, 3, 0.1) | | --replicates <n> | separate processes behind each timing (default 5). One orders nothing | | --no-competitors, --no-throughput, --no-opt | drop a group or an axis | | --emphasize <name> | highlight one cache in the report | | --json | also write results.json |

cache-arena help lists all of them.

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
});

API

Plain functions, no global state. Everything the CLI does is reachable from here.

// workloads
standardWorkloads(seed?: number): Workload[]
zipf({ keys, alpha, ops, seed }): Int32Array
scan({ keys, alpha, ops, period, scanLen, seed }): Int32Array
loop({ keys, ops }): Int32Array
shift({ block, alpha, phaseLen, phases, seed }): Int32Array
twoPool({ hotKeys, hotFrac, coldKeys, ops, seed }): Int32Array
asWorkload(name, trace, about?): Workload
footprintOf(trace): number

// real traces
parseTrace(text, options?): Key[]                  // pure: no filesystem
traceToWorkload(name, keys, about?): Workload
loadTrace(path, options?): Promise<Workload>       // Node only

// subjects
referencePolicies(rng?): Subject[]                 // FIFO, LRU, LFU, Random, CLOCK, SIEVE, S3-FIFO
competitors(): Promise<{ subjects: Subject[]; missing: string[] }>
adapter({ name, make, policy?, source?, miss?, capacityFactor? }): Subject

// measurement
measureResidency(subject, nominals?): Residency
measureAllResidency(subjects, nominals?): Residency[]
missRatioCurves({ subjects, workloads, fractions?, includeOpt?, minSize?, residency? }): MrcResult
throughputResults({ subjects, workloads, fraction?, warmup?, trials?, residency? }): ThroughputResult
throughputAcrossProcesses({ subjects: SubjectSource, workloads, residency, replicates?, ... })
builtinSubjectSource({ seed?, competitors? }): SubjectSource   // this package's own panel
createSubjects({ seed?, competitors? }): Promise<Subject[]>    // what a child calls
optimalHitRatio(trace, capacity): number           // Belady, O(n log n)
hitRatio(cache, trace): number                     // the has-gated efficiency driver
replay(cache, trace): number                       // the timing driver: feed the return to consume()

// output
buildReport({ mrc, throughput?, emphasize?, chartDir?, meta? }): { markdown, charts }
mrcTable, mrcChart, throughputTable, throughputChart

Three things worth knowing before you wire your own run:

• A panel cannot be handed to a replicate, only described to it. A Subject is closures and a closure does not cross a process boundary, so throughputAcrossProcesses takes a SubjectSource: a module specifier, an exported factory and a JSON argument, which the child imports and calls. builtinSubjectSource is that description for the panel here, and subject-entry.ts is the twenty-line shape to copy for your own. Calling throughputResults directly still works with closures and measures in one process, which orders nothing.
• Measure residency once and pass it to both axes. missRatioCurves and throughputResults each measure it if you do not, which is slower and lets the timing run be sized differently from the simulation. The CLI calls measureAllResidency first and hands the same array to both.
• replay returns a sink and you must consume it. A timed loop nobody reads can be deleted whole by the optimizer, and a deleted call does not look like an error, it looks like a very fast cache. Pass the return value to consume(). throughputResults already does this, and times a do-nothing subject in the same rounds to establish the floor.

MrcResult carries cells, opt, the measured residency table, and violations: cells that scored above the Belady ceiling, which is always a broken adapter and never a win. ThroughputResult carries cells, the noopMops floor, and the subjects the guard flagged.

Known limits, stated rather than hidden

• Entries, not bytes. There is no byte instrument here. Per-entry overhead differs enough between libraries that equal occupancy is not equal memory, and the report prints the occupancy table so you can see exactly what was held equal.
• A workload has no clock. It is a key stream plus its footprint, with no timestamps. TTL expiry, time-based admission, and anything that decays with wall-clock time are not exercised at all.
• The values are the number 1. Keys are integers or short strings, values are a constant. Value size, serialization, and the GC pressure of real payloads are outside the frame, and they can dominate a real system.
• The surface is synchronous has / get / set. A promise-returning cache, a loading cache with stampede protection, a Redis client: none of them fit it. Everything runs in one thread in one process, so there is no concurrency axis either.
• A subject with no membership test is measured through a get fallback. That perturbs recency in most caches. Prefer a cache with a side-effect-free has, or the hit ratio is measuring your adapter as much as your cache.
• OPT's memory grows with the trace, not with the cache. It holds a next-use position per request and up to one heap entry per request: O(n log n) time, O(n) space over the whole stream. Sample or window a trace of hundreds of millions of requests before asking for the ceiling.
• Trace ingestion is text only. One key per line, or a CSV column. The classic ARC and LIRS corpora encode a start block and a count per line, so they have to be expanded into a key stream first, and binary formats such as libCacheSim's .oracleGeneral are out of scope by design.
• The synthetic suite is mostly IRM: each request drawn independently from a fixed popularity distribution. loop, scan and shift break that on purpose, but none of them reproduce the temporal locality of real traffic. That is why trace ingestion exists, and why a ranking you care about should be confirmed on your own trace.

One more bears on any timing you quote from here: unanimity across five replicates is p = 0.0625 per pair, and a panel asking dozens of pairs will hand out a separation by chance eventually. The report prints how many it expects, and --replicates is the lever. A close pair on a decision that matters wants more processes, not a closer reading of the medians.

When not to use this

There is no rival harness to send you to: I know of no other cache benchmark harness on npm. So these route you to what people actually do instead, because a package that only names where it wins is advertising.

You want ops/sec for a call, not a comparison between policies. Then a microbenchmark library is the better instrument: tinybench or mitata give you warm-up, repeated samples and a spread over any callable, with none of the workload machinery here. The throughput axis in this package exists to keep the efficiency winner honest about what it costs, not to be the last word on speed.

You have one trace and two candidates. The honest answer is a thirty-line script: replay your own trace through both, count hits, and make sure you sized them the same. What this package adds is the sizing rule, the OPT ceiling and the panel, and with two candidates most of that is scaffolding you do not need. Take measureResidency and optimalHitRatio from here if you want the two parts that are easy to get wrong.

You are evaluating a new policy rather than choosing between shipped ones. libCacheSim and the Caffeine simulator implement more policies and read more trace formats than this does, binary corpora included. Start there, and come back when the question is which npm package to install.

You need bytes. Stated above and worth repeating as a routing decision: this harness equalizes entries. If the question is how much RAM a cache costs on your own values, a heap snapshot (v8.writeHeapSnapshot()) answers it directly and this does not.

You just need a cache and a miss is cheap. Install lru-cache and move on. LRU is a good default, most services never notice the difference, and running a benchmark is a cost you pay to make a decision you actually have. Measuring pays when the miss is expensive: a database round trip, a metered API call, a cold model load.

You want a ranking you can quote as a general fact. A run here is a ranking on these workloads, at these sizes, on your machine's Node, at equal measured occupancy. That is evidence, and it is a great deal more than the numbers in most cache READMEs, but it is not a property of the libraries.

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
• [x] Residency measured at the capacity being benchmarked, rather than extrapolated from the worst small-capacity probe
• [x] The throughput axis in K separate processes, with a paired sign test and both dispersions reported
• [ ] 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