# Benchmarks — the evidence run

Every number below comes from one instrumented harness (`examples/gauntlet.rs` +
`scripts/gauntlet.sh`), rerun in full for this document. ~500 process launches; each cell is
15–35 observations. Raw data reproduces with two commands (bottom).

## Machine

Intel i9-14900KF (8 P-cores + 16 E-cores, 32 threads; L1d 896 KiB, L2 32 MiB total, L3 36 MiB),
64 GiB RAM, kernel 7.1.2 (CachyOS), rustc nightly 1.97, `--release` + `lto=fat`.
**Governor: powersave, turbo enabled** — absolute ns/op would be lower on a performance governor;
every comparison below is within-run, interleaved, so the *ratios* are the stable claim.

## Method

- **Process isolation.** One backend per process; backends interleaved round-robin across launches
  so thermal/scheduler drift lands on everyone equally. This box's process-to-process variance is
  ~±10pp — no conclusion here rests on a single run.
- **Cold vs hot.** `cold` = the first pass after build (rep 0, read path unwarmed); `hot` =
  mean ± sd of all later reps across all launches; `min` = the least-contended observation.
- **Pinning.** Single-thread workloads pinned to one P-core (`taskset -c 2`); parallel workloads
  unpinned (they need the cores).
- **RAM.** Peak-RSS delta (VmHWM) around the structure's lifetime, cross-checked against slot math —
  they agree to <1% (e.g. FreqMap 1M: 34,897 kB measured vs 34,816 kB predicted).
- **CPU.** utime+stime across all threads per op, reported as utilization vs wall — a parallel win
  that burns 26 cores is reported as exactly that.
- Criterion is used only for within-run medians (`benches/`); never for cross-run deltas
  (unchanged code swings ±20–40% between runs).

## What hashbrown is, in its own words — and what we test

hashbrown 0.17's README: a "Rust port of Google's high-performance SwissTable hash map, adapted to
make it a drop-in replacement for Rust's standard `HashMap`"; "SIMD lookups to scan multiple hash
entries in parallel"; "only 1 byte of overhead per entry"; and its default hasher (foldhash) "does
*not provide the same level of HashDoS resistance* as SipHash."

So hashbrown is *designed* for: keyed point lookup/insert, minimal per-entry overhead, single-key
SIMD probing. It is *not designed* for: bulk reads (no batch API), whole-table parallel reduce (no
API), keyless/approximate compact counting, or adversarial determinism. On those faces we do not
compare against a strawman: each face gets the strongest thing a hashbrown user can actually write —
**rayon-parallel hashbrown** for bulk and reduce, an **identity-hashed `HashMap<u64,V>` over our own
fold** (`hbid` — SwissTable's body executing our keep-no-key architecture) for the keyless face, and
an owning `HashSet` plus a Bloom filter for dedup.

## 1. Point ops, opaque strings (hashbrown's designed face) — pinned, ns/op

1M / 4M distinct `&str` keys, presized, hot mean (±sd ≤ ~3):

| backend | build 1M/4M | get-hit 1M/4M | get-miss 1M/4M | RSS @1M |
|---|---|---|---|---|
| hashbrown (keyed)       | 40.5 / 43.8 | 30.7 / 35.2 | 9.9 / 11.8   | 51.3 MB |
| **FreqMap** (keyless)   | **20.8 / 23.4** | **22.8 / 29.8** | 10.2 / 11.3 | **34.9 MB** |
| **Table** (exact, keyed)| 40.7 / 49.3 | **22.6 / 30.3** | 22.6 / 34.2 | 65.6 MB |
| hbid (steelman, keyless)| 22.5 / 22.5 | 16.7 / 22.5 | 7.9 / 9.4    | 34.9 MB |

- **FreqMap vs hashbrown as shipped: build −46…−49%, get-hit −15…−26%, miss parity (+4/−4%,
  inside noise), one-third less RAM.** The domain claim, reproduced at 20–35 obs/cell.
- **Table — the exact, key-returning face — beats hashbrown on out-of-cache hits (−14…−26%).**
  Its build is parity/+13% (a lossy fold must keep the key; `FoldDepth.fold_is_lossy`).
- **Table's miss is +129…+189% — the one accepted loss.** This is THE CUT, on record: the 1-byte
  tag line that rejects misses in one SIMD scan was deleted from the exact face as two extra arrays
  riding on every table for one workload. The remedy is not hypothetical — it is the proven
  byte-tag group probe FreqMap ships (`GroupProbe.winnow_exact`, `home_and_tag_jointly_balanced`),
  which is exactly how FreqMap's miss sits at parity. Miss-heavy exact workloads: use FreqMap in
  front, or wait for the tag port.
- **hbid — the finding we publish rather than bury.** SwissTable's body, fed our 64-bit fold as an
  identity hash, executes the same keyless architecture 25–35% faster still on point ops. Two
  readings, both true: (1) the *architecture* — route by fold, keep no key — is worth ~2× over
  keyed hashbrown in ANY body, ours or theirs; the thesis is vindicated by its strongest opponent.
  (2) FreqLine's probe currently pays 25–35% in implementation constants vs RawTable at identical
  slot size (17B), load, and fold. The gap is constants, not structure: the GroupProbe theorems
  prove both probes share the forced shape (`winnow_exact`, `tag_width_is_maximal`,
  `stop_not_before_placement`). What hbid does NOT have is a flood bound: its home slot is the low
  bits of an unseeded public fold — congruent-fold key sets are constructible offline — and
  triangular probing has no adversarial separation theorem. FreqMap's descent does
  (`chain_separates_within_radix`, `group_descent_dichotomy`). Fast path without the bound, or the
  bound at +25%: today that is the menu; closing the constants is scheduled work, not a hope.

## 2. Point ops, dense/coordinate keys — pinned, shuffled access order

Dense `u64` ids, *randomized* read order (the hard case; sequential/streaming order is far more
favorable and pattern-dependent — the old ~10× read figure is a sequential-order result):

| backend | build 1M/4M | get-hit 1M/4M | RSS 1M/4M |
|---|---|---|---|
| **CoordMap** | **5.4 / 6.8** | **3.6** / 13.3 | **28.2 / 112.5 MB** |
| hashbrown    | 12.3 / 19.6   | 8.1 / 14.3     | 38.8 / 155.0 MB |

Build **2.3–2.9× faster** (no hash, no probe — the address is the key), hit **2.2× faster** while
the table fits cache, **−7% (≈parity)** at 4M where both structures are DRAM-latency-bound — one
random cache line each, and physics doesn't care whose line it is. RAM −27% at both scales (no
stored key, no `Option` tag). Worst-case probe stays 1 under any key pattern.

## 3. Bulk read (sweep) — unpinned, 1M/4M present keys, ns/key

| backend | 1M / 4M | CPU utilization |
|---|---|---|
| hashbrown serial loop        | 31.9 / 41.1 | 1.0× |
| **get_each (one core)**      | **21.9 / 29.3** | **1.0×** |
| get_all (threaded)           | 6.6 / 8.9   | 6.3–7.5× |
| hashbrown + rayon (steelman) | **2.6 / 3.2** | 26.5× |

Verdict, both directions: **rayon-parallel hashbrown wins bulk wall-clock** — with rayon in your
tree, `par_iter` is the bulk read, and `get_all`'s scoped-threads-per-call loses to a persistent
work-stealing pool by ~2.5× (while doing ~25% less total CPU work). The claim that survives is
`get_each`: **−29…−31% vs the serial loop at 1.0× utilization** — memory-level parallelism on a
single core, which no `HashMap::get` loop and no thread pool can express (pipelining requires
owning the iteration; `Web.node_independent` is what licenses overlapping the misses). Use
`get_each` when cores aren't yours to burn; use rayon (or `get_all`) when they are. A rayon-backed
`get_all` is planned — `Web.preduceAt_schedule_free` licenses any scheduler, including theirs.

## 4. Whole-table reduce (encircle) — unpinned, ns/entry

| backend | 1M / 4M | CPU utilization |
|---|---|---|
| hashbrown serial `values().sum()` | 2.4 / 2.6 | 1.0× |
| **encircle**                      | 1.03 / **0.72** | 11–19× |
| hashbrown + rayon `par_values`    | **0.44** / 0.67 | 27–31× |

`encircle` beats serial iteration **2.3–3.7×**. Against the rayon steelman: loses in-cache (their
pool spins up faster than our scoped spawn), **ties at 4M (0.72 vs 0.67, inside sd) at ~70% of
rayon's CPU** — the low-load 16-byte-slot scan is bandwidth-lean. Same planned fix as sweep: a
rayon-pool backend.

## 5. Keyless dedup/count — pinned, 4M-item stream, 1M distinct, ns/item

Stream semantics: keys are transient, so an owning set must copy every distinct key; keyless
structures store nothing per key. Structure RAM = peak-RSS minus the shared 16 MB stream index.

| backend | ns/item | structure RAM | exact? | counts? |
|---|---|---|---|---|
| hashbrown `HashSet<String>` (owning) | 97.8 | ~98 MB | yes | no |
| **FreqMap** | **55.0** | **~35 MB** | 2⁻⁶⁴ fp | **yes** |
| `HashSet<u64>` over the fold | 48.8 | ~19 MB | 2⁻⁶⁴ fp | no |
| Bloom filter (fp 10⁻⁹) | 245.5 | ~5 MB | 10⁻⁹ fp | no |

All four found exactly 1,000,000 distinct. Against the structure everyone actually writes (the
owning set): **−44% time, 2.8× less RAM.** The fold-set steelman is 11% faster and smaller still —
but it is a set (no counts; FreqMap carries an 8-byte value lane), and it inherits hbid's missing
flood bound. Bloom is 5–20× smaller and 4.5× slower with a 10⁻⁹ (vs 2⁻⁶⁴ per-pair) false-positive
rate — a different point on the curve, listed so you can pick it when it's right.

## 6. HashDOS

`examples/redteam.rs`, 12k adversarial keys, build-time blow-up: hashbrown/foldhash `FixedState`
**48×**; Table, same crafted keys, 1.3×; CoordMap 1.0×. hashbrown's README itself disclaims its
default hasher's DoS resistance; seeding it costs determinism. Here there is no seed and no bucket
to flood — `k·PHI` is a bijection, distinct keys separate within `⌈64/bits⌉` digit steps
(`RadixDescent.chain_separates_within_radix`), and the group probe preserves the bound
(`GroupProbe.group_descent_dichotomy`). The steelmen (hbid, fold-set) do NOT carry this property.

## Scorecard — what survives the steelmen

| claim | verdict |
|---|---|
| FreqMap vs hashbrown-as-designed (opaque count/dedup/index) | **wins**: build 1.9×, hit 1.2–1.35×, miss parity, RAM −32% |
| Keyless architecture vs keyed maps | **wins ~2× in every body** — including hashbrown's own (hbid) |
| FreqLine constants vs RawTable at same architecture | **behind 25–35%** on point ops; shape proven equal, constants are work |
| Exact `Table` point ops | hits **win** −14…−26%; build parity; **miss +129…+189%** (the cut; proven remedy shelved) |
| Coordinate keys, random access | build 2.3–2.9×, in-cache 2.2×, RAM −27%, DRAM-bound parity |
| Coordinate keys, sequential access | ~10× (pattern-conditional; criterion `comprehensive`) |
| Bulk read | `get_each` −30% at 1.0× CPU (unique); threaded forms lose to rayon's pool |
| Reduce | 2.3–3.7× vs serial; ties rayon at scale on ~70% CPU; loses in-cache |
| Dedup stream | −44% time, 2.8× less RAM vs the owning set |
| Flood immunity | structural, deterministic, no seed — unique among everything measured |

## Reproduce

```sh
cargo build --release --example gauntlet
bash scripts/gauntlet.sh            # ~20 min; writes /tmp/gauntlet.raw (spec header included)
python3 scripts/gauntlet-report.py  # aggregates: cold/hot mean±sd/min, ratios, CPU, RSS
```

Claims → theorems: `proof/THEOREMS.md`. Within-run medians for the sequential-order and argmin
faces: `cargo bench --bench comprehensive`, `--bench encircle`.