benchmarking.md

Benchmarking & reproducibility

This is the operational companion to performance-goals.md: how the Phase 6 validation matrix is run, what it measures, and how to reproduce the numbers. performance-goals.md fixes the success criteria; this page fixes the method.

What is measured

Two halves, both under benchmarks-jvm (the raw-JMH tier — JVM-only, which is where the competitor libraries live):

1. Time — JMH benchmarks comparing our primitive maps against the boxed standard library and four reference-ceiling competitors, across operation, size, and key distribution. Reported as ns per full sweep of size entries.
2. Memory — the exact retained heap of every map, measured with JOL (deterministic, not a GC estimate), reported as bytes per entry.

The maps in the matrix

impl	Map	Role
OURS	LongLongMap / IntIntMap	the subject
HASH_MAP	boxed java.util.HashMap	the baseline the project commits to beating
FASTUTIL	Long2LongOpenHashMap / Int2IntOpenHashMap (8.5.18)	reference ceiling
HPPC	LongLongHashMap / IntIntHashMap (0.10.0)	reference ceiling
ECLIPSE	Eclipse Collections primitive *HashMap (13.0.0)	reference ceiling
AGRONA	Long2LongHashMap / Int2IntHashMap (2.5.0)	reference ceiling

The four primitive competitors are a ceiling, not a gate: fastutil and HPPC are co-fastest among the classic open-addressing libraries, and we do not expect to beat them on raw single-thread JVM lookup. Our credible differentiators are memory footprint, true Kotlin Multiplatform (all four competitors are JVM-only), and Kotlin-idiomatic ergonomics. The committed win is against HASH_MAP.

Operations (LongLongMatrixBenchmark, IntIntMatrixBenchmark)

lookupHit (random-access, the fair gate), lookupMiss, insertPresized, insertGrowing (folds in resize cost), and churn (remove + re-insert every key — size-stable). There is deliberately no iterate op: our primitive-value maps expose no non-boxing traversal (a lean-surface choice, DP-10), so a fair head-to-head cannot include it. Every competitor does offer non-boxing iteration; closing that gap is tracked as a follow-up.

Sizes and key distributions

• Sizes: 10_000 (cache-resident) and 1_000_000 (out of cache) — the regimes where the layout advantage is, respectively, marginal and decisive.
• Distributions (dist): DENSE (consecutive 0..n-1) and CLUSTERED (strided keys, low bits zeroed — a distribution-sensitivity check for the hash finalizer). The CLUSTERED Int set is necessarily milder than the Long one: a key set that collides in a million-entry table cannot be built in-range for 32-bit keys without overflow, so the Int stride zeroes only the low 8 bits versus 21 for Long.

Load-factor sweep (LoadFactorBenchmark)

Lookup cost as a function of load factor {0.50, 0.75, 0.90, 0.95, 0.99}, for the two competitors that can be held at a high load — fastutil and HPPC, whose load factor tunes up to 0.99. Our SwissTable-family maps run at a fixed maximum load (7/8 = 0.875, then they grow) and HashMap resizes at 0.75, so neither can be held at an arbitrary load — they are fixed reference points, not sweepable. Agrona is excluded too: its load factor is capped at 0.9 (its constructor rejects a higher value), so it cannot reach the ≥0.95 points — its lookup at its own load is in the main matrix instead. The high-load (≈0.99) regime is the home of the paper structures (FunnelLongMap, ElasticLongMap), whose bounds are asserted by their own probe-count specs rather than this wall-clock sweep.

To land on a chosen load on a power-of-two table, capacity is pinned at 2^20 and the entry count is round(loadFactor · 2^20); every invocation then does the same 2^20 random lookups, so scores are comparable across the load axis.

Fairness discipline

Enforced in the harness, not left to convention:

• Primitive-vs-primitive, each map pre-sized in its own units (ours by expected entries; HashMap at its 0.75 load; the competitors by their own expected-element or initial-capacity arguments). No map is forced onto another's load factor.
• Random-access lookups (Fisher–Yates, fixed seed 42, identical order across maps and runs), so no map is flattered by insertion-order locality.
• An adversarial/clustered key set always accompanies the dense one.
• Monomorphic call sites: JMH runs a separate fork per impl, so the measured loop sees exactly one adapter type — the boxed baseline never pollutes the primitive maps' type profile.
• A correctness gate in @Setup: each map is verified to return the stored value for every key (the hit-sum must equal the key-sum) before any number is taken — a benchmark on a miswired adapter is worthless.

Running it

The full authoritative matrix

./benchmarks-jvm/run-matrix.sh <label>

This captures the environment, runs the JOL footprint report, runs the full JMH matrix (@Fork 3, warmup 5×1s, measurement 5×1s, AverageTime — the settings in benchmarks-jvm/build.gradle.kts), and collects a self-describing bundle under benchmarks-jvm/results/<label>/:

environment.txt   JDK + OS + CPU + whether frequency was pinned
footprint.md/tsv  retained-heap footprint
jmh-results.json  the JMH time matrix

The full matrix takes a few hours on a quiet machine. Pin CPU frequency where you can and keep the machine idle; environment.txt records what you could not control (on Apple Silicon, turbo and P/E scheduling are not controllable — say so).

Pinned Linux run (citable numbers)

Absolute time numbers are only citable when the machine is pinned — a Linux box is the right tool (Apple Silicon exposes none of these knobs). Prep the box, then pass a core list as the second argument to run the single-threaded matrix under taskset (the JMH jar runs directly, so no Gradle daemon shares the cores):

sudo cpupower frequency-set -g performance                       # fix the governor
echo 1 | sudo tee /sys/devices/system/cpu/intel_pstate/no_turbo  # Intel: turbo off
# AMD instead: echo 0 | sudo tee /sys/devices/system/cpu/cpufreq/boost
# best: also boot with isolcpus=<cores> so nothing else is scheduled there

./benchmarks-jvm/run-matrix.sh linux-pinned 2,3   # pin to 2 cores (bench + GC/JIT)

environment.txt then records the governor, turbo state, and pinned cores, so the bundle proves it was pinned. Pin to two cores for these @Threads(1) benchmarks — one runs the measured thread, the other absorbs GC/JIT so they don't perturb it. The multi-threaded read-scaling / mixed-load benchmarks are deliberately excluded from the pinned run (they measure scaling and need all cores); run them separately, unpinned.

A quick slice

Compile the jar once, then filter with JMH's own CLI:

./gradlew :benchmarks-jvm:jmhJar
JAR=$(ls -t benchmarks-jvm/build/libs/*-jmh.jar | head -1)
java -jar "$JAR" "LongLongMatrixBenchmark.lookupHit" \
    -p impl=OURS,HASH_MAP,FASTUTIL -p size=1000000 -p dist=DENSE \
    -f 1 -wi 3 -i 5 -rf json -rff slice.json

Allocation profiling (bytes/op) is a JMH profiler flag, not extra code:

java -jar "$JAR" "IntIntMatrixBenchmark.insertGrowing" -prof gc -f 1

Footprint only (fast, deterministic)

./gradlew :benchmarks-jvm:footprintReport
# -> benchmarks-jvm/build/reports/footprint/footprint.{md,tsv}

JOL runs in reflection mode (no agent needed); the numbers match the library's own MemoryFootprintSpec guard.

Result: memory footprint

Retained bytes per entry at n = 229_376 (the 7/8 load of a 2^18 table), each map pre-sized in its own units. Measured with JOL on Apple M4 Max, Corretto 17. The retained totals are exact; bytes/entry are derived and rounded to 0.1 for display, and the ratios are computed from the exact totals (so display rounding never inflates them).

impl	Long→Long B/entry	vs HashMap	Int→Int B/entry	vs HashMap
OURS	19.4	4.59×	10.3	7.11×
HASH_MAP	89.1	1.00×	73.1	1.00×
FASTUTIL	36.6	2.44×	18.3	4.00×
HPPC	36.6	2.44×	18.3	4.00×
ECLIPSE	36.6	2.44×	18.3	4.00×
AGRONA	36.6	2.44×	18.3	4.00×

The memory win is decisive and, notably, holds against the specialist primitive libraries too, not only the boxed baseline: LongLongMap (19.4) is ~1.9× more compact than the competitors (36.6) and IntIntMap (10.3) is ~1.8× more compact than theirs (18.3). The competitors are themselves 2.4×/4.0× more compact than boxed HashMap, and we go further still — because of load factor and layout: our maps pack keys and values plus one control byte per entry at 7/8 load, where the competitors carry parallel key/value arrays at a lower occupancy. This is the project's strongest, most portable result.

Result: time

Absolute time numbers are hardware-specific and must be regenerated on pinned hardware — they are not committed as headline figures (an unpinned laptop with turbo and opaque P/E scheduling is not a citable bench). Run run-matrix.sh on a controlled machine and read jmh-results.json. Two findings are qualitative and survive the hardware caveat, because they are ratios and their effects dwarf the run-to-run noise:

• vs HashMap (the gate): OURS is faster on out-of-cache (1M) random-access lookup and on presized insert; in-cache the margin narrows to near parity as the SWAR + fmix64 arithmetic offsets the saved indirection.

• Distribution robustness (the important one). Our fmix64 finalizer scatters strided keys as well as dense ones, so LongLongMap barely moves between DENSE and CLUSTERED, while the competitors' lighter mixers collapse on the adversarial set. Indicative 1M lookupHit, Apple M4 Max / Corretto 17 (single-machine, ×1–2 forks — the ratios, not the absolute ms, are the point):

  dist	OURS	FASTUTIL	ECLIPSE
  DENSE	9.9 ms	7.7 ms	2.0 ms
  CLUSTERED	10.2 ms	36 ms	13 ms

  On dense keys Eclipse's weak spread keeps 0..n-1 contiguous and cache-resident and it wins; on clustered keys that same weak spread produces long probe chains and it degrades ~6×, while fastutil degrades ~5×. OURS is essentially flat and becomes the fastest map under adversarial keys. A DENSE-only benchmark would have inverted this conclusion — which is why the fairness gate mandates the clustered set.

On raw dense lookup we sit in the same band as fastutil/HPPC/Agrona, not ahead of them; the committed differentiators remain memory, distribution robustness, and multiplatform reach — not single-thread dense-key JVM speed.

Report every number with its baseline named and its environment.txt alongside; never cross-compare JVM and Native as a single figure.