lexindex v4.0.0

Changed

• DictIndex came down on every cell of the size sweep, and the format is BDX3. Thirteen
  corpora at a hundred thousand keys, eleven at a million and six at ten million, each at blocks of
  128, 256 and 1024: ninety cells against 3.0.0, ninety of them smaller. The median is 13 % at a
  hundred thousand, 25 % at a million and 38 % at ten million; the ends are 0.9 % on pypi at the
  smallest scale and 56 % on numeric. Seven changes, each priced on its own:

  The entry headers are one stream a shard wide. BDX2 spent a byte on every front-coded entry's
  (lcp, len) pair, four bits each, and two varints on every pair that did not fit. The pair
  distribution inside one shard is far narrower than that byte: a frame of reference over a run
  (min lcp, min len, two widths, all-ones escaping to the varints at the head of that entry's
  suffix) or a learned table of the 2^w - 1 costliest pairs at one to ten bits each carries almost
  all of them, and which of the two wins is a property of the shard, so one byte a group chooses it
  from every run at once. That is why a shard is now collected before any of it is written — the
  code cannot be chosen from a block — and both builds go through the same collection, so a streamed
  blob is still byte-identical to one held in memory. At block 1024: paths 14.34 → 12.46 bytes a
  key, urls 11.25 → 9.28, dna 7.70 → 7.27.

  A shard whose alphabet is narrow skips the symbols. A symbol table spends eight bits on a code
  and earns them back by naming runs of bytes; on a shard drawn from four characters, or sixteen, or
  sixty-four, that is the wrong trade twice over — two bits already meet the order-0 bound, and no
  run of bases is frequent enough to pay for a symbol. The two are priced against each other on the
  shard's own bytes, and each shard takes the winner, so a blob holding both shapes gets both. The
  codes of a run are continuous — an entry's suffix starts where the one before it ended, mid-byte —
  because padding each to a byte costs 0.32 bytes a key on DNA, the whole margin. At block 256: dna
  7.36 → 4.34 bytes a key, opaque 13.24 → 10.36, numeric 1.39 → 0.98. uuid keeps its tables on
  every shard; seventeen characters do not fit a nibble.

  The block sample is taken past the prefix every head shares. A million URLs all begin
  https://example.com/, so the eight bytes a block's sample held were the same word for 3 899 of
  3 907 blocks and the binary search that opens every lookup answered nothing. The sample is taken
  at g, the bytes every head in the blob shares — two bytes of header, none per block. Measured on
  a million URLs: 165 samples duplicate their neighbour against 3 899, a probe's run of candidate
  blocks is 2.02 against 3 271, and an id compares 1.13 heads against 11.54. Sorting is unchanged,
  since every head shares those bytes, and a probe that does not share them is answered by the
  boundary rather than a search.

  What the whole blob repeats is named once. Front coding takes the head a key shares with the key
  before it; what is left still repeats across blocks — /index.html, .example.com/,
  - Wikipedia — and no symbol reaches past eight bytes. A dictionary of such spans is mined over
  the blob's own suffixes and stored once; a shard that buys it gives up symbols for phrase codes,
  a split at s symbols leaving 255 - s byte codes that name 256 phrases in one further byte or
  65 536 in two, with 255 still the escape. A suffix is parsed by dynamic programming over the
  cheapest coding in bits, and the miner is three rounds of that parse and a count of windows of up
  to three adjacent tokens covering three to thirty-two bytes, keeping only candidates whose gain
  clears six times what they cost to store. Mining stops after the first round unless one of three
  sampled shards would take a split by 2 % on its own bytes — what the miner ranks is what coding a
  span once would save, and what decides the format is whether a shard would rather spend those byte
  codes on symbols; on a million opaque keys 40 000 spans clear the first bar and no shard takes
  one. Each shard then decides for itself and has its table retrained on what its phrases did not
  cover, and a blob no shard bought stores no dictionary. The vocabulary is a function of the keys
  alone — the miner's candidate pools are a constant rather than the thread count, so the same keys
  give byte-identical blobs on machines with one core and sixteen. At block 1024 over a million
  keys: urls 9.26 → 7.27 bytes a key, English titles 9.08 → 7.21, paths 12.48 → 9.32.

  The per-block samples are derived, not stored. The binary search that opens a lookup runs over
  eight bytes of every block's head, and BDX2 carried those bytes a second time in a section of
  their own. They are built from the heads at load instead: the same array, in the same place, for
  eight bytes a block off every blob — 2.666 bytes a key to 2.635 on the word list at the default
  block, 1.099 to 1.037 on a million numeric keys at 128 — and neither the load nor a lookup moved
  (five corpora, load within 0.9 % and id and key within 3 %, both directions). load_mmap
  borrows every section there now is.

  A microblock's start is an offset inside its own block. BDX2 measured every microblock start
  from the start of the blob, which needed a u64 base every 64 of them and a delta wide enough to
  cross four blocks — thirteen bits an entry on the word list at the default block, and the third
  largest section of a dictionary of decimal ids. A block's own start is a word the lookup reads
  before it needs any of them, so the array is stored relative to it: no bases at all and eleven
  bits an entry, 41 243 bytes against 52 493. It is smaller on every corpus and block measured
  (twenty-four cells, eight corpora at 32, 256 and 1024): −0.04 % to −3.7 %, the small blocks
  gaining most because they hold the most microblocks — numeric ids −3.7 % at 32 and −2.3 % at the
  default, the word list −1.6 % and −0.6 %. It is also one load fewer on the search path, worth
  −0.7 % to −1.3 % of the instructions an id retires and the same off key_into.

  The vocabulary is the miner's, and nothing prunes it after. A candidate is kept when what it
  saves over the whole blob clears its storage — the miner's bar carries a scale, because the
  gains are counted on a sample of the suffixes and paid for by every key. A pass then re-asked the
  same question with the scale taken off: it parsed those samples and dropped every phrase no
  sampled piece picked. A phrase that earns its keep at one key in ten thousand appears zero times
  in such a sample, so the pass could only remove what the blob-scaled test had already approved —
  3 265 phrases to 1 461 on a million domains, 19 089 to 10 392 on a million paths. Measured over
  ten corpora at four blocks, dropping the pass is smaller on 36 of 44 cells and larger on 8, every
  loss under 0.17 %: domains −4.3 to −4.9 %, paths −2.0 to −4.6 %, identifiers −0.8 to −3.6 %, urls
  and English titles at a hundred thousand −2.3 to −3.0 %, Russian titles −1.2 to −1.6 %. A variant
  that kept the pass but only re-ranked, never dropping, lands within 0.08 % of no pass at all, so
  the ordering it substituted is worth nothing. It costs the lookup, because a shard that reaches
  more phrases gives up symbols for them: id +0.4 to +1.4 % and key_into +0.7 to +4.8 %.

  End to end, BDX2 against BDX3 at the default block over a million keys each (lexindex build --index dict, sizes being a function of the keys): urls 11.25 → 7.51 bytes a key, paths 14.67
  → 9.87, article titles 9.37 → 7.37 in English, 11.36 → 7.67 in Russian and 8.28 →
  6.27 in Chinese, DNA 7.70 → 4.37, opaque ids 13.80 → 10.40, numeric 2.13 → 1.01,
  identifiers 6.66 → 5.23, domains 5.07 → 4.50, UUIDs 20.45 → 18.04; the dictionary's
  479 823 words 2.84 → 2.64 and 889 864 PyPI names 4.91 → 4.17. That is 7.0 % off the word
  list at one end and 52.5 % off decimal ids at the other. Against marisa-trie at its own best
  num_tries on each corpus, that makes DictIndex the smallest key-storing structure on ten of
  the eleven sweep corpora at a million keys and on all six at ten million, where 3.0.0 gave
  English titles and urls back to the trie — the two it takes back are won by 0.11 % and 0.33 %,
  which is a tie and a lead rather than a comfortable win on either.
  plan() prices the dictionary and the vocabulary's growth, so its estimate follows.

  What it costs to build. The price is the phrase machinery and nothing else, so it is paid only
  by the corpora that buy phrases. lexindex build --index dict end to end, the two binaries
  alternated X-2-2-X-X-2-2-X and the minimum of four taken: the word list 0.12 → 0.13 s at 1.29× the
  peak, DNA 0.52 → 0.54 s at 1.51×, urls 0.53 → 0.86 s at 1.82×, paths 0.70 → 1.13 s at 1.69×. Most
  of that wall clock is reading the file and sorting it, which the format does not touch; the build
  call on its own is 1.04× on DNA, 1.31× on decimal ids, 1.42× on the word list, 2.30× on domains
  and 3.20–3.75× on titles, urls and paths at a million keys. The miner's own cost is fixed — it
  reads a bounded sample of the suffixes and holds a bounded pool of candidates — so it amortises
  where a blob that size is actually built: at ten million keys the CLI is 1.20× on urls (6.77 →
  8.15 s, peak unchanged at 977 MB) and 1.21× on English article titles (6.14 → 7.42 s, 937 →
  977 MB), and the build call 2.42× and 2.09×. Turning the miner off outright is what names its
  share: −70 % of the build's retired instructions on urls, −63 % on domains, and −3.1 % on the
  word list, where the scout refuses after one round over a sixteenth of the pieces and the blob
  comes out byte-identical either way — the 3.1 % is the scout's own price for a decision that saves
  the other two thirds. That is what buys the wide end of the size range above; a corpus the scout
  turns away keeps only what the other four changes give it.

  Those multipliers were measured before the parse was tuned, and the parse is a third of a build's
  instructions. Six changes to it — the symbol table's eight bytes carried backwards rather than
  re-read, the double array's step reading one record instead of two and needing no bounds check,
  the parse token packed from twelve bytes into one word, one word a byte shared across the memo's
  rows, and one induction variable in the walk — take a build's retired instructions, net of reading
  and sorting the keys, down 9.9 % on urls, 9.6 % on English titles, 9.2 % on identifiers and
  8.8 % on paths, and the build call itself down 2.4–3.6 % in wall clock; the blobs are
  byte-identical. Dropping the pruning pass takes a further 5.2 % to 8.6 % off the same
  measure. Corpora that buy no phrase, decimal ids and the word list among them, are flat by
  construction.

  What it costs to read. Against BDX2 over a million keys at block 256, the two binaries
  alternated X-2-2-X-X-2-2-X so that code layout is not mistaken for the format: id runs 0.80×
  to 1.24× and key_into 0.77× to 1.46×. key_into is the lane that came out ahead — nine
  corpora of twelve, by 23 % on UUIDs, 17 % on urls, 16 % on paths and 14 % on Russian titles — and
  id is the one that did not: three of twelve, urls 0.80×, opaque ids 0.95×, UUIDs 0.95×. Behind
  on both are decimal ids (1.24× / 1.46×), where the blob is 0.49× and a BDX2 lookup is the
  fastest of any corpus, and the word list (1.20× / 1.00×) and domains (1.13× / 1.02×), whose short
  keys make the coded header the whole cost. A header that is coded rather than a byte is read with
  a shift and a mask, and that is the price of the bytes it saves.

  BDX1 and BDX2 are refused by name, as one reader and not three, so a dictionary blob written
  before 4.0 has to be rebuilt from its keys, which BDX2 stores: 3.x answers key(id) over the
  whole blob and 4.0 builds from the list. docs/migration-4.md is the worked path, index by index,
  with what happens to the ids. golden-2.2.0-dict.bdx joins the refused fixtures and golden-4.0.0-dict.bdx pins
  the new bytes.

• plan() prices BDX3, and the DictIndex estimate lands within 1.0 % of the built blob at the
  median. Three changes, each scored on the same 69 cells — 23 corpora at each of the three priced
  blocks.

  The old model read a blob as one byte an entry plus a compressed suffix, which is what BDX2
  wrote; BDX3 codes the headers and can spend well under a byte on one, so the plan was charging
  for a byte that is not there and discounting the suffix to match. The two are now measured apart —
  the sample blob is walked rather than added up by section — and the phrase dictionary is priced as
  its own term, per key, since it grows with the corpus and not with the shards the tables follow.

  The sample is built with the corpus's economics, not its own. The miner admits a phrase on what
  it saves over the whole blob against what storing it costs once, so a hundred thousand keys afford
  a tenth of the dictionary a million do: built as an index of its own, the sample reads the suffix
  ratio 0.71 where the million-key blob spends 0.53 on article titles. No slope fitted below the
  sample reaches the corpus either — the vocabulary is flat below a hundred thousand keys and falls
  convexly above them — so the sample is mined at the corpus's key count instead, over every suffix
  it holds, and the rate is carried flat. A million urls goes from 14 % high to 0.9 % low, three
  million article titles from 24 % to 1.4 %. That vocabulary is bought once a plan, not once a
  block: the three priced blocks read the ratio within 0.4 % of each other, and mining at each of
  them was both two thirds of what a plan spends and less accurate — the smallest block's own draw
  reads the ratio 21 % high on decimal ids.

  And what a stored entry costs comes off a second draw. A (lcp, len) pair is coded against its
  shard's own distribution, which is a property of the neighbours a key is coded against; a uniform
  draw puts those n / 100 000 positions apart and read a million decimal ids 0.51 bytes a header
  where that blob spends 0.34, a third of it. So the plan draws twice — uniformly for what a suffix
  compresses to and what an fst spends on a node, and in runs of 4 096 consecutive keys for what an
  entry and a block cost — both decided by hash, so plan_file makes the same two draws over a
  merged stream that plan makes over the sorted keys, and the two still print the same ladder to
  the byte on a 7 343 721-line path list.

  1.0 % median, 4.2 % at the 90th percentile, 7.2 % at worst, against 9.0 / 14.2 / 23.9 for the
  same model reading one flat-rate sample and 8.8 / 23.8 / 33.3 for the model BDX3 inherited.
  Corpora whose suffixes repeat nothing — DNA, UUIDs, opaque ids — land inside 0.5 %; the spread is
  an identifier list at 4.3 % low and a 7.3-million-line path list at 7.2 % high. The second draw and
  the corpus-economy mine cost a fixed 0.35 s and 44 MB a plan, so the ratio is worst on the
  cheapest plan and vanishes on the largest: 1.30× the wall time and 1.39× the peak on a million
  urls, 1.22× and 1.62× on a million Chinese titles, 1.06× and 1.12× on ten million English ones,
  and no change either way on the streamed 7 343 721-line path list, where the external sort's
  run budget is already higher than the miner ever reaches. docs/usage.md carries the numbers and
  says which way the estimate errs.

• The miner's gain maps are a third smaller, and the build spends 6–9 % fewer cycles for the same
  instructions. A candidate span was keyed by a u128 — two 64-bit rolling hashes carrying its
  length — and a u128 aligns a map entry to sixteen, so (key, (gain, span)) was padded from 40
  bytes to 48. Folding both lanes into one word takes it to 32. Nothing else moved: over fifteen
  corpus-block cells the blob is byte-identical, and the instruction count falls 0.6–0.9 % while the
  cycles fall 6.0–9.3 % — these maps were never the build's work, they were its misses.
  reserve_rehash over them is 8.5 % of the build's cycles against under 1.5 % of its
  instructions, and 39 % of its page faults, which is what the earlier profile could not explain.
  A million urls, alternated A-B-A-B: 18.7 → 17.0 G cycles, 0.904 → 0.863 s, 115 k → 96 k faults,
  peak 293 → 252 MB; a million paths 21.5 → 20.2 G cycles and 121 k → 108 k faults; plan, which
  mines densely, 187 → 158 MB on the same urls. A sixty-four-bit key can collide, which credits one
  span with another's gain and drops the loser from the dictionary — bytes, not correctness, at
  about one run in forty million.

• The latency model is re-fitted to BDX3, and the fit is worse where it should be. The
  constants in src/estimate.rs were fitted to BDX2 lanes, so on BDX3 they under-priced every
  DictIndex lookup by about a third — plan(.., Objective::Latency) was ranking the dictionary
  with a number the format no longer produces. Re-measured over the same 240 cells (four blocks ×
  three sizes × the corpus set, one process, bench/latency_model.py measure) and re-fitted from
  that artifact. Mean absolute error on id(key) is 6–13 %; held out a corpus at a time the model
  still names the fastest id(key) in 30 of 30 cells, the fastest key(id) in 30 and the fastest
  under a common_prefix-heavy workload in 30. Where it got worse is the one place the format
  moved: picking between DictIndex and StringIndex held out falls to 16 of 30 with a worst
  case of 1.75×, from 24 and 1.24×, because BDX3 raised the dictionary's id lane by about a
  sixth while the transducer's stayed where it was and the two now cross inside the corpus set
  rather than outside it. prefix_count is fitted at 26–46 % mean error and is quoted as such: its
  cost is dominated by how many keys the prefix matches, and the model has no term for that.

• The remap's samples are two levels, and cost half of what they did. Every 64 values of the
  remap carried the position of their block's first one in a u32, half a bit a value. The
  position is what a lookup adds to nothing else, so what it actually needs is the offset from a
  coarser mark: a u32 every 2 048 values and a u16 every 64 above it is 0.27 bits a value
  against 0.5, and the two loads are independent — both tables are small enough to stay in L1 and
  only their sum feeds the window's address, so the lookup gains an add and no dependent read. The
  width is safe by construction rather than by luck: the low bits are chosen to leave the high
  stream about as dense as it is sparse, so it holds about two positions a value and a super-block
  spans about 4 096; measured on real tables of 1 M, 10 M and 50 M keys the widest block offset was
  4 414, 4 710 and 4 789, a fourteenth of what a u16 holds, and a sequence that would defy that
  is refused by name rather than wrapped. The remap's samples fall from 0.0071 / 0.0067 / 0.0065
  bits a key to 0.0038 / 0.0035 / 0.0035 at those three sizes — 0.0033 / 0.0032 / 0.0030 off the
  whole function, which is where MPH3's last third of a hundredth of a bit was hiding.

• The perfect hash is 1 % smaller again and bumps a sixth fewer keys: a seed is chosen by the
  product of its keys' positions, not their sum. Of the seeds that place a bucket, MPH3 took
  the one whose keys' in-slice positions summed lowest, since low positions are what the buckets
  still to come cannot use. A sum is indifferent to how those positions are spread; the product
  of the positions plus a constant — PHast's ShiftOnlyProdWrapped objective, due to Piotr
  Beling — wants the lowest of them lowest, which packs the front of every slice tighter where
  the later buckets are placed. It is scored from a 16 KB table of log₂ in fixed point, one
  entry a key a candidate; the search itself, its candidates and its windows, is unchanged.
  Measured on 10 M real word-bigram hashes at the shipped λ 4.5: 1.935 bits/key against
  1.952 and 1.30 % of keys bumped against 1.57 %; at 100 M, 1.932 against 1.948 and 1.29 %
  against 1.56 %. The constant is flat between 50 and 150 and 95 is shipped. The build runs
  about 57 more instructions a key for the scoring, 2–3 ns of 63 on a hot machine, at the same
  cycle count within noise. The seeds change, so the golden-4.0.0-* fixtures are re-pinned; the
  format does not.

• The checked lookups run on fewer instructions: CompactHashIndex::id 37 % fewer,
  PerfectHashIndex::id 53 % fewer. CompactHashIndex::id called its slot lookup and the
  pair hash out of line and read every fingerprint through the bit-packed path with its overflow
  and tail checks, and once inlined still paid four bounds checks and an Option for a table
  whose length the loader had already checked. Now the lookup is inlined into the caller as one
  unit and the default-width fingerprint is one byte load with no check, on the loader's
  invariant: a blob's perfect hash is validated to map every hash into [0, m) when it is
  parsed, and the fingerprint table to hold exactly m entries. 1 M URLs, keys read from
  memory: 198 → 125 instructions a lookup (perf stat, exact counts; 16-bit fingerprints
  200 → 178). PerfectHashIndex::id validated the stored key as UTF-8 before comparing it with
  the probe — a pass over every byte that equality with a &str already implies — and called
  its slot lookup out of line: 420 → 198 instructions and 920 → 540 cycles a lookup on a hot
  machine. And every index's byte source now resolves its pointer once, when it is built or
  loaded, instead of on every access — a tag match, an Arc dereference and a range check a
  lookup: compact id 125 → 115 instructions, perfect id 198 → 180, DictIndex::id
  5 490 → 4 950. In this regime the instruction count bounds how many keys' cache misses the
  core overlaps, so it is the lever: the fingerprint derived from the hash's own state (below)
  took the compact lookup from 117 to 65 ns on a hot machine where the in-cache hash alone
  gained 5.

• The batch lookups prefetch a key's last line as well as its first. ids_of on the three
  hash indexes pulled in the first byte of a key 32 keys ahead and left the rest of the key to a
  demand miss; the hash reads a key to its end, and a key of a few dozen bytes lies across two
  lines as often as not. Naming the last byte too: on 1 M URLs ClosedHashIndex::ids_of 32 → 17
  ns a key and CompactHashIndex::ids_of 47 → 22, on 1 M titles 20 → 12 and 29 → 18, on 1 M
  paths 54 → 48 and 91 → 79 (hot machine, ratios). Cool, at the head of this release and with the
  lookup work that followed, the same six read 12.8 / 14.6, 9.7 / 13.2 and 41.2 / 47.5 ns a key
  (bench/results/mphf-strings-2026-09-17-*). A single id cannot make that prefetch — it has no
  next key to look at — and does not change.

• The key hash is new — branch-free over the key's length, half the time on real words — and
  every hash blob moves to BMP8, BCH8 and BCL2. The hash 2.0–3.x shipped read a key eight
  bytes at a time in a loop and finished with a tail switch; on real keys 6 of its 9.5 ns were
  branch mispredictions, and with MPH3 at 3.8 ns a lookup the hash had become the cost of a
  string lookup. The new hash reads a key of 4–16 bytes as four overlapping 4-byte loads, 17–32
  as its first and last sixteen, longer keys through two multiply lanes over 32-byte blocks that
  end on the last 32, and 1–3 bytes as one word; the words go through two 64×64→128 multiplies
  folded to 64 bits, side by side, and one more that merges them with the length — no loop and
  no branch on the length inside a class, and no bounds check: every load's index is in bounds
  by construction, and the six checks LLVM could not prove cost 6–16 % of the hash on real keys.
  The constants are consecutive words of π. The fingerprint is no longer a second pass: it
  folds the hash's own two lane products under its own constants with the length rotated — one
  multiply over the hash instead of a second merge and a second lane pair per block, so the pair
  every CompactHashIndex lookup computes costs 1.06–1.23× the hash alone where it cost
  1.6–1.95× (URLs 13.2 → 7.8 ns, UUIDs 12.2 → 7.1, 125-byte paths 21.7 → 12.6), with the same
  distribution battery result and hash_key itself unchanged. Measured
  A-B-A-B in one process on 2026-09-16, the hash alone over keys read in order: dictionary words
  3.9 ns against 7.3, English titles 7.4 against 11.2, URLs 6.5 against 13.2; 8-byte keys are the
  one loss, 3.8 against 2.9. The distribution battery (bench/results/hash-quality-*) reads the
  same. End to end, ClosedHashIndex::id over 1 M URLs / UUIDs / titles / paths reads 43 / 39 /
  28 / 65 ns against 54.5 / 46 / 32 / 92 in the same protocol over the old hash, a path that
  includes the key's own cache miss (bench/results/mphf-strings-2026-09-16-*); PtrHash's fast
  set over xxh3 of the same strings reads 55 / 50 / 38 / 100. Every blob keyed on the old hash would answer wrong ids under the new one, so BMP7,
  BCH7 and BCL1 join the refused lists with a message naming lexindex < 4.0 and the
  rebuild; BIX4 and OVL2 are untouched, and the standalone MPH1–MPH3 tables
  still load — a table is keyed on nothing but the hashes it was handed. hash_key_bytes
  (feature bench-mphf) returns the new values. Rebuilding from the keys is the migration; the
  golden-4.0.0-* fixtures pin the new bytes and the 2.0.0 ones become refused fixtures.

• The perfect hash is 6 % smaller and bumps half as many keys: its seeds gain modes, and the
  blob format moves to MPH3. An MPH2 seed was one shift: a bucket's keys sit at fixed
  offsets in their slices and the seed slides them along together, 255 positions at stride 2,
  and a bucket two of whose keys share an offset can never be placed — that was half of the 3 %
  of keys bumped to the next level. An MPH3 seed is two mode bits and six shift bits: each mode
  reads a bucket's offsets from a different field of the hash, so the four modes are four
  independent constellations of the bucket, each slid 64 positions at a stride of a sixty-fourth
  of the slice, and the seed taken is the lowest-sum placement over all four. Measured on 10 M
  real word-bigram hashes: 1.954 bits/key against 2.088, 1.58 % of keys bumped against
  3.03 %, for 1.4× the single-thread build time (fewer than half of PtrHash's or PHast+'s). The
  search runs on one occupancy word a key per mode — a key's 64 shifts are 64 consecutive bits of
  one plane of the map, its run to the wrap and the rest before it — so the feasible shifts of a
  bucket are the zero bits of an OR, and the lowest sum is at the first free shift at or after
  some wrap: a trailing_zeros a wrap. Every hash blob written from here on carries an MPH3
  table, which 3.0 cannot read; the MPH2 tables 1.1 to 3.0 wrote still load standalone and
  keep their seed geometry when written back. The golden-4.0.0-* fixtures pin the new bytes.

• A bumped key's remap is a sampled Elias–Fano stream, read in two steps. MPH2 sent a
  bumped key through four dependent lines after its first-level seed: the next level's seed, a
  rank word over the lower levels' values, the hole list's select sample and low word, its high
  words. MPH3 stores the remap as a non-decreasing sequence over every value of the lower
  levels — a value no key takes repeats its predecessor's hole — so it needs no rank: the
  values' high parts in one unary stream, a u32 sample a block of 64 values holding the
  position of the block's first one, and a packed array of their low bits. A lookup reads its
  block's sample — four bytes a block, under a megabyte for a billion keys, so in cache — then
  counts through the four words from there with four popcounts and one select, beside its low
  word; a block whose ones run past those four words, under one lookup in ten thousand on the
  tables measured, goes on word by word. A bumped key is now its next level's seed, then its
  four words and its low word side by side, and index_all has one prefetch stage fewer.
  Measured on 10 M real word-bigram hashes: 1.917 bits/key, the remap 0.116 of them at
  6 low bits, where MPH2's rank vector and hole list would take 0.125 for the same sequence;
  at 100 M, 1.915 and 0.114. Blocks of 128 values would save 0.003 bits a key and need eight
  words a lookup: 5–20 % slower on a bumped key and 1.5–6 % on index_all, hot.
  An MPH2 blob's rank vector and hole list are decoded into the stream when it loads, so it is
  written back as MPH3 under its own seed geometry — not byte for byte, as OVL1 became OVL2
  in 1.x.

• The perfect hash's tables ask for transparent huge pages. A table of a huge page or more —
  the first level's seeds from about 9 M keys up — is allocated on a 2 MiB boundary and advised
  MADV_HUGEPAGE before its first write, so a Linux kernel with transparent huge pages at
  madvise (the common default) or always backs it with 2 MiB pages from the first touch, and
  a random lookup stops missing the TLB on nearly every seed. Measured against the same process
  with huge pages turned off: single lookups 10 % faster at 10 M keys and 3–4 % at 100 M,
  batches 12 % and 2–3 %; bits and build unchanged. Nothing changes below 2 MiB, on other
  systems, or where the advice is refused; the file-backed tables of load_mmap cannot get
  them. No dependency: one madvise declaration.

• index_all finds each key's bucket once and reads its geometry as immediates. The batch
  loop pulled a key's seed in 64 keys ahead and then found the key's bucket a second time when
  its turn came, multiplied the shift by a stride it read from the level, and kept the level's
  geometry and its own bookkeeping on the stack. It now keeps the buckets it found in a ring of
  64, shifts instead of multiplying, and runs each block through a function of its own with
  the geometry every table of this version has — four modes of 64 shifts, slices of 1024 —
  folded in as constants: 54 → 47 instructions a key. Measured A-B-A-B against the loop before
  it: 7–10 % faster at 10 M keys, 3–5 % at 100 M; below 2^18 first-level seeds the batch is the
  single lookup in a loop, as before, and unchanged.

• index_all pulls a seed in three times on a first level past L3, and a seed's prefetch
  checks no range. The batch pulled each key's seed in once, 64 keys ahead. From about 75 M
  keys the first level outgrows a client core's 16 MB L3 and its lines come from DRAM, and with
  one issued every key that far ahead more are outstanding than the core has fill buffers for:
  at a billion keys a fifth of the lines were loaded on demand all the same, a stall each, against
  one in fifty at 16 keys ahead — a lead that was 20 % slower than 64 at 100 M. A first level of
  16 MB or more now pulls a seed in 56, 28 and 14 keys ahead, so that a dropped prefetch is issued
  again while there is still time, at the cost of a hit where the line has come. And no seed
  prefetch checks its range any more — a bucket is below the table's length by construction, and
  a prefetch cannot fault — a compare and a branch a key. Measured in one process against the loop
  before, A-B-A-B on a hot machine: 3–7 % faster from 3 M to 60 M keys, 22 % at 100 M, 19 % at
  300 M and 17 % at a billion (10.3 → 8.5 ns/key), 3–7 % on eight threads from 100 M up.

• A lookup reads its seed's mode from a table. A seed's top two bits pick which field of the
  hash is a key's offset, and the lookup decoded them into a shift on every placed key: a copy of
  the seed, a shift and a mask. A 256-byte table indexed by the seed holds the shift instead, one
  load from lines that stay in L1. Measured against the lookup before, processes alternated A-B-B-A
  on a hot machine, fat LTO: a single lookup 12 % faster at 10 M keys, 7 % at 100 M and 9 % at a
  billion (18.6 → 16.9 ns), a loop collecting ids 8 %, and index_all 1–5 %.

• An index's own arrays ask for huge pages too, and from_bytes copies a blob once. The
  perfect hash's tables were on 2 MiB pages, but the arrays around them sat on 4 KiB pages, and a
  PerfectHashIndex arena of a few hundred megabytes read at random missed the TLB twice a
  lookup, for the key's offset and for its bytes. Every byte array an index owns — the arena, a
  CompactHashIndex's fingerprints, a DictIndex's blocks, a StringIndex's transducer — is
  now allocated as those tables are, on a 2 MiB boundary from a huge page up and advised before
  its first write. The fingerprint table is built in place, and from_bytes copies the blob
  once, where it copied it into a Vec and then into an Arc. Measured at 10 M URLs, UUIDs and
  Wikipedia titles, processes alternated A-B-B-A against the build before on a hot machine, fat
  LTO: PerfectHashIndex::id 8–11 % faster, ids_of 4–14 % and key 10–16 %, built or
  loaded; its build 7–12 % faster, and from_bytes 4.6–4.8× (0.86 → 0.19 s on 10 M URLs —
  2.1× of that is the copy saved, measured with huge pages off).
  DictIndex::id 2–5 % and key_into 2–6 % faster, its batch within 1 % with huge pages on and
  off in one build; CompactHashIndex::id 1–2 %, its fingerprint table being one line a lookup.
  The arena gains from 480 k words and 1 M URLs up (id 5–10 %, key 5–12 %); nothing
  below 2 MiB moves — CompactHashIndex at 1 M keys, ClosedHashIndex at any size — and build
  peaks are unchanged. A mapped index reads its file's pages, as before.

• Mphf::build over hashes in any order: the serial sort is gone — 2.3–2.7× faster on eight
  threads, and a third of the peak at 100 M. Hashes handed over out of order were copied and the
  copy sorted on one thread before the first level could cut them into chunks: 22–25 ns a key on
  one thread or eight, and a construction peak the size of the keys. Now each thread marks its
  share of the keys with their group of chunks — two bits a key, four groups over equal shares of
  the buckets — and counts them by chunk; a group's keys are copied out by chunk when its first
  chunk is claimed, and each chunk is put in bucket order by one counting sort on the thread that
  places it, whose cursors end as the chunk's bucket offsets. Grouping every chunk up front by its
  buckets' two low bytes cost three times that sort, and copying all the keys at once is within
  2 % of four copies of a quarter. Measured on splitmix64 hashes in generation order against the
  build before, processes alternated A-B-B-A on a hot machine, fat LTO: 10 M 84.1 → 72.2
  ns/key on one thread and 32.8 → 14.3 on eight, 100 M 87.1 → 71.8 and 35.3 → 12.9; the
  construction peak above the keys 82 → 30 MB and 84 → 48 MB at 10 M, 818 → 261 MB and
  820 → 280 MB at 100 M. The same hashes in ascending order build as before (61.8 / 10.6 ns at
  10 M, 61.9 / 10.2 at 100 M), into the same table whatever the order and the thread count. Every
  index here hands its perfect hash sorted hashes, so the gain is Mphf's callers' — and the
  comparison's with PtrHash and PHast, which bucket their keys inside the build in any order.

• Mphf::build searches a bucket's seed over fixed lanes: 1.8–1.9× faster on one thread, 1.3–1.4×
  on eight, and ahead of PHast+ on both. The seed search spent its time on loops whose trip counts
  the branch predictor could not know — one a key a mode, a candidate loop a wrap, and a collision
  check that struck candidates out one at a time — and its placement order was a queue a size class
  under a binary heap, whose updates were most of the placement's instructions. Now a bucket of 1 to
  16 keys runs through a function of its own width, every loop's count known to the compiler. Two
  keys can meet under a mode's shifts only if their values are equal modulo the slice, so a table of
  the mode each residue was last seen in sends a mode to the exact check only when two of its keys
  agree, and the shifts a meeting rules out are a span of the mode's word; the first free shift at
  or after every wrap comes out of one addition, and a seed's score and the seed are one key, so the
  lowest needs no order. The buckets wait in a bitmap of priority slots — a bucket's index less its
  size class's term, in whole buckets, and a place in the slot the class fixes — taken from the
  lowest set bit behind a cursor. The seeds, and so the tables, are byte-identical, and a test holds
  the lanes to the search they replace over 24 000 buckets. Measured with bench/mphf_vs on a cool
  machine, splitmix64 keys in generation order, against the run before: 75.2 / 70.6 / 70.3 →
  42.8 / 37.5 / 37.5 ns/key on one thread at 1 M / 10 M / 100 M, 16.5 / 13.6 / 12.3 → 12.3 /
  10.6 / 8.7 on eight, and 12.8 → 7.7 s for 10⁹ keys on eight; PHast+ builds the same keys in
  55.4 / 60.2 / 67.9 ns on one thread, ahead of the old build at every size, and 17.9 / 15.4 / 16.5
  on eight.

• Measured against PtrHash and PHast on a cool machine, with three faults in the comparison
  harness corrected. bench/mphf_vs at 1 M / 10 M / 100 M splitmix64 keys, one process, A-B-A-B:
  MPH3 1.929 / 1.918 / 1.914 bits/key, the smallest function in every table, builds 42.8 /
  37.5 / 37.5 ns/key on one thread and 12.3 / 10.6 / 8.7 on eight, the fastest in every table,
  single lookups 1.9 / 2.6 / 10.0 ns, batches 2.2 / 2.5 / 3.5, a construction peak of 6 /
  30 / 262 MB above the keys — against ptr_hash 2.1.1's compact set at 2.143 bits, 148–165 ns
  builds, 4.0 / 5.5 / 16.8 lookups, 4.2 / 4.7 / 6.2 batches and 16 / 156 / 906 MB; its fast set at
  2.990 bits, level on the single lookup at 1 M, 1.9; and the ph crate's PHast+ at 2.146–2.160
  bits, whose builds read 55.4 / 60.2 / 67.9 ns on one thread and 17.9 / 15.4 / 16.5 on eight. The
  harness sorted the keys for its dedup, and every build took them sorted: Mphf skips its own sort
  on sorted hashes, while PtrHash and PHast bucket their keys whatever the order, so every earlier
  table read MPH3's build at 55–58 ns on one thread with a 60 MB peak at 100 M; the keys are built
  on in generation order now. The ph crate's PHast+ hashes with wyhash in the harness: its default
  is std's SipHash-1-3, which every earlier table timed, so its rows read 2–4× slower than the crate
  intends (PHast+ 8.8 → 3.5 ns at 1 M with the right hasher, its build 69.6 → 58.3). And the
  harness's lookup loops were inlined into one function beside each row's build, which cost lexindex
  0.7–3.6 ns a lookup and the other rows nothing measurable; each row's loop now stands alone. The
  tables and the corrections are in docs/benchmarks.md; the string-to-id path end to end, on real
  key corpora, is bench/mphf_vs's strings binary and bench/results/mphf-strings-*.

• Mphf::index_all answers the keys the first level bumps in staged prefetches, and the single
  lookup ranks and selects off derived counts. The batch used to pull in only the first level's
  seed, sixteen keys ahead, so each of the ~3 % of keys that level bumps made four more dependent
  misses in turn — its next level's seed, the rank words, the select sample, the high words — and
  at 100 M keys the batch stopped at 13.5 ns a key against 6.9 for PtrHash's index_stream. The
  keys now go through the first level in blocks of 1024 with each seed pulled in 64 keys ahead,
  and a block's bumped keys 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. The single lookup gains too: the
  remap's rank reads a 16-bit count per word instead of counting its 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. Both
  count directories are derived on build and on load and never written — the blob format is
  unchanged — and cost 0.023 bits a key in memory. In bench/mphf_vs at 1 M / 10 M / 100 M keys:
  the batch 4.3 / 5.3 / 13.5 → 3.2 / 4.2 / 5.8 ns, ahead of PtrHash compact and balanced
  (4.6 / 4.9 / 6.3) at every size and never above the single lookup; the single lookup 3.7 / 5.8 /
  20.1 → 3.2 / 4.9 / 15.8 ns (compact 4.2 / 6.0 / 17.6). PtrHash's fast set, at 2.99 bits,
  still leads both lookup columns outright. docs/benchmarks.md carries the re-measured tables.

• plan prices each DictIndex block as a candidate of its own. The block is a knob worth
  2.51 against 2.85 bytes a key on an English word list — a spread wider than the gap between some
  whole indexes — and the ranking hid it by pricing the default, 256, and nothing else. Fast
  (32), Balanced (256) and Compact (1024) are three rows on the ladder now, each with its own
  size and modelled latency, Plan::best may name any of them, and lexindex build --index auto
  builds the block on the line it marked rather than the default one. On an English word list the
  three are modelled at 2.83, 2.61 and 2.48 bytes a key against built blobs of 2.85, 2.64 and 2.51
  — every one of them within 1.3 %. Two consequences inside. The
  sample is fitted per block — the compression ratio, the packed per-block arrays and the symbol
  table all move with the block, and carrying the default block's constants across read 9.5 % high
  at 32. And Plan::close compares the two cheapest candidates of different kinds: two blocks of
  one index are always within a per cent or two of each other, and warning about that would be
  warning about every plan. --block is still refused alongside --index auto, now because
  naming one would ask the planner to rank the three and then overrule its answer.

• The planner draws its sample by hash instead of by position. step_by(n / 100_000) was
  neither a sample nor 100 000 keys: integer division gives a step of one at 150 001 keys, so "the
  sample" was the whole corpus and every constant was read off a build the size of the real index —
  and above that, a stride over sorted keys takes one key from every prefix group whatever the
  group's size. A key is kept now while its hash is under a cutoff that falls as the draw fills:
  a uniform sample of the distinct keys, the same one on every run over the same keys, needing
  neither the corpus's size in advance nor the corpus in memory — which is what lets plan_file
  answer exactly as plan does. It is also the more accurate draw. Measured over 23 corpora at all
  three blocks, the modelled DictIndex size is within 1.3 % of the build at the median and
  5.1 % at worst outside the two corpora the plan flags as thin (from 1.4 % and 5.4 % for a
  stride), and the StringIndex estimate from 3.4 / 9.8 % median and 90th percentile to 3.0 / 7.6.
  Against the step_by draw this replaces, on the corpora it read worst: idents-full 12.3 % →
  2.5 %, titles-zh at a million keys 15.5 % → 3.0 %, titles-zh whole 26.3 % → 7.1 %.

• lexindex plan and lexindex build --index auto now assume an open vocabulary, which means
  they imply --exact and so rank only the three indexes that can tell a stranger from a member.
  Left to itself the ranking was won by ClosedHashIndex at 0.24 bytes a key, which answers a key
  it has never seen with some member's id — the right index for a fixed vocabulary, and a trap for
  a reader who has not decided yet. The two probabilistic indexes are put back by
  --closed-vocabulary, and the ladder says on stderr that they were left out and how to ask
  for them; that line is printed only when the default is what excluded them, since any other need
  rules them out anyway. Naming one with --index closed still builds it. The library is
  unchanged: Needs::default() asks only for id(key) in Rust and Python, because plan's
  caller there has already decided and a command line's has not.

• A new blob format now ships beside a reader for the old one. 1.0 and 3.0 each refused what
  the previous major wrote; from 3.0 on a writer change lands in a minor release whose loader
  still reads the previous format, and dropping a reader is reserved for a major with lexindex dump as the published way back. BDX2 is frozen under that rule. docs/design.md § Versioning
  carries it.

• SECURITY.md names the supported version. Its table still said 2.1.x, and promised that 2.1
  blobs load — 3.0 refuses the BDX1 dictionary. Now: 4.0.x supported, and every row below it says
  which of its blobs this version refuses and which two still load — the new key hash retires
  BMP7, BCH7 and BCL1 alongside BDX2, so a 3.x install has four of five indexes to rebuild.
  Its unsafe inventory was recounted with it: thirteen unsafe fns and thirty-eight blocks in
  the library, not the nine and eleven it still claimed. Four of the functions and twenty-seven of
  the blocks are this release's own — the key hash's unchecked loads, the huge-page allocator, and
  writing into a Vec's spare capacity before extending it — and the document had described
  unsafe as confined to memory mapping and one prefetch, which stopped being true in 4.0.

• Stale figures in the docs and the source comments, corrected to what the code does. The
  DictIndex example in the README quoted 3.2 B/key (the block-32 figure) and docs/usage.md
  2.9, where the default block measures 2.64; src/offsets.rs described two packed arrays where
  there are three, and priced them at the old block; docs/design.md gave the per-block
  directory as 0.147 B/key and 5 % of the blob, the micro = 16 figure, against 0.100 and 3.5 %
  measured at 32; the microblock was documented as one per sixteen keys and the symbol table as
  one per index rather than one per shard; BDX2 was attributed to 2.2. The README's capability
  table now carries what load_mmap does not borrow — the per-block samples, eight bytes a block.

• The research frontier is cited, not just named. docs/benchmarks.md tables PDT, SuRF/FST,
  XCDAT, CoCo-trie, C² and the front-coding line this index descends from (libCSD, IBiS) with
  their papers, repositories and licences, and the README and bench/compare.py point at it.

• bench/sweep.py prices marisa at eight and sixteen tries as well. Four tries is its floor on
  an English word list and was taken for its floor everywhere; on keys with long shared prefixes,
  and on random identifiers, the deeper recursion is smaller.

• bench/mphf_vs measures the function, not the caller's key array. Its lookup pass read
  each probe key through keys[order[i]] — a random 8-byte fetch from an 80 MB array per query,
  one DRAM miss charged to every row alike — and the perfect hash's lookup was published as 29 ns
  at 10 M; with the keys copied into an array in probe order it is 5.8 (PtrHash compact 6.6,
  PHast+ 14.2), the builds unchanged. The harness now prints every minimum's spread and a batch
  column (index_all against index_stream), and docs/benchmarks.md carries the re-measured
  comparison at 1 M, 10 M and 100 M keys — where the 100 M batch is the one column PtrHash leads,
  6.9 against 13.5 ns — with ConsensusRecSplit on the authors' harness in its own process:
  1.46–1.58 bits a key at 7–49× the build and 15–27× the lookup. The 2026-09-10 results file stays
  as measured.

• The fuzzers run daily, on four processes for thirty minutes a target. They had ten minutes a
  week on one core inside sanitize.yml; fuzz.yml gives each target two CPU-hours a day,
  starting from the corpus the last run left and minimising it with cargo fuzz cmin before it is
  kept, so what the cache carries is the smallest set that reaches the same coverage rather than
  every file a month of runs ever wrote.

Added

• A wheel for free-threaded CPython 3.14. The module has told CPython it does not need the GIL
  since 0.12, and CI has run the suite on 3.14t since then — but the published wheels are abi3,
  and free-threading has no stable ABI before 3.15 (PEP 803 puts abi3t there), so pip install
  on a 3.14t interpreter fell through to the sdist and compiled the extension itself. It now finds
  lexindex-<version>-cp314-cp314t-<platform>.whl for the same six platforms the abi3 wheel covers,
  minus the cross-built macOS x86_64 one — a version-specific build needs the interpreter it is
  built against, which a cross build does not have. The wheel is the same source with the same
  guarantees, and its smoke test asserts sys._is_gil_enabled() is false after the import, so a
  release cannot quietly ship a module that switches the GIL back on.

• Kind::answers is
  public: whether an index of that kind answers everything a Needs asks for, which is what plan
  filters its five candidates by. A caller that presents the ranking can now say why a kind is
  missing from it without restating the capability table — which is exactly what the command line
  above needed.

• lexindex inspect <blob> --sections and
  DictIndex::sections,
  which return a DictSections: where a dictionary blob's bytes actually go. Thirteen byte fields
  that sum to the blob — the symbol tables, the block heads, the samples, the three packed offset
  arrays, and the front-coded data split the way it is written, into one header byte an entry, the
  (lcp, len) varints of the entries too wide for that byte, and the symbol-coded suffixes — plus
  the counts of restarts, entries and wide headers. The sum is exact for any blob, including one
  this crate did not write: the codes are what is left after the headers rather than what a walk
  managed to read, so a damaged stream leaves the split approximate and the total right. On an
  English word list at the default block it reports 56 % suffix codes, 34 % header bytes and
  3.3 % directory, which is the measurement a change to the format has to start from.

• A C ABI, under the capi feature: one opaque LexindexIndex handle over the five indexes
  and fourteen lexindex_* functions — open, from bytes, build, save, kind, len, id, ids,
  contains, key, free, and the version, ABI-version and last-error accessors — declared in
  include/lexindex.h, which cbindgen generates from src/capi.rs and CI regenerates to check.
  Every fallible call returns a LexindexStatus; the message behind a failure is thread-local and
  read with lexindex_last_error. A C caller opens a blob it may not have written, so the kind is
  a run-time fact and one handle type serves all five: what a kind cannot answer — key on the
  two that store no keys, contains on the bare perfect hash — is LEXINDEX_STATUS_UNSUPPORTED
  rather than a missing symbol. cargo build --release --features capi exports it from the
  cdylib; cargo rustc --release --features capi --crate-type staticlib gives the archive.
  examples/capi.c walks the whole surface and runs in CI against the built library. The ABI has
  a number of its own, LEXINDEX_ABI_VERSION, append-only within a crate major. Not in it, each
  additive when asked: Overlay, the mmap loaders, the automata queries, the fingerprint and
  block knobs of build.

• plan_file(path, needs, objective):
  the ranking of a keys file, without ever holding it. The file is sorted externally — runs in
  memory, spilled beside it, merged back — and the merge is where the key count, the mean length
  and both shared-prefix distances are counted, exactly rather than from a sample; only the
  three constants no statistic gives still come from one, and that sample is drawn by hash, which
  does not need the corpus in hand. So this is not an approximation of plan: on a 925 MB,
  7 343 721-line path list the two print the same ladder to the byte, at 0.27 GB of
  resident memory against 1.30 and in less wall time. lexindex plan <file> and lexindex build --index auto use it, so a ranked build now streams like a named one — where --index auto used
  to read the corpus in and say on stderr that pricing it meant holding it. Standard input still
  cannot be planned this way: it cannot be read twice.

• plan_for(keys, needs, objective)
  and Objective: the ranking
  can be for something other than the blob size. Memory is what plan has always answered and
  stays the default — plan is exactly plan_for(…, Objective::Memory), and its signature has not
  moved. Latency ranks by the modelled cost of one id(key); Balanced picks whichever
  candidate gives up least on the axis it does worse on. The candidates and their sizes do not
  change with the objective, only the order and so Plan::best. On an English word list asked for
  a reverse lookup, Memory answers DictIndex at 2.48 bytes a key and block 1024, Latency
  answers PerfectHashIndex, four times the size and a third of the wait, and Balanced answers
  the same dictionary at block 32 — 17 % faster for 14 % more space. lexindex plan|build --objective memory|latency|balanced and Python's plan(..., objective=...) reach it, and every
  estimate now carries nanos.

• Objective::Workload: rank
  by what the index will actually be asked. A Workload weighs hits, misses, reverse,
  prefix, common_prefix and longest_prefix against each other — relative weights, so counts
  read off a log serve as they are — and batch sets the keys an ids_of call holds. Every
  candidate is priced at the workload's mean operation from constants fitted per operation, and one
  that cannot answer an operation prices itself out. An operation is a need as well: reverse rules
  out the two indexes that store no keys and a prefix query asks for an ordered one, and
  Plan::needs says what
  a ranking was made under. The ordered pair is where it decides something: on an English word list
  common_prefix nine to one against hits answers StringIndex at 420 ns against 1 502 for the
  fastest dictionary, prefix in the same proportion answers DictIndex at block 32, 298 ns
  against 824, and batches of 1 024 leave PerfectHashIndex first at 74 ns a key. A workload that
  asks nothing is Latency. lexindex plan|build --objective hits=9,misses=1,batch=64 and Python's
  plan(..., objective={"hits": 9, "misses": 1, "batch": 64}) reach it.

• Plan::nanos, and a
  nanosecond column on the ladder. a + b·s + c·len + d·s·len per structure, operation and
  DictIndex block, where len is the mean key length and s is log2 of the candidate's blob
  over 64 KiB — what a lookup waits on is how far its bytes are from the CPU, which the key count
  alone does not say. Fitted on relative error to 240 cells: eight structures over thirteen corpora
  at 100 000 keys, eleven at 1 000 000 and six at 10 000 000, timed in one process with every
  operation over fresh probes of its own and every structure timed at every place in its round.
  bench/latency_model.py is the harness; its fit re-derives the tables in src/estimate.rs
  from the artifact in bench/results/, so the constants are checkable rather than asserted. Mean
  absolute error 5–13 % on id(key), 23–28 % at worst on prefix counts. It is an ordering, not a
  prediction. Fitted with a corpus left out, it names the fastest id(key) on that corpus in 30
  of 30 corpus-size cells and the fastest ordered index in 24, never picking one more than 1.24×
  slower; against the published sweep, which it was not fitted to, it picks between DictIndex and
  StringIndex the way the measurement does in 24 of 30 cells, never one more than 1.20× slower.
  And because the cells were timed through the Python binding it reads 311 and 318 ns for
  StringIndex and DictIndex on the word list where the Rust harness in docs/benchmarks.md
  measures 234 and 266; that overhead falls on every candidate alike, so it moves the numbers and
  not the ranking. The ladder says so on its last line, every time it prints one. A corpus under
  100 000 keys is priced as its 100 000-key equivalent, and the blob and key length are held at the
  smallest the fit saw rather than extrapolated past the evidence.

• lexindex build --stream: the command line builds without holding the corpus. With a named
  --index and a keys file, build feeds the file into the streaming builders instead of reading
  it into a Vec<String> first — auto (the default) past a quarter of the memory
  /proc/meminfo reports available, always / never either way, or a size (1000, 512M,
  4G). Measured on a 925 MB, 7 343 721-line path list, the peak resident set falls from 1.34 to
  0.28 GB for string, 1.42 to 0.26 for dict, 1.29 to 0.15 for compact and for closed, and
  2.96 to 0.97 for perfect — whose blob is itself 935 MB, so it is the one index that cannot
  finish below the file it was built from. All five blobs are byte for byte the ones the
  in-memory build writes: --stream is a memory setting, never a format. Standard input is never
  streamed, because the dictionary builder reads its source three times and a pipe cannot be
  rewound. --index auto streams as well, since plan_file prices a file without holding it
  either: the ladder comes off the streamed plan and its winner is built the same way.

• ClosedHashIndex::build_to_file,
  the fifth and last index to get one, so every kind the command line can build now has a
  streaming path. One pass hashes each key to its 16-byte pair and drops the string; runs are
  spilled and merged beside the output and the perfect hash is built from the merged file. There
  is no second pass — this index stores nothing per key, so what is left in memory is the perfect
  hash itself, which is the blob. It keeps the check build makes, one bit per slot, that the
  construction was minimal and perfect: an index that stores nothing per key has no second chance
  to notice that two keys were handed one id.

• lexindex dump <blob>, the fourth subcommand: the keys a blob holds, one per line, in id
  order — sorted order for StringIndex and DictIndex, construction order for
  PerfectHashIndex, live keys only for an Overlay. lexindex dump old.blob | lexindex build - new.blob is a migration off any format a later version stops reading, and it round-trips:
  rebuilding from a dump reproduces the blob byte for byte. The two keyless indexes say so rather
  than writing an empty file, and a key holding a line break is an error naming its id rather than
  a line a builder would read back as two keys.

• The research frontier, measured. bench/frontier/ builds the C² paper's benchmark — C²-FST,
  C²-CoCo and C²-MARISA beside FST, CoCo-trie, MARISA, PDT, ART and C-ART, every dependency at a
  pinned commit — and XCDAT, and runs DictIndex and StringIndex under the same protocol: one
  build, then one cold pass over every key in a fixed shuffle, three rounds a structure, each
  process waiting for a quiet machine. docs/benchmarks.md tables it at a million and ten million
  keys. lexindex is on the size–latency front on all thirteen corpora and all six; DictIndex is
  the smallest structure on twelve of the thirteen at a million keys and five of the six at ten
  million, the fastest on dna at ten million, and builds before every compressed trie on every
  corpus. The one corpus that keeps a trie smaller is numeric, where StringIndex holds the whole
  corpus in a few hundred bytes; C²-MARISA reads faster than DictIndex on ten of the thirteen
  and is larger on all of them. Nothing of the competitors is
  vendored — CoCo-trie is GPLv3, PDT non-commercial — and bench/tables.py renders the published
  frontier tables from their artifacts and checks them like the rest.

Fixed

• A streaming build no longer opens one file per spilled run. The external sort merged every
  run it had written in one heap, a descriptor and a 1 MiB read buffer each — so the resident cost
  of the merge followed the corpus, in a builder whose whole point is that nothing does. At 256 MiB
  of keys a run, a thousand runs is a corpus of ~256 GiB: a gigabyte of read buffers, and a
  descriptor count that outruns a 1 024 soft limit wherever one is still in force. The runs are now
  collapsed in groups of 128 first, so a merge opens at most 128 readers whatever the corpus was —
  one extra pass over the spilled bytes per factor of 128, and the common case, a build that spills
  fewer runs than that, does no extra work at all.
• The hash battery reported 99 999 collisions in 100 000 keys on a machine without a
  dictionary — its first scheduled run, on a CI runner. The hash was not at fault: the paths
  family was spelled from dictionary words outside the check that there is a dictionary, and the
  stand-in word made it one key repeated a hundred thousand times. The families that need words
  are built only where the words exist now, and every family is checked for a repeated key before
  its collisions are counted. Every number the battery prints is unchanged.
• StringIndex::from_untrusted_bytes refuses a hostile transducer structurally, so it no longer
  depends on unwinding. The loader caught fst's decoder panic and returned it as an
  IndexError, which is not a defence under panic = "abort" — an embedded profile, a size-tuned
  wasm build — where the same blob aborted the process. The cause was upstream and specific:
  fst::raw::Fst::new reads the root address out of the footer and then checks it only when it is
  zero, its (root == EMPTY && len != empty_total) && root + addr_offset != len short-circuiting
  on the first conjunct, so a blob naming a root past its own end is accepted and Fst::root
  indexes the blob with it — address 881 into 107 bytes for the committed
  tests/data/panicking-1.0.0-string.bix, raised inside fst before this crate sees a node. Every
  address the walk hands to fst is now measured against the blob first, from the fields that
  decide how many bytes a node occupies — the state byte, the pack sizes, the transition count and
  the packed deltas — and a node claiming more than sit below it, or a transition whose delta would
  be subtracted past the blob's start, is refused before the decoder is called. It is a bounds
  check and not a second decoder: it reads no input byte, no output and no transition index,
  because none of those can move a read. The catch_unwind stays as a backstop for a decode this
  crate has not modelled. tests/data/unfitting-4.0.0-string.bix pins the second shape, 40 bytes
  whose pack sizes underflow the node's end address, found in the first seconds of a fuzz run
  against an aborting build; both specimens now come back as Format, and SECURITY.md no longer
  carries the exception. What the claim rests on: the same target rebuilt with panic = "abort",
  where a panic is a crash and not a caught error, ran 3 832 487 116 executions over 24 CPU-hours
  without producing one.
• The weekly 32-bit Miri job stopped at the first overlay test that streams a perfect hash into
  a file. The arena is written through a file mapping, which Miri cannot interpret, so that test
  and every overlay test after it went unchecked on a 32-bit target. The mapping half of the two
  tests that reach it is compiled out under Miri; the rest of both still runs there.
• An MPH2 blob whose remap ran backwards panicked the loader. The v2 upgrade path decodes the
  older remap and re-encodes it as the sampled Elias–Fano stream, and it checked that every decoded
  value lands inside the image but not that the sequence is non-decreasing. The high parts arrive
  in order because the bitmap is walked in order; the low part under a repeated high part is
  whatever the blob says, so two entries sharing a high part could come back out of order and reach
  Remap::encode, which takes a non-decreasing sequence by contract. Now refused as a Format
  error at the boundary, where the range check already was. Found by the nightly fuzz job's
  parse_mphf target, which had been red since 2026-09-16; the specimen is
  tests/data/panicking-3.0.0-mphf.bin.
• An MPH3 blob whose level claimed a one-value slice panicked the loader. A level's stride is
  its slice shifted down by the geometry's mode bits, so a slice narrower than one shift leaves a
  stride of zero and a shift of 64 — an address the level is then read at with whatever the
  arithmetic wraps to. The loader checked that the slice is a power of two and fits the level, but
  not that it is wide enough for the stride it implies; slice_for never returns under 256, so no
  build writes one. Now refused as a Format error beside the other three shape checks. Found by
  the same parse_mphf target on the run that followed the fix above; the specimen is
  tests/data/panicking-3.0.0-mphf-slice.bin.