Skip to content

Benchmarks

Every number here is a claim about one machine on one day, and every timed table cites the file under bench/results/ that holds its raw samples and the environment that produced them. The README carries the two headline tables; this page holds the rest and the protocol behind every number — read the ratios, not the absolutes, and what the error bars are before reading a lookup time closely.

bench/reproduce.sh is the other half of that promise: it refuses a tree whose code does not match the commit the artifact will be named after, pins the competitor versions, verifies every corpus against its hash, records the machine, and finishes by putting the run's Python call floor beside the published one — the number no change to this library can move, and therefore the one that says whether your machine is comparable to the one in the tables at all.

This page was recounted on 2026-11-05, at ea82db8, on the 5.0 candidate. One window of 11 h 13 ran 615 cells on one kernel and one compiler, every CPU on the performance governor, with at most 2 MiB of swap in use when a cell started (recount-env-2026-11-05-arz-ea82db8.txt, recount-campaign-2026-11-05-arz-ea82db8.log). Every table that reads the perfect hash past about 1.18 M keys was measured again that day at 7b65814, after the hash's chunk of buckets went back from 2¹⁹ to 2¹⁶, in a second window of 8 h 20 (recount-env-2026-11-05-arz-7b65814.txt, recount-campaign-2026-11-05-arz-7b65814.log); its competitor rows at ten million keys read 0.89–1.04 of the first window's, median 0.99. The older dated rows ran on powersave, as every September artifact that names a governor records. Do not subtract the one from the other: at an unchanged version, the competitors' medians read 0.95–0.99× of 2026-09-25 and MARISA's 1.02×, so a gap of that size across the two proves nothing about a library. Each table names its run.

Not re-measured, and still dated: positioning, the A/Bs of old builds (mphf-cool-ab, dict-onelevel-ab, dict-stair, id-ab), the uuid cold figures, the MPH3 figures with huge pages off at 100 M, and the size floor of MARISA at its smallest at ten million and 19.2 M keys. A version claim is never a comparison of two rows: it needs both builds in one session, as the rel-1m-2026-11-05-arz-ea82db8.txt run of 4.5.3 against this commit does.

How old each section is

Read off this page by bench/tables.py, which CI runs, so a section cannot move without this table moving: the artifacts each section cites, and the oldest and newest of them with the release dated that day, or main past the newest release before it. A size needs no quiet machine and a time does, so a section's newest artifact can be younger than its timed columns; each table says which version it timed. Main after 4.5.3 on 2026-11-05 is 5.0.0 before its version moved: nothing those artifacts time changed after them.

section artifacts cited oldest newest
Every competitor, and the version measured 1 2026-10-31 (main after 4.5.3) 2026-10-31 (main after 4.5.3)
Serialised size on real English words 2 2026-11-05 (main after 4.5.3) 2026-11-05 (main after 4.5.3)
Against other Rust string indexes 2 2026-10-31 (main after 4.5.3) 2026-11-05 (main after 4.5.3)
Which one to pick, and how much the corpus decides it 1 2026-09-19 (main after 3.0.0) 2026-09-19 (main after 3.0.0)
Where lexindex loses 0 — —
The corpus set 0 — —
Every structure over the whole set 11 2026-09-20 (main after 3.0.0) 2026-11-05 (main after 4.5.3)
Lookup speed from Python, against dict and marisa-trie 1 2026-11-05 (main after 4.5.3) 2026-11-05 (main after 4.5.3)
Point-lookup latency vs the standard library 2 2026-11-05 (main after 4.5.3) 2026-11-05 (main after 4.5.3)
The perfect hash against PtrHash and PHast 23 2026-09-10 (2.0.0) 2026-11-05 (main after 4.5.3)
A fingerprinted PerfectHashIndex on mostly-absent keys 3 2026-09-10 (2.0.0) 2026-11-05 (main after 4.5.3)
ClosedHashIndex: the perfect hash alone 1 2026-11-05 (main after 4.5.3) 2026-11-05 (main after 4.5.3)
DictIndex: the ordered dictionary against StringIndex 4 2026-09-11 (2.1.0) 2026-11-05 (main after 4.5.3)
Prefix queries against the tries 1 2026-11-05 (main after 4.5.3) 2026-11-05 (main after 4.5.3)
Common-prefix queries — the other direction 10 2026-09-24 (4.4.2) 2026-11-05 (main after 4.5.3)
Hash quality 4 2026-09-12 (main after 2.1.0) 2026-11-04 (main after 4.5.3)
Error bars, and where a lookup number comes from 4 2026-09-19 (main after 3.0.0) 2026-11-05 (main after 4.5.3)
The research frontier, cited 0 — —
The research frontier, measured 9 2026-09-22 (4.1.0) 2026-11-05 (main after 4.5.3)
Scaling to millions of keys 2 2026-09-19 (main after 3.0.0) 2026-11-05 (main after 4.5.3)
Instructions a key as the keys double 1 2026-11-13 (main after 5.0.0) 2026-11-13 (main after 5.0.0)

Every competitor, and the version measured

Every library this page compares against, at its latest release on 2026-10-31, or at its latest commit where it has none. Bumping one moved no size on this page: each was rebuilt at the new version, and every size came out the same to the last digit published. The recount of 2026-11-05 timed them at these versions, and the last column names the exceptions.

competitor language structure latest in the timed tables
MARISA, s-yata/marisa-trie C++ recursive LOUDS Patricia trie 0.3.1, 3e87d53, 2025-07-20 0.3.1; the floor table's sizes are 0.2.6's, e54f296, the same at 0.3.1 (2026-10-12)
marisa-trie (PyPI) Python over C++ the same trie 1.4.1, 2026-04-08 1.4.1, which bundles C++ marisa 0.2.7, as its main branch does
rsmarisa Rust a port of MARISA 0.4.2, 2026-06-01 0.4.2
XCDAT, kampersanda/xcdat C++ compressed double-array trie 0.2.2, 2451441, 2024-09-10 the same
C²-FST, C²-CoCo, C²-MARISA, alexztc/C2 C++ succinct tries with cache-conscious bit vectors and unary-path compression 92c1b86, 2026-06-20 the same
FST, CoCo-trie, PDT, ART, C-ART, as C² carries them C++ LOUDS-Dense/Sparse trie (SuRF); collapsed-node succinct trie; path-decomposed trie; adaptive radix tree C² 92c1b86; CoCo-trie's adapted headers at ee860d4, 2026-04-09 the same
sdsl-lite, sux (C++), ds2i, FSST: C²'s libraries C++ succinct structures; string compression 0b861c7 2026-10-10, 568903f 2024-10-07, 4f46606 2021-01-21, e638d4c 2026-04-06 the same
fst Rust minimal acyclic finite-state transducer 0.4.7, 2021-06-06 0.4.7, also StringIndex's own dependency
yada Rust byte-wise double-array trie 0.7.0, 2026-06-06 0.7.0; the word-list sizes were 0.5's, the same at 0.7.0 (rust-tries-sizes-2026-10-31-arz.txt)
crawdad Trie, MpTrie Rust character-wise double-array trie; minimal-prefix trie 0.4.1, 2026-08-12 0.4.1
daachorse Rust character-wise double-array Aho–Corasick automaton 5.1.0, 2026-10-18 5.1.0
cedarwood Rust cedar's reduced double-array trie 0.6.1, 2026-09-07 0.6.1
darts-clone, s-yata/darts-clone C++ double-array trie 0.32 at 87b71af, 2025-05-11 the same
dawg2, datrie Python over C++ / C DAWG (dawgdic); double-array trie (libdatrie) 0.13.3, 2025-10-08; 0.8.3, 2025-08-28 the same
jieba, jieba-rs Python, Rust the segmenter whose lexicon and DAG the Chinese runs use 0.42.1, 2020-01-20; 0.11.0, 2026-09-16 the same
ptr_hash Rust PtrHash minimal perfect hash, its Elias–Fano from sucds 0.8.3, the major version it requires (0.11.0 is the latest) 2.1.3, 2026-10-21 2.1.3
ph Rust PHast and PHast+ minimal perfect hashes 0.11.0, 2026-02-12 the same
sux (Rust) Rust PHastR minimal perfect hash 0.15.3, 2026-10-29 0.15.3

Python's dict and Rust's HashMap are the interpreter's and the toolchain's, named beside each table. The research-frontier tables come from bench/frontier/ here and from the string-index-benchmarks suite, whose pins.sh files hold the same C++ commits.

Serialised size on real English words

python bench/compare.py on /usr/share/dict/words (479 823 words, 9.3 B/key raw). Keys are a real vocabulary, never a synthetic entity-{i} sequence — sequential keys collapse the FST to a near-regular automaton and report a misleading ~0 B/key, so the benchmark refuses them. Smaller is better; the capability columns are why you would still pick a larger one.

library prefix common prefix range fuzzy reverse id→str exact membership zero-copy mmap bytes/key ns/lookup
lexindex ClosedHashIndex — — — — — none (closed vocabulary) — 0.24 73
lexindex CompactHashIndex (fp=4 bits) — — — — — probabilistic ✅ 0.74 77
lexindex CompactHashIndex (fp=1) — — — — — probabilistic ✅ 1.24 70
lexindex CompactHashIndex (fp=2) — — — — — probabilistic ✅ 2.24 78
lexindex DictIndex (512 per block) ✅ ✅ ✅ — ✅ ✅ ✅ 2.51 318
lexindex DictIndex (256 per block, default) ✅ ✅ ✅ — ✅ ✅ ✅ 2.62 292
marisa-trie (4 tries, tiny cache — its smallest here) ✅ ✅ — — ✅ ✅ ✅ 2.96 455
marisa-trie (default) ✅ ✅ — — ✅ ✅ ✅ 2.98 439
marisa-trie (huge cache) ✅ ✅ — — ✅ ✅ ✅ 3.07 413
lexindex StringIndex ✅ ✅ ✅ ✅ ✅ ✅ ✅ 5.95 182
lexindex HashedDictIndex (fp=8) ✅ ✅ ✅ — ✅ probabilistic ✅ 6.24 87
lexindex PerfectHashIndex — — — — ✅ ✅ ✅ 9.25 134
DAWG (dawg2) ✅ ✅ — — — ✅ — 23.96 219
datrie ✅ ✅ — — — ✅ — 30.91 525
builtin dict — — — — — ✅ — — (in RAM only) 281

Every cell above is one run of a wheel built from ea82db8, the 5.0 candidate, on performance, in the window of 2026-11-05, whose load average went 0.33 into the run and 0.75 out of it (bench/results/compare-2026-11-05-arz-ea82db8.json) — every cell's build and lookup samples, the false-positive measurement, the CPU, kernel, rustc, Python and the load average at both ends of the run. Its Python call floor is 44 ns, against the 51 of the powersave run of 2026-09-24 at 3a73ed5 this table carried until now, and the controls did not move together: the builtin dict read 14 % slower, marisa-trie 2.8–3.4 % faster, DAWG and datrie 6–9 % faster. So read this table against itself. Beside that run the lexindex rows read faster too, DictIndex 9 %, CompactHashIndex and HashedDictIndex 13–17 %, StringIndex 21 %, PerfectHashIndex 23 %, with no cause separated from the floor's move. Bytes moved most on PerfectHashIndex, 9.25 a key against 10.88, the merged arena, and by 0.5 % on the DictIndex rows. Another session on this page measured a floor of 100 and every row fifty nanoseconds higher, two hours apart and within 2 ns of each other; a run on the same corpus on 2026-09-22, with an editor session on the machine, measured 61 and read 15–20 % slower on every row including the builtin dict. That is the reproducibility problem this page documents further down and the reason bench/reproduce.sh prints the floor beside the published one. marisa-trie appears three times because it is a curve: its own documentation says the right configuration depends on the data, so the table carries its compact end, its default and its fast end rather than one point somebody could call untuned.

What ns/lookup measures. One exact lookup through Python — id on a lexindex index, get on the tries and on the dict — over 100 000 probes, half members and half strangers made by swapping a member's last character for another the corpus uses. Shuffled with a fixed seed, because a strided walk through keys laid out in insertion order is learned by the L2 prefetcher and has reversed a ranking on this machine before. The strangers stay inside every trie's alphabet on purpose: a miss spelled with a character no key contains is rejected at the first node by a trie and still hashed in full by a hash index, which is not a comparison.

Every structure takes one pass per round, five rounds, minimum per cell, with all the others resident while it runs — a harder memory environment than holding one at a time, and the same one for every row. Running each candidate to completion in turn is not the same measurement and is what this benchmark did first: every library was then timed immediately after its own six builds, and CompactHashIndex at a 2-byte fingerprint came out 88 ns in one run and 136 ns in the next. Two consecutive runs of the interleaved form agree within 1.9 % on ten of the thirteen rows; the other three differ by 10.7 %, 5.5 % and 3.7 %, and are the cells nearest the call boundary, where a few nanoseconds is a few per cent.

Two costs are named rather than assumed. The Python call boundary — the same loop calling a function that does nothing — is 44 ns in this run, which every row pays and no difference between rows contains. And .get on a miss is each library's own miss path, not try: t[key] except KeyError: default: timed apart, a miss costs less than a hit everywhere (0.68–0.86×), while that wrapper written out by hand over marisa's __getitem__ costs 1.70× a hit (bench/results/lookup-fairness-2026-11-05-arz-ea82db8.txt). Half the probes are misses, so a library that paid for exceptions would have been charged for CPython rather than for its own structure.

The smallest rows are also the fastest, which is not a paradox. ClosedHashIndex and the three CompactHashIndex widths answer in 70–78 ns against a builtin dict's 281, because they store no keys at all: one hash, one probe, at most a fingerprint to compare. What they cannot do is tell a stranger from a member with certainty, or give a key back for an id. Among the structures that do keep their keys, DictIndex is both smaller and faster than every marisa-trie setting measured at either block — 2.51 B/key and 318 ns at 512, 2.62 and 292 at the default 256, against 2.96–3.07 and 413–455 — and the fastest is HashedDictIndex, that default-block dictionary with a hash beside it: 87 ns at 6.24 B/key, under a third of the builtin dict's time with every query the dictionary answers still on offer, though its id tells a stranger from a member only to within 2^-8.

Two honest crowns, both scoped to what is measured above — libraries a Python or Rust project can actually install. The research-grade C++ frontier (MARISA aside, which is installable) has no binding and is not in these claims: it is listed with its papers and licences under the research frontier, cited and measured on its own protocol under the research frontier, measured. CompactHashIndex is the smallest string → dense id map here that can reject a non-member — 2.4× below marisa-trie at the default 8-bit fingerprint, 4.0× at 4 bits — when you can accept a bounded false-positive rate (about 2^-fingerprint_bits by design — the fingerprint comes from a second hash, uncorrelated with the slot hash for well-distributed keys — measured 0.375 % at 8 bits and 3 in 100 000 at 16 over 100 000 non-member probes in this run, and, on the key hash before 5.0, 6.2530 % at 4 bits and 1.5553 % at 6 over 2 M non-member probes, z = +0.18 / −0.83 against theory) and don't need id → key. It is not a security primitive: both hashes are deterministic and unseeded, so an adversary who chooses the queries can find false positives at will. It stays below marisa's 2.98 B/key at every width up to 21 bits — the width guide tables the trade-off. StringIndex is the only structure here that answers fuzzy and subsequence queries, at 4× below a plain DAWG; an ordered range is a range of ids on DictIndex, which needs no automaton for it. On this corpus DictIndex at its default block is smaller than marisa-trie and answers everything marisa does plus key(id), lower_bound and range — a result about these words at these settings, not a general ranking: a trie's size swings 3× across corpora and marisa carries tuning parameters of its own.

Against other Rust string indexes

marisa-trie is C++, but since 2026-01 it has a pure-Rust port: rsmarisa, BSD-2-Clause, with the same operations — exact lookup, reverse lookup, common-prefix and predictive search, mmap, and binary compatibility with the C++ format. This page used to say no succinct LOUDS trie existed in Rust to depend on, and rested a "smallest pure-Rust ordered index" claim on it. Both were wrong, and the second was wrong about this crate too: DictIndex shipped at 3.52 B/key in 2.0 and was never added to the table below. Measured rather than argued, same real words, one process:

Rust structure bytes/key vs C++ marisa id, half strangers build
lexindex DictIndex (512 per block) 2.508 0.84× 269 ns 24 ms
lexindex DictIndex (256 per block, default) 2.622 0.88× 242 ns 26 ms
lexindex DictIndex (64 per block) 2.710 0.91× 211 ns 27 ms
marisa-trie (C++ reference, default) 2.978 1.00× — —
rsmarisa (4 tries, tiny cache — its smallest) 3.003 1.01× 325 ns 137 ms
rsmarisa 0.4.2 (default) 3.168 1.06× 301 ns 145 ms
rsmarisa (3 tries, huge cache — its fastest) 3.823 1.28× 282 ns 167 ms
fst::Set (membership only — no ids, no reverse) 4.85 1.63× — —
lexindex StringIndex (ordered + fuzzy + reverse) 5.95 2.00× — —
yada (double-array) 15.98 5.4× — —
crawdad::MpTrie (minimal-prefix) 19.63 6.6× — —
crawdad::Trie (double-array) 26.22 8.8× — —

rsmarisa and DictIndex from bench/results/rsmarisa-2026-11-05-arz-ea82db8.txt — one process: 20 000 probes, half members and half strangers spelled in the corpus's own alphabet, shuffled with a fixed seed; five rounds with the six lanes alternating and reversing on odd rounds, the first discarded and the minimum of the other four kept. Three such processes, on performance, the table quoting the minimum of the three. The other rows are sizes from the older sweep with crawdad 0.4, yada 0.5 and fst 0.4, the same to the hundredth at 0.4.1, 0.7.0 and 0.4.7 (rust-tries-sizes-2026-10-31-arz.txt); size is serialised bytes ÷ keys throughout, and rsmarisa's io_size() is asserted equal to the file it saves. rsmarisa is the control across sessions: its lanes read 1–3 % over the powersave run of 2026-09-23, and DictIndex's 18–19 % under it; the search changes of 4.3.3 and 4.4 lie between the two runs, and two sessions cannot separate them from the governor. In the session before that a further process, run seconds after a git commit, read 8–20 % slower on every row including rsmarisa's and was discarded on that evidence rather than on its shape — which is the whole reason this page insists on a control that the change under test cannot touch. None of these crates is a lexindex dependency: the harness is a throwaway.

So the statement is a crown after all, with the frontier behind it. DictIndex at its default block dominates rsmarisa at its most compact setting outright — 2.622 against 3.003 B/key, 242 against 325 ns, 5.3× faster to build — and at 64 per block it is the fastest structure here at 211 ns for 2.710, under rsmarisa's smallest setting on both axes at once. Since BDX3 every block from 64 to 512 is smaller than every rsmarisa setting, so the block size now picks only the latency axis, not the size one.

Two further things the table settles. The Rust port is larger than the C++ original on this corpus (+6.4 % at the default, +1.6 % at its smallest), so a pure-Rust project pays for the port. And reaching marisa's 2.98 as a trie remains closed to the fst route: the byte-oriented automaton is ~1.6× away by construction, and even a bare fst::Set storing no ids at all is 4.85. DictIndex gets under marisa by not being a trie — front-coded blocks under one FSST table — and CompactHashIndex takes the size crown the third way, by dropping the keys entirely.

Which one to pick, and how much the corpus decides it

Every size above is one corpus at one n, and the ranking is stable across neither. The reason is structural: a trie's size depends on how much the keys share, and a fingerprint index's does not. The same structures over three corpora built from the same word list, one process per cell (local/positioning.py, 2026-09-19 at 999e933, positioning-2026-09-19-arz-999e933.txt; the bare-MPHF row is a ClosedHashIndex built over the same three key sets in the same session; sizes only, not re-measured on 2026-11-05, and the PerfectHashIndex row predates its overlapped arena, which holds single words in 9.25):

bytes/key 479 823 single words 1 M word.word pairs, drawn at random 1 M word.word, 1 000 × 1 000 grid
the bare MPHF (no keys, no membership, no reverse) 0.24 0.24 0.24
lexindex CompactHashIndex (fp = 1 byte) 1.24 1.24 1.24
lexindex DictIndex (256 per block) 2.65 6.84 1.95
marisa-trie 2.98 6.21 2.12
lexindex StringIndex 5.95 15.19 0.68
lexindex PerfectHashIndex 10.88 21.91 12.49

The DictIndex row swaps places with the marisa-trie one inside a single table — under it on single words and on the grid, 1.10× over it on random pairs — which is the whole argument of this page in three columns: the two are different shapes, and which is smaller is a property of the keys. The grid is where BDX3 changed the answer: at 2.50 bytes a key it sat 1.18× over the trie, at 1.95 it is 8 % under. At 10 M the trie numbers move again — marisa 4.14 on random pairs against 2.36 on the grid, StringIndex 12.44 against 2.00, DictIndex 5.51 against 2.58 — while CompactHashIndex stays at 1.24 and the bare MPHF at 0.24, because their size is a function of n and the fingerprint width alone. The grid is a full cross product and is the most favourable set a trie can be handed; it is what the scale table below uses, and on it StringIndex at 0.68 B/key undercuts even a keyless perfect hash. Treat that as the ceiling of what shared structure can buy, not as a headline.

So, in decision order:

  • Do the keys need to come back out, or be scanned in order? If yes, the fingerprint indexes are out; StringIndex (ordered, prefix / range / fuzzy / subsequence), DictIndex (ordered, id → key, lower_bound, prefix, range, no automata so no fuzzy — the smallest of the three on single words) or PerfectHashIndex (exact membership, id → key, no ordering) are the candidates, and all three pay for the keys they store.
  • Is a bounded false-positive rate acceptable? If yes, CompactHashIndex is 2.4× smaller than marisa-trie on single words, 5.0× on random pairs and 3.3× at 10 M — and one byte per key larger than a bare MPHF (1.24 against 0.24), which is exactly the fingerprint that buys the membership check.
  • Do the keys share a lot of structure (a path namespace, a versioned catalogue, a cross product)? Then measure before choosing: that is the regime where an FST can beat a keyless hash outright.
  • A dict / HashMap is not in the table because it has no serialised form to measure. It cost 71–95 bytes per key above the key list itself across these corpora (58–60 at 10 M, where the table amortises better), and it has to be rebuilt from the keys on every process start; every structure here loads from a file instead, and every one but ClosedHashIndex by mapping it.

Where lexindex loses

Every loss measured so far, in one place; each line links to the section that measured it.

  • Exact id against XCDAT 15. At a million keys lexindex's fastest exact search over sorted ids is behind on six corpora of thirteen, by 1.20–1.41×. It is within 3 % either way on words, paths, uuid and titles-ru, and ahead on numeric, dna and urls (measured). At ten million keys opaque is 1.35× behind, 425 ns against 316, and the other five corpora are ahead. HashedDictIndex is 4.0–8.6× faster than XCDAT in a free loop and 1.7–3.7× when each lookup waits on the last, through id_unchecked, which takes a key's membership on trust, so it is not an exact search (against XCDAT).
  • Size on paths without labels. MARISA at its smallest, 8.81 bytes a key at 23 tries under the tiny cache, beats a plain DictIndex block 1024's 9.28 there; only the opt-in labels=True build takes the corpus. And at lexindex 4.5.2, at ten million keys and at 19.2 million, mapped MARISA was 0.4–1.8 % smaller on titles-en and urls, where DictIndex is the smaller by file (MARISA at its smallest).
  • Bits against PHastR built on one thread. MPH3 takes 1.925 / 1.915 / 1.911 bits a key at 1 M / 10 M / 100 M, PHastR 1.919 / 1.904 / 1.902 at bucket size 4.5 and 1.850 / 1.823 / 1.819 with 10-bit seeds (the perfect hash).
  • The eight-thread build against PHastR at 1 M and 10 M. MPH3 reads 13.6 / 10.5 ns a key against PHastR's 10.4 / 10.1, which takes higher bits than MPH3 at 1 M and lower ones at 10 M; at 100 M MPH3 leads, 8.7 against 10.8 (the perfect hash).
  • Eight lookup threads at a billion keys. MPH3's batch is 17 % behind PtrHash compact on the same memory: it fetches 0.98 lines a key from DRAM against compact's 0.82. With huge pages on, its single lookup is 5 % behind PtrHash fast's, 3.6 ns against 3.4; with them off the two are level (the perfect hash).
  • The double array's build. 0.160 s on the jieba dictionary, 3.0× darts-clone's time and 1.6× cedar's (on Chinese running text).

The corpus set

Everything above is one corpus at one n, which is why the section before it exists. The set that can settle the question is built by bench/corpora.py: thirteen corpora at 100 000, 1 000 000 and 10 000 000 keys wherever the source has them, nested so that the small file is a prefix of the large one and a difference between two sizes is scale and never composition.

corpus keys available B/key what it is
words 479 823 9.3 the Fedora word list — every table above is this one
titles-en 19 217 770 21.0 English Wikipedia article titles
titles-ru 4 988 075 35.8 Russian titles: Cyrillic, two bytes a character
titles-zh 2 997 733 16.9 Chinese titles: three bytes a character, and short
urls 19 217 771 52.4 those titles as https://en.wikipedia.org/wiki/…
domains 1 000 000 13.8 registered domains, the Tranco ranking
pypi 889 864 13.3 PyPI package names
paths 7 311 150 125.1 this machine's filesystem
idents 1 047 267 17.3 identifiers in the vendored Rust sources
uuid generated 36.0 UUIDv4, hyphenated
numeric generated 4.9–6.9 dense decimal ids, 0 to n-1
opaque generated 16.0 16-symbol base64url ids
dna generated 24.0 24-mers over ACGT

The four generated corpora are seeded rather than random: the same file comes out of the same version of the script, on any machine. The fetched ones are pinned — a dated Wikipedia dump and not latest, a Tranco list by its permanent id — and both the download and every file derived from it carry a SHA-256 in bench/corpora.json. python bench/corpora.py verify re-hashes what is on disk and says which files have moved. The corpora themselves are gitignored: 4.6 GB of keys has no place in a git history, and the manifest is what makes them checkable without it.

Two of them are honest about their limits. paths is this machine's /usr and $HOME, so it is reproducible nowhere else — the manifest records the host. idents is whatever crates this machine has vendored, which is a sample of Rust, not of source code. Both are samples of a filesystem that keeps moving, this repository's own build directory included, so build keeps what is on disk when it matches the manifest and only build --force draws a new one: two sweeps a week apart otherwise compare different paths corpora and report the difference as a change in the index.

What no single corpus can support is the claim of which structure is smallest, and where. The next section settles it.

Every structure over the whole set

bench/sweep.py builds eleven structures on each corpus and measures serialised bytes per key, build time and one lookup: three DictIndex block sizes against five marisa-trie configurations, because both are curves and a single point of either invites the objection that the other was left untuned. Marisa's curve runs to sixteen tries because four — its floor on an English word list, and what this page took for its floor everywhere — is not where it bottoms out on keys that share more, or on keys that share nothing. The two keyless indexes are there to show what a structure that stores no keys costs, which turns out to be the only row a reader can carry to their own corpus without measuring it.

Bytes per key at one million keys

corpus raw ClosedHash CompactHash Dict 128 Dict 256 Dict 1024 String marisa 4 marisa 8 marisa 16 marisa def. marisa fast
dna 24.0 0.24 1.24 4.45 4.37 4.23 17.74 7.52 7.52 7.52 7.56 7.71
domains 13.8 0.24 1.24 4.53 4.48 4.34 10.50 4.81 4.80 4.80 4.87 4.99
idents 17.3 0.24 1.24 5.28 5.22 5.06 10.55 5.45 5.34 5.30 5.62 5.74
numeric 5.9 0.24 1.24 1.04 1.01 0.92 0.00 1.62 1.62 1.62 1.64 1.72
opaque 16.0 0.24 1.24 10.43 10.40 10.29 21.44 18.23 15.55 15.55 18.82 19.04
paths 125.0 0.24 1.24 10.28 9.83 9.28 17.48 9.26 9.04 8.83 9.47 9.60
titles-en 21.0 0.24 1.24 7.40 7.33 7.18 17.28 7.79 7.52 7.49 8.19 8.37
titles-ru 35.8 0.24 1.24 6.90 6.84 6.67 31.75 8.07 7.67 7.61 8.61 8.77
titles-zh 16.9 0.24 1.24 5.87 5.83 5.67 17.52 6.33 6.22 6.22 6.54 6.70
urls 52.4 0.24 1.24 7.67 7.49 7.24 16.88 7.95 7.61 7.57 8.39 8.58
uuid 36.0 0.24 1.24 18.11 18.04 17.89 37.11 32.93 22.99 22.98 34.58 34.80

The bold cell in a row is the smallest structure that keeps its keys. words, pypi and jieba-dict have no million-key file; their 100 000 grid and the 100 000 rows for the rest are in bench/results/sweep-2026-11-05-arz-ea82db8.json — one run of the whole set at ea82db8, 275 cells, and every column above comes from it, the three DictIndex blocks included, so this table needs no reconciliation between harnesses. Against the 4.3.0 run (sweep-2026-09-23-arz-4f2a0e9.json), 181 of the 275 read the same to the fourth decimal. The 94 that moved are 46 of the 50 keyless cells, by at most 1.3 %, with the key hash of 5.0 between the runs, and 48 DictIndex cells, by −1.17 % to +2.70 %. Of the 264 cells that 4.3.0 run shares with the 4.0.0 one (sweep-2026-09-20-arz-8a8778a.json), 252 read the same to the byte; the twelve that moved are the DictIndex cells of titles-ru and titles-zh.

DictIndex is the smallest key-storing structure on ten of these eleven corpora, measured against marisa's best setting on each and not its default. The margin runs from 4.4 % on titles-en (7.18 against 7.49) and 4.5–4.9 % on urls and idents, through 10 % on titles-zh and domains and 14 % on titles-ru, to 28 % on uuid, 51 % on opaque, 77 % on numeric and 78 % on dna. The eleventh is paths, where a million paths run through a few thousand directories and marisa at sixteen tries holds 8.83 against 9.28 — 4.9 % — which is what a LOUDS trie is for and what front coding in fixed blocks still does not answer. Through 3.0.0 this table read the other way round, marisa smallest on nine of the eleven; the BDX3 codec is what turned it, and 4.0.0's phrase work moved all 72 DictIndex cells of the sweep again — 71 of them down, domains by 4.9 % and paths by 3.0 %, with titles-zh at 1024 keys a block the one cell that grew, by 0.05 %. 4.3.0's character code moved twelve and nothing else: titles-ru 10.1–11.1 % smaller at a million keys and 13.8–14.7 % at 100 000, titles-zh 6.7–7.0 % and 9.2–9.3 %, which took their margins from 2.2 % and 1.6 % to 14 % and 9 %. A code can only pay where two bytes in fifteen or more are outside ASCII, so the Latin corpora keep their blobs byte for byte.

Its floor is eight or sixteen tries on nine of the eleven, not the four this page quoted through 3.0.0. The recursion keeps paying wherever the keys share — titles-ru 8.07 → 7.61, urls 7.95 → 7.57, paths 9.26 → 8.83, about 5 % each — and it pays most where they share least: opaque 18.23 → 15.55 and uuid 32.93 → 22.98, 15 % and 30 % of the blob. The two corpora where four tries is not beaten are dna and numeric, where all three settings agree to the hundredth; on domains the gain is 0.3 % and on titles-zh 1.8 %, so "tune it" is worth measuring and not worth assuming. What the tries cost is time, and the cost is where the gain is: uuid builds 1.35× and answers 1.59× slower at sixteen tries than at four, paths answers 1.22× slower, and on the corpora where the setting buys nothing the two are level. Marisa's smallest configuration is its slowest.

The margin is still widest where the keys share least. DictIndex leads by half a blob on opaque (10.29 against 15.55) and by more than that on dna and numeric — keys with nothing to share, where a trie pays for a node per character and front coding pays for a prefix that is not there. Where the keys do share, the lead is a couple of per cent and a tuned marisa is the thing to measure against: on urls and titles-en the two are within 5 % of each other, and paths is still marisa's. On words, the corpus every table above is measured on, DictIndex at its default block is 3.33 against marisa's 3.70 at 100 000 keys and 2.62 against 2.96 on the full 479 823 — and there four tries really is marisa's floor, eight and sixteen reading 3.71 and 3.74. Read the spread between dna and paths as the honest range: which is smaller is a property of the keys, and the corpus set is there so that neither end can be quoted alone.

The two keyless rows are flat and every other row is not. ClosedHashIndex is 0.24 bytes a key and CompactHashIndex 1.24 on all eleven corpora at all three sizes, because their size is a function of n and the fingerprint width and of nothing about the keys. Against the best trie that is a 7.1× margin on paths and 1.3× on numeric — the same two structures, neither of them changed, and the whole spread between those two numbers belongs to the corpus.

StringIndex on numeric reads 0.00 bytes a key, and it is not a bug. Ten million dense decimal ids compile to an FST of 356 bytes: the automaton is very nearly regular, one path per digit, and the keys are recovered from the transitions. Read it as the ceiling of what shared structure can buy an FST and never as a size claim — it is exactly the ~0 B/key that bench/compare.py refuses to report for synthetic entity-{i} keys, and it is in this table only because dense ids are a corpus somebody really has.

Lookups at one million keys

corpus raw ClosedHash CompactHash Dict 128 Dict 256 Dict 1024 String marisa 4 marisa 8 marisa 16 marisa def. marisa fast
dna 24.0 63 117 341 339 355 542 914 988 978 934 917
domains 13.8 62 120 387 397 436 389 734 753 747 735 722
idents 17.3 62 110 417 423 476 386 926 980 1016 892 857
numeric 5.9 52 71 296 294 316 90 269 264 263 260 235
opaque 16.0 78 107 339 335 365 368 1372 1462 1414 1105 1106
paths 125.0 81 134 697 699 751 875 2914 3327 3546 2461 2157
titles-en 21.0 73 107 430 436 488 483 1103 1156 1164 1094 1031
titles-ru 35.8 80 127 492 493 532 655 1553 1603 1582 1392 1396
titles-zh 16.9 67 123 444 447 502 430 1016 1031 1031 952 909
urls 52.4 68 121 449 455 498 557 1216 1343 1520 1212 1129
uuid 36.0 84 117 416 399 422 475 1708 2688 2721 1298 1240

DictIndex answers faster than every marisa-trie setting on ten of the eleven corpora — 1.8–3.3× at its default block, against marisa's fastest setting on each and not its smallest. The eleventh is numeric, where marisa's fastest is 20 % ahead of the default block (235 ns against 294) and StringIndex ahead of both at 90: a million dense decimal ids are the corpus where a trie has the least to walk. DictIndex also builds 2.5–7.7× faster than marisa's quickest build on all eleven, numeric included, where marisa was 1.2× ahead through the 2026-09-19 run. So the size table above is not the whole trade, and the settings that make marisa smallest are the ones that make it slowest: on paths, the one corpus it still wins on size, its sixteen-try floor is 1.05× smaller than DictIndex at 1024 a block, 4.7× slower to answer and 4.2× slower to build.

The block is a smaller knob than it was. A lookup scans one restart a microblock and then one microblock whatever the block, so 128 → 1024 keys a block moves a lookup by +1.5 % (uuid) to +14 % (idents), where the one-level format paid 3.8× from 32 to 1024, and buys 0.12–1.00 bytes a key over 128, every corpus in the same direction. It did not use to be: paths at 1024 keys a block stored more than at 256 (16.13 against 15.89), and the cause was the symbol table rather than the layout, whose per-block arrays only shrink as the block grows. The table trained on whole blocks, so a larger block bought fewer neighbourhoods — 19 at 1024 against 157 at 128 — and a table trained on 19 of them is a lottery. A training run is now a constant 256 keys whatever the block, trained per shard of 65 536 keys, and paths at 1024 reads 9.28. 256 is the default the README quotes.

Measured 2026-11-05 at ea82db8, on performance, from sweep-2026-11-05-arz-ea82db8.json, whose load average went 0.40 into the run and 1.08 out of it. Lookups are one run of three rounds of 20 000 probes a cell, so a column is comparable within itself and a cell carries a few per cent: in September a second run of one build read the same bytes to the last digit and lookups 1–15 % higher on every structure, controls included.

Ten million keys

corpus raw ClosedHash CompactHash Dict 128 Dict 256 Dict 1024 String marisa 4 marisa 8 marisa 16 marisa def. marisa fast
dna 24.0 0.24 1.24 4.03 3.95 3.81 15.98 6.69 6.69 6.69 6.75 6.99
numeric 6.9 0.24 1.24 1.04 1.02 0.92 0.00 1.63 1.63 1.63 1.66 1.77
opaque 16.0 0.24 1.24 10.08 10.05 9.95 21.47 15.19 14.72 14.72 18.33 18.68
titles-en 21.0 0.24 1.24 5.60 5.53 5.37 13.25 5.57 5.49 5.48 5.71 5.87
urls 52.4 0.24 1.24 5.87 5.68 5.42 13.10 5.66 5.56 5.55 5.83 5.99
uuid 36.0 0.24 1.24 17.63 17.56 17.42 36.07 29.97 20.62 20.62 33.21 33.56

Ten times the keys moves every trie and neither hash: at its floor marisa goes 7.49 → 5.48 on titles-en and 7.57 → 5.55 on urls as the sharing deepens, DictIndex at its default block 7.33 → 5.53 and 7.49 → 5.68, and the two keyless rows do not move at all. Through 3.0.0 this was where the ranking turned over: titles-en and urls are two of the ten corpora DictIndex leads at a million, and at ten million the trie took both back, by 2.8 % and 0.7 %. It no longer does. At 1024 keys a block titles-en reads 5.366 against 5.484 and urls 5.422 against 5.548, a 2.1 % and a 2.3 % lead, where the 4.3.0 run read 0.11 % and 0.33 %: since then a build past about 2.6 million keys mines its phrases from more of its sample, 1.9–2.1 % smaller on these two corpora and the same bytes on the other four. At the default block of 256 the trie's floor still holds both, 5.53 against 5.48 and 5.68 against 5.55. Read each lead as what a build setting can move, not as a comfortable win.

Scale narrows every gap in the trie's favour. DictIndex is smallest on all six at ten million, four of them by a distance — dna 3.81 against marisa's tuned 6.69 and numeric 0.92 against 1.63, both 43 %, opaque 9.95 against 14.72 and uuid 17.42 against 20.62, 32 % and 16 % — but three of those four margins are narrower than the same corpus gives at a million and numeric is level, uuid most of all, 22 % there against 16 % here. The reason is the trie's, not ours: ten times the random identifiers share ten times more three- and four-character fragments, and a recursive trie is built to find exactly that, while a block of front-coded keys shares only with its own block. Read the margins as gaps that narrow with n, and do not build a claim on a single one of them.

The block buys less here. 128 → 1024 keys a block is 0.12–0.45 bytes a key over these six, against 0.12–1.00 at a million. Ten times the keys is ten times the blocks, so the per-block arrays a bigger block saves were already a smaller share of the index; what is left is the coded suffixes, and those are the symbol table's business, not the block's — which is why the table is trained on runs of a constant length and per shard. With whole-block training over one table a bigger block bought fewer neighbourhoods to train on, and titles-en at 1024 came out above its own 256.

Measured 2026-11-05 at 7b65814 (bench/results/sweep10m-2026-11-05-arz-7b65814.json), marisa-trie 1.4.1, one build per cell at this size and three rounds of 20 000 lookups. Sizes only: this table has no timed column. Every marisa cell reads to the hundredth what the runs of 2026-09-13, 09-19 and 09-23 read: a size is exact, so runs agree wherever the builder did not move. Against the 4.3.0 run (sweep10m-2026-09-23-arz-4f2a0e9.json), 48 of the 66 cells read the same to the byte. Of the eighteen that moved, six are the three DictIndex blocks on titles-en and urls, by −1.86 % to −2.07 %, and twelve are the keyless rows, by −0.09 % to +0.01 %.

A cold mapping, and what is actually resident

Every size in this page is the blob. A process that maps one and answers a thousand queries never reads most of it, and what decides whether an index fits inside a container limit is the resident set. local/coldmmap drops each file's page cache with posix_fadvise(POSIX_FADV_DONTNEED) — no root needed, and the resident set straight after load_mmap is the control that the drop worked — then reads /proc/self/smaps after 1 000 random lookups and after a further million.

Ten million English Wikipedia titles, bytes per key except the latencies:

structure file mapped after 1 k after 1 M cold ns warm ns
DictIndex 32 6.01 0.75 4.64 6.01 30 282 546
DictIndex 32, MADV_RANDOM 6.01 0.75 1.82 6.01 81 198 1 455
DictIndex 256 5.53 0.12 4.15 5.53 29 346 539
DictIndex 256, MADV_RANDOM 5.53 0.12 1.05 5.53 93 819 1 519
DictIndex 1024 5.37 0.06 3.97 5.37 29 737 576
DictIndex 1024, MADV_RANDOM 5.37 0.06 1.16 5.37 125 404 1 492
CompactHashIndex 1.24 0.24 1.23 1.24 6 039 27
CompactHashIndex, MADV_RANDOM 1.24 0.24 0.70 1.24 62 728 149
StringIndex 13.25 0.01 10.10 13.25 88 172 645
StringIndex, MADV_RANDOM 13.25 0.01 2.27 13.25 418 978 3 128

load_mmap really is lazy, which the mapped column exists to prove: 0.01 to 0.75 bytes a key resident before the first query, which is the header and the little the loader validates. Nothing else is read until something asks for it. The figure rises as the block shrinks because a smaller block means more per-block arrays, and BDX3 validates their framing at load.

The first thousand queries cost far more pages than they need. DictIndex at 256 ends them with 4.15 of its 5.53 bytes a key resident — 75 % of an index nobody has finished reading — while the same thousand queries under MADV_RANDOM leave 1.05, which is what they actually touch: about two pages a lookup, the sample array and the block. The 4.0× between those two numbers is the kernel's readahead, and it is buying latency with memory: turning it off costs 3.2× on the cold lookups and 2.8× on the warm ones, because the advice outlives the warm-up. The warm column is also where the microblock shows on ten million keys: 1024 a block answers in 576 ns where the one-level format took 2 108. Readahead is the right default here; MADV_RANDOM is for the case where a container limit, and not a latency budget, is what binds.

Cold start is where the smallest structure wins outright, and the mechanism is pages. CompactHashIndex answers its first thousand queries at 6.0 µs against DictIndex's 29.3 and StringIndex's 88.2 — 4.9× and 15× — because its whole file is 12.4 MB and a fault brings in a useful fraction of it. On uuid, not re-run in the recount, where its 1.24 bytes a key sit against DictIndex's 17.56 and StringIndex's 36.07, the powersave run of 2026-09-22 read 19× and 46× (5.2 µs against 99.9 and 240.4). A structure that stores no keys has no keys to fault in.

After a million queries every structure is fully resident, to within a hundredth of a byte. The distinctive answer to "how much memory does this index need" only exists during warm-up: past it, against a workload that touches every key, the resident set is the file, and the size table above is the steady-state RSS.

Measured 2026-11-05 at 7b65814, on performance, NVMe under LUKS on btrfs, 38 GB RAM — so "cold" means this file's page cache was dropped and not that the machine was short of memory (bench/results/coldmmap-2026-11-05-arz-7b65814.txt; the uuid run is in coldmmap-2026-09-22-arz-41478d0.txt). StringIndex is the control: its resident columns are identical to the 2026-09-22 run's to the hundredth (0.01 mapped, 10.10 after a thousand, 13.25 after a million), and its latencies read 0.2 % slower cold and 23 % quicker warm; this run cannot separate the governor from later work on its reader. DictIndex moved its bytes for a reason: at 256, 5.65 → 5.53 on disk and 4.17 → 4.15 resident after a thousand queries. CompactHashIndex's cold column read 13 % slower, 5 336 → 6 039 ns, and its warm one 28 → 27, with the key hash of 5.0 between the two runs. MADV_RANDOM is applied by the harness through /proc/self/maps; load_mmap does not set it, and on this evidence should not.

One mapping, many readers

Every index here is immutable once built. A reader needs no lock, no copy and no per-thread instance: one load_mmap is shared by reference and answers from as many threads as there are cores. local/readscale is whether that is near-linear — 8 Mi random member probes split evenly, the mapping warmed first so this measures the structure and not page faults, the ladder run three times and the best kept per thread count.

Ten million English Wikipedia titles, nanoseconds a lookup with the speedup over one thread:

threads DictIndex 128 CompactHashIndex StringIndex
1 518 17.1 594
2 264 (1.96×) 11.4 (1.50×) 297 (2.00×)
4 134 (3.86×) 6.3 (2.71×) 150 (3.95×)
8 69 (7.49×) 3.8 (4.50×) 80 (7.47×)
16 42 (12.32×) 3.6 (4.75×) 47 (12.70×)
M lookups/s at 16 23.8 275 21.4

Eight cores give 4.5–7.5×, 56–94 % of them, on a mobile part whose clock falls as cores light up — the number already carries that, so a machine with a flatter boost curve can only do better.

The sixteen-thread row is SMT and it is worth having. 12.3× and 12.7× over one thread for the two structures that answer out of DRAM, well past the eight physical cores, because a point lookup is a chain of dependent loads and a core spends most of it waiting. A second thread on the same core fills those stalls with someone else's work.

StringIndex and DictIndex scale alike — 2.00× and 1.96× on two threads, 12.70× and 12.32× on sixteen. Both walks are dependent misses, and two cores keep twice as many of them in flight as one. At a million keys, where the 17 MB transducer and the 7.4 MB dictionary sit mostly in cache, there is less to overlap: 1.93× and 1.89× on two, 12.60× and 10.50× on sixteen.

CompactHashIndex saturates first, at 4.75×, and it is the one structure that has run out of something other than cores: 275 M lookups a second over a 12.4 MB index that fits this machine's 16 MB L3, at 3.6 ns a lookup. The others are answering out of DRAM and have latency left to overlap; this one does not. It saturates earlier than it did on 3.0.0 — 9.43× then, 4.75× now — for the good reason that its single-thread lane got about 50 % quicker while its sixteen-thread lane, already bandwidth-bound, moved 3.7 → 3.6 ns.

Measured 2026-11-05 at 7b65814, on performance (bench/results/readscale-2026-11-05-arz-7b65814.txt, which carries the million-key ladder as well), Ryzen 7 5800HS, 8 cores and 16 hardware threads. Shared by &index across std::thread::scope; no index is cloned and none is rebuilt per thread. Three processes and the minimum per cell; CompactHashIndex at ten million is the column that needed them, reading 24.3 / 17.1 / 24.7 ns on one thread and 3.7 / 3.6 / 3.8 on sixteen across the three, where StringIndex spread 6–8 % and DictIndex at most 2 %. The powersave run of 2026-09-23 (readscale-2026-09-23-arz-fdc28bc.txt) read DictIndex 128 at 605 ns over 5.71 bytes a key, StringIndex at 803 and CompactHashIndex at 15.9 on one thread.

rsmarisa, the pure-Rust port

The same question in Rust, where marisa-trie is a C++ library with no binding a Rust project would take. rsmarisa 0.4.2 is a pure-Rust port of it, BSD-2-Clause, and local/rsmarisacmp puts its three cache levels against three DictIndex block sizes, 64, 256 and 512, on every corpus:

corpus rsmarisa smallest DictIndex 512 rsmarisa build DictIndex build rsmarisa fastest DictIndex fastest (block)
dna 7.61 4.25 1 280 ms 63 ms 604 ns 228 ns (64)
domains 4.87 4.35 680 ms 147 ms 475 ns 262 ns (64)
idents 5.50 5.06 639 ms 167 ms 612 ns 308 ns (64)
numeric 1.64 0.92 102 ms 37 ms 161 ns 254 ns (256)
opaque 18.27 10.29 1 534 ms 76 ms 1 030 ns 238 ns (256)
paths 10.07 9.39 5 532 ms 365 ms 1 693 ns 577 ns (512)
titles-en 7.85 7.19 1 017 ms 296 ms 804 ns 318 ns (64)
titles-ru 8.22 6.70 1 493 ms 240 ms 1 056 ns 379 ns (256)
titles-zh 6.40 5.68 777 ms 177 ms 672 ns 317 ns (64)
urls 8.38 7.29 2 006 ms 299 ms 839 ns 336 ns (256)
uuid 33.01 17.91 2 065 ms 127 ms 1 149 ns 278 ns (512)

BDX3 changed the shape of this table. Through 3.0.0 rsmarisa was the smaller structure on nine of these eleven corpora — everything but opaque and uuid, the two whose keys share nothing for a trie to fold. It is now larger on all eleven: 7.2 % on paths and 8.7 % on idents at the narrow end, and 78–84 % on dna, opaque, decimal ids and UUIDs at the wide one, while DictIndex builds 2.8–20× faster and answers 1.8–4.3× faster on ten of the eleven. numeric is the one exception left, and only on latency: rsmarisa answers it in 161 ns against 254, having lost the size there (1.64 against 0.92) and the build (102 ms against 37). The right-hand column has no single answer for the block: the fastest is 64 on five corpora, 256 on four and 512 on two, and on five the three are within 10 % of each other. The ends are what it teaches. Short keys — domains, idents — are 15–20 % slower at 512 than at 64, where the scan is what a lookup waits on; uuid, whose 18 MB blob is the one larger than the L3, is 22 % slower at 64 than at 512, where fewer blocks are fewer dependent misses in the search over their heads. At nominally the same configuration rsmarisa is larger than the C++ marisa measured above — on words, 1.6 % at the smallest setting, 6.4 % at the default and 24 % at the fastest — so the flag words evidently do not mean quite the same thing, and each library's own curve is what to read. "Smallest" here is the smallest of its three cache levels at the default number of tries, not its floor: the sweep above shows the C++ library bottoming out at eight or sixteen tries on nine of these corpora, by 30 % on uuid, and this harness does not turn that knob. Read the left column as one point on a curve whose other end is not measured.

Measured 2026-11-05 at ea82db8, on performance (bench/results/rsmarisa-2026-11-05-arz-ea82db8.txt), rsmarisa 0.4.2, in one process per corpus, six lanes alternating within each of five rounds, on corpora checked against the manifest's hashes. rsmarisa's lanes, whose code has not changed, read −8.5…+3.7 % against the powersave run of 2026-09-23 (rsmarisa-corpora-2026-09-23-arz-fdc28bc.txt), and DictIndex's −9…−23 %. It is a throwaway crate under local/: rsmarisa is not a lexindex dependency and is not proposed as one. The Rust build times are not comparable with the Python ones above — that harness copies every key across the language boundary and this one does not.

Lookup speed from Python, against dict and marisa-trie

bench/latency_py.py — one process per corpus, every structure built up front, the seven lookup forms rotated inside each round so none keeps the position that pays to warm the probe list. Measured 2026-11-05 at ea82db8, the 5.0 candidate, on performance, with Python 3.14.8 and marisa-trie 1.4.1. The rows below are the minimum over two 15-round passes per corpus. Ratios are quotients of the minima against dict on the same probe set, and the gate is on those: worst 4.7 % / median 1.4 % (words), 8.5 % / 1.8 % (random), 7.3 % / 2.7 % (grid), against a bar of 10 %. All three passed (latency-py-agreement-2026-11-05-arz-ea82db8.json holds the gate's reading). The gate does not sit on the absolute minima, which carry the machine's thermal state that the ratio divides out.

Nothing about a lexindex version can be read out of this table, and that is a measured claim, not a disclaimer. Same session, alternating A-B-B-A (the order matters: A-B-A-B gives A both early slots and this machine drifts), the released 1.0.0 wheel against a 1.1 working tree — on random every cell landed within 1.01–1.04×, on words within 0.98–1.09×, and the widest gaps in both belong to dict and marisa-trie, code that is byte-identical in the two runs.

probe set structure 479 823 words 1 M random pairs 1 M grid pairs
members dict absolute, for scale 208.8 ns 212.8 ns 178.0 ns
marisa-trie 2.53× 4.43× 3.13×
StringIndex.id 1.28× 1.82× 1.30×
PerfectHashIndex.id 0.94× 1.22× 0.95×
CompactHashIndex.id 0.75× 0.76× 0.58×
PerfectHashIndex.ids_of 0.44× 0.49× 0.45×
CompactHashIndex.ids_of 0.36× 0.35× 0.36×
absent dict absolute, for scale 141.8 ns 190.1 ns 187.3 ns
marisa-trie 3.19× 4.70× 2.80×
StringIndex.id 1.19× 1.43× 1.01×
PerfectHashIndex.id 0.44× 0.36× 0.34×
CompactHashIndex.id 0.39× 0.31× 0.30×
CompactHashIndex.ids_of 0.20× 0.25× 0.15×

Below 1.00× is faster than dict. So: a CompactHashIndex answers a present key in 0.58–0.76× the time of a dict, a missing one in 0.30–0.39× and batched ids_of in 0.15–0.36× — while occupying 1.24 bytes per key on disk against the dict's 71–95 bytes per key in RAM. PerfectHashIndex trades level with dict on single words and on the grid (0.94–0.95×), costs a fifth more on random pairs (1.22×), and wins on misses everywhere (0.34–0.44×); marisa-trie costs 2.5–4.7× and StringIndex 1.0–1.8×, and both swing with the corpus exactly as their sizes do.

Read the ratios, not the absolutes. This machine drifted 2.2–9.5 % over fifteen rounds while idle — measured with a cache-resident integer loop that touches no memory — so absolute nanoseconds here are a statement about one laptop's thermal envelope. The ratios divide that out within a session. Two caveats in dict's favour, both deliberate: CPython caches a string's hash inside the object, so a repeated probe over the same str skips rehashing where lexindex hashes the bytes every call; and every column pays the same per-call binding overhead, which flatters the slower ones. The denominator's instability across sessions is a standing, unexplained property of this machine, and it has now been seen five times: grid's dict read 251 ns, then 194–196 the next day, then 216, then 227.3, and 178.0 here on performance; words' read 327.9, then 258.5, then 267.8, and 208.8 here. Ruled out on the day it was first chased: the extension (the released wheel measured the same as the working tree), the interpreter (one virtualenv throughout), the corpus generator (unchanged) and background load (raising it did not restore the old figures). The mechanism is still not identified. What follows for the protocol is that a cross-session delta in this table means nothing on its own — not even as a shape across columns, which the A-B-B-A run above tested directly and found empty. A version claim needs both builds in one session.

Point-lookup latency vs the standard library

cargo run --release --example bench — 1 M real dictionary-word bigrams (word_i.word_j, the same key generator as bench/scale.py; mean key 10.9 bytes). Keys are never synthetic entity-000…N sequences — those arrive pre-sorted and hash-degenerate and flatter every number. Measured 2026-11-05 at ea82db8, the 5.0 candidate, on performance: six runs of the example back to back, each lookup cell the minimum of five timed passes after a warm-up pass (bench/results/latency-rs-2026-11-05-arz-ea82db8.txt). The table quotes the minimum over all six. They agree within 1 % on CompactHashIndex, both HashedDictIndex forms and PerfectHashIndex::id_unchecked, within 1.2 % on both HashMap controls and within 2 % on DoubleArrayIndex; PerfectHashIndex::id spreads 6 %, BTreeMap 8 %, DictIndex 9 %, with no trend, and StringIndex reads 256–257 ns on four runs and 276 on two. Absolute numbers are machine-dependent — the std::HashMap control reads 233 ns here, as in the 4.4 table, against the 234 of the 4.1 table, the 241 of the 4.0 table, the 285 of v3.0.0, the 295 of 2.1.0, the 289 of 2.0.0 and the 245 of 1.1.0 — so compare the ratios, only within a column, and read a shift under ~15 % between tables as the session: against this HashMap, PerfectHashIndex::id_unchecked is 0.24×, CompactHashIndex::id 0.29×, HashedDictIndex::id_unchecked 0.31× and its id 0.35×, PerfectHashIndex::id 0.46×, DoubleArrayIndex 0.95×, StringIndex 1.10×, DictIndex 1.65×, BTreeMap 2.83×.

structure build lookup note
lexindex PerfectHashIndex::id_unchecked ~317 ms ~56 ns closed vocabulary, no membership check
lexindex CompactHashIndex::id (fp=1) ~30 ms ~68 ns fingerprint-verified, 2^-8 false-positive rate
lexindex HashedDictIndex::id_unchecked ~151 ms ~71 ns closed vocabulary; the id is the key's rank, so key(id), prefix and range stay on the same index
lexindex HashedDictIndex::id (8 bits) ~161 ms ~82 ns fingerprint-checked, 2^-8; builds are the dictionary's and the sidecar's together
lexindex PerfectHashIndex::id (verified) ~310 ms ~107 ns one extra cache line + full key compare
lexindex DoubleArrayIndex::id ~344 ms ~221 ns a character a load, 17.67 B/key here; 0.95× its HashMap
std::HashMap<String, u32> ~167 ms ~233 ns in-RAM, not serialisable
lexindex StringIndex (FST) ~231 ms ~256 ns and prefix / range / fuzzy
lexindex DictIndex (256 per block) ~98 ms ~383 ns ordered, exact reverse; 1.93 B/key here against the FST's 0.68 — a word.word cross product is what a transducer factors out, and what a block of front-coded keys does not (on the dictionary: 2.62 against 5.95, 280–293 ns against 168–181)
std::BTreeMap<String, u32> ~159 ms ~658 ns in-RAM

The memory-bound rows swing between sessions; the three hash rows halved at 4.0, and that was not a session. Over seven sessions BTreeMap read 3.19× → 3.34× → 2.63× → 3.24× → 3.01× → 3.06× → 3.04× → 2.83× of HashMap, and StringIndex, while its code stood still from 0.5.1 to 4.2, 1.30× → 1.47× → 1.32× → 1.47× → 1.32× → 1.34×, with no trend and no single outlier, while the FxHash map sits at 0.586× → 0.60× → 0.58× → 0.60× → 0.60× → 0.60× → 0.61× → 0.59× throughout. The two that move are exactly the two that miss to DRAM, they move together and in the same direction, and they moved across sessions in which their code did not change — the signature of the machine, not of a release. Against that background StringIndex now reads 1.10×, below every session before it, which is 4.3's reader of its transducer; and the three rows the key hash reaches moved at 4.0 by more than any session ever has: PerfectHashIndex::id 0.95× → 1.04× → 1.02× → 1.03× → 0.50× → 0.47× → 0.47× → 0.46×, id_unchecked 0.269× → 0.26× → 0.24× → 0.26× → 0.21× → 0.21× → 0.21× → 0.24×, CompactHashIndex::id 0.435× → 0.45× → 0.45× → 0.45× → 0.25× → 0.25× → 0.25× → 0.29×. 4.1 and 4.4 left all three within 6 %. With the key hash of 5.0, id_unchecked and CompactHashIndex::id read 14–16 % over their 4.4 ratios of 0.21× and 0.25×, and PerfectHashIndex::id holds. Verified id is now under half the HashMap it used to trail. Three controls holding still while three rows halve is what the new key hash, the MPH3 seed layout and the prefetched second level look like from outside. HashedDictIndex reads 71 ns closed and 82 at eight fingerprint bits, against 63 and 77 on 4.1 — 5.4× and 4.7× its own dictionary's id — and builds in the dictionary's 98 ms and 53–63 more for the sidecar. DictIndex reads 383 ns for 1.93 B/key at the default of 256 keys a block, against 442 on 4.1 — the search changes of 4.3.3 and 4.4 lie between — and 2.0.0's 507 for 3.19 at 32 a block. CompactHashIndex builds in 30 ms against 48 on 3.0.0 and 69 on 1.1.0. This corpus is DictIndex's worst case by construction: the 1 M keys are 1 000 words crossed with 1 000, which the transducer stores once per factor (0.68 B/key) and a block of front-coded keys stores once per key. Real keys move lookups in lexindex's favour versus synthetic ones, while every build reads higher than a synthetic sequence would, because real input is not pre-sorted and sorting is part of the build.

HashMap here is the std one, which hashes with SipHash — hardened against hash-flooding and correspondingly slow on short keys. That is the map most Rust code actually uses, so it is the right default comparison, but it is not the fastest map available: the same HashMap with a non-cryptographic hasher is much quicker, and cargo run --release --example bench prints that row too (FxHash, written out in the example rather than added as a dependency). In the same session as the table above, HashMap + FxHash reads ~137 ns and PerfectHashIndex::id_unchecked ~56 ns — so on a closed vocabulary the perfect hash is about 2.5× faster than a fast-hashed map, not merely level with it. That reverses what this README said through 0.12, where two 12-run sessions on a shared machine put FxHash at 196/200 ns against id_unchecked's 216/216 and concluded the latency advantage was gone. What changed is not the measurement conditions but the code: 1.0's own perfect hash and its 8-byte-at-a-time key hash, and then 4.0's replacement of both. CompactHashIndex::id (~68 ns) is 2.0× faster than the FxHash map and still carries the membership check and the 1.24 B/key blob; HashedDictIndex::id (~82 ns) is 1.7× faster with the same check and the keys kept, in order.

Two things the table above cannot show, both from an independent harness (local/latency/, one process, all forms alternated per round, min of 12, latency-forms-2026-11-05-arz-7b65814.txt):

  • 25–36 ns of every number in it is reaching the probe key, not looking it up. The bench probes keys[i * STEP % n] — the original allocations in strided order, which is what a long-lived key list looks like. Hand the same index a probe list allocated in probe order and PerfectHashIndex::id_unchecked falls from 32.2 to 6.9 ns/op at 1 M, CompactHashIndex::id from 38.7 to 11.9, and PerfectHashIndex::id, which fetches a stored key either way, from 69.4 to 33.1. The batched ids_of is the layout-insensitive one at 10 M, 29.8 scattered against 26.2 contiguous on CompactHashIndex, because its software prefetch does for scattered keys what the hardware does for contiguous ones; at 1 M its two cells carry a spread of 16 % and 58 %. So read any sub-100 ns lookup figure, here or anywhere, as a statement about the caller's key layout as much as about the index.
  • On a miss-heavy workload std::HashMap no longer wins. An absent key costs the SipHash map 33.2 ns at 1 M against CompactHashIndex::id's 11.8 and PerfectHashIndex::id's 18.8; at 10 M, 61.0 against 14.5 and 48.4. On 0.11 this read the other way at 1 M, 32 ns against 41: the map fails on an empty bucket after one cache line, where a fingerprint index runs the whole perfect hash and reads a fingerprint before it can say no, and that whole path has since become cheaper than the SipHash of the key.

Honest reading: for a fixed / closed vocabulary, PerfectHashIndex::id_unchecked is the fastest of the structures in the table above — 4.2× as quick as the SipHash HashMap and 2.5× the FxHash one (no probing, no membership comparison) and compact + serialisable. CompactHashIndex::id keeps a probabilistic membership check and still beats the SipHash HashMap on lookup (3.4× here), and builds in a fifth of its time. Full verification (id) pays one extra cache line + a key comparison; StringIndex trades more latency for ordered / prefix / range / fuzzy queries the hash maps cannot answer at all. So: CompactHashIndex when footprint dominates and a rare false positive is fine; HashedDictIndex when the ids must be the key order and id is the hot path; PerfectHashIndex::id for exact membership + reverse; StringIndex when order or fuzzy/prefix matters; HashMap when you just need a general in-RAM map with nothing persisted.

The perfect hash against PtrHash and PHast

bench/mphf_vs is its own crate, outside the workspace, so that neither competitor becomes a dependency of lexindex: cd bench/mphf_vs && cargo run --release -- <keys> <rounds> <threads>. One process builds every function in turn over the same distinct splitmix64 keys, in the order they were generated, three rounds A-B-A-B (builds: the minimum), and looks every key up in one shuffled probe order (the minimum of nine passes) — the keys copied into an array in that order, so that a query reads its own key from a sequential stream, and each function's lookup inlined into a loop of its own, so that the column is the function alone. Beside every minimum the harness prints its spread, the slowest repeat over the fastest, and a batch column: lexindex's index_all and ptr_hash's index_stream::<32, _> over chunks of 4096 keys, the two forms that pull a later key's cache line in while the current one resolves (ph has no batch form). The construction peak is the process's high-water mark over the build above what it held before it — the memory a build needs beyond the keys — exact where the tables are large enough to be mapped whole (10 M and 100 M). ph 0.11.0 is the PHast authors' crate, with its wyhash feature on (its default hasher is std's SipHash, which nobody benchmarks it with): Function2 with ShiftOnlyWrapped is PHast+ with wrapping, the design this crate's MPH3 grew out of; Function with SeedOnly is regular PHast. Both at 8-bit seeds and bucket size 4.5, as here. ptr_hash 2.1.3 is PtrHash's three parameter sets, and sux 0.15.3 is PHastR at five settings. Bits and lookups are the 1-thread process's; the 8-thread process builds PtrHash and MPH3 to the same bits, ph to within 0.02 and PHastR to within 0.04, which the prose below takes up.

1 M keys — 241 KB of table, inside L2:

function bits/key build, 1 thread build, 8 threads lookup batch
lexindex MPH3 1.925 37.2 ns/key 13.6 ns/key 1.6 ns 1.8 ns
ph PHast+ (ShiftOnlyWrapped) 2.160 54.5 17.2 3.4 —
ph PHast (SeedOnly) 1.933 573.6 98.5 2.8 —
ptr_hash compact 2.144 145.7 81.2 3.5 4.2
ptr_hash balanced 2.378 90.0 46.5 3.7 4.2
ptr_hash fast 2.990 70.7 62.2 1.8 2.6
sux PHastR (8-bit, 4.25) 1.960 53.4 10.8 3.1 —
sux PHastR (8-bit, 4.5) 1.919 49.3 10.4 3.3 —
sux PHastR (8-bit, 4.75) 1.915 47.8 11.0 3.8 —
sux PHastR (10-bit, 5.75) 1.850 99.0 20.9 3.7 —
sux PHastR (10-bit, 6) 1.852 94.1 20.9 4.1 —

10 M keys — 2.4 MB, inside the 16 MB L3:

function bits/key build, 1 thread build, 8 threads lookup batch
lexindex MPH3 1.915 34.3 ns/key 10.5 ns/key 2.4 ns 2.4 ns
ph PHast+ (ShiftOnlyWrapped) 2.147 60.8 15.5 4.9 —
ph PHast (SeedOnly) 1.921 580.4 89.9 3.6 —
ptr_hash compact 2.143 157.6 44.1 5.1 4.5
ptr_hash balanced 2.378 101.1 27.9 5.1 4.5
ptr_hash fast 2.990 144.9 132.8 2.8 2.8
sux PHastR (8-bit, 4.25) 1.943 58.3 10.6 4.4 —
sux PHastR (8-bit, 4.5) 1.904 54.2 10.6 4.9 —
sux PHastR (8-bit, 4.75) 1.899 52.8 10.1 5.6 —
sux PHastR (10-bit, 5.75) 1.823 104.2 18.5 5.7 —
sux PHastR (10-bit, 6) 1.823 99.5 17.8 6.3 —

100 M keys — 24 MB, every scalar lookup a DRAM miss:

function bits/key build, 1 thread build, 8 threads build peak lookup batch
lexindex MPH3 1.911 35.2 ns/key 8.7 ns/key 262 MB 8.5 ns 3.5 ns
ph PHast+ (ShiftOnlyWrapped) 2.146 70.8 17.4 1 526 15.8 —
ph PHast (SeedOnly) 1.920 591.0 90.9 1 526 13.0 —
ptr_hash compact 2.143 160.3 43.4 906 15.9 5.9
ptr_hash balanced 2.378 102.2 26.1 886 16.4 5.9
ptr_hash fast 2.990 222.1 183.0 1 408 10.5 4.9
sux PHastR (8-bit, 4.25) 1.942 61.4 11.1 918 15.3 —
sux PHastR (8-bit, 4.5) 1.902 57.6 10.8 924 16.0 —
sux PHastR (8-bit, 4.75) 1.897 56.2 11.1 925 17.2 —
sux PHastR (10-bit, 5.75) 1.819 108.0 17.9 906 17.6 —
sux PHastR (10-bit, 6) 1.819 101.7 17.5 909 18.3 —

MPH3 is not the smallest function in these tables. sux 0.15's PHastR (Vigna, arXiv:2610.17833), built on one thread over the same keys in the same process and hashing each with its own ToSig for u64 (xxh3), takes fewer bits at 1 M / 10 M / 100 M keys: 1.919 / 1.904 / 1.902 at expected bucket size 4.5 and 1.915 / 1.899 / 1.897 at 4.75, against MPH3's 1.925 / 1.915 / 1.911, and 1.850 / 1.823 / 1.819 with 10-bit seeds. Only its default bucket size, 4.25, is the larger: 1.960 / 1.943 / 1.942. Regular PHast is the larger too, 1.933 / 1.921 / 1.920. What those bits cost is the time: at bucket size 4.5 PHastR answers in 3.3 / 4.9 / 16.0 ns against 1.6 / 2.4 / 8.5, and with 10-bit seeds in 3.7–4.1 / 5.7–6.3 / 17.6–18.3, and builds on one thread in 49.3 / 54.2 / 57.6 ns/key against 37.2 / 34.3 / 35.2, at 94–108 with 10-bit seeds. Built on eight threads, PHastR cuts its levels into more chunks than MPH3 does, and each chunk costs bits: at 1 M it reads 1.943 at bucket size 4.5 and 1.935 at 4.75, above MPH3's 1.925, and 1.879–1.886 with 10-bit seeds, still under it; at 10 M and 100 M it stays under MPH3 at 4.5 and 4.75 by 0.008–0.014 bits (mphf-vs-2026-11-05-arz-7b65814.txt).

MPH3's lookups lead at every size, single and batch: 1.6 / 2.4 / 8.5 ns against PtrHash's fast set's 1.8 / 2.8 / 10.5, and 1.8 / 2.4 / 3.5 in a batch against its 2.6 / 2.8 / 4.9. That set is the one that comes near, on 3 bits a key, a table half again as large whose one probe is a seed byte with no bumped keys' chain behind it. 4.5.1 took the single lookup ahead: in a cool A/B of these two rows alone on 2026-09-25, on powersave, one lookup thread, six processes a commit (bench/results/mphf-cool-ab-2026-09-25-arz-e523ecd.txt), MPH3's went 1.8 → 1.65 ns at 1 M against fast's 1.8, and 2.5 → 2.4 at 10 M against 2.9, and its batch 2.0 → 1.9 and 2.5 → 2.45 against 2.4 and 2.8. Among the rows near 2 bits MPH3's lookups are the fastest at every size — PtrHash compact's 3.5 / 5.1 / 15.9 ns single and 4.2 / 4.5 / 5.9 in a batch, PHast+'s 3.4 / 4.9 / 15.8, and regular PHast's 2.8 / 3.6 / 13.0 at fifteen to seventeen times the build and without a batch form. The bits column is the serialised table, which MPH3 loads as it is — the rank and select counts MPH2 derived in memory, 0.023 bits/key, went with its remap.

MPH3's build is the fastest on one thread at every size: 37.2 / 34.3 / 35.2 ns/key against PHastR's 47.8 / 52.8 / 56.2 at its quickest, PHast+'s 54.5 / 60.8 / 70.8 and PtrHash fast's 70.7 at 1 M. On eight threads it reads 13.6 / 10.5 / 8.7 against PHast+'s 17.2 / 15.5 / 17.4 and PHastR's 10.4 / 10.1 / 10.8: PHastR builds faster at 1 M and 10 M, at higher bits than MPH3 at 1 M and at lower bits at 10 M, with a spread at 1 M of up to 26 % against MPH3's 13 %, and MPH3 at 100 M. Against PtrHash's compact set MPH3 builds 3.9–4.6× faster on one thread and 4.2–6.0× on eight. The run before, at e147b05, had PHast+ ahead on one thread at every size, 57 / 57 / 68 ns against 75 / 71 / 70, over the same tables: since then a bucket's seed is searched over fixed lanes, one function a bucket width from 1 to 16 keys with every loop's count known to the compiler, a mode's keys that could meet are found by their residues modulo the slice, and the buckets wait for placement in a bitmap of priority slots taken from its lowest set bit, not in a queue a size class under a heap. On one thread the construction peak is the column apart: 31 MB at 10 M and 262 MB at 100 M above the keys, against 77–156 MB and 886–1 526 MB — the table is built a chunk of buckets at a time, the keys of a quarter of the chunks copied out at once, and nothing the size of the key set is ever held beside it. On eight threads it is too: MPH3's 49 MB at 10 M reads under PHast's 78 and PHastR's 79–82, and its 281 MB at 100 M under 901–1 428. Every table here before 2026-09-17 timed the builds over keys the harness had sorted for its dedup: MPH3 skips its own sort on sorted hashes, and the other rows bucket their keys whatever the order (PtrHash's compact and fast sets read within 3 % either way, alternated), so those tables read MPH3's build at 55–58 ns/key on one thread and 9–11 on eight with a peak of 6 MB at 10 M and 60 MB at 100 M — the path a caller handing over sorted hashes takes, as every index in this crate does, but not the one the other rows were timed on. One asymmetry is in the numbers and should be read out of them: lexindex takes the keys as 64-bit hashes (its indexes hash the string once, before), while ph hashes each key with wyhash on build and on every lookup level and ptr_hash with one multiply — a nanosecond or two of the gap on the ph rows is that.

String keys. The tables above take the keys as 64-bit hashes. bench/mphf_vs's strings binary runs the path a user of string keys sees, end to end, on real corpora (local/corpora, not in the repository: an English word list, URLs, UUIDs, English Wikipedia titles, file paths): ClosedHashIndex::id — the key hash, then MPH3 — against PtrHash's fast set over the same key hash, which isolates the perfect hash, and over xxh3 of the bytes, PtrHash as one would build it over strings with a general-purpose string hash. The key hash is lexindex's own hash_key_bytes (the design notes); xxh3 is the 64-bit XXH3 of xxhash-rust, PtrHash's hash::Xxh3, which its default features build. PtrHash's documentation recommends StringHash for strings instead, which is GxHash and needs its gxhash feature. No row here uses it, and GxHash's 128-bit form, the StringHash128 PtrHash recommends past 10⁹ keys, has a collision that no seed removes: two 88-character strings that differ in five positions share their hash under each of a million seeds (Groot Koerkamp, 2026-07), so a build over a set that holds the pair cannot tell them apart. One process a corpus, three rounds; a round builds every row first and then times the rows in turn within each pass, each turn preceded by an untimed sweep over the first 2^20 probe keys, so that a machine warming through a round slows every row alike and no row holds the caches to itself for a turn of its own. Every key is looked up once in a shuffled order with the key read from the corpus, the minimum of nine passes; batch is ids_of against index_stream in chunks of 4096; ×8 is the wall time a key with eight lookup threads. Each cell is lookup / batch / ×8 in ns. Measured 2026-11-05 at 7b65814, on performance.

corpus, keys (mean bytes) lexindex ClosedHashIndex ptr_hash fast, the same hash ptr_hash fast, xxh3
words, 480 k (9) 8.8 / 6.1 / 1.7 9.0 / 7.5 / 1.7 24.1 / 19.1 / 3.9
URLs, 1 M (52) 46.9 / 12.6 / 8.2 47.7 / 37.2 / 7.9 68.1 / 70.8 / 10.0
UUIDs, 1 M (36) 41.7 / 10.7 / 7.2 42.5 / 34.4 / 7.1 61.4 / 57.5 / 9.0
titles, 1 M (21) 26.3 / 10.4 / 4.3 26.6 / 22.3 / 4.3 50.2 / 46.5 / 6.9
paths, 1 M (125) 70.9 / 47.8 / 14.8 72.1 / 66.1 / 14.8 114.6 / 122.5 / 17.8
URLs, 10 M (52) 55.2 / 14.3 / 8.9 55.9 / 41.5 / 8.9 78.2 / 80.9 / 11.1
UUIDs, 10 M (36) 53.6 / 13.0 / 8.5 54.6 / 40.2 / 8.5 73.3 / 67.7 / 10.6
titles, 10 M (21) 38.5 / 11.9 / 6.7 41.9 / 29.5 / 6.9 72.1 / 66.7 / 10.2

With the key read from memory the hash is most of the cost, and the same hash under both perfect hashes is what the middle column holds fixed: ClosedHashIndex leads the fast set on all eight corpora, by 0.2 to 1.2 ns on seven and by 3.4 ns on 10 M titles. The hash decides the rest: the same set over xxh3 is 15 to 44 ns behind. The batch column is the crate's alone: ids_of hashes the next keys and pulls in both ends of each key while the current ones' lines arrive, 12.6 / 10.7 / 10.4 ns on 1 M URLs / UUIDs / titles against index_stream's 37.2 / 34.4 / 22.3 over the same hash and 70.8 / 57.5 / 46.5 over xxh3, which does not overlap the hashing — 2.1 to 3.2× on every corpus but the word list, whose keys are 9 bytes, and the 125-byte paths. The CompactHashIndex row's single lookup is id_unchecked, the same perfect-hash probe without the fingerprint compare, within 6.9 ns of ClosedHashIndex on every corpus and below it on seven of the eight; its batch is ids_of, which does compare, and pays the fingerprint line's miss, 4.1 to 5.7 ns above it.

The xxh3 column moved and nothing here explains it. Against the powersave run of 2026-09-17 (mphf-strings-2026-09-17-arz-2a9acef.txt) the fast set over xxh3 reads 15–46 % slower on the single lookup, 1 M URLs 51.5 → 68.1 ns and 10 M titles 49.3 → 72.1. No code of this crate is in that path, and the cause is not traced. The same set over lexindex's hash reads 2–18 % slower, 1 M URLs 45.7 → 47.7, and is no control: the key hash of 5.0 lies between the two runs. So do not read the wider gap to xxh3 as a gain of this crate: the smaller gaps of September are as good a reading of what a general-purpose string hash costs.

The earlier history of this table is in the older files, read against each other through the ptr_hash over xxh3 rows, which then agreed within 3 % across two runs. Between 2026-09-16 at 7215616 and 2026-09-17 at 2a9acef every lexindex row got quicker — 1 M URLs 43.0 → 38.5 ns single and 28.7 → 12.8 in a batch, 10 M URLs 48.1 → 43.1 and 30.9 → 14.6 — over eighteen commits to src/, the batch column following the one that prefetches a key's last line as well as its first. The key hash's own gain was measured the same way one commit earlier: against the b4544db file over the hash 2.0–3.x shipped, in the protocol both of those runs used, every lexindex row was 10–30 % quicker — 1 M URLs 54.5 → 43.0 ns, paths 92 → 65, titles 32 → 28, UUIDs 46 → 39 — while the xxh3 rows, the same code in both, read 3–15 % slower in the newer one, so that gain too is at least the difference shown. Results files: bench/results/mphf-strings-2026-11-05-arz-7b65814.txt, bench/results/mphf-strings-2026-09-17-arz-2a9acef.txt, bench/results/mphf-strings-2026-09-16-arz-7215616.txt.

The lexindex row ran once more at each size in a process with transparent huge pages turned off (prctl(PR_SET_THP_DISABLE)), the control for the MADV_HUGEPAGE its tables ask for from 2 MiB up: 1.6 / 1.9 ns at 1 M against 1.6 / 1.8 with them (nothing to get below one huge page), and 2.6 / 2.6 against 2.4 / 2.4 at 10 M, 8 % and 8 %. The recount has no such process at 100 M: on 2026-09-17, on powersave, it read 10.8 / 4.1 against 10.0 / 3.5, 8 % and 17 %, with the results file's huge MB column showing the pages the process holds after the build, 40 MB at 100 M against none without them.

How the batch got there. Before this measurement index_all prefetched only the first level's seed, sixteen keys ahead, and stopped at 13.5 ns at 100 M against index_stream's 6.9: the ~3 % of keys the first level bumps made four more dependent misses each — their next level's seed, the rank words, the select sample, the high words — and a prefetch that names one line cannot hide a chain. The keys go through the first level in blocks of 1024 now, each seed pulled in 64 keys ahead; the bumped keys of a block are answered after it in five stages that run eight keys apart, each stage pulling in what the next one reads. Below 2^18 first-level seeds (about 1.2 M keys) the level sits in L2 and the batch is the single lookup in a loop, which is why the 1 M batch is the single lookup plus the cost of writing its answers out. The single lookup gained from the same work: the remap's rank reads a count per word instead of counting a block's words in a loop, and the Elias–Fano select compares a window of counts at once and finds the bit inside its word without a loop, where the old scan's mispredicted exits were most of a bumped key's cost (3.7 → 3.2, 5.8 → 4.9 and 20.1 → 15.8 ns). Since then the remap became one line of Elias–Fano (one prefetch stage fewer), the batch keeps the buckets it finds in a ring and reads the geometry as immediates (54 → 47 instructions a key), and the tables sit on huge pages: the 100 M batch went 5.8 → 3.8 ns and the single lookup 15.8 → 13.7. Since then the placed lookup lost nine of its 32 instructions — the seed's mode and shift come out of one shift and one mask, the wrap is a cold call — and the single lookup went 2.6 → 2.1 ns at 1 M, 3.8 → 3.1 at 10 M and 13.7 → 12.0 at 100 M, the 1 M batch 2.8 → 2.3. Since then a bucket's seed is chosen by the product of its keys' positions, which bumps a sixth fewer keys, a bumped key's remap is a sampled Elias–Fano stream read in two steps, a first level past L3 has each seed pulled in three times, and a seed's mode shift is read from a table: the single lookup went 2.1 → 1.9 ns at 1 M, 3.1 → 2.6 at 10 M and 12.0 → 10.2 at 100 M, the batch 2.3 → 2.2, 2.9 → 2.5 and 4.0 → 3.6.

ConsensusRecSplit (Lehmann, Sanders, Walzer, Ziegler 2025), the space record at 1.444 + ε bits, is C++20 under the GPL, so it ran in its own process on the authors' harness at their commit 11deea6: XorShift64 keys, one construction timed in milliseconds, the queries drawn with replacement into a plan array (as above, no key fetch inside the query), single-threaded, one run per configuration, on the same machine on the same day as the tables above (mphf-consensus-2026-11-05-arz-ea82db8.txt). k is the bucket size, ε the overhead over the bound, -o the query-optimised variant.

function 1 M: bits/key build lookup 10 M: bits/key build lookup
ConsensusRecSplit k = 256, ε = 0.1 1.583 271 ns/key 51 ns 1.579 267 ns/key 88 ns
… k = 256, ε = 0.1, -o 1.579 383 68 1.575 392 78
… k = 256, ε = 0.01 1.480 1 631 51 — — —
… k = 32 768, ε = 0.1 1.619 614 95 — — —
… k = 32 768, ε = 0.01 1.492 1 995 94 1.459 1 977 141
… k = 32 768, ε = 0.01, -o 1.491 3 046 118 1.459 3 066 131
lexindex MPH3, one thread 1.925 37.2 1.6 1.915 34.3 2.4

The last row is the tables' own MPH3; the MPH2 row this table carried went with its format, gone since 4.0. The trade is 0.46 bits a key — on a CompactHashIndex at 1.24 bytes a key, 5 % of the index — for 8–89× the build and 33–59× the lookup at 10 M. That is the right answer for an archive written once and read rarely; this crate's tables are read on every id, and 1.91 bits is where its lookup stays first.

What this campaign does not have. A second CPU: one Ryzen 7 5800HS, a mobile part with 16 MB of L3, and the 100 M rows are where its memory system shows — a server part with a larger cache and more channels moves every row there. A 1 B row in the tables — it has runs of its own, eight build and eight lookup threads with the probe order sampled to 10 M keys, because the full one is another 8 GB beside a 14 GB construction peak. The recount, on 2026-11-05 at 7b65814 on performance, is three processes with four copies of each table and where each copy landed read beside it, and a fourth with huge pages off (bench/results/mphf-vs-1b-2026-11-05-arz-7b65814.txt): MPH3 builds over 10⁹ keys in 7.5 s at 1.911 bits and 2.6 GB above the keys, against 25–417 s and 8.0–14.4 GB for PtrHash's three sets. Its single lookup is the fastest of the four rows there, 12.6 ns against PtrHash fast's 13.7 and compact's 24.2, and so is its batch, 6.8 against 7.7 and 8.0 (medians over twelve copies). With eight lookup threads every row waits on how fast the memory under its table answers random loads, and on this machine — two unequal modules, the top 16 GiB of memory interleaved across both channels — that can be where the table lands. On 2026-09-26, on powersave (bench/results/mphf-vs-1b-2026-09-26-arz-8537f35.txt), MPH3's tables, on the huge pages they ask for, landed on memory 21–23 % slower for random loads than PtrHash's on small pages. Here they did not: all four rows read 3.27–3.34 ns a load, MPH3 3.34. So with eight threads its lookup reads 3.6 ns against fast's 3.4 and compact's 4.2, and its batch 3.3 against compact's 2.8, balanced's 2.7 and fast's 3.2. With huge pages off the rows land within 3 % of each other, 3.09–3.17, and the lookup reads 3.33 against fast's 3.33 — level — but the batch 3.04 against compact's 2.60 and balanced's 2.63: the eight-thread batch is where MPH3 loses at a billion keys, 17 % behind PtrHash compact on the same memory, and with huge pages on its single lookup is 5 % behind fast's. Hardware counters over the two batches in a separate harness say what that is made of (bench/results/mphf-lanes-1b-2026-11-05-arz-7b65814.txt): with huge pages off, compact's batch fetches 0.82 lines a key from DRAM against MPH3's 0.98 and finds 0.20 in the L3 against 0.10. Its bucket function is skewed, so the pilots of its dense buckets answer a large share of the keys and stay in the 16 MB cache; MPH3's buckets are uniform, and over its 240 MB about one line in fifteen can be cached. Without huge pages its one-thread batch also reads 3 % faster here and its single lookup 13 % slower; a machine with matched modules has no slower part for huge pages to land in, and this campaign has none to measure that on. On 2026-09-17 (bench/results/mphf-vs-1b-2026-09-17-arz-08094a1.txt) the eight-thread columns moved by up to 58 % between processes over the same code, and that is the size of this: MPH3's copies moved as much with where they landed, 32–58 % between the table built and its clones in a run that read the sequential rate only. That run also holds the ph rows, 21–100 s and 9.7 GB to build, whose PHast answered a lookup in 19.6 ns. The 1 B run before the harness corrections above, on a hot machine, read 30.0 and 9.9 ns for MPH3's single and batch lookups over sorted keys, behind every PtrHash set. The mphf-lanes-1b file of 2026-09-26 read compact's batch at 0.83 lines on powersave. Confidence intervals: in their place, every cell's minimum with the spread of its repeats, in the results file — builds repeat within 9 % on one thread but for PHast+ with huge pages off (15 %), and within 13 % on eight but for PHastR (up to 26 %), both at 1 M; lookups within 12 % at 1 M, 14 % at 10 M and 9 % at 100 M; batches within 8 % at 1 M (passes of about 2 ms), 9 % at 10 M and 2 % at 100 M.

The three tables were measured 2026-11-05 at 7b65814 (bench/results/mphf-vs-2026-11-05-arz-7b65814.txt), on performance, in one window with no editor open, 40 °C at the start. The run before, on powersave, is 2026-09-17 at 08094a1 (bench/results/mphf-vs-2026-09-17-arz-08094a1.txt), on mains with an editor open, after a wait for Tctl under 60 °C and a load under 0.7 (49.0 °C and 0.26 at the start, 52 minutes after a reboot); this file's comparisons below are to that one. The run before it, at e147b05 (mphf-vs-2026-09-17-arz-e147b05.txt), 51.9 °C and 0.29 at the start, built the same tables before the seed search's lanes: MPH3's builds read 75.2 / 70.6 / 70.3 ns/key on one thread and 16.5 / 13.6 / 12.3 on eight, its lookups within 0.2 ns of these. Its other rows' builds on one thread agree with this file's within 2.3 % but for PHast+'s at 10 M, 57.2 against 60.2, and PtrHash fast's at 100 M, 194.1 against 247.5; on eight within 2.4 % at 1 M and up to 10 % faster at 10 M and 100 M; their single lookups within 0.5 ns, and PtrHash compact's and balanced's batches 0.4–0.7 ns faster (compact's 3.6 / 4.0 / 5.7 against 4.2 / 4.7 / 6.2). The run before that, at ba0580b (mphf-vs-2026-09-16-arz-ba0580b.txt), is the last over sorted keys: its MPH3 rows read 1.966 / 1.953 / 1.949 bits, builds of 57.7 / 55.6 / 57.6 ns/key on one thread and 11.1 / 9.2 / 9.0 on eight, and single lookups of 2.1 / 3.1 / 12.0 ns. Its other rows' builds agree with the e147b05 file's within 4 % but for PHast+'s 16 ms build on eight threads at 1 M (11 %), the 100 M builds on eight threads, 4–8 % slower there, and PtrHash fast's on one, 249.7 against 194.1 ns — the same row read 233–242 in four more processes within the hour of the e147b05 run, the keys in generation order and sorted alternated, so the key order does not move it — and their lookups within 0.9 ns. The morning's run at b4544db (mphf-vs-2026-09-16-arz-b4544db.txt), two minutes after a reboot at Tctl 49 °C, read 2.6 / 3.8 / 13.7 ns for MPH3's single lookup before the placed path was cut; its other rows agree with the ba0580b file's within their spreads. Two corrections to the harness are in that commit, and they change how the earlier files read. ph's default hasher is std's SipHash-1-3 — its seedable_hash dependency has default features off — so every earlier file's ph rows timed a configuration the crate does not intend (PHast+ 8.8 / 12.9 / 42.5 ns in mphf-vs-2026-09-16-arz-c1ff98b.txt against 3.5 / 5.3 / 17.3 with wyhash, its build 69.6 / 77.7 / 102.7 against 58.3 / 61.3 / 71.9), and their headers' "wyhash" is wrong. And the lookup loops were inlined into one large function beside each row's build, which cost lexindex 0.7–3.6 ns a lookup and no other row anything measurable: a cool run of the previous harness the same morning read 3.3 / 4.8 / 17.3 against 2.6 / 3.8 / 13.7 in that file. The old files stay as they were measured; the MPH2 of the c1ff98b tables (2.099 / 2.088 / 2.086 bits, 42.9 / 40.8 / 41.2 ns builds, over sorted keys) is what 1.1 to 3.0 write, and MPH3's build over the same sorted keys at ba0580b took 1.3× its time for 6 % fewer bits and half the bumped keys. The file before, mphf-vs-2026-09-13-arz-a5ad812.txt, is the one the Consensus table's former MPH2 row and mphf-consensus-2026-09-13-arz-a5ad812.txt were measured beside. The 2026-09-10 file's lookups (mphf-vs-2026-09-10-arz-5ba9f36.txt) are five times those — 29 ns for MPH2 against the c1ff98b file's 5.8, 46 against 6.6 for PtrHash compact — because that harness read each probe key through keys[order[i]], a random 8-byte fetch from an 80 MB array per query, and so charged every row one DRAM miss that was the caller's, not the function's; the builds agree within 7 %.

Misses a lookup, not only nanoseconds

A lookup column says a row is slower. It does not say whether the row touches another cache line or merely does more work between two loads, and those are different findings with different fixes. With MPHF_VS_MISSES=1 the harness opens a PERF_COUNT_HW_CACHE_MISSES counter on the timing thread through perf_event_open(2) -- there is no /proc file for it -- and resets and reads it around each single-lookup pass. It is off by default: an ioctl either side of a timed pass is a syscall this page's nanoseconds are not taken with.

The probe order is read sequentially at eight keys a 64-byte line, so 0.125 of every count below is the key fetch, not the function. Net of it, over 300 million keys, where no table is resident:

function bits/key LLC misses a lookup net of the key fetch lookup ns batch ns
lexindex MPH3 1.911 1.073 0.948 11.1 5.8
sux 0.15 PHastR (8-bit, 4.25) 1.942 1.173 1.048 19.4 —
sux 0.15 PHastR (8-bit, 4.5) 1.902 1.227 1.102 21.2 —
ph 0.11 PHast (SeedOnly) 1.921 1.234 1.109 16.8 —
ptr_hash 2.1.3 compact 2.143 1.239 1.114 21.0 6.9
ptr_hash 2.1.3 fast 2.990 1.245 1.120 12.4 7.0
sux 0.15 PHastR (8-bit, 4.75) 1.898 1.295 1.170 23.7 —
ptr_hash 2.1.3 balanced 2.378 1.296 1.171 21.3 7.0
sux 0.15 PHastR (10-bit, 5.75) 1.820 1.394 1.269 23.8 —
sux 0.15 PHastR (10-bit, 6) 1.819 1.434 1.309 25.4 —
ph 0.11 PHast+ (ShiftOnlyWrapped) 2.146 1.435 1.310 23.1 —

mphf-misses-2026-11-05-arz-7b65814.txt — the same three sizes in one file, 10 M, 100 M and 300 M, one process each, eight build threads and one round; the cell is the fastest of three passes. The nanoseconds in this table are taken with the counter running and are not the ones the tables above publish.

The survey's figures for the same quantity are PtrHash 1.0 lines a query and PHast 1.1, and these agree with them. MPH3 is the only row under one line, and that is the reading of its single-lookup lead over ptr_hash fast at this size — 11.1 ns against 12.4, on 15 % fewer misses, 36 % fewer bits and a build 43 times faster. On the same two rows the powersave run of 2026-09-20 (mphf-misses-2026-09-20-arz-1a9003e.txt) read a tie, 16.3 against 16.2. At 100 million keys the tables are 24–37 MB against a 16 MB L3 and partly resident, and MPH3, PtrHash's sets, PHast and PHastR's 8-bit rows at 4.25 and 4.5 sit between 1.039 and 1.096 — the ordering there says nothing, and the gap only opens once nothing is resident.

What an instruction costs inside the miss

A lookup that waits on memory is often said to get its arithmetic for free. It does not, and the price is measurable: local/uopspad welds PAD padding instructions into the probe loop between one query and the next, with PAD a const generic so the padding unrolls rather than becoming a loop of its own. Four shapes — a nop, which needs no port and no operand; independent adds on four rotating registers; a chain of adds on one register; and dependent loads inside 4 KiB that never leave L1.

n table 0 4 16 64 128 ns an instruction
100 M 22.8 MB 8.97 10.50 13.69 21.86 28.84 0.11 (nop)
100 M 22.8 MB 8.96 14.43 20.14 30.99 48.15 0.27 (independent add)
100 M 22.8 MB 10.14 12.51 17.84 33.52 66.38 0.51 (a chain)
10 M 2.3 MB 2.47 2.86 3.60 6.45 9.63 0.050 (nop)

uops-pad-2026-11-05-arz-7b65814.txt — ns a lookup, the minimum of three rounds taken A-B-A-B over the pad counts, and the slope over the last two. Three 100 M runs read the nop slope at 0.1091, 0.1090 and 0.1083: ±0.4 %. The control is the probe order: the third of those is the generation order rather than shuffled, so the loop waits on the table and not on the probe array, which is read sequentially either way.

The loop is not paying for the instruction's execution. It is paying because the instruction displaces another query from the window, and the window is what buys the memory-level parallelism: one dependent load at a time over a region the size of the table takes 43.4 ns at 22.8 MB and 10.6 at 2.3 MB, while the loop answers a key in 8.97 ns, so it keeps 4.8 misses in flight. Latency over the slope reads 397–399 instructions at 100 M — above Zen 3's 256-entry reorder buffer, so take it as an upper bound on the window rather than a reading of it, since some nops are eliminated at rename. At 10 M the same arithmetic gives 213 and means nothing: that loop is throughput-bound, not window-bound, which is exactly why its slope is under half the other's.

The powersave run of 2026-09-20 (uops-pad-2026-09-20-arz-db32225.txt) read every price about twice this, 0.23 ns a nop and 85.3 ns a dependent load, on the same table at 15.0 ns a key. The two runs differ in governor, kernel and compiler, and this harness does not separate them.

Two things follow. A dependent instruction costs 0.51 ns a step against an independent one's 0.27 and a nop's 0.11, so a chain welded onto a lookup path costs what two independent instructions or about five nops do — which is the argument against trading a table load for a longer arithmetic chain, not for it. And 0.11 ns an instruction is the exchange rate for the last of the lookup column: at 300 million keys MPH3 answers in 11.1 ns against ptr_hash fast's 12.4 with the counter running, so that gap is worth about twelve instructions, and MPH3 reaches it on 15 % fewer misses.

A fingerprinted PerfectHashIndex on mostly-absent keys

local/negfp, a throwaway harness beside the crate, builds the dictionary twice — plain and with build_with_fingerprints — and a CompactHashIndex as the control, then probes the 480 k words as members and, with a digit appended (no dictionary word ends in one, so the length distribution is the members'), as absent keys, in a shuffled order. The headline rows are taken one index per process, so the two arenas never compete for the cache: six alternations of the five modes in both orders, ten passes each, the minimum — after three warm-up pairs, because the part is a mobile one and runs a third faster for the first minute after an idle spell. The in-process A-B-A-B (all three indexes resident, seven rounds) gives the batched rows and the 50/50 mix.

probe plain with fingerprints
id, member 46 ns 50 ns one index per process
id, absent 39 ns 30 ns one index per process
id, 50 % absent 52 ns 52 ns in-process
ids_of, member 48 ns 50 ns in-process
ids_of, absent 44 ns 32 ns in-process
CompactHashIndex::id_unchecked (control) 22 ns 22 ns
bytes per key 9.25 10.25 exactly +1

This dictionary now builds the merged arena, 9.25 bytes a key, whose fingerprints sit in a row of their own ahead of the entries: an absent probe reads that table and stops, and the key — the second cache miss — is never read. A member pays the second hash and one compare, a few nanoseconds.

On the blocked layout, which a key set that does not merge still takes, an absent probe stops at the block: the offset line says no key with that fingerprint is in the slot. Measured there on 2026-09-10, the fingerprint bytes follow the block's offsets; interleaving them with the offsets cost a member 6 ns instead of 3, because the offset pair moved up to 36 bytes from the base and split cache lines more often. And the fingerprint is compared before the slot's offsets are read: an absent probe was then about 255 instructions long, the width of the reorder buffer, which is what lets its one cache miss overlap the next probe's. A three-instruction marker check added for the overflow blocks pushed the path past that and cost 11 ns with no change in cache or branch misses; moving the fingerprint first shortened it by the whole span computation and took the absent probe from 91 to 74.

Measured 2026-11-05 at ea82db8, on performance (bench/results/negfp-2026-11-05-arz-ea82db8.txt). The control moved: CompactHashIndex::id_unchecked reads 22 ns here against 41 on 2026-09-10, over 4.0's key hash and a change of governor, so no row here compares with the table this replaces. The blocked figures are bench/results/negfp-2026-09-10-arz-679a8c6.txt, Ryzen 7 5800HS, load 1.0–1.1 with an editor open; the fingerprint layout itself was chosen on negfp-2026-09-10-arz-8f136d3.txt.

ClosedHashIndex: the perfect hash alone

local/closedbench builds the dictionary as a ClosedHashIndex and as a CompactHashIndex at the default width, checks that every word gets the same id from both, then probes the 480 k words in a shuffled order: nine rounds in one process, the order of the modes reversed on every other round, the minimum per row. The two id_unchecked-style lookups are the same perfect-hash probe and measure the same; the fingerprint compare on top of it is what CompactHashIndex::id pays, and the batched ids_of loses the fingerprint line's prefetch and compare.

ClosedHashIndex CompactHashIndex (fp=1)
id, member 19.5 ns 24.0 ns (id), 19.7 ns (id_unchecked)
ids_of, member 7.5 ns 18.2 ns
bytes per key 0.242 1.242

Measured 2026-11-05 at ea82db8, on performance, three processes back to back and the minimum of the three, which agree within 3 % (bench/results/closed-2026-11-05-arz-ea82db8.txt), Ryzen 7 5800HS. Both id rows halved against the 2.0.0 table that first published them (40 → 19.5 and 68 → 24.0), which is the new key hash and the MPH3 seed layout, and both sizes fell 0.021 B/key with the hash; the powersave run of 2026-09-19 read 19.8 and 24.7. Within a process the rows alternate between the two mode orders the harness reverses on alternate rounds — whichever lane runs second finds the key array warm — so the minimum is the warm one, in this table as in the one it replaces.

DictIndex: the ordered dictionary against StringIndex

local/dictbench builds the dictionary as a StringIndex and as a DictIndex at six block sizes, then probes all 479 823 words in a shuffled order — members, strangers (each word with a byte appended), and every id for the reverse lookup — five rounds in one process, the variants alternated within each round, the minimum per cell; StringIndex is the control.

StringIndex DictIndex 32 DictIndex 64 DictIndex 128 DictIndex 256 DictIndex 512 DictIndex 1024
bytes per key 5.95 2.84 2.71 2.65 2.62 2.51 2.50
of which per-block arrays — 0.152 0.121 0.105 0.100 0.050 0.051
microblocks a block — 2 4 8 16 16 32
entries a lookup scans — 16 18 22 30 46 62
build 104–105 ms 28–29 27–28 26 24–26 23–25 30–31
id, member 168–181 ns 252–260 257–266 260–273 280–293 313–320 342–355
id, stranger 126–129 ns 205–207 205–207 218–220 240–241 272–273 299–301
key_into (no allocation) — 140 149–150 167 194–195 255–257 301–303
key (owned string) 453–466 ns 190–192 209–212 233–234 263–265 325–328 371–372
lower_bound, stranger — 203–205 203–205 217–218 238 269–270 299–300
prefix, 2 000 three-byte prefixes of ~760 keys — 32.3–32.5 µs 32.3–32.4 32.2–32.4 32.2–32.3 31.6–31.8 31.8–31.9
routed: restart words, bytes a key in memory — 0.50 0.50 0.50 0.50 0.25 0.25
routed id, member — 227–234 226–230 222–229 216–230 249–257 238–248
routed id, stranger — 177–180 171–172 164–165 160–162 191–193 190–191
routed lower_bound, stranger — 174–178 169–170 163 159–160 190–191 188–189

Three runs of the same ladder, each once as a load leaves the index and once after route_microblocks(); where the runs differ the table gives the range. At the default 256, DictIndex answers id 62–67 % slower than StringIndex in the same process and key_into at less than half its key, while storing 56 % less. The ladder does not cross the control anywhere, routed or not, and the gap has widened since 4.1: 4.3's reader of the transducer took 22 % off StringIndex's id, and the 5.0 candidate's took more since, up to 15 % against 4.5.3 on a million keys; the search changes of 4.3.3 and 4.4 took 11–13 % off the dictionary's. BDX3's codes had cost more to decode than the varint pairs BDX2 stored — every block got 6–10 % smaller and every id 17–24 % slower when it landed. The sequential lane does not move with the block at all.

Routed, the block stops costing the search. The words take the walk over a block's restarts out of the lookup and leave the one microblock's scan, so from 128 keys a block up id no longer pays for the block's length: 222–229 ns at 128 and 216–230 at 256, both microblocks of 16 keys, and 249–257 at 512 and 238–248 at 1024, microblocks of 32. Against the same block unrouted, paired run by run, that is 18–25 % off id at 256 and 28–31 % at 1024, 29–37 % off a stranger's id and lower_bound from 256 up, and 7–11 % off id at 32, where the run is a single restart. Beside StringIndex in the same process the gap at 256 falls from 62–67 % to 21–30 %. The words are paid in memory — 8 / micro bytes a key, 0.5 up to 256 and 0.25 at 512 and 1024, in no blob — so routed, the default is no longer the obvious point: 1024 keys a block, routed, holds 2.75 bytes a key and answers id in 238–248 ns, faster than any block unrouted, 32 included, and still under every marisa-trie setting's 2.96–3.07, while the default block routed, at 216–230 ns, holds 3.12 and is no longer.

A lookup scans a microblock, not a block. A block is cut into microblocks of 16 to 32 — the smallest divisor of the block at or above its square root — and the first key of each is a restart front-coded against the restart before it, so a lookup walks the restarts to one microblock and scans that: block / micro + micro − 2 entries, which is 30 at the default where the block holds 255. That is what unties the size from the latency. Against the one-level format at the same size the reverse lookup halves and id does not move: 244–246 ns and 392–399 for 2.819 B/key, where one level at 128 keys a block stored 2.827 for 460–464 and 393. The one-level format reaches 0.10 B/key further down, and that is what it costs: its floor of 2.701 at 1024 keys a block answers key_into in 3 190 ns and id in 984, against 287–289 and 420–426 for 2.80 here. Both ladders ran alternated by process in one session, the base built from the commit before microblocks in a worktree, with StringIndex at 340–353 ns as the control (dict-onelevel-ab-2026-09-12-arz-386b2e6.txt). Its control read 340–353 ns on powersave, where this section's table reads 168–181 on a transducer reader made faster since, so read each comparison inside its own session and neither against the other.

The reverse lookup does not decode the whole run. An entry stores what it shares with its predecessor, so an entry whose shared-prefix length is at least a later entry's contributes nothing that survives to the key being asked for. The ones that do contribute form a strictly increasing staircase of that length, and a monotonic stack over the run's headers finds it in the pass the walk already makes: every header is still read — a header is what says where the next one begins — but only the staircase is decoded. Measured over the dictionary and a path list when it landed, the staircase is 2.5 entries deep on average and 12 at the deepest with a block of 32, 18 with a block of 1024; past 32 the walk stops tracking it and decodes each entry, which is slower and not wrong. That was worth −16 % on key_into at 32 keys a block, −33 % at 128 and −37 % at 256 (dict-stair-2026-09-11-arz.txt holds the before and after), and it costs no bytes and no format change.

256 is a middle of the curve, not a limit, and build_with_block is the knob. The size falls because a larger block spreads what it stores once — its first key whole, where that key ends, where the block starts, and an offset for each microblock — over more keys: 0.44 bytes a key at 32, 0.06 at 1024. The front-coded data moves the other way and less, 2.39 to 2.48 at the default as keys that were heads are coded against their predecessors instead, and back to 2.43 at 512, where microblocks double to 32 keys and a restart comes half as often. What the block costs is the scan, 16 entries at 32 and 62 at 1024, where one level scanned block − 1. At 512 the index is 2.51 bytes per key, well under the 2.98 marisa stores on this corpus — and unlike marisa it answers key(id) and lower_bound at all, since a marisa id is not the lexicographic rank (7 051 of 19 999 consecutive sorted pairs come back with a decreasing id). Pick 32 or 64 if the lookups are hot, 512 or 1024 if the bytes are — or name the point instead of the number: DictProfile::Fast, Balanced and Compact in Rust, block="fast" | "balanced" | "compact" in Python, are 128 in microblocks of 8, 256 and 1024. Where a quarter of a byte a key of memory costs less than the scan, Compact routed is both smaller and faster than block 32: 2.75 bytes a key at 238–248 ns against 2.84 at 252–260. Against block 32 over the thirteen corpora of the research frontier, Fast reads a median 0.999× the id, from 0.92× on dna to 1.14× on numeric, and routed against routed a median 0.88×, faster on all thirteen, in a file smaller or equal on all thirteen.

Measured 2026-11-05 at ea82db8, on performance (bench/results/dictbench-2026-11-05-arz-ea82db8.txt), three runs of the whole ladder, each the minimum of five alternated rounds, unrouted and routed in two processes whose order alternates between runs; the table gives the range over the three, and the prefix matches a prefix come from the prefix stage. The bytes, the per-block arrays, the restart words and the two structural rows are exact, not measured. StringIndex is the control inside every process — 168–181 ns in the unrouted ones, 170–184 in the routed — but no longer across releases: it read 200–210 in the powersave session of 2026-09-24 (dictbench-2026-09-24-arz-3a73ed5.txt), and 256–270 before 4.3 changed its reader. key_into and key do not route and read the same in both processes; the table gives the unrouted ones.

Prefix queries against the tries

A prefix is a range of a sorted dictionary, so DictIndex answers one without an automaton: prefix_id_range is two lower_bounds and prefix walks the run they name. local/prefixbench.py puts that against the tries a Python project can install, on the same words — 20 000 three-byte prefixes drawn from random words, so the average prefix carries 763 keys.

bytes/key prefix_count first 10 every match + ids keys only
lexindex DictIndex 256 (default) 2.62 380 ns 2 045 ns 100 807 ns 75 433 ns
lexindex DictIndex 512 2.51 425 2 237 100 094 72 180
lexindex StringIndex 5.95 537 4 057 154 588 318 244
marisa-trie 2.98 118 176 2 523 90 817 90 708
dawg2 23.96 66 731 1 441 46 845 46 970
datrie 30.69 514 086 514 439 515 076 513 915

Counting is where the structures differ in kind rather than by a constant. prefix_count costs two order lookups whatever the prefix carries, so it runs 278× faster than marisa's at 512 per block and 311× at the default — marisa has to enumerate all 763 matches to count them, its ids not being lexicographic ranks, so there is no arithmetic to do instead. At every block that goes under marisa on size — which since microblocks is the default too — DictIndex is also ahead on autocomplete (2 045–2 237 ns against 2 523) and on handing back a prefix's keys (72 180–75 433 against 90 708) — with a rank for each, which marisa has none to give.

Those keys come fastest through the id range, which inverts what this page said until 2026-09-12. prefix_id_range and then keys_of costs 75 433 ns at the default block, against 100 807 for prefix, which decodes an id for every match as well. keys_of used to re-enter the block for every id and was the slower of the two by 2.1×; it now keeps one walk open across the ids that ascend through a block, which is exactly the shape an id range hands it. The inversion is DictIndex-only: StringIndex has no block to stay inside, its keys_of walks the transducer once per id, and prefix is still the API for this query there (154 588 against 318 244). It is also why there is no prefix_keys method: it would be these two calls, and the table says what a third one would buy — 25 %, which two existing calls already have.

The last two columns are this benchmark's error bar as well as a result. A trie has no ids to return, so for marisa-trie, dawg2 and datrie they are one call measured twice — and within a run they come out 0.12 %, 0.27 % and 0.23 % apart. Nothing narrower than that is a finding here: DictIndex at 256 against 512 on full enumeration (100 807 against 100 094) is a 0.7 % difference and near it, while the 1.20× over marisa on keys alone is well outside it.

dawg2 enumerates about 1.6× faster at 9.1× the bytes, with no reverse lookup and no mmap: a different point on the curve, not a smaller one. datrie is a double-array built for point lookups; prefix walking is not what it is for.

Measured 2026-11-05 at ea82db8, one run on performance (bench/results/prefix-2026-11-05-arz-ea82db8.txt), marisa-trie 1.4.1, dawg2 0.13.3, datrie 0.8.3 over the same word list, Ryzen 7 5800HS. None of the three is a lexindex dependency — reproduce in a throwaway environment.

Common-prefix queries — the other direction

prefix returns the keys a query starts. The reverse question — which keys are prefixes of the query — is what a longest-match tokeniser asks of a vocabulary, and it was the one operation marisa-trie, dawg2 and datrie all answered and lexindex did not. local/cpbench.py measures it on the same words: 20 000 queries, each a real word with one to three more letters on it except every fourth, which is random letters. Every structure is first held to marisa's answer on 2 000 of them, both calls, and every row returns (key, id) pairs where the structure has that form — dawg2's IntCompletionDAWG has only the keys — so the timings compare the same work.

bytes/key common_prefix longest_prefix
lexindex DoubleArrayIndex 24.42 468 ns 213 ns
lexindex StringIndex 5.95 491 273
dawg2, keys only 23.96 544 590
datrie 30.69 693 337
marisa-trie 2.98 1 061 1 180
lexindex DictIndex 256 (default) 2.62 2 310 926
lexindex DictIndex 512 2.51 2 516 1 010
datrie, keys only 30.69 286 198

DoubleArrayIndex reads 5 % under StringIndex on common_prefix in two runs of three and 17 % over it in the third, at four times the transducer's bytes, and it leads on longest_prefix. The double array walks a character a load and reads a match's id from the slot that reaches it: paired run by run, −5…+17 % against the transducer on common_prefix and 21–22 % faster on longest_prefix, and 1.23–1.48× and 1.57–1.60× faster than datrie, the other double array, returning the same pairs. Through 4.5.2 the first figure read 8–11 % in the double array's favour; the transducer's reader is what moved. The query is the path, for both: one walk, every key it passes a match, O(query characters) whatever the index holds. The last row is the form the 4.4.2 table timed for datrie: the keys without their values, less work than a pair — 286 ns against its own 693 — and quicker than any row that returns ids; lexindex has no keys-only call. Held to that form, 4.4.2's table had StringIndex and datrie level.

Out of cache the transducer leads the first column. The table times each call after an untimed pass of its own, the steady state of a tokeniser. Timed instead right after another structure's pass — the protocol of the 4.4.2 table — DoubleArrayIndex's common_prefix reads 658 ns against StringIndex's 534: its array is 11.7 MB on these words against the transducer's 2.9, and comes back from memory. datrie, at 14.7 MB, reads 958. The second column, timed there right after the structure's own first pass, reads 224 against 273, though the double array's three runs there spread 46 %.

DictIndex has no walk to make and the table shows what that costs. One order lookup per character boundary, so a ten-character query is ten binary searches where the trie made one descent: 2.2× marisa's time at the default block, 2.4× at 512. longest_prefix is the exception — it starts at the query and stops at the first hit, so it never pays for the boundaries under the match, and both blocks land below marisa (926 and 1 010 ns against 1 180) while storing fewer bytes than it. A caller who asks this question often should hold a DoubleArrayIndex or a StringIndex; one who asks it occasionally, alongside the ranks and ranges only DictIndex gives, can have it for a binary search per character.

Measured 2026-11-05 on a wheel built from ea82db8, on performance (bench/results/common-prefix-2026-11-05-arz-ea82db8.txt): three runs in each regime, each the minimum of five rounds; a cell is the minimum of the three. The three agree within 3 % on every cell of the table but DoubleArrayIndex's common_prefix, which read 468, 575 and 468. In the other regime they spread up to 46 %, on the same structure's longest_prefix, 224, 327 and 235. The harness is the 4.4.2 table's (bench/results/common-prefix-2026-09-24-arz-b101076.txt) with the DoubleArrayIndex row, (key, id) forms for datrie (prefix_items, longest_prefix_item) and marisa-trie (its prefix iterator with ids; for the longest, which it has no call for, its key list and then the last key's id), a check on every longest_prefix answer, and the warm regime; 4.5.0's run on powersave is common-prefix-2026-09-25-arz-902e4b4.txt. Sizes are each structure's saved file, built as the harness builds it. Nanoseconds per query through Python 3.14.8; the call overhead is in every row, and the three tries are C extensions too. marisa-trie 1.4.1, dawg2 0.13.3, datrie 0.8.3; none is a lexindex dependency — reproduce in a throwaway environment.

On Chinese running text, from Rust and from Python

A Chinese segmenter asks this question at every character: jieba builds a DAG of every word that starts at each position of a sentence. The run below asks it at all 178 338 positions inside the blocks jieba segments — runs of Han characters, ASCII letters and digits, its re_han_default — of UD Chinese GSDSimp r2.18's 4 997 sentences, against jieba 0.42.1's 349 045-word lexicon, each query running to the end of its block. Before any timing, every structure gave the same set of (length, id) pairs at every position: 237 465 matches.

Rust, ns a character bytes/word in text order shuffled
lexindex DoubleArrayIndex, for_each_occurrence 15.62 10.6 11.1
lexindex DoubleArrayIndex, a walk a position 15.62 13.0 17.7
lexindex DoubleArrayIndex, mapped, a walk a position 15.62 13.7 18.6
daachorse 5.1.0, charwise, a block at a time 47.95 14.8 15.8
crawdad 0.4.1 Trie 18.40 15.5 20.9
crawdad 0.4.1 MpTrie 22.17 17.9 23.6
yada 0.7.0 17.75 26.7 33.2
darts-clone 0.32 17.75 27.5 33.9
cedarwood 0.6.1 60.57 28.8 35.7
lexindex StringIndex 9.24 54.0 65.4

On this walk lexindex is now first, in every lane. DoubleArrayIndex labels a character, not a byte, by its frequency in the lexicon, and its eight-byte slot carries everything a step reads, the matched word's id included, so a step is one load and a match costs none past it (the design notes). Walked a position at a time, as the rivals are, it takes 0.47–0.48 of darts-clone's time in text order and 0.52–0.53 shuffled, 0.45–0.50 of cedar's, 0.83–0.85 of crawdad's Trie, the fastest per-position rival, and 0.68–0.76 of its MpTrie — each ratio paired within a process. daachorse answers a whole block at a time, so its like is for_each_occurrence, which decodes a block once and walks from every character: 0.63–0.72 of daachorse's time, at a third of its bytes. That like matters shuffled, where daachorse's block scan is ahead of the per-position walk, 15.8 against 17.7 ns: a block at a time spreads what a lone position pays. Mapped from its file rather than held in the huge pages a build or a load puts it in, the walk costs under a nanosecond more. And the index is the smallest double array here: 15.62 bytes a word against 17.75 for darts-clone and yada, 18.40 for crawdad; cedar's figure is its resident heap, its array growing by doubling so that a quarter of its slots sit idle, and its 0.6 file form saves 60.55 bytes a word (da-sizes-2026-10-31-arz.txt).

StringIndex is the other end of the same trade. Its walk takes 3.7–4.2× the double array's, at 59 % of its bytes: at 4.4.1 it ran 1 025 instructions a character against cedar's 150 and darts-clone's 151, 5.9 steps down the transducer, each reading a node's header afresh — its state, the widths its fields are packed in, a target and an output — where a double array reads one slot. 4.4.2's table of the state past every first character took that to 581 (bench/results/prefix-walk-counts-2026-09-24-arz-dda19a7.txt). The table is 0.29 of the 9.24 bytes a word, held in memory only; the file is 8.95. What the transducer has and the double array does not is everything but this walk: a key back from its id, prefix enumeration, ranges, fuzzy matching.

jieba's lexicon build load
lexindex DoubleArrayIndex 0.160 s 0.37 ms mapped · 1.66 read
darts-clone 0.32 0.054 0.50 read
cedarwood 0.6.1 0.101 38.60 read
yada 0.7.0 0.328 2.84 read
crawdad 0.4.1 Trie 1.244 1.00 read
crawdad 0.4.1 MpTrie 1.583 1.27 read
daachorse 5.1.0 1.581 3.41 read unchecked · 5.61 read
lexindex StringIndex 0.083 from sorted keys 0.41 mapped · 1.36 read, each with its first walk

Where the double array loses: the build. It builds from the words in 0.160 s — under half of yada's time, an eighth to a tenth of crawdad's and daachorse's — but in 3.0× darts-clone's time and 1.6× cedar's. Every row takes the lowest base where it fits, found over bitmaps; the window of open blocks darts-clone searches instead, and a start that only moves up, each cost 9–10 % of the size on this lexicon. 4.5.1 brought the build down from 0.354 s: the trie is built from the keys in byte order, each decoded once, and the search for a row's base tests a sparse stretch word by word and a dense one four words an instruction where the CPU has AVX2. The load no longer loses. It walks every slot once, so that no slot names a row past the array or an id past the keys and no query checks a bound, and since 4.5.1 that walk runs on the slots' 32-bit halves, eight slots an instruction with AVX2: 0.37 ms mapped, 1.66 read, which copies the file and checks its hash as well, where darts-clone's open, which reads the file and checks nothing, took 0.50 ms. In a pairwise run on 2026-09-25, both timed in each of four processes, the mapped load read 0.62 ms against open's 0.59–0.66 across the four: level. darts-clone's set_array, which takes a mapped array as it lies, costs nothing at all, not timed here. crawdad and daachorse deserialise, in 1.0–5.6 ms, and cedarwood's file form, new in 0.6, reads in 38.6.

Measured 2026-11-05 at ea82db8, on performance (bench/results/cjk-2026-11-05-arz-ea82db8.txt, which holds this page's three Chinese tables and every version, hash and flag): three processes. A process ran 20 rounds, the rows in a seeded shuffle each round and each timed after two untimed passes of its own — the steady state of a segmenter, whose lexicon stays in cache; a cell is the minimum over the three. "In text order" walks each block's positions in order with the sentences in a seeded shuffle; "shuffled" takes the same positions in a seeded random order; for_each_occurrence and daachorse take whole blocks, in the same two orders. The lexindex rows spread 0.3–1.1 % across the processes and the rivals 0.3–1.7 %, but for crawdad's MpTrie, 3.8–6.1 %, and daachorse's, 2.5–14.2 %. The control row, jieba-rs 0.11.0's cut_all, read 33.9, 33.9 and 40.5. The table before 2026-09-25 ran the rows alternated, each timed after whatever the rows before it had left in cache, which favoured the rows nearest the turn of a round: it had darts-clone at 41.1 and 34.8 ns and StringIndex at 63.9 and 76.5. A cold regime, 64 MiB written before every pass, spread the control by 16.5 % and is not quoted. The build and load table ran one process each, the minimum of 7 builds and 30 loads, the structures in a shuffled order each round, the files in the page cache, and each load followed by one lookup so that nothing it defers escapes the timing; a StringIndex load is timed with its first walk, which derives the first-character table. The powersave runs of 2026-09-25 are cjk-walk-2026-09-25-arz-902e4b4.txt, cjk-build-load-2026-09-25-arz-6623184.txt and cjk-build-load-2026-09-25-arz-902e4b4.txt, the last two holding the double array's own before and after, 1.03 → 0.62 ms mapped, pairwise; between those two runs the loads read from the page cache moved by up to 41 % (crawdad's Trie 1.17 → 1.64 ms), so a load across runs is weak evidence. rustc 1.99.1; darts-clone at 87b71af, built with g++ 16.2.1 -O3. The harness is not in the repository. No competitor here is a lexindex dependency.

Through Python the walk is the small part of the cost. Plugged into jieba 0.42.1 in place of its own dictionary, one occurrences call a block rather than one common_prefix call a position takes the DAG from 841 to 472 ns a character over the double array, and from 886 to 532 over the transducer — the same walks, fewer calls. Every backend also answers jieba's one other dictionary read, the FREQ.get that decides whether a run of single characters goes to the HMM:

Python, ns a character DAG lcut(HMM=False) lcut()
DoubleArrayIndex.occurrences 472 1 017 1 513
StringIndex.occurrences 532 1 069 1 579
jieba's own dictionary 638 1 463 1 985
DoubleArrayIndex.common_prefix 841 1 357 1 851
StringIndex.common_prefix 886 1 389 1 901
dawg2 prefixes 983 — —
marisa-trie 1 391 1 906 2 452
DictIndex 256 2 006 2 439 2 961

Over DoubleArrayIndex.occurrences a cut takes 30 % less time than over jieba's own dictionary, and 24 % less with the HMM, jieba's default, which adds 490–550 ns a character to every row. Against StringIndex.occurrences the double array takes 11–12 % off the DAG but 4–6 % off a cut, paired within each process: in Rust its walk takes about a quarter of the transducer's time, and through Python that saving is a few tens of nanoseconds in a call that spends most of its time building tuples and jieba's DAG. DictIndex is the slowest here for the reason the English table gives: a binary search a character boundary.

Measured 2026-11-05 on a wheel built from ea82db8, on performance (bench/results/cjk-2026-11-05-arz-ea82db8.txt): three processes, a cell the minimum over the three. The DAG column is per character in blocks (178 338), the cut columns per character of text (195 832). Before any timing every backend gave jieba's own DAG on every block and its cuts of every sentence. The control row, jieba's own dictionary, spread 2–4 % across the processes and reads 2–3 % under the powersave run of 2026-09-25 (cjk-prefix-py-2026-09-25-arz-902e4b4.txt). CPython 3.14.8 with the GIL; marisa-trie 1.4.1, dawg2 0.13.3. That run's harness is not in the repository; bench/cjk_segment.py times the same backends after the same check. No competitor here is a lexindex dependency.

Hash quality

Size and speed both rest on the key hash being indistinguishable from random on real keys, so the claim is measured rather than argued. The battery lives with the hash it tests (src/hash.rs, behind bench-mphf) and runs as one test:

cargo test --release --features bench-mphf -- --ignored --nocapture hash_quality

Every statistic is reported as a standard-normal z, so one bound reads across the whole battery. A chi-square goes through the Wilson–Hilferty transform rather than the textbook (x − k) / sqrt(2k), which is wrong exactly where a threshold sits: at 255 degrees of freedom and a true z of 6.00 the two read 5.99 and 7.07 (checked against incgam in PARI/GP). The bound is |z| < 6.5, a false alarm once in about 6 500 runs of a battery of 1 894 400 cells, whose largest |z| should sit near sqrt(2 ln N) ≈ 5.4.

test what it would catch result
strict avalanche, both hashes, key lengths 4–33 an input bit that does not reach every output bit worst 4.53 over 88 064 cells
bit independence, 2 016 output pairs per input bit two output bits that flip together worst 4.82 over 1 806 336 cells
two-byte differential, every position pair and bit pair the pre-2.0 collision family: keys differing at bytes 8i+7 and 8i+11 collided in both hashes 13–100 % of the time through 1.1 0 double collisions over 17 664 combinations
per-corpus distribution — slot-hash collisions, top 12 bits, low 12 bits, the 8-bit fingerprint, and the joint (slot, fingerprint) table a family of keys the hash folds together, and any correlation between the two hashes ten corpora, no collisions, every value under 1.7

The ten corpora are the shapes that break hashes in practice: dictionary words, word bigrams, a shared prefix (https://example.com/a/b/…), a shared suffix (…@mail.example.com), a dense numeric tail (key_000000001), plain decimal integers, UUIDs, Cyrillic, DNA, and filesystem paths.

Committed output: bench/results/hash-quality-2026-11-04-arz-8ca5a3c-dirty.txt (5.0's 128-bit state, the table above; run again on 2026-11-05, it printed the same), and bench/results/hash-quality-2026-09-16-arz-166ac74.txt (the 4.0 hash with its derived fingerprint, at a smaller battery: avalanche worst 4.31 over 44 032 cells, bit independence 4.52 over 258 048, per-corpus under 2.7; the run before the fingerprint was derived is hash-quality-2026-09-16-arz-67650b3.txt, and the 2.0–3.x hash's run of the same battery is hash-quality-2026-09-12-arz-d82e296.txt). The two hashes are deterministic and unseeded, so none of this is a statement about an adversary who picks the queries — see SECURITY.md.

Error bars, and where a lookup number comes from

Every timed number on this page is the minimum of a few alternated passes. A minimum is the right estimator for a laptop — it is the sample least contaminated by whatever else the machine was doing — but it carries no width, and a claim about a frontier is a claim about an ordering, which needs one. local/statbench runs 30 independent passes a structure with the six lanes round-robin, so drift lands on all of them equally, and reports the median with p5/p95 and a bootstrap interval around the median. The interval is a percentile interval over 10 000 resamples rather than mean ± t·s: the samples are not normal, since a pass that met a scheduler tick sits far above the rest and nothing at all sits below the hardware.

479 823 English words, 200 000 probes a pass, half of them members, ns a lookup:

structure B/key min median p5 p95 95 % CI of the median
ClosedHashIndex 0.24 11.3 11.6 11.4 13.2 11.5 – 11.7
CompactHashIndex fp=1 1.24 16.4 16.4 16.4 18.2 16.4 – 16.4
PerfectHashIndex 9.25 41.2 42.6 41.6 48.5 42.0 – 44.7
StringIndex 5.95 141.7 144.4 141.8 150.4 142.6 – 146.3
DictIndex 256 2.62 248.0 248.7 248.0 267.8 248.6 – 248.9
DictIndex 512 2.51 276.8 278.9 277.0 290.8 278.3 – 279.2

The minimum is within 4 % of the median everywhere, and the p5–p95 band is 5–16 % of it, so quoting the minimum costs nothing — same probe set, same binary, thirty consecutive passes. An earlier session of the same harness put the band under 50 ns at 45 % and the minimum 25–29 % under the median while the slow lanes kept their 2–10 %: a fast lane's width is the machine's that day, not the structure's, and the interval column is what says which day it was.

The probe set is part of the working set. Only the number of probes a pass changes here:

probes a pass Closed Compact fp=1 Perfect String Dict 256 Dict 512
100 000 10.3 17.0 39.4 140.5 247.9 276.3
200 000 11.6 16.4 42.6 144.4 248.7 278.9
400 000 23.6 25.7 50.5 162.7 263.6 294.3

ClosedHashIndex goes 2.3×; DictIndex 256 moves 6 %. The probe array is a second structure the loop walks: 100 000 String headers are 2.4 MB, 400 000 are 9.6 MB before the bytes they point at, and past some point between the two the probe stops being in cache and starts being fetched at the same cost as the lookup it pays for. The smaller the index, the larger the share of the total that is. The counters say it in one line — the instruction count does not move and the cycle count does:

structure instr cycles at 100 k at 400 k branch misses L1 fills LLC misses
ClosedHashIndex 94 43.8 81.9 0.07 2.31 1.13–1.27
CompactHashIndex fp=1 116 64.2 104.7 0.06 3.15 2.00–2.22
PerfectHashIndex 150 118.5 199.0 0.68 5.11 3.96–4.21
StringIndex 1002 577.8 706.6 4.07 14.46 7.00–7.56
DictIndex 256 2274 1066.3 1166.1 14.74 18.16 4.18–4.77
DictIndex 512 2677 1202.3 1305.1 17.33 17.47 4.10–4.65

Three things fall out of that table that no nanosecond showed:

  • DictIndex does the most work and misses about three fifths of what StringIndex does, and neither is what it waits for. 2 274 instructions at 256 against StringIndex's 1 002, and 4.2–4.8 LLC misses against 7.0–7.6. On 2026-09-12 the one-level format at 128 keys a block spent 3 226 instructions and missed 6.6 a lookup; the microblock cut both by a fifth and a third, and at equal size the latency did not move — because what a lookup waits for is a chain of dependent misses, the sample search then the restart run then the microblock, which is the same length whatever the scan, and the instructions and the streamed misses of the scan overlap under it. IPC 1.9–2.2 says the core is busy; the chain says with what. It is also why a block of 32 keys and one of 512 sit about a quarter apart on id and not 2.9× apart on the entries they scan.
  • PerfectHashIndex is pure latency. 150 instructions, 4.0–4.2 LLC misses, IPC 0.8–1.3: it does almost no work and waits for all of it.
  • StringIndex misses the most, 7.0–7.6 a lookup. That is the same fact as its thread scaling above: dependent misses are what a transducer walk is made of, and they are also what another core can overlap.

A second mechanism arrives between 200 000 and 400 000 probes, on the counters of 2026-09-19, which the recount did not read again. Data-TLB misses a lookup go from 0.001 to 0.393 for ClosedHashIndex and from 0.004 to 0.523 for DictIndex 256: the probe array has outgrown a 2048-entry L2 TLB, and every structure now pays for a page walk it did not pay for before. PerfectHashIndex is the one that misses at every size (0.195 at 100 000), its 5.2 MB arena being spread over more pages than the TLB holds to begin with.

The Python table is worse than any of this, and it is worth saying where. bench/compare.py was run twice from clean trees of the same commit on this machine, hours and a reboot apart, with the same word list and byte-identical probes. Every lane moved: 1.27× on the slow rows, 2.2× on the fast ones, and the empty Python call that no library can influence went 49 → 86 ns. Both runs are internally tight — five passes within 2 % of each other in each — and the Rust ladders above reproduced across the same span to within a few per cent, so it is neither noise nor the machine but something in one process's heap that the next one does not repeat. The ordering held: of fourteen rows, only two adjacent pairs swapped, and both pairs were inside each other's spread already. Read that table as a ranking with sizes attached, not as a stopwatch reading — bench/reproduce.sh prints the call floor beside the published one for exactly this reason.

What survives all of it is the ordering. At all three probe counts the six bootstrap intervals are disjoint and in the same order, which is what a frontier table claims and all it claims. The absolute nanoseconds belong as much to the harness as to the structure: bench/compare.py draws 100 000 probes, so that is the column its published numbers sit in, and a lookup time quoted without its probe set is half a number.

Measured 2026-11-05 at ea82db8, on performance (bench/results/stats-2026-11-05-arz-ea82db8.txt, which carries all thirty samples of every row; counters statperf-100-100000-2026-11-05-arz-ea82db8.csv and statperf-100-400000-2026-11-05-arz-ea82db8.csv), Ryzen 7 5800HS. Counters are perf stat over 100 passes minus a build-only control, so the build's own cycles and faults stay out of the lookup's — at 20 passes a 30 ns lane's difference sat inside the build's own run-to-run noise; in those runs every structure is built but only one is probed, which is the kinder case — the table above has six rotating through the cache. The counter columns read 100 000 probes, and LLC is the range over 100 000 and 400 000; the table of 2026-09-19 (stats-2026-09-19-arz-a3f7503.txt) read 200 000 and three counts.

The research frontier, cited

The tables above measure libraries a Python or Rust project can install. The academic state of the art in compressed string dictionaries is research-grade C++ with no such binding, so it is listed here and measured in a harness of its own rather than claimed against in those tables. Each entry says what it is, where the code is, and under what licence — the licence matters, because a benchmark harness that vendors GPL or non-commercial code is not something this repository can carry.

Structure Paper Code, licence What it is
MARISA Yata, 2011 (the reference implementation's own notes) s-yata/marisa-trie, BSD-2-Clause / LGPL-2.1 recursive nested patricia tries with tail sharing; the one competitor above that is installable, as marisa-trie on PyPI
PDT Grossi, Ottaviano, Fast compressed tries through path decompositions, JEA 2014 ot/path_decomposed_tries, MSR-LA — non-commercial centroid path decomposition, labels vbyte- or csp-coded
FST, SuRF Zhang et al., SuRF: Practical range query filtering with fast succinct tries, SIGMOD 2018 efficient/SuRF and kampersanda/fast_succinct_trie, Apache-2.0 LOUDS-Dense over LOUDS-Sparse. SuRF is a filter with false positives, not a dictionary — it answers membership and range, never id → key
XCDAT Kanda, Morita, Fuketa, Compressed double-array tries for string dictionaries supporting fast lookup, KAIS 2017 kampersanda/xcdat, MIT xor-compressed double-array trie; the fast-lookup end of the space
CoCo-trie Boffa, Ferragina, Tosoni, Vinciguerra, SPIRE 2022 and Information Systems 2024 aboffa/CoCo-trie, GPLv3 subtries collapsed by a bottom-up optimisation over a pool of integer codes
C² Zhang, Zhao, Xu, Cache-conscious succinct tries with adaptive unary path compression, arXiv:2606.16104, 2026 alexztc/C2, MIT a cache-conscious layout and an FSST/Re-Pair tail container applied to FST, CoCo and MARISA; ships one harness that builds all of the above
libCSD Martínez-Prieto, Brisaboa, Cánovas, Claude, Navarro, Practical compressed string dictionaries, Information Systems 2016 migumar2/libCSD, LGPL-2.1 front coding (PFC, HTFC), Re-Pair and FM-index dictionaries — this is DictIndex's lineage: front coding in blocks with a restart every k keys is that paper's PFC
IBiS Brisaboa, Cerdeira-Pena, de Bernardo, Navarro, Improved compressed string dictionaries, CIKM 2019 gitlab.lbd.udc.es/gdebernardo/improved-csd hierarchical front coding with Re-Pair and DACs; the direct descendant of the row above

Two structures in that list are what DictIndex is measured against in spirit: PFC/HTFC, which it descends from, and MARISA, which it is benchmarked against throughout this page because it is the one with a binding. The next section runs six of them on the same corpora under one protocol; SuRF is a filter with no id to time, and libCSD and IBiS are not in that harness yet. The standalone suite has libCSD's sizes in sib baselines, and its times are still owed.

The research frontier, measured

The C² paper ships one benchmark that builds its three cache-conscious structures — C²-FST, C²-CoCo and C²-MARISA — beside everything it measures them against: FST, CoCo-trie, MARISA, PDT, ART and C-ART. bench/frontier/build.sh builds that benchmark with every dependency at a pinned commit, and XCDAT's four trie types beside it; bench/frontier/run.sh runs all of them against DictIndex at blocks of 32, 128 in microblocks of 8, 256 and 1024 keys — each once as a load leaves it and once routed by 4.4's route_microblocks() — its labelled builds at 256 and 1024, HashedDictIndex at three widths, StringIndex, PerfectHashIndex and 4.5's DoubleArrayIndex, over the corpus set above at a million keys and, where a corpus has them, ten million. Nothing of the competitors is vendored or linked: it is fetched into a gitignored directory, which is what lets the campaign include GPLv3 and non-commercial code.

The protocol is benchmark.cpp's, not this page's: read the file, sort and deduplicate it, build once, take the structure's own account of its size, then look every key up once, in one fixed shuffle, and report the mean of that single pass. There is no warm-up, so these numbers do not compare with the warm tables above. xcdat_frontier and frontier_lex repeat the protocol line for line, down to where the query bytes live: benchmark.cpp looks up a shuffled std::vector<std::string>, which keeps a key of up to 15 bytes inside the string object, and frontier_lex lays such keys out in probe order too — borrowing every query from its key vector charged each lookup a fetch from a random place in the heap that the C++ rows do not pay, and read DictIndex 14–30 % slow on the corpora of short keys. The C++ is compiled with the flags C² builds with, -O3 -march=native; lexindex is built as it ships, without target-cpu=native.

Every structure runs in its own process, three rounds of them, every other round in reverse order, and each process first waits until the rest of the machine keeps less than one CPU busy for a second. A cell is the median of its three rounds; the logs keep every run, and how busy other work kept the machine while it ran. Sizes are each structure's own account: the serialised blob for lexindex — for a routed DictIndex, the blob and the restart words it holds beside it, which no file carries — space_cost() for the benchmark's structures, memory_in_bytes for XCDAT. ART and C-ART count their nodes and not the keys they point to, so they are kept out of every comparison. ρ is the recursion depth benchmark.cpp takes as max_recursion — for MARISA, one less than its number of tries. A structure is on the front when no other one is at least as small and at least as fast.

corpus Dict 256 smallest fastest lexindex on the front
words-full 2.62 @ 231 lexindex Dict 1024 2.50 @ 291 lexindex HashedDict closed 5.24 @ 14 Dict 1024 labelled, Dict 1024 routed, Dict 128/8 routed, Dict 256, Dict 256 routed, HashedDict closed
dna-1000000 4.37 @ 305 lexindex Dict 1024 4.23 @ 335 lexindex HashedDict closed 7.12 @ 51 Dict 1024 labelled, Dict 1024 routed, Dict 128/8 routed, Dict 256 labelled, Dict 256 routed, HashedDict closed
domains-1000000 4.48 @ 294 lexindex Dict 1024 labelled 4.22 @ 408 lexindex HashedDict closed 7.22 @ 29 Dict 1024, Dict 1024 labelled, Dict 1024 routed, Dict 128/8 routed, Dict 256, Dict 256 labelled, Dict 256 routed, HashedDict closed
idents-1000000 5.22 @ 359 lexindex Dict 1024 labelled 4.88 @ 451 lexindex HashedDict closed 7.96 @ 38 Dict 1024 labelled, Dict 1024 routed, Dict 128/8 routed, Dict 256, Dict 256 labelled, Dict 256 routed, HashedDict closed
numeric-1000000 1.01 @ 233 lexindex StringIndex 0.0003 @ 52 lexindex HashedDict closed 3.75 @ 13 HashedDict closed, StringIndex
opaque-1000000 10.40 @ 314 lexindex Dict 1024 10.29 @ 354 lexindex HashedDict closed 13.14 @ 49 Dict 1024, Dict 1024 routed, Dict 128/8 routed, Dict 256, Dict 256 routed, HashedDict closed
paths-1000000 9.83 @ 657 lexindex Dict 1024 labelled 8.50 @ 838 lexindex HashedDict closed 12.57 @ 103 Dict 1024, Dict 1024 labelled, Dict 1024 routed, Dict 128/8 routed, Dict 256, Dict 256 labelled, Dict 256 routed, HashedDict closed
pypi-full 4.14 @ 306 lexindex Dict 1024 labelled 3.88 @ 390 lexindex HashedDict closed 6.88 @ 27 Dict 1024, Dict 1024 labelled, Dict 1024 routed, Dict 128/8 routed, Dict 256, Dict 256 labelled, Dict 256 routed, HashedDict closed
titles-en-1000000 7.33 @ 374 lexindex Dict 1024 labelled 6.91 @ 473 lexindex HashedDict closed 10.07 @ 44 Dict 1024 labelled, Dict 1024 routed, Dict 128/8 routed, Dict 256, Dict 256 labelled, Dict 256 routed, HashedDict closed
titles-ru-1000000 6.84 @ 455 lexindex Dict 1024 6.67 @ 513 lexindex HashedDict closed 9.58 @ 58 Dict 1024, Dict 1024 routed, Dict 128/8 routed, Dict 256, Dict 256 routed, HashedDict closed
titles-zh-1000000 5.83 @ 362 lexindex Dict 1024 5.67 @ 436 lexindex HashedDict closed 8.57 @ 35 Dict 1024 labelled, Dict 1024 routed, Dict 128/8 routed, Dict 256 labelled, Dict 256 routed, HashedDict closed
urls-1000000 7.49 @ 425 lexindex Dict 1024 labelled 6.98 @ 527 lexindex HashedDict closed 10.23 @ 65 Dict 1024 labelled, Dict 1024 routed, Dict 128/8 routed, Dict 256, Dict 256 labelled, Dict 256 routed, HashedDict closed
uuid-1000000 18.04 @ 391 lexindex Dict 1024 17.89 @ 413 lexindex HashedDict closed 20.78 @ 61 Dict 1024, Dict 1024 routed, Dict 128/8 routed, Dict 256 labelled, Dict 256 routed, HashedDict closed

A million keys, measured 2026-11-05 at ea82db8, the 5.0 candidate (bench/results/frontier-1m-2026-11-05-arz-ea82db8.json), Ryzen 7 5800HS, GCC 16.2.1, rustc 1.99.1, on the performance governor. A cell reads bytes a key @ nanoseconds a lookup. Its competitors are pinned as they were in the 2026-09-25 campaign at 6969644, on powersave, and they are the control: all 260 of their cells come back at byte-identical sizes and read 0.87–1.07 of it, median 0.97, with each family's median at 0.95–0.99 and MARISA's at 1.02. That is what the governor moved, and a lexindex row has to move further than that to have moved. DictIndex reads medians of 0.95–0.97 of that campaign unrouted and 0.91–0.92 routed, at sizes up to 0.6 % smaller, and HashedDictIndex closed 0.92–1.32 (median 1.04), the high end paths, 78 → 103 ns. StringIndex reads 0.62–1.00 (median 0.93), the low end numeric, 84 → 52 ns. DoubleArrayIndex reads 0.96–1.02 (median 0.97). Other work while the 1 403 processes behind the table ran: median 0.02 busy CPUs, most 0.75.

lexindex is on the front on all thirteen corpora — DictIndex on twelve, StringIndex on numeric, HashedDictIndex on every one — and DictIndex builds before every other structure on twelve, and second to PerfectHashIndex on urls, 335 ms against 277. It is ahead of the fastest build from elsewhere by 1.8× on words and titles-en and 2.1–8.1× on the rest. It is the smallest structure the campaign times on twelve of them, by 7.4 % on opaque up to 31 % on dna, the labelled build of block 1024 on domains, idents, paths, pypi, titles-en and urls and the plain one elsewhere: 2.50 bytes a key on words against MARISA's 2.98 at ρ=2, 4.23 on dna against CoCo-trie's 6.14, 6.67 on titles-ru against 8.61, 17.89 on uuid against PDT's 21.44 from a 16.2-second build. paths is the cell that turned over in 4.0: labelled, 8.50 against MARISA's 9.47 at ρ=2, 10.2 %, and plain, 9.28, 2.0 %, where MARISA reads 3.1 times slower and builds 3.8 times slower. MARISA at its smallest, which the campaign does not time, takes 8.81 bytes a key at 23 tries under the tiny cache (below), under the plain block and over the labelled one. Only numeric keeps a trie ahead of DictIndex on size, and there the trie is beside the point: CoCo-trie's 0.52 against block 1024's 0.92, while StringIndex folds a million decimal ids into about 300 bytes. The fastest structure on every corpus is HashedDictIndex closed — id_unchecked, which takes a key's membership on trust (below) — at 13–103 ns a lookup, 4.0–6.1 times as fast as XCDAT 15. XCDAT 15 is the fastest structure from elsewhere on all thirteen corpora, ART aside, which does not count its keys and reads 180 ns on opaque against 199; XCDAT 15 is at 1.9–7.0 times the bytes of DictIndex at its default block, and on the front of none. No structure from elsewhere is on any front. C²-MARISA shared six at 4.3.3, and on those six a routed DictIndex is now smaller and faster than every depth of it: block 128 in microblocks of 8, routed, reads 361 ns at 8.08 bytes a key on titles-ru against 381 at 9.14, and 248 at 7.08 on titles-zh against 277 at 7.57. DoubleArrayIndex is on no front: it holds six of the thirteen corpora, and on each of them HashedDictIndex closed is both smaller and faster.

Where this loses, and by how much. Size is the axis DictIndex is built to win and latency is the axis it pays on. The table puts lexindex's exact searches — the ones that answer a stranger exactly, which a hash does not — beside XCDAT 15: DictIndex at its default block as a load leaves it, the four blocks routed, StringIndex, and DoubleArrayIndex where it can hold the corpus.

corpus XCDAT 15 Dict 256 32 routed 128/8 routed 256 routed 1024 routed StringIndex DoubleArray PerfectHash, hash-order ids
words-full 7.30 @ 76 2.62 @ 231 3.34 @ 169 3.82 @ 139 3.12 @ 157 2.75 @ 185 5.95 @ 126 24.41 @ 75 9.25 @ 27
dna-1000000 22.46 @ 275 4.37 @ 305 5.50 @ 285 5.60 @ 241 4.88 @ 250 4.48 @ 256 17.74 @ 404 — 17.76 @ 80
domains-1000000 10.33 @ 146 4.48 @ 294 5.30 @ 246 5.73 @ 196 4.98 @ 215 4.60 @ 241 10.50 @ 197 65.16 @ 543 15.45 @ 60
idents-1000000 13.78 @ 194 5.22 @ 359 6.10 @ 298 6.48 @ 255 5.72 @ 276 5.31 @ 308 10.55 @ 232 64.40 @ 719 16.60 @ 71
numeric-1000000 7.05 @ 53 1.01 @ 233 1.72 @ 185 2.16 @ 175 1.51 @ 165 1.17 @ 163 0.0003 @ 52 8.00 @ 29 4.12 @ 26
opaque-1000000 20.02 @ 199 10.40 @ 314 11.14 @ 290 11.56 @ 262 10.90 @ 265 10.54 @ 283 21.44 @ 283 — 16.49 @ 80
paths-1000000 25.11 @ 618 9.83 @ 657 13.46 @ 622 11.63 @ 617 10.33 @ 628 9.53 @ 701 17.48 @ 765 — 123.56 @ 169
pypi-full 9.92 @ 132 4.14 @ 306 4.95 @ 251 5.45 @ 210 4.64 @ 227 4.25 @ 255 10.00 @ 186 48.68 @ 431 13.05 @ 51
titles-en-1000000 17.13 @ 232 7.33 @ 374 8.27 @ 322 8.57 @ 283 7.83 @ 293 7.43 @ 323 17.28 @ 316 — 22.85 @ 80
titles-ru-1000000 23.08 @ 351 6.84 @ 455 7.78 @ 402 8.08 @ 361 7.34 @ 374 6.92 @ 397 31.75 @ 548 — 33.81 @ 95
titles-zh-1000000 13.58 @ 183 5.83 @ 362 6.59 @ 311 7.08 @ 248 6.33 @ 269 5.92 @ 310 17.52 @ 264 33.15 @ 231 18.24 @ 71
urls-1000000 18.14 @ 352 7.49 @ 425 9.29 @ 376 8.87 @ 332 7.99 @ 340 7.49 @ 374 16.88 @ 416 — 54.63 @ 124
uuid-1000000 38.88 @ 329 18.04 @ 391 19.10 @ 356 19.25 @ 332 18.54 @ 333 18.14 @ 338 37.11 @ 412 — 34.97 @ 118

From the same campaign (bench/results/frontier-1m-2026-11-05-arz-ea82db8.json). A routed cell's bytes are the blob's and the restart words' together — 0.5 a key at blocks 32 and 256, 1.0 at block 128 in microblocks of 8, 0.25 at 1024 — which no file holds and every process that routes pays in memory. A DoubleArray cell is a dash where the corpus's trie needs more slots than 23-bit bases address. The PerfectHash column answers a stranger exactly too, but in hash-order ids, so it is not the contract of the sorted searches and no count below includes it. It is the fastest exact answer on all thirteen, at 0.58× (numeric) to 4.9× (paths) XCDAT 15's bytes.

At a million keys lexindex's fastest exact search beats XCDAT 15 on three corpora of thirteen. DoubleArrayIndex takes numeric, 29 ns against 53 at 8.00 bytes a key against 7.05. Block 128 in microblocks of 8, routed, takes dna, 241 ns against 275 at 5.60 bytes a key against 22.46, and urls, 332 ns against 352 at 8.87 against 18.14. Four are within 3 % either way: words, on DoubleArrayIndex, 75 against 76, and paths, 617 against 618, uuid, 332 against 329, and titles-ru, 361 against 351, on that routed block. A cell is the single cold pass. A run of 4.5.3 against this commit reads DoubleArrayIndex's id on words at medians of 115 and 114 ns against 113 and 131, the spread of its own lanes (rel-sentinels-2026-11-05-arz-ea82db8.txt). The other six trail by 1.20× to 1.41× — DoubleArrayIndex on titles-zh, 231 ns against 183, the routed block of 128 on titles-en, opaque and domains, and StringIndex on idents and pypi. Against ART, which reads faster than XCDAT 15 on opaque alone and does not count its keys, opaque is 1.46×. DoubleArrayIndex is the fast end only where its trie is small: the other seven corpora would need more than 2²³ slots, which its 23-bit bases cannot address, and on the long keys of domains, idents and pypi, at 49–65 bytes a key, it is the slowest exact search lexindex has. Routing is most of the rest: at 4.3.3 the fastest DictIndex row read 1.2× to 3.0× behind XCDAT 15 on the twelve corpora other than numeric, and now it reads 0.88× to 1.83× there — block 128 in microblocks of 8, routed, the fastest DictIndex on all twelve, and 4–33 % faster than the same block unrouted, a comparison across processes. paths is the corpus it helps least: its restart keys tie in the eight bytes the words hold, and block 256 routed reads 628 ns where block 256 reads 657. What moved there is 4.4.1's tie trie, which places a probe among blocks whose samples tie — 3 899 of 3 907 at block 256 — by a trie of their eight-byte words, and which 4.5.1 keeps for runs of eight or more: on powersave, block 256 read 794 ns in 4.4.0's campaign and 699 in 4.5.2's, 4.4.1's in-process A/B put it at 768 → 704, and the fastest DictIndex, block 128 in microblocks of 8, routed, is level with XCDAT, 1.00×, where it was 1.20×. The rest of the bill is structural. Unrouted, a probe walks a block's restarts to one microblock and scans it — block / micro + micro − 2 header decodes, 62 at block 1024 — and routed it still scans the microblock, where a double-array trie takes one indexed load per byte of the key and decodes nothing. Front coding buys its bytes by making a comparison cost work, and that is the bill; routing pays part of it back in memory, which costs the size lead where it was thinnest — block 256 routed is larger than MARISA at ρ=2 on words, domains, idents and pypi, and every routed block is on paths. HashedDictIndex, which answers id without the search, does not pay the bill at all; what it costs instead is measured against XCDAT below.

The bill shrinks with n, and then it stops shrinking. Unrouted, the same ratio is 3.1× on words at half a million keys, 1.6× on titles-en at a million and 1.16× on titles-en at ten million; with 4.0's DictIndex, on powersave, which is what the campaigns past ten million keys ran, it is 1.17× on all 19.2 million English titles, while urls goes from 1.07× at ten million to 1.08× whole. At a hundred million keys 4.0's DictIndex is 1.21× behind on uuid (1.24× at ten million) and 1.59× on opaque (1.72×); dna goes from a 9 % lead at ten million to a tie, 844 ns against 864 and inside what memory placement alone moves a lookup on this machine; and StringIndex answers numeric in 156 ns against 408. This paragraph used to end on a prediction: that past the last level of cache a blob a third the size takes a third of the misses, so the dna crossing would generalise at a hundred million keys. That campaign has run, and it did not. What the numbers fit instead is one step — from a million keys, where a structure this size still sits largely in the 16 MiB last-level cache, to ten million, where every one of them pays DRAM misses — after which the ratio is set by how many dependent misses a probe takes, not by how many bytes it could touch. That is a reading, not a measurement; a miss profile of both lookup paths is what would settle it. The claim for the rows above is the measured one: smallest on every corpus, counting MARISA at its smallest, paths through the opt-in labelled build, and on the front of all of them; at ten million keys, routed, faster than XCDAT 15 on numeric, dna, urls, titles-en and uuid and 1.35× behind on opaque; at a hundred million, with 4.0 and no routing, faster on numeric, level on dna and 1.2× and 1.6× behind on uuid and opaque. The 19.2 M and 100 M numbers are the standalone benchmark suite's, at its a6c13d0 with lexindex 4.0.0 from crates.io: frontier-full-2026-09-21-arz-a6c13d0.json runs every structure over both corpora whole, and frontier-100m-2026-09-21-arz-a6c13d0.json runs only DictIndex at blocks 256 and 1024, StringIndex and XCDAT 15, since the full set at a hundred million keys would run for two days.

corpus Dict 256 smallest fastest lexindex on the front
dna-10000000 3.95 @ 481 lexindex Dict 1024 3.81 @ 463 lexindex HashedDict closed 7.19 @ 72 Dict 1024, Dict 1024 routed, HashedDict closed
numeric-10000000 1.02 @ 286 lexindex StringIndex 3.6e-05 @ 62 lexindex HashedDict closed 4.25 @ 36 HashedDict closed, StringIndex
opaque-10000000 10.05 @ 520 lexindex Dict 1024 9.95 @ 542 lexindex HashedDict closed 13.29 @ 73 Dict 1024, Dict 1024 routed, Dict 256, Dict 256 routed, HashedDict closed
titles-en-10000000 5.53 @ 635 lexindex Dict 1024 labelled 5.15 @ 720 lexindex HashedDict closed 8.77 @ 67 Dict 1024, Dict 1024 labelled, Dict 1024 routed, Dict 256, Dict 256 labelled, Dict 256 routed, HashedDict closed
urls-10000000 5.68 @ 704 lexindex Dict 1024 labelled 5.20 @ 789 lexindex HashedDict closed 8.92 @ 80 Dict 1024, Dict 1024 labelled, Dict 1024 routed, HashedDict closed
uuid-10000000 17.56 @ 625 lexindex Dict 1024 17.42 @ 636 lexindex HashedDict closed 20.80 @ 78 Dict 1024, Dict 1024 routed, Dict 256 labelled, HashedDict closed

Ten million keys, measured 2026-11-05 at 7b65814 (bench/results/frontier-10m-2026-11-05-arz-7b65814.json), on the performance governor, with two hours allowed a process and none reaching it. At this scale every lexindex row runs beside every competitor. The competitors read 0.88–1.14 of the 2026-09-20 campaign at 7e42c43, on powersave, median 0.97, MARISA's median 1.03, every size byte-identical. Other work while the 620 processes ran: median 0.01 busy CPUs, most 0.13.

At ten times the keys lexindex is on the front of all six corpora, and nothing from elsewhere is on any of them: HashedDictIndex closed on all six, DictIndex on five, and StringIndex on numeric, where it is the smallest and the fastest exact search. DictIndex is the smallest structure on the other five: dna at 3.81 bytes a key at block 1024 against C²-CoCo's 5.98 at ρ=1, opaque 9.95 against PDT's 13.73 and uuid 17.42 against PDT's 20.59 — builds of 113 and 124 seconds against 0.9 and 1.2 — and, by a narrower 9.8 % and 10.8 % with the labelled build and 6.1 % and 7.0 % without it, titles-en and urls against MARISA at ρ=2. On dna block 1024 as a load leaves it reads 463 ns to XCDAT 15's 556, so it is smaller and faster than everything from elsewhere. DictIndex builds before every one of them again, in 0.49–2.3 s, where the next is MARISA at 2.9–10.8 times that (PDT, at 2.4 times, on numeric), C²'s structures take 10–31 s and PDT up to 124 s. Only numeric keeps a trie smaller than DictIndex: CoCo-trie's 0.51 bytes a key against block 1024's 0.92, and neither is near StringIndex. urls, the corpus with the longest keys, is below whole.

urls-10000000 — 10,000,000 keys, 52.37 bytes a key raw

structure bytes/key % of raw build ms id ns spread front
lexindex Dict 32 7.01 13.4 2275 703 4 %
lexindex Dict 128/8 6.07 11.6 2352 714 1 %
lexindex Dict 256 5.68 10.8 2309 704 1 %
lexindex Dict 1024 5.42 10.4 2318 729 0 % ●
lexindex Dict 32 routed 7.51 14.3 2305 678 1 %
lexindex Dict 128/8 routed 7.07 13.5 2426 604 1 %
lexindex Dict 256 routed 6.18 11.8 2354 574 1 %
lexindex Dict 1024 routed 5.67 10.8 2306 568 1 % ●
lexindex Dict 256 labelled 5.45 10.4 9950 760 4 %
lexindex Dict 1024 labelled 5.20 9.9 9979 789 3 % ●
lexindex StringIndex 13.10 25.0 8807 712 6 %
lexindex HashedDict closed 8.92 17.0 3579 80 1 % ●
lexindex HashedDict fp=8 9.92 18.9 3572 107 1 %
lexindex HashedDict fp=16 10.92 20.8 3602 109 0 %
lexindex DoubleArray — — — — — refused: build error: double-array: more than 8 388 608 keys; ids are 23 bits
lexindex PerfectHash (ids in hash order) 52.89 101.0 4135 163 0 %
C²-FST 9.41 18.0 11847 1508 0 %
C²-FST ρ=1 8.20 15.7 13772 1789 1 %
C²-FST ρ=2 8.20 15.7 14338 1796 0 %
C²-CoCo 9.92 18.9 27923 1525 2 %
C²-CoCo ρ=1 8.71 16.6 29927 1782 1 %
C²-CoCo ρ=2 8.71 16.6 30605 1744 1 %
C²-MARISA 8.34 15.9 11850 871 3 %
C²-MARISA ρ=1 6.92 13.2 14151 1154 1 %
C²-MARISA ρ=2 6.92 13.2 14803 1161 1 %
FST 9.54 18.2 15419 1913 1 %
CoCo — — — — — aborted: std::bad_alloc
MARISA 8.66 16.5 10756 1120 1 %
MARISA ρ=1 6.23 11.9 12330 1556 4 %
MARISA ρ=2 5.83 11.1 12513 1664 1 %
PDT 7.34 14.0 27235 1125 0 %
ART 35.80 68.4 3560 837 5 % ref
C-ART 16.85 32.2 4123 879 10 % ref
XCDAT 7 12.37 23.6 12608 862 3 %
XCDAT 8 11.96 22.8 12273 801 5 %
XCDAT 15 14.75 28.2 12593 687 5 %
XCDAT 16 15.43 29.5 12259 723 3 %

From the same artifact (bench/results/frontier-10m-2026-11-05-arz-7b65814.json). spread is the range of a cell's three rounds over their median, and ref marks the two structures that do not count their keys. Four rows are on the front: block 1024 labelled, the smallest structure here at 5.20 bytes a key against MARISA's 5.83 at ρ=2; block 1024, 5.42 bytes; block 1024 routed, 568 ns at 5.67, against XCDAT 15's 687 at 14.75; and HashedDictIndex closed, 80 ns at 8.92. bench/frontier/tables.py prints this table for every corpus at both scales from the logs.

These are the same campaign's exact searches:

corpus XCDAT 15 Dict 256 32 routed 128/8 routed 256 routed 1024 routed StringIndex DoubleArray PerfectHash, hash-order ids
dna-10000000 16.00 @ 556 3.95 @ 481 5.08 @ 556 5.17 @ 469 4.45 @ 421 4.06 @ 402 15.98 @ 713 — 16.47 @ 116
numeric-10000000 7.06 @ 193 1.02 @ 286 1.76 @ 303 2.16 @ 306 1.52 @ 226 1.17 @ 201 3.6e-05 @ 62 — 4.61 @ 77
opaque-10000000 21.66 @ 316 10.05 @ 520 10.79 @ 477 11.22 @ 455 10.55 @ 425 10.20 @ 430 21.47 @ 471 — 16.33 @ 116
titles-en-10000000 13.95 @ 547 5.53 @ 635 6.51 @ 583 6.80 @ 532 6.03 @ 497 5.62 @ 507 13.25 @ 615 — 21.59 @ 116
urls-10000000 14.75 @ 687 5.68 @ 704 7.51 @ 678 7.07 @ 604 6.18 @ 574 5.67 @ 568 13.10 @ 712 — 52.89 @ 163
uuid-10000000 38.58 @ 531 17.56 @ 625 18.64 @ 575 18.79 @ 524 18.06 @ 507 17.67 @ 493 36.07 @ 530 — 34.64 @ 157

From the same campaign (bench/results/frontier-10m-2026-11-05-arz-7b65814.json). The DoubleArray column is empty because the format stops at 8 388 608 keys: an id takes 23 bits. XCDAT 15 reads 0.98–1.02 of 4.4's subset of 2026-09-24 at 3a73ed5, every DictIndex row 0.83–1.01, StringIndex 0.96–1.07 but on numeric, 95 → 62 ns. DictIndex sizes match it to the byte on dna, numeric, opaque and uuid; on titles-en and urls a DictIndex is 1.6–2.1 % smaller, block 256 at 5.53 and 5.68 where it was 5.65 and 5.78, since a build past about 2.6 million keys mines its phrases from more of its sample.

Routed, the exact search is ahead of XCDAT 15 on five corpora of six at ten million keys: numeric, where StringIndex reads 62 ns against 193 and holds all ten million keys in 356 bytes; dna, block 1024 routed at 402 against 556; urls, block 1024 routed at 568 against 687; titles-en, block 256 routed at 497 against 547; and uuid, block 1024 routed at 493 against 531. opaque is the loss: 425 ns for block 256 routed against 316, 1.35×. ART and C-ART, which do not count their keys, read faster than XCDAT 15 on three of the six, and against them numeric is 0.44 (ART's 140 ns), uuid 0.99 (ART's 497) and opaque 1.69 (ART's 251). Unrouted, block 256 is ahead on dna (0.87), level on urls (1.02), and trails by 1.16–1.65× on the other four. Routing keeps the size lead on every one of the five that a DictIndex holds — block 1024 routed is still under every structure from elsewhere — and it is thinnest on titles-en, 5.62 bytes a key against MARISA's 5.71 at ρ=2, where 4.4's 5.73 was over it.

Not every structure runs everywhere, and a cell that failed says why instead of carrying a number. C²'s three structures crash with a segmentation fault on numeric at every depth and both scales, and on dna at ten million keys at ρ=2. CoCo-trie stops with Sequence is not sorted on the three title corpora at a million keys, and runs out of the 28 GB of address space each process is allowed on uuid at a million and on every corpus but numeric at ten million. DoubleArrayIndex refuses seven corpora at a million keys and all six at ten million, and says which limit it hit.

The campaign puts the rest of the frontier beside marisa-trie, and what it finds there has moved: no compressed trie here builds faster than blocks of front-coded keys, and none the campaign times is smaller either, bar CoCo-trie on numeric, where StringIndex holds the whole corpus in 301 bytes at a million keys and 356 at ten million and beats both by three to four orders of magnitude. A block still shares only with its own neighbours, so where long fragments repeat across the whole key set — URLs, titles, paths — the plain block's lead is narrowest: 6.1 % on titles-en and 7.0 % on urls at ten million keys, and 2.0 % over MARISA at ρ=2 on paths at a million, the cell 4.0 turned over; the labelled build's are 9.8 %, 10.8 % and 10.2 %. Against MARISA at its smallest the two ten-million margins, last counted at 4.5.2, were 0.11 % and 0.30 %, and the plain block loses paths (below). Where C²'s cache-conscious MARISA reads faster than DictIndex as a load leaves it, on eight of the twelve corpora it runs at a million keys, it is larger. Routed, DictIndex reads faster than it on all eight. On titles-ru HashedDictIndex closed reads 58 ns against its 381, at 9.58 bytes a key against 9.14.

MARISA at its smallest

The campaign builds MARISA as benchmark.cpp does, at ρ of 0 to 2 — one to three tries — under the default cache, and that is not marisa's smallest trie: at the same depth the tiny cache is smaller on every corpus here, and most go on shrinking past three tries. The standalone benchmark suite builds the pinned marisa at 1 to 32 tries under both caches and keeps the smallest file, and counts what each loaded index holds on the heap beside its file. Three of this repository's corpus files — paths, idents and pypi — are not the suite's, so the suite's binaries were run over these files. Nothing is timed: marisa's own documentation says a deeper recursion "degrades the search performance", so these configurations have no lookup column and no place on a front.

corpus lexindex, smallest MARISA, smallest margin mapped: lexindex mapped: MARISA margin
words-full 2.50 (Dict 1024) 2.96 (4 tries, tiny) +15.3 % 2.55 2.96 +13.9 %
dna-1000000 4.23 (Dict 1024) 7.52 (3 tries, tiny) +43.8 % 4.25 7.53 +43.5 %
domains-1000000 4.22 (Dict 1024 labelled) 4.80 (8 tries, tiny) +12.1 % 4.27 4.80 +11.2 %
idents-1000000 4.88 (Dict 1024 labelled) 5.30 (11 tries, tiny) +8.0 % 4.93 5.31 +7.2 %
numeric-1000000 301 B (StringIndex) 1.62 (1 try, tiny) +99.981 % 333 B 1.62 +99.980 %
opaque-1000000 10.29 (Dict 1024) 15.55 (6 tries, tiny) +33.8 % 10.31 15.55 +33.7 %
paths-1000000 8.50 (Dict 1024 labelled) 8.81 (23 tries, tiny) +3.5 % 8.59 8.84 +2.9 %
pypi-full 3.88 (Dict 1024 labelled) 4.39 (9 tries, tiny) +11.5 % 3.93 4.40 +10.6 %
titles-en-1000000 6.91 (Dict 1024 labelled) 7.49 (15 tries, tiny) +7.8 % 6.96 7.51 +7.3 %
titles-ru-1000000 6.67 (Dict 1024) 7.61 (19 tries, tiny) +12.3 % 6.84 7.63 +10.4 %
titles-zh-1000000 5.67 (Dict 1024) 6.22 (12 tries, tiny) +8.8 % 5.96 6.23 +4.4 %
urls-1000000 6.98 (Dict 1024 labelled) 7.57 (20 tries, tiny) +7.8 % 7.04 7.59 +7.3 %
uuid-1000000 17.89 (Dict 1024) 22.98 (10 tries, tiny) +22.1 % 17.94 22.99 +22.0 %

A million keys, 2026-11-05, sizes only: a size depends on no governor (bench/results/marisa-floor-1m-2026-11-05-arz-4cb6401.json): the suite's marisa_floor and marisa_resident at its f93ff85, marisa at 3e87d53, this repository's resident at 4cb6401, every blob at a million keys the size the campaign above logged. A MARISA size is its file, io_size(), 220 to 270 bytes a trie more than the space_cost() the campaign counts. Mapped adds the heap a load keeps after a pass of lookups, counted as the bytes its allocations asked for: the tables load_mmap derives beside a DictIndex blob, and what marisa's Trie::mmap keeps.

Against its smallest, every margin holds, and paths is the narrowest: 8.50 bytes a key in the labelled build at block 1024 against 8.81 at 23 tries under the tiny cache, 3.5 % by file and 2.9 % once both are mapped. It takes that opt-in build: a plain block 1024's 9.28 is 5.3 % larger than MARISA's. In that build, in a subset run of 2026-11-05, microblocks of 64 take 1.4 % off paths for 2.2 % on id and 0.5–0.9 % off titles-en, urls and domains for about 5 %, and microblocks of 128 cost 11–24 %. On the other twelve, by file, the margins start at 7.8 % on titles-en and urls; mapped, where a DictIndex also holds the 0.02–0.29 bytes a key it derives at load — the most on titles-zh and titles-ru, whose character-code tables are the largest — against MARISA's 1–26 KB, they start at 4.4 % on titles-zh. At ten million keys this repository's six corpus files are the suite's, byte for byte, as are its two 19.2-million-key files, so the suite's artifacts answer for them (resident-10m, resident-full): DictIndex is 0.11 % smaller than MARISA at its smallest on titles-en and 0.30 % on urls by file, and mapped MARISA is 1.8 % and 1.5 % smaller; at 19.2 million, 1.0 % and 1.3 % by file, and mapped MARISA 0.7 % and 0.4 %. Those two ten-million margins are 4.5.2's: a DictIndex on titles-en and urls is 2.0 % and 2.0 % smaller since, the labelled build 4.0 % and 4.1 % smaller again, and the floor has not been counted against either. dna, opaque and uuid keep 15–43 % either way, and numeric is StringIndex's, in a few hundred bytes.

HashedDictIndex against XCDAT

HashedDictIndex (4.1) keeps a DictIndex whole and answers id without searching it: a minimal perfect hash over the keys' hashes and a bit-packed table holding each key's rank at its slot, so a lookup is two hashes of the key and two reads (the design). The campaign runs it at three widths: closed, which is id_unchecked at zero fingerprint bits, and id checking eight and sixteen bits. Its size is the whole blob, the dictionary included, and its build is both, from the keys. At a million keys it is part of the full campaign above, and the first table below takes its rows from that run, beside Dict 256, the dictionary it is built over, and XCDAT 15, the fastest structure from elsewhere that counts its keys on every corpus. Before that campaign it had run at a million keys only in a subset run of 2026-09-22 (artifact), against which XCDAT 15 read 0.97–1.05 in the 4.3.3 campaign and the sidecar's own cells 0.94–1.14 — the widest on pypi at sixteen bits, 32 → 36 ns, where a nanosecond is 3 % — the 4.4 campaign reads the sidecar at 0.93–1.10 of 4.3.3's, and 4.5.2's at 0.89–1.11 of 4.4's, 4.5.1's faster perfect hash. The campaign of 2026-11-05 reads closed at 0.92–1.32 of 4.5.2's, median 1.04.

At ten million keys it ran only in subsets before the 5.0 recounts, on the campaign's protocol — a process a structure and corpus, three rounds, every other one in reverse order. The first ran on 2026-09-22 beside Dict 256 and XCDAT 15 alone, twice: on the working tree that added the index (artifact), then on the committed code after a reboot (artifact); 4.4's of 2026-09-24 put every lexindex row beside XCDAT 15 (artifact). The second table below is the full campaign's. Against 4.4's subset XCDAT 15 reads 0.98–1.02 and HashedDict closed 0.96–1.19. Every ratio below is taken inside one run.

corpus XCDAT 15 Dict 256 HashedDict closed fp=8 fp=16
words-full 7.30 @ 76 2.62 @ 231 5.24 @ 14 6.24 @ 17 7.24 @ 17
dna-1000000 22.46 @ 275 4.37 @ 305 7.12 @ 51 8.12 @ 60 9.12 @ 61
domains-1000000 10.33 @ 146 4.48 @ 294 7.22 @ 29 8.22 @ 34 9.22 @ 35
idents-1000000 13.78 @ 194 5.22 @ 359 7.96 @ 38 8.96 @ 44 9.96 @ 45
numeric-1000000 7.05 @ 53 1.01 @ 233 3.75 @ 13 4.75 @ 18 5.75 @ 17
opaque-1000000 20.02 @ 199 10.40 @ 314 13.14 @ 49 14.14 @ 59 15.14 @ 59
paths-1000000 25.11 @ 618 9.83 @ 657 12.57 @ 103 13.57 @ 116 14.57 @ 116
pypi-full 9.92 @ 132 4.14 @ 306 6.88 @ 27 7.88 @ 31 8.88 @ 32
titles-en-1000000 17.13 @ 232 7.33 @ 374 10.07 @ 44 11.07 @ 51 12.07 @ 51
titles-ru-1000000 23.08 @ 351 6.84 @ 455 9.58 @ 58 10.58 @ 67 11.58 @ 68
titles-zh-1000000 13.58 @ 183 5.83 @ 362 8.57 @ 35 9.57 @ 43 10.57 @ 43
urls-1000000 18.14 @ 352 7.49 @ 425 10.23 @ 65 11.23 @ 78 12.23 @ 80
uuid-1000000 38.88 @ 329 18.04 @ 391 20.78 @ 61 21.78 @ 73 22.78 @ 72

A million keys, from the full campaign measured 2026-11-05 at ea82db8 (bench/results/frontier-1m-2026-11-05-arz-ea82db8.json). A cell reads bytes a key @ nanoseconds a lookup, the median of three rounds.

corpus XCDAT 15 Dict 256 HashedDict closed fp=8 fp=16
dna-10000000 16.00 @ 556 3.95 @ 481 7.19 @ 72 8.19 @ 86 9.19 @ 87
numeric-10000000 7.06 @ 193 1.02 @ 286 4.25 @ 36 5.25 @ 50 6.25 @ 52
opaque-10000000 21.66 @ 316 10.05 @ 520 13.29 @ 73 14.29 @ 85 15.29 @ 85
titles-en-10000000 13.95 @ 547 5.53 @ 635 8.77 @ 67 9.77 @ 78 10.77 @ 79
urls-10000000 14.75 @ 687 5.68 @ 704 8.92 @ 80 9.92 @ 107 10.92 @ 109
uuid-10000000 38.58 @ 531 17.56 @ 625 20.80 @ 78 21.80 @ 103 22.80 @ 105

Ten million keys, from the full campaign measured 2026-11-05 at 7b65814 (bench/results/frontier-10m-2026-11-05-arz-7b65814.json). Other work while the 620 processes ran: median 0.01 busy CPUs, most 0.13.

On all nineteen, HashedDictIndex is both faster than XCDAT and smaller. Closed, id_unchecked is 4.0× faster (opaque at a million keys) to 8.6× (urls at ten million), median 5.4×, at 1.39× (words) to 3.16× (dna at a million) less space; id at eight fingerprint bits is 2.9–7.0× faster and 1.17–2.77× smaller; at sixteen, 3.1–6.9× faster, and the size lead narrows to 0.9 % on words, 7.24 bytes a key against 7.30. At all three widths it is faster than every structure either campaign measured, the searches that beat XCDAT included: on numeric at a million keys 13 ns against DoubleArrayIndex's 29, on dna at ten million 72 against block 1024 routed's 402, on numeric there 36 against StringIndex's 62. Against the search of the dictionary it carries, the hash is 6.0–17.8× faster closed and 5.1–13.3× at eight bits — 4.9–12.6× and 4.1–9.1× against the same dictionary routed — for 2.6–3.2 bytes a key more: 2.62 on words, 2.74 at a million keys and 3.24 at ten million, where a rank takes 24 bits. And it builds before XCDAT on every corpus, from 1.28× on words to 6.2× on dna at ten million, in 1.32–2.76× the time of the dictionary alone.

A loop whose lookups can overlap flatters a hash. Those ratios are the cold pass, a free loop in which the next lookup starts before the last one's misses return. In the three chained passes these rows time after it, each query's slot waits on the answer before it: the latency a dependent caller sees. XCDAT 15 reads 0.99–1.09 of its cold pass there and Dict 256 0.98–1.01, and HashedDict closed 1.6–2.6× its own. It stays ahead on all nineteen, by less: XCDAT 15 is 1.69× (opaque at ten million) to 3.72× (paths at a million) behind closed, median 2.8×, 1.64–3.63× behind eight bits and 1.61–3.66× behind sixteen; Dict 256 is 2.56–8.2× behind closed.

corpus, chained XCDAT 15 Dict 256 HashedDict closed fp=8 fp=16
words-full 7.30 @ 77 2.62 @ 232 5.24 @ 28 6.24 @ 31 7.24 @ 29
dna-1000000 22.46 @ 273 4.37 @ 303 7.12 @ 118 8.12 @ 120 9.12 @ 122
domains-1000000 10.33 @ 146 4.48 @ 293 7.22 @ 47 8.22 @ 51 9.22 @ 51
idents-1000000 13.78 @ 200 5.22 @ 354 7.96 @ 70 8.96 @ 75 9.96 @ 75
numeric-1000000 7.05 @ 56 1.01 @ 235 3.75 @ 30 4.75 @ 32 5.75 @ 32
opaque-1000000 20.02 @ 201 10.40 @ 314 13.14 @ 112 14.14 @ 117 15.14 @ 117
paths-1000000 25.11 @ 623 9.83 @ 662 12.57 @ 168 13.57 @ 172 14.57 @ 170
pypi-full 9.92 @ 137 4.14 @ 300 6.88 @ 43 7.88 @ 48 8.88 @ 49
titles-en-1000000 17.13 @ 234 7.33 @ 374 10.07 @ 85 11.07 @ 91 12.07 @ 92
titles-ru-1000000 23.08 @ 357 6.84 @ 453 9.58 @ 126 10.58 @ 128 11.58 @ 129
titles-zh-1000000 13.58 @ 185 5.83 @ 354 8.57 @ 63 9.57 @ 70 10.57 @ 68
urls-1000000 18.14 @ 357 7.49 @ 423 10.23 @ 143 11.23 @ 148 12.23 @ 148
uuid-1000000 38.88 @ 334 18.04 @ 390 20.78 @ 135 21.78 @ 140 22.78 @ 138

A million keys (bench/results/frontier-1m-2026-11-05-arz-ea82db8.json): bytes a key @ the median of the rounds' chained means.

corpus, chained XCDAT 15 Dict 256 HashedDict closed fp=8 fp=16
dna-10000000 16.00 @ 575 3.95 @ 481 7.19 @ 185 8.19 @ 192 9.19 @ 197
numeric-10000000 7.06 @ 194 1.02 @ 286 4.25 @ 83 5.25 @ 93 6.25 @ 97
opaque-10000000 21.66 @ 321 10.05 @ 519 13.29 @ 189 14.29 @ 196 15.29 @ 199
titles-en-10000000 13.95 @ 580 5.53 @ 635 8.77 @ 156 9.77 @ 163 10.77 @ 167
urls-10000000 14.75 @ 746 5.68 @ 703 8.92 @ 203 9.92 @ 208 10.92 @ 212
uuid-10000000 38.58 @ 562 17.56 @ 625 20.80 @ 199 21.80 @ 204 22.80 @ 209

Ten million keys (bench/results/frontier-10m-2026-11-05-arz-7b65814.json), the same.

Its build needs no more memory than the dictionary's. The sidecar holds a 16-byte hash pair a key and the table, and builds after the dictionary has freed its own buffers, so the dictionary's build is the high-water mark. Measured on the thirteen corpora at a million keys and six at ten million (cargo run --release --example peak -- hashed 0 <bits> with LEXINDEX_PEAK_KEYS naming the corpus file, one process a cell), the build adds 88–191 bytes a key over the key list at a million keys and 31–73 at ten million, and at ten million every width's peak is its dictionary phase's to the byte. At a million keys the sidecar raises the peak on nine corpora of thirteen, by 0.1–5.1 bytes a key, the most on titles-zh; the same dictionary built in two processes reads up to 8 bytes a key apart, so the gap is the allocator's size, not the sidecar's (artifact).

What it does not do. XCDAT answers a stranger exactly. HashedDictIndex does only through the dictionary's search — id at zero bits, the Dict 256 column, which dict().route_microblocks() routes like any other DictIndex — so for a stranger the exact searches earlier in this section are the comparison. Unrouted, XCDAT leads by 1.06–4.4× at a million keys and 1.16–1.65× at ten million on four corpora of six, dna there turning over (0.87×) and urls level (1.02×); routed at block 256, the dictionary is ahead on dna and urls at both scales and on titles-en and uuid at ten million, and 1.01–3.1× behind everywhere else. With fingerprint bits, id answers a stranger as present at 2^-bits — 0.4 % at eight, 0.0015 % at sixteen, CompactHashIndex's rate — and with none, id_unchecked gives it some rank below n. The sidecar is also bytes the dictionary does not spend: where size is the only column, DictIndex is still the answer, and the smallest structure on every corpus above but numeric, which StringIndex holds.

Scaling to millions of keys

python bench/scale.py on real high-entropy keys (dictionary-word bigrams). Build time and memory grow linearly, lookups stay sub-microsecond, and CompactHashIndex's 1.24 bytes/key holds constant as n grows. Each row is measured twice: handing the constructor a list of keys, and handing it a generator. The second is what CompactHashIndex's streaming build exists for — it keeps a 16-byte pair per key and drops the string — and it is the only way to see the index's own footprint rather than the corpus's:

n structure keys build bytes/key peak RSS lookup
1 M StringIndex list 0.32 s 0.68* 155 MB 134 ns
1 M StringIndex generator 0.46 s 0.68* 148 MB 135 ns
1 M CompactHashIndex list 0.08 s 1.24 145 MB 92 ns
1 M CompactHashIndex generator 0.20 s 1.24 79 MB 67 ns
10 M StringIndex list 4.2 s 2.00* 1109 MB 541 ns
10 M StringIndex generator 5.7 s 2.00* 1033 MB 543 ns
10 M CompactHashIndex list 0.63 s 1.24 953 MB 218 ns
10 M CompactHashIndex generator 1.8 s 1.24 266 MB 250 ns

Measured 2026-11-05 at 7b65814, on performance (bench/results/scale-2026-11-05-arz-7b65814.json), one process per cell and the minimum of five per cell, at load 0.35 and 0.93 at its two ends. Against 2026-09-19 at 4ee80d2 (artifact), StringIndex's build is the control and reads back within its noise: 0.33 → 0.32 and 0.48 → 0.46 s at 1 M, 4.3 → 4.2 and 5.9 → 5.7 s at 10 M. Its lookup is no control now, since 4.3 changed the reader. CompactHashIndex's builds read 0.08, 0.20 s at 1 M and 0.58 → 0.63, 1.8 s at 10 M, and its blob stays 1.24 B/key. Lookups at 1 M read 189 → 134 and 72 → 92 ns; the second is a blob and a reader this recount did not change, which the first window of 2026-11-05 read at 64, so the move is not the code's (its samples read 92–97, and 72–153 on 2026-09-19). The lookup column at 10 M is not a measurement of the structures: the same CompactHashIndex blob's five samples read 218–329 ns from the list, median 247, and 250–353 from the generator, and StringIndex's 541–716 and 543–678, so a minimum of five says little there and 218 against 2026-09-19's 210 is not a finding by itself; the medians read 247 against 267. Why they scatter is not traced. The generator build's peak at 10 M is 266 MB against the corpus-holding build's 953, against 268 and 956 on 2026-09-19 — that gap, not the blob, is what the streaming constructor exists for.

Instructions a key as the keys double

A build that is linear in its keys retires about the same instructions a key at every size; a quadratic one does not, and a count shows it on any machine. bench/growth/ counts the user-space instructions one build or one load retires (perf stat with its counters enabled only around that operation), the process pinned to one CPU so that every build runs on one thread, at 2^16 to 2^24 keys on five corpora: 13 builds and 10 loads, 731 runs. analyse.py flags a phase whose instructions a key grow by more than 10 % in each of the last two doublings; a log factor adds about 5 % a doubling at these sizes. A count is not a time — a phase that waits on memory retires the same instructions however long it waits — so this tests the shape of a cost, and needs no quiet machine: v4.5.3 counted on a loaded machine repeats the counts of 2026-10-28 to within 0.01 %.

DoubleArrayIndex build, instructions a key 2^16 2^17 2^18 2^19 2^20 2^21
Chinese titles, 4.5.3 7 204 7 855 9 772 13 738 20 817 32 365
Chinese titles, 5.0 7 089 6 622 5 995 5 623 5 539 5 870

On 4.5.3 a row of several children searched the whole occupied array for a base, and the count a key grew 51.5 % and 55.5 % over the last two doublings; 5.0 searches a window under the top (8c92679), and a quiet A/B timed a million Chinese titles at 561 ms against 1 466 (CHANGELOG 5.0.0). Keys shaped against the placer, gen.py wide-rows (rows of 8 children out of 20 000 characters) at 2^20: 20 834 a key on 4.5.3, 3 164 on 5.0; alpha3000: 42 101 and 10 916. At 5.0 no phase is flagged. Three move by a step, not a slope: the file-backed PerfectHashIndex build once its key bytes pass the 32 MiB spill window (+61 % at 2^21 Chinese titles, flat before), the file-backed CompactHashIndex build at 2^24 URLs (+13.8 %), and plan() on words, which rises 11 % and then halves. CI keeps the double array's property without perf: a_wide_row_searches_no_further_than_the_window_once_it_applies counts search rounds in a test build: at most 34 a wide row, where a search without the window takes 75.

Counted 2026-11-13 at 7509fe9 and at v4.5.3 (bench/results/growth-2026-11-13-arz-7509fe9.txt), instructions:u, one CPU. To repeat: cargo build --release --manifest-path bench/growth/Cargo.toml, then bench/growth/sweep.sh > results.txt over the corpora bench/corpora.py writes, and python3 bench/growth/analyse.py results.txt.