Changelog

All notable changes to this project are documented here. The format follows Keep a Changelog and the project adheres to Semantic Versioning.

[Unreleased]

Added

• PerfectHashIndex stores its keys overlapped where that is smaller: 10.88 → 9.25 bytes a key on the 479 823-word dictionary. A new arena encoding, tag 0x13, holds a greedy shortest common superstring of the keys — a key inside another costs no bytes, and an overlap between two is stored once — with one packed (start, length − min) entry a slot, the fingerprint in the same entry, and an overflow table for lengths past the entry's field. build and build_with_fingerprints price it beside the blocked layout and keep the smaller, a tie to the blocked one, so no key set grows. Over sixteen benchmark corpora the arena shrinks by 46 % on numbers, 33 % on DNA, 13–15 % on words, Chinese words, identifiers and package names, 11 % on Russian titles, 9–10 % on hex keys and UUIDs and 0.1–5 % on other titles; URLs, domains and paths keep the blocked layout. key(id) is still a zero-copy &str and membership one comparison. The merge runs on an Aho–Corasick automaton in O(N log σ + n log n) for N key bytes, deterministically, ties to the lower slot; it holds 9 bytes a trie node and a few dozen a key, freed before the arena is laid out. A load checks every merged entry once — inside the data and on character boundaries — so load_mmap of a merged arena is O(n), and a crafted entry is refused. Two golden blobs pin the encoding byte for byte and seed the parse_perfect fuzz target.
• Compatibility: upgrade readers first. The magic stays BMP8; lexindex 4.0–4.5 refuse a merged arena as arena: unknown offset encoding, and a blob whose arena stays blocked loads on every 4.x. build_to_file, build_to_file_with_fingerprints, a streamed lexindex build and Overlay::compact_to_file write the blocked layout as before: the same ids as build + save, not always the same bytes. plan prices the merged arena from a sample and reads high where the overlap grows with n: 9.67 bytes a key on the dictionary against 9.25 built.

Documentation

• The perfect hash's tail exhausts its 64 hash seeds only on duplicate hashes, now measured. Over 10 000 random 256-key tails 9.05 % needed a second hash seed and 8.1 % of those a third — independent attempts, under which 64 failures are about 10⁻⁶⁷ (mphf::spike::tail_attempt_histogram, behind bench-mphf).

[4.5.2] — 2026-09-25

Fixed

• A crafted DictIndex blob whose restart keys run out of order could make a routed lookup panic. Since 4.4.0 route_microblocks sends a lookup to its microblock by words it reads off each block's restart keys, and the route counts the bytes the probe shares with the word below it. That count stays inside the probe only while the words ascend, and nothing checked that they did: in a blob libFuzzer's daily parse_dict run found, the word taken as below was above and agreed with the probe's zero padding, so the scan began past the probe's end. A debug build panicked on the subtraction; a release build compared the stored suffix against more padding, and a dictionary in a packed code slices the probe from there, which panics in any build. Every read is bounds-checked, so none left the probe. Words out of order now leave their block to its restart run. Only a dictionary route_microblocks was called on was exposed, a HashedDictIndex's included; an index this crate built always has its words in order, so none changes. The blob is kept with a test that fails without the check (tests/data/panicking-4.5.0-dict-route.bdx).

[4.5.1] — 2026-09-25

Fixed

• A DictIndex lookup at ten million keys and block 32 is back at 4.4.0's time; 4.4.1 had made it up to 23 % slower. 4.4.1 gave every run of two or more blocks whose samples tie a trie of their words — a threshold measured on file paths, whose runs are 183 and 3 572 blocks long. Where runs are short, the trie's reads (its roots, a node, three edge arrays megabytes apart) replaced two or three head compares on adjacent lines: over ten million DNA reads at block 32 all 312 500 blocks sit in 65 536 runs of 3–7, so every lookup took a trie, 6.3 MB of them, for 6.4 more L2-missing fills and 2.3 more page walks a probe. Only a run of eight blocks or more gets a trie now. In a quiet A/B, three processes a variant, alternated (bench/results/ties-ab-2026-09-25-arz-2be75f3.txt): DNA 724 → 595 ns (4.4.0: 588), the routed layout 705 → 605 (600), English titles 677 → 661 (646), URLs 774 → 747 (738); paths at block 256 keep 4.4.1's gain, 700 against 4.4.0's 782; and DNA at 1024, where no samples tie, reads 472–475 in all three. A minimum of 32 read as 8 does on titles and URLs, 660 and 749. Blobs are unchanged.
• On a 32-bit target, a crafted blob of a hash index could make a load panic rather than fail. The count of the perfect hash's remap low words was multiplied in usize, which wraps there for a header claiming enough entries over a wide enough image; the table came out short, and only the bounds checks on its reads kept a load inside it, by panicking. The count is now checked, and such a blob is refused as too large — which the remap's reads, unchecked since this release (below), depend on. A property test holds the count to the exact one worked out in 128 bits.

Changed

• DictIndex builds 9–33 % faster, on every one of 13 corpora at blocks 32, 256 and 1024, blobs byte for byte the same. A build already ran on every thread; the gain is in the part no thread shared. Training draws its samples from the runs it keeps rather than walking every key; the order check and the key view's page faults run on every thread; the phrase trie a round builds is laid out 64 slots at a time and reads a candidate's head in one load; and a round ranks its candidates by merging the partitions' sorted leads. In a quiet A/B, one build a process, 11 rounds alternated (bench/results/dict-build-ab-2026-09-25-arz-8c99766.txt): English titles at block 32 397 → 349 ms, Chinese titles 272 → 224, URLs 404 → 367, numbers 85 → 60 — the least gain 9.3 % (URLs), the most 32.5 % (numbers at 1024). ART, the quickest builder in the string-index suite, built the English titles in 161 ms in its 4.5.0 campaign, where lexindex's quickest took 400: the gap is narrower, not closed.
• DoubleArrayIndex builds in under half the time, and maps its file as fast as darts-clone opens one. Over jieba 0.42.1's 349 045 words (bench/results/cjk-build-load-2026-09-25-arz-6623184.txt), a build takes 0.159 s where 4.5.0 took 0.354, 6.49 G instructions → 2.49 G: the trie is built from the keys in byte order, each decoded once; a narrow row's search tests a sparse stretch of the array word by word; and the placement tests four words an instruction where the CPU has AVX2. darts-clone still builds in 0.055 s and cedarwood in 0.099 — 2.9× and 1.6× quicker. A load's walk over every slot, which is what lets no query check a bound, now runs on the slots' 32-bit halves, eight slots an AVX2 instruction or four with SSE2, 15.0 M → 2.7 M instructions: load_mmap 1.03 → 0.62 ms in a pairwise run against darts-clone's open at 0.59–0.66 in the same processes, and 0.70 against 0.81 in the table's run; load 2.1 → 1.6. The same slots are refused, and blobs are byte for byte 4.5.0's.
• The perfect hash's lookup: a key the first level bumps runs 22.5 % fewer instructions, and the single lookup is ahead of PtrHash's fast set at a million keys where it was level. The seed's shift is added to the hash before its field is cut out, one instruction fewer on every placed key. A bumped key decodes its later level through the step table the first level ships; counts the remap's window with popcnt where the CPU has it, found by std's cached detection — every other target and Miri run the portable build, and a property test holds the two to the same answers; and reads the remap's tables without a bounds check past the one on its entry, on lengths and samples the loader has validated. Per key at a million keys, the harness's loop included: 284.8 → 220.7 instructions a bumped key, 24.7 → 22.8 over all keys, and 2.85 fewer in the id of ClosedHashIndex, CompactHashIndex, HashedDictIndex and PerfectHashIndex. In a cool A/B of bench/mphf_vs, one lookup thread, six processes a commit (bench/results/mphf-cool-ab-2026-09-25-arz-e523ecd.txt): the single lookup 1.8 → 1.65 ns at 1 M against fast's 1.8, and 2.5 → 2.4 at 10 M against 2.9; index_all 2.0 → 1.9 and 2.5 → 2.45, against 2.4 and 2.8.

Documentation

• SECURITY.md counts 21 unsafe fns and 62 blocks, the three builds for an instruction the x86-64 baseline lacks among them — the remap's popcnt lookup and the double array's AVX2 placement and slot check — each entered only once is_x86_feature_detected! has found it.
• The double array's build and load numbers are 4.5.1's in the README, the design notes and the benchmarks, whose table now says where it still loses (the build) and where it no longer does (the load); the perfect hash's benchmarks record the single lookup's lead.
• The frontier harness times DoubleArrayIndex, and reports a corpus past its limits as refused rather than as a failure; the tables list only the structures a campaign ran.

[4.5.0] — 2026-09-25

Added

• DoubleArrayIndex: a character-wise double-array trie for matching a lexicon against running text, and the fastest walk measured over Chinese. Over UD Chinese GSDSimp against jieba 0.42.1's 349 045-word lexicon it finds every word at every position in 10.6 ns a character, against daachorse's 15.5 for the same block scan, and walks a position at a time in 13.4 against crawdad's 15.8, darts-clone's 27.8, cedar's 29.0 and StringIndex's 58.6 (bench/results/cjk-walk-2026-09-25-arz-902e4b4.txt). A label is a character — its frequency rank in the lexicon, read from a table indexed by code point — rather than a byte, so a Chinese word of three characters is three steps, not nine, and each eight-byte slot holds everything a step reads: the label, whether a key ends there and whether anything continues, the child row's base and the key's id. A step is one load, and a match costs none past it. It answers common_prefix, longest_prefix, for_each_common_prefix, for_each_occurrence — every key at every position, the text decoded once — and id, with the ids StringIndex gives the same keys; no key(id), no prefix enumeration. 15.62 bytes a word on that lexicon, against 17.75 for darts-clone and yada, 18.40 for crawdad, 47.95 for daachorse and 60.57 held in memory by cedarwood. It loses on the build and the load (bench/results/cjk-build-load-2026-09-25-arz-902e4b4.txt): 0.35 s over the lexicon against darts-clone's 0.06 and cedar's 0.10, and load_mmap, which walks every slot, 1.07 ms against darts-clone's open, which checks nothing, 0.78. Every row goes to the lowest base where it fits, and floors — the lowest slot a set of labels could take never moves down — keep that exact fit fast on a small alphabet: 0.5 s over 480 k English words, where the plain search took 16.6. Limits, refused at build: 2²³ keys, 65 535 distinct characters, 2²³ slots. The blob is BDA1, checked slot by slot on every load, load_mmap included, so a crafted blob answers wrong ids and never reads out of bounds; a fuzz target (parse_double_array) and a golden blob pinned byte for byte. Python: lexindex.DoubleArrayIndex, whose occurrences counts characters; plugged into jieba it cuts in 30 % less time than jieba's own dictionary, 24 % with the HMM, and 4–6 % less than StringIndex.occurrences (bench/results/cjk-prefix-py-2026-09-25-arz-902e4b4.txt). inspect reports it; plan, Overlay and the C ABI do not take it.

Documentation

• paths is re-measured at 4.4.2 in the million-key frontier, and the Python jieba lane on 4.4.2's wheel. paths alone, every structure, three rounds (bench/results/frontier-named-2026-09-24-arz-b101076.json): with 4.4.1's tie trie DictIndex reads 712 ns at block 256 and 758 at 1024, where the 4.4.0 campaign read 794 and 826, against XCDAT 15's 618 — still behind, by 1.15× at block 256 and 1.11× at block 32, where it was 1.25× and 1.20×. Every competitor reads 0.971–1.012 of the campaign and every size is byte-identical. Through Python (bench/results/cjk-prefix-py-2026-09-24-arz-b101076.txt), jieba over StringIndex.occurrences builds the DAG in 560 ns a character against 649 over its own dictionary and cuts in 27 % less time, 21 % with the HMM.
• The common-prefix table on English words compares the same work, and DoubleArrayIndex answers both queries fastest there. Re-measured at 4.4.2 first (bench/results/common-prefix-2026-09-24-arz-b101076.txt: StringIndex 561 and 285 ns against datrie's 544 and 279, where 3.0.0 read 636 and 357), the table timed datrie's keys alone against lexindex's (key, id) pairs. It now times datrie's prefix_items and longest_prefix_item and marisa's ids, keeps datrie's keys-only row as such, and times each call after an untimed pass of its own (bench/results/common-prefix-2026-09-25-arz-902e4b4.txt): DoubleArrayIndex 473 and 234, StringIndex 530 and 295, datrie 780 and 417, its keys alone 344 and 237. Timed after another structure's pass instead, as before, DoubleArrayIndex's common_prefix reads 691 against StringIndex's 578: its array is 11.7 MB on these words.
• The Chinese walk table is re-measured with every double array, each row timed warm. The table it replaces ran the rows alternated, each 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 cedar at 49.5 and 46.2; timed after two passes of its own they read 27.8 and 34.5, 29.0 and 36.2. yada, crawdad's Trie and MpTrie and daachorse join them, with a build and load table.
• The README and the docs' front page say what StringIndex is for and what it is not. It is the automaton index — autocomplete, fuzzy search, ordered browse — and for an exact string ↔ id alone HashedDictIndex is faster and DictIndex smaller, and for matching a lexicon against text DoubleArrayIndex.

[4.4.2] — 2026-09-24

Changed

• A StringIndex prefix walk — common_prefix, longest_prefix, occurrences — takes its first character from a table: over Chinese text it runs 18–21 % faster. A walk reads the query down the transducer a byte at a time, each node's header read afresh, and a query's first character crosses the widest nodes, the root and the ones that spell the rest of its bytes. Over UD Chinese GSDSimp against jieba 0.42.1's lexicon that character took 649 of a walk's 1 025 instructions. The first walk now derives the state past every first character in the Basic Multilingual Plane — a bitmap of 64-code-point pages up to the highest such character, a count a page, a node address and output sum a character that begins a key — and a walk starts from there, or stops at once when no key begins with its first character; a character outside the plane is walked as before. 581 instructions a character. Against 4.4.1 in one binary over five processes (bench/results/cjk-prefix-ab-2026-09-24-arz-dda19a7.txt): 80.8 → 63.9 ns a character in text order and 93.5 → 76.5 shuffled, 0.79–0.80 and 0.81–0.82 of 4.4.1's time in every process. cedarwood 0.5.0 walks the same text in 49.5 and 46.2 ns and darts-clone 0.32 in 41.1 and 34.8, so lexindex still loses this walk, by 1.3–1.7× and 1.6–2.2× where it lost by 1.6–2.0× and 2.0–2.7×. On five more corpora a walk runs 22 % fewer instructions over a million Chinese titles, 10 % over words and Russian titles, 8 % over English titles and 3 % over URLs (bench/results/prefix-walk-counts-2026-09-24-arz-dda19a7.txt, counts only). The table is held in memory only and no blob changes: 0.29 bytes a key on jieba's lexicon, 0.085 on the Chinese titles, 0.03 on the English and Russian ones. The first walk derives it, not the load, so an index that only answers id never holds it; on the lexicon that first walk runs 2.9 M instructions more.

Documentation

• The common-prefix walk over Chinese text is measured against cedar and darts-clone, and lexindex still loses it. docs/benchmarks.md gains a section on jieba's lexicon over 4 997 sentences: from Rust, 4.4.2's StringIndex walks 1.3–1.7× slower than cedarwood 0.5.0 and 1.6–2.2× slower than darts-clone 0.32, holding a seventh of cedar's bytes and half darts-clone's; from Python, jieba over 4.4.0's StringIndex.occurrences cuts in 25 % less time than over its own dictionary, 18 % with the HMM, the fastest backend measured (bench/results/cjk-prefix-2026-09-24-arz-3a73ed5.txt).

[4.4.1] — 2026-09-24

Changed

• A DictIndex lookup that lands among blocks whose samples tie is placed by a trie of their words: on a million file paths id takes 8 % less time, at the default block and at 1024. A lookup opens with a binary search over one eight-byte sample a block, taken past the bytes every head shares; where a run of blocks shares the probe's sample, their heads were compared one at a time. On paths that run is the index — 3 899 of 3 907 samples tie at the default block, paths sharing long prefixes — and a lookup made 11.4 head compares, a quarter of its instructions. A load now splits each such run by its heads' eight-byte words past what they share, and a sub-run that ties again the same way past its own prefix: on paths 1 136 nodes and 5 035 edges, nine levels at the deepest. A lookup descends it reading only the probe, checks once against the head it arrives at, and starts the block's scan from that compare: 16.3 % fewer instructions a member id at 256 and 10.8 % at 1024, and within 0.6 % — all of it fewer — on words, English titles, URLs and UUIDs. Every answer is the one 4.4.0 gives, and no blob changes, byte for byte. The trie is held in memory only: 0.10 bytes a key on paths at 256, 0.02 at 1024, under 0.005 on titles and URLs, nothing where no samples tie. A load of paths runs 11 % more instructions at 256 and 3 % at 1024, and at most 1 % more elsewhere. Against 4.4.0 in one process, each build loaded twice, over three processes (bench/results/id-ab-2026-09-24-arz-b362f43.txt): id on paths 768 → 704 ns at 256 and 812 → 750 at 1024, every allocation of the new build under every one of the old; on English titles, URLs, UUIDs and words, and every key_into, within ±1.5 %. What it costs is at load, where the trie is built: a mapped load of paths takes 238 µs against 130 at 256 and 118 against 96 at 1024, and from_bytes, which reads and checks the whole blob, 4.2 and 0.2 % longer. Elsewhere from_bytes moves by at most 1.7 % and load_mmap by at most 5 %, 12 µs.
• A load of a DictIndex in a character code holds half the tables it did. Every load built the code's lookup tables beside the blob — a mapped one too — and they held the alphabet twice, took four bytes a codeword where sixteen bits carry it, and covered all of Unicode at their first level whatever the keys used. On jieba's lexicon a from_bytes index held 3.687 bytes a key, 21 % over its 3.040-byte blob and above marisa-trie's 3.578, whose load is its file to within 0.1 %; it holds 3.392 now, 5.2 % under marisa's. A million Chinese titles go from 6.474 to 6.243 bytes a key and a million Russian ones from 7.254 to 7.138, the tables halving on all three. Blobs are unchanged, byte for byte (bench/results/resident-2026-09-24-arz-b362f43.txt, which has the marisa rows). What it costs is in spelling the query, where a codeword is widened from sixteen bits: id on the lexicon runs 1 % more instructions and takes 1–2 % more time, 260 → 266 ns in the A/B above, and on the titles 0.6 and 0.7 %; key_into is level on all three.

Documentation

• What a mapped DictIndex builds is stated as it is. The README, the docs' front page and the Python module said a load_mmap builds only the per-block samples; it also decodes the symbol tables and, where they apply, builds a code's tables and the trie above — 0.07–0.39 bytes a key in all over the corpora measured, of which docs/design.md gives the parts.

[4.4.0] — 2026-09-24

Added

• DictIndex::route_microblocks, in Rust and in Python: a faster DictIndex search for eight bytes of memory a microblock. Once the samples and the head have chosen a block, a lookup walks the block's restart run — the first keys of its microblocks, coded against one another — to find the microblock it scans. route_microblocks() derives, for every block, the bytes its restarts share with its head and each restart's eight bytes past them; a lookup then counts the words below its own instead of walking, and walks only where a word ties it. No answer changes, and no blob, byte for byte: the words are held in memory only, 8 / micro bytes a key — 0.5 at the default block of 256, 0.25 at 1024 — and the method returns the bytes they take. It is a method rather than the default because it is paid for twice. Routed, the default block would give up its size lead over the smallest trie on four corpora of the thirteen at a million keys — words, domains, idents and pypi, where it leads by 0.34–0.39 B/key — and deriving the words reads every block's restart run, which a lazy load_mmap leaves unread until a lookup needs it. It takes &self, so a dictionary shared through an Arc — the Python object, HashedDictIndex::dict — routes in place, and a lookup that races it walks the run. Against the same index unrouted, in one process and in two builds of the harness (bench/results/id-ab-2026-09-24-arz-0216b39.txt): at the default block id takes 19–31 % less time on twelve corpora at a million keys and 13–22 % on six at ten million, and ids_of 16–24 % and 7–17 %; at 1024 keys a block id takes 23–36 % and 14–28 % less. With the change below, against 4.3.3, a routed id at the default block takes 23–41 % less time at a million keys and 19–31 % at ten million. paths, whose restarts tie in the eight bytes past what they share, moves between −2.4 and +1.8 %. At 32 keys a block, two microblocks, the words save at most 15 %, and cost numeric at ten million 3–10 %.

Changed

• A DictIndex lookup is faster with nothing asked for: id by 4–16 % and ids_of by 4–13 % on twelve corpora of thirteen at a million keys. Most of a lookup's instructions go to two front-coded scans, and the scan matched on the shard's codec for every entry it compared. It now picks the codec and the kind of header code once a run and walks the run in a loop of its own for that pair; reads the probe's last eight bytes once a walk, where every compare that reached the end of the key had folded them a byte at a time; and tests the symbol table's own codes before its escape and phrase prefixes. Blobs are unchanged, byte for byte. Against 4.3.3 in the run above, unrouted: id takes 4.9–15.5 % less time at the default block on twelve corpora at a million keys and 2.3–11.7 % on six at ten million, 6.3–16.4 % and 2.8–15.7 % at 1024 keys a block, and 3.7–15.2 % and 0.6–14.0 % at 32; ids_of at the default block 3.7–12.7 % and 2.2–9.6 %. On paths every lookup is 1.1–2.6 % faster.

[4.3.3] — 2026-09-24

Fixed

• DictIndex::id on a blob in a character code is as fast as 4.2.0's again. 4.3.2's id was 6 % slower than 4.2.0's on a million Chinese titles. Counted per query, the search was not the cause — in code it costs fewer cycles than 4.2's search in UTF-8 — but spelling the query: 342 instructions and some 130 cycles, run before the first step of the search could issue. The code keeps order, so the blocks a query falls between are the same whether the per-block samples are taken from the heads as coded or as decoded, and a coded blob's loader now takes both. Where the decoded samples tie no more blocks than the coded ones — 51 of 3 907 against 70 on the Chinese titles, none either way on jieba's lexicon — id searches them with the query's own UTF-8 and spells it while that search waits on its loads. The Russian titles tie 659 decoded against 161 coded, eight bytes of UTF-8 being four letters, and keep the coded route. The decoded samples are derived at load like the coded ones and take as much memory, eight bytes a block; blobs are unchanged, byte for byte. With the change below, against 4.2.0 and 4.3.2 in one process, in two builds of the harness (bench/results/id-ab-2026-09-24-arz-af19cb7.txt): on the Chinese titles id is level with 4.2.0 (−0.5 and +0.3 %) and 5.7–6.5 % faster than 4.3.2, on the lexicon 6.7–8.0 % faster than 4.2.0, and on the Russian titles 2.7–3.0 % faster than 4.3.2 and 0.8–2.7 % slower than 4.2.0.
• DictIndex::ids_of on a blob in a character code is 6–13 % faster. It checked every &str key as UTF-8 a second time, and grew, zero-filled and cut back an arena the size of the whole batch a key at a time. It now takes a str as it is, and spells 32 keys at a time into one arena reused across the batch, so it no longer holds a spelled copy of every key. Against 4.3.2 in the same run: 8.1–8.3 % faster on the Chinese titles, 12.6–12.9 % on the Russian ones and 6.1–6.7 % on the lexicon. That still leaves it 2.8–4.5 % and 1.2–2.4 % slower than 4.2.0's on the two sets of titles, and 5.0–5.3 % faster on the lexicon: on all three corpora a batch is slower than a loop of id in every version measured, so the spelling has no wait to run beside.

Changed

• A DictIndex lookup compares a head only where the samples leave it open, and id is faster on every corpus but paths. A block whose sample is below the probe's has its head below the probe, and one whose sample is above has its head above, so only a run of blocks sharing the probe's sample leaves heads to compare. Every lookup had also compared the head of the block before that run: one more dependent load and a memcmp, for a block the samples had already chosen. Between 0.4 and 12.4 % of the probes land in a run on thirteen of the fourteen corpora measured; on paths all of them do, since every path shares one byte and past it the samples tie 3 899 blocks of 3 907. On the eleven corpora that take no code, against 4.3.2 in the same run, id is 2.7–5.5 % faster on eight of them, 0.9–4.3 % on identifiers and UUIDs and level on paths; ids_of is 2.8–5.2 % faster on nine and level on paths, and on identifiers 4.0 % faster in one harness build and 1.5 % slower in the other, whose whole row, the control's included, the machine slowed by 9–25 %.

[4.3.2] — 2026-09-24

Fixed

• DictIndex builds faster than 4.2.0 again; 4.3.0 had made every in-memory build 11–81 % slower. Before building, 4.3.0 counted the keys' bytes outside ASCII to learn whether a character code could pay, and where one could it counted their characters and spelled every key: three passes on one thread, in key order, over the caller's keys. Those lie wherever the caller allocated them, so such a pass waits on memory at every key, and the byte count compiled to four instructions a byte, which keeps few of those loads in flight. The count now takes eight bytes a step; the three passes run a range of keys a thread, over one view of the keys that the encoder's threads now share rather than taking their own; and every pass prefetches the key 32 places ahead. The order check and the deduplication in front of the build — a sort's check for a run and a dedup_by, two more passes of the same kind — are now one pass that reads ahead. Blobs are unchanged, byte for byte. Over the thirteen corpora of the million-key frontier, at blocks 1024 and 256, alternated with 4.2.0 and 4.3.1 in one run (bench/results/build-ab-2026-09-23-arz-152a00f.txt), a build takes 11–53 % less time than 4.3.1's on every corpus; against 4.2.0's it is 29–35 % faster on Russian titles, 11–14 % on Chinese ones, 3–25 % on eight Latin corpora, and within 2 % on paths, English titles and URLs. The loss was found by re-measuring the frontier at 4.3.1 (bench/results/frontier-1m-2026-09-23-arz-8dc8b73.json), where DictIndex no longer built first on three corpora of the thirteen, and the corpus sweep at 4.3.1 shows it too (bench/results/sweep-2026-09-23-arz-8dc8b73.json).

[4.3.1] — 2026-09-23

Fixed

• key_into on a blob in a character code is back at 4.2.0's speed, and id much closer to it. 4.3.0 decoded a key a character at a time through the tables the code is stored in — the codeword's lead found among the leads, a branch on the mode and on the lead's width, char::encode_utf8 — and then checked the finished key as UTF-8 a second time; it spelled a query through a two-level index, behind a branch on the mode. A codeword now decodes in two reads and one four-byte store, out of a table of the 256 values its first byte can take and one of every character's UTF-8. What the decoder writes is whole characters out of a table built from chars, so it becomes a String without the second pass; a debug build still checks it, and so do the fuzz targets. Code points below U+0800 — ASCII, Cyrillic and every other script UTF-8 spells in two bytes — are one flat level of the index, and under the eight-bit mode ASCII is in the index too, so spelling a query no longer asks which mode it is in. Blobs are unchanged, byte for byte. Against 4.2.0 in one process, in two builds of the harness (bench/results/charcode-ab-2026-09-23-arz-668a1d3.txt): key_into is 2.5–3.3 % faster on a million Russian titles, where 4.3.0 was 19–23 % slower, within 2 % on a million Chinese ones (4.3.0: 11–12 % slower) and level on jieba's lexicon (4.3.0: 4–5 % slower); id is 1–2 % slower on the Russian titles (4.3.0: 6–7 %), 6–8 % on the Chinese ones (4.3.0: 12–13 %) and 3–4 % faster on the lexicon, as in 4.3.0. English titles, whose blob is 4.2's, read within 2 % of 4.2.0, the band two builds of the harness move by. Most of what id still pays is spelling the query: all of it on the Russian titles, where spelling it twice adds 610 instructions and id pays 605 over 4.2.0, and two thirds of the 530 instructions it pays on the Chinese ones.

Documentation

• The million-key size table and the README's margin over marisa-trie are re-measured at 4.3.0 (bench/results/sweep-2026-09-23-arz-4f2a0e9.json), so they show the character code. Of the 264 cells the run shares with the 4.0.0 one, 252 are the same to the byte; the twelve that moved are DictIndex on the Russian and Chinese titles, 6.7–14.7 % smaller, and their margins over marisa's best setting go from 2.2 and 1.6 % to 14 and 9 %, so the README's range now starts at English titles' 3.9 %. At ten million keys (bench/results/sweep10m-2026-09-23-arz-4f2a0e9.json) all 66 cells are the same to the byte: the code takes none of those six corpora. The run's timings are not published, since the machine was busy.

[4.3.0] — 2026-09-23

Changed

• DictIndex spells keys mostly outside ASCII in a character code of their own, and such a blob is 6.7–17.9 % smaller. UTF-8 spends three bytes on a Chinese character and two on a Cyrillic letter, and the dictionary's symbol tables win back only part of that. A build now counts the characters its keys hold and, where they are mostly outside ASCII, may respell every key in a code fitted to them: the most frequent characters a byte each, the rest two. The codewords rise with the characters and none is a prefix of another, so coded keys sort exactly as the keys do — ids stay ranks, a prefix stays a prefix, and every query answers as it did, a query holding a character the code does not spell included. The code is kept only where it pays: it has to take a tenth off the keys, table included, and a twentieth of what it saves has to cover the table, because the codec behind it removes much of the same redundancy on its own. At the default block, jieba's 349 045-word lexicon goes from 3.653 to 3.040 bytes a key (−16.8 %) — under marisa-trie's smallest setting on it, 3.58, which was smaller than 4.2's blob — a million Chinese Wikipedia titles from 6.270 to 5.851 (−6.7 %) and a million Russian ones from 7.664 to 6.862 (−10.5 %); at 100 000 keys the three come out 17.6, 9.2 and 14.2 % smaller. English titles, words, paths, PyPI names, URLs, identifiers and domains take no code and write the blob 4.2 wrote, byte for byte. The bar is conservative on a small corpus: three thousand random keys over two thousand ideographs would have come out 4.1 % smaller coded, and are kept in UTF-8. What it costs is time, where it is taken, since a query is spelled in the code before the search and a key decoded after it is read: against 4.2.0 in one process, id is 6 % slower on the Russian titles, 10 % on the Chinese ones and level on the lexicon, and key_into 22, 11 and 5 % slower. On a corpus that takes no code both are within 3 % of 4.2.0.
• A blob in a character code is BDX4: BDX3's layout with the code appended as its last section, its length in four header bytes BDX3 reserved. 4.3 reads every BDX3, and a build that takes no code still writes one. 4.2 and earlier refuse a BDX4, and with it a HashedDictIndex whose dictionary is one, so a reader has to be on 4.3 before the first such build reaches it. DictSections::chars and lexindex inspect --sections say what the code weighs.
• plan() prices the code: it chooses one off its two draws as a build would off the corpus, spells the draws in it and scales the corpus's shape by what the spelling did to them. On the three corpora above the DictIndex estimate lands within +1.6 to +3.1 %, −3.2 to −3.9 % and −0.3 to −0.6 % of the built blob across the three priced blocks, where an estimate priced in UTF-8 would carry what the code saves as its error.
• StringIndex reads its transducer one step at a time. id, contains, ids_of and every prefix walk — common_prefix, longest_prefix, occurrences, for_each_common_prefix — went through the fst crate's node decoder, which reads a whole node — its pack sizes, transition count, end address and final output — before it can say where one byte leads. A walk down one path needs two answers at each node it passes, whether the node is final and where the next byte goes, and now reads only those, from the same bytes. The answers are unchanged, and three checks hold the reader to fst's decoder: a property test over random maps with arbitrary values, the transducer formats before version 3, and the parse_string fuzz target, which walks every key of a parsed blob both ways. Against 4.2.0 in one process, over a million titles in English, Chinese and Russian and over jieba's lexicon, id is 29–34 % faster and a common-prefix walk 20–26 % faster.

[4.2.0] — 2026-09-23

Added

• StringIndex.occurrences(text): every key that occurs in a text, in one call. A dictionary segmenter — jieba and its ports among them — asks for the keys that start at each character of a sentence, and from Python that was a common_prefix call per character, each one a crossing of the binding for a walk that is over within a few characters. occurrences runs the same walk at every character on the Rust side and returns (start, end, id) triples, with text[start:end] the key: starts ascend, and within a start the shortest key comes first — the order jieba's word graph is built in. Offsets count characters, as a str is indexed, not UTF-8 bytes. The empty key, which would occur at every position, is not reported.
• StringIndex::for_each_common_prefix, the walk under common_prefix and longest_prefix, is public: f(end, id) for every key that is a prefix of the query, shortest first, with the key &query[..end] and nothing allocated. The walk stops where no key continues, so the query can be the whole rest of a text.

Fixed

• lexindex.inspect's docstring opened with somebody else's paragraph, a note on the extension module's gil_used = false that has sat above inspect since inspect was added in 2.0.0 — so help(lexindex.inspect) began with it, and so did inspect's entry on the API page, which is rendered from the same docstring. The note is back beside the #[pymodule] it explains, as a plain comment that cannot become a docstring again.
• The API page carried 73 links to nowhere and 26 Sphinx roles printed as typed. The binding's doc comments in src/python.rs are Python docstrings — help() and the API page both read them — but they were written as rustdoc: [id](Self::id) is a dead link in Markdown, and [PyStringIndex::to_bytes] names a Rust type no Python caller meets. Those are code spans now, and DictIndexIterator's docstring, which was a note on its lock, describes the iterator. The stub and lexindex/__init__.py used Sphinx roles (:meth:, :class:, 105 of them), which Markdown shows verbatim; they are double-backtick literals now, as the rest of those docstrings already were. A test holds every docstring the runtime or the stub carries to that.
• docs.yml: its release: published trigger never fired, in 24 releases — release.yml creates the GitHub Release with GITHUB_TOKEN, whose events start no workflow — and its push filter missed two files the site is built from: polars/README.md, which is the Polars page, and src/python.rs, whose doc comments are the docstrings the API page renders for every compiled class and function. The trigger is gone and the filter names both, so a change to either redeploys the site on the push that carries it.

[4.1.1] — 2026-09-23

Fixed

• The latency model is re-fitted to a clean run, and the 1.75× it was quoted at does not reproduce. The constants plan ranks by under Objective::Latency, Balanced and Workload came from a run taken beside other work — its load average was 0.64 when it started and 1.82 when it ended, 2.41 over its last five minutes — and from before the three commits that took 6–13 % off the instructions of a DictIndex lookup ahead of 4.0.0. Re-measured on a freshly booted, idle machine over the same 240 cells (bench/results/latency-model-2026-09-23-arz-7731027.json), every structure's id(key) reads 9–19 % faster at the median, and at 100 000 keys StringIndex is faster than DictIndex at block 32 on six corpora of thirteen rather than three. On the published sweep, which neither fit saw, the model now picks the faster of DictIndex and StringIndex in 29 of 30 cells, never more than 1.02× slower (was 27, 1.18×), and the fastest DictIndex block in 21 (was 15). Held out a corpus at a time, the ordered id(key) pick is the fastest in 19 of 30 cells and within 5 % of it in 23, never more than 1.11× slower. The 1.75× the 4.0.0 notes put down to BDX3 — numeric at 100 000 keys — belonged to the loaded run: scored on the new cells, the old constants do no worse than 1.11× either. bench/latency_model.py fit reports the within-5 % count beside the exact one, since 5 % is about what placement in physical memory moves a single-threaded probe on this machine and the ordered candidates are often closer than that. The run also times HashedDictIndex, closed and at eight fingerprint bits; plan still does not price it, because a new Kind breaks an exhaustive match and waits for a major release.

Documentation

• The plan examples in docs/usage.md still showed StringIndex at 2 744 604 bytes on the word list, the estimate from before 4.0.1 priced the transducer off the run draw; re-run with the new constants, it is 2 882 400.
• The word-list ladder and both rsmarisa tables are re-measured on an idle machine, every run started only once a readiness check passed. The ladder (bench/results/dictbench-2026-09-23-arz-fdc28bc.txt) predated the microblock offsets and the three commits to the dictionary's compare path that 4.0.0 shipped: its sizes are 0.3–1.6 % lower now and every id row 4–8 %, one to five points more than the StringIndex control moved, and the paragraph under it is recounted — heads and arrays go from 0.44 bytes a key at 32 to 0.06 at 1024, no sample has been stored since BDX3, a block of 32 scans 16 entries rather than 31, and 512 stores 2.52 bytes a key rather than 2.81. The word-list rsmarisa table (bench/results/rsmarisa-2026-09-23-arz-fdc28bc.txt) moved little — its rsmarisa rows 1–3 %, DictIndex 3–5 % — but its caption described a protocol the harness does not run, and now names the one it does. The eleven-corpus table (bench/results/rsmarisa-corpora-2026-09-23-arz-fdc28bc.txt) did move: the 2026-09-19 run was taken while other benchmarks shared the machine, and its rsmarisa column, whose code has not changed, read 21–44 % slower than it does now. Its finding that the largest block is the fastest on ten corpora of eleven does not survive — the fastest block is 64 on four, 256 on five and 512 on two, and within 10 % of the others on eight — while DictIndex is still smaller than rsmarisa on all eleven and answers 1.5–3.7× faster on ten.
• The read-scaling table is re-measured the same way (bench/results/readscale-2026-09-23-arz-fdc28bc.txt); its 2026-09-19 run shared the machine with other benchmarks too. Its one-thread cells were inflated, so its speedups were: the StringIndex it said scaled best, super-linearly at 2.09× on two threads, now reads 2.00× and scales like DictIndex (1.95×); eight cores give 5.5–7.8× rather than 5.7–8.1×, and CompactHashIndex saturates at 413 M lookups a second rather than 385.

[4.1.0] — 2026-09-22

Added

• HashedDictIndex: a DictIndex whose id is a hash. A dictionary answers id by searching — the block samples, one block's restarts, one microblock's scan — and that search is the column the frontier campaign lost: XCDAT 1.2–5.1× faster at a million keys, and 1.1–1.8× at ten million on five of the six corpora there. HashedDictIndex::from_dict(dict, fingerprint_bits) keeps the dictionary whole and adds a minimal perfect hash over the keys' 64-bit hashes and a bit-packed table holding each key's rank at its slot, ⌈log2 n⌉ + fingerprint_bits bits wide. id is two hashes of the key and two reads and never touches the dictionary; key(id), prefix, range and iteration go to dict(), whose ids are the same ranks. On the campaign's protocol, beside Dict 256 and XCDAT 15 as controls that read within 4.9 % of the published campaign on all 38 of their cells, it is faster than XCDAT and smaller on all nineteen corpora: id_unchecked 3.9–8.9× faster at 1.39–3.16× less space, id at eight fingerprint bits 3.1–7.6× and 1.17–2.77×, and it builds before XCDAT on every one. Against its own dictionary's search it is 7.6–20.5× faster closed and 6.1–17.0× at eight bits, for 2.62 bytes a key on the 480 k-word dictionary, 2.74 at a million keys and 3.24 at ten million.

The width is chosen once, at build, and it decides the contract. From one fingerprint bit up id answers a stranger as present at 2^-fingerprint_bits, CompactHashIndex's rate; at zero bits id is the dictionary's exact search, and the hash is id_unchecked alone — a member's rank, and some rank below n for anything else. Keys sharing a 64-bit hash are told apart by the full second hash in a side table, so a member's rank is exact at every width. The format is BHD1: a 48-byte header, the dictionary's BDX3 blob byte for byte — checked by DictIndex's own loader — then the perfect hash, the rank table and the side table. load_mmap borrows the dictionary and the rank table, and a crafted blob answers wrong ranks, never ranks past the end. Python has the same class, HashedDictIndex.from_dict(dict, fingerprint_bits=8), with ids_of, in, indexing and .dict, and the batch forms DictIndex has — ids_of_bytes, ids_into and the Arrow pair ids_of_arrow and ids_into_arrow — writing uint64 ids and MISSING_ID for a miss. The C ABI opens BHD1 blobs and builds the index at eight bits as LEXINDEX_KIND_HASHED_DICT, a sixth kind under the same ABI version: a caller compiled against the older header meets it only for a blob its library refused. plan does not price it yet, and Overlay does not take it: its ids are ranks. - The command line in the wheel. plan, build, inspect and dump were reachable only through cargo install lexindex, so a pip install could price a corpus from Python code but not from a shell. The wheel now carries the binary's own program — src/cli.rs, compiled into both — as a lexindex command and as python -m lexindex, so the subcommands, their output and their exit statuses are the same whichever way lexindex was installed: pip install lexindex && lexindex plan keys.txt. Ctrl-C ends a run as it ends the binary's, rather than waiting for the Rust code to return. - A Polars plugin, in polars/. lexindex-polars is a package of its own — its own crate, wheel, version and changelog — carrying four expressions over an index blob named by path: pl.col("track").lexindex.id("tracks.bdx"), and id_unchecked, contains and key beside it. They are plugin expressions rather than a map_batches callback, so polars runs them in its own threads, inside a lazy plan and under the streaming engine, with no GIL; one expression serves all six index kinds, because the blob says which kind it is. Nothing about the lexindex crate or wheel changes: polars' plugin ABI moves on polars' cadence, which is not this library's, so it stays out of the dependency tree and ships separately. - A fuzz target for BHD1. parse_hashed_dict loads arbitrary bytes as a HashedDictIndex and holds every rank id, id_unchecked and ids_of answer below the key count; it runs in CI's fuzz matrix beside parse_dict, and tests/data/golden-4.1.0-hashed.bhd pins the format by its bytes and seeds the corpus. - Pull requests are fuzzed. One that touches src/, fuzz/ or the seeds runs every libFuzzer target, ten minutes between them, under ClusterFuzzLite — OSS-Fuzz's build and fuzzing images, on the repository's own runners — before it is merged; the daily campaign still fuzzes main. .clusterfuzzlite/ is the build an OSS-Fuzz project would use, and it builds all ten targets with the instrumentation intact: 2 448 counters in parse_compact, where an LTO build keeps a few hundred. - The C ABI under the sanitizers. The weekly AddressSanitizer run compiled tests/capi.rs to nothing, since it needs the capi feature, and Miri could not run it at all: the test calls the C functions through copies of the header's #[repr(C)] enums, which Miri holds to be other types than the callee's and stops at the first call. Both run it every week now, Miri through the module's own types, and both pass. - bench/frontier/run.sh --only PATTERN runs the campaign's processes whose label matches, into an artifact named frontier-<scale>-subset-*; frontier_lex takes hashed0, hashed8 and hashed16, and bench/tables.py renders a campaign's HashedDictIndex table with view=hashed.

Fixed

• bench/frontier/run.sh refused to run at 4.0.1: it builds frontier_lex with --locked, and that crate's lock file still named lexindex 4.0.0 — as bench/mphf_vs's did. CI now fails when a tracked Cargo.lock names another version of lexindex than Cargo.toml does, so a release commit that misses one is red before it is tagged.
• The release preflight checks the tag's own date. It compared CITATION.cff's date-released with the CHANGELOG heading and neither with the day of the tag, so a release prepared on one day and tagged on another passed — 4.0.0 was re-dated twice by hand. It now reads the annotated tag's date, in the tagger's zone, and refuses a mismatch or a lightweight tag before anything is built.

Documentation

• docs/api.md rendered four of the public names. Overlay (public since 0.12), DictIndex (2.0), plan (3.0), inspect and the types they return were never on it; every name in __all__ is now, and a test fails when one is not.
• CI fails when a page cites a bench/results file that is not committed. A citation of an untracked artifact is a 404 from the day it is pushed; one reached a commit this cycle and was caught by hand before the push.
• plan_file's page on docs.rs has linked a private constant since 4.0.0, a dead link there, and HashedDictIndex's contract — what fingerprint_bits decides — sat in a private module's documentation, which docs.rs does not render. Both are on the public pages now, and CI denies rustdoc's warnings on the build docs.rs makes, where a link to a private item is reported.
• SECURITY.md listed the fuzzed formats as of 1.1, without MPH3, the perfect hash's format since 4.0.0; it names MPH3 and BHD1 now. Its unsafe inventory is recounted from the source — 15 unsafe fns where it said 13, 41 blocks where it said 38, eleven in the Python bindings where it said nine, HashedDictIndex's memory maps and the phrase trie's unchecked walk among the difference — and names what it left out: the four unsafe impls of Send and Sync, the unsafe trait behind zeroed huge-page tables, and the C ABI's five internal unsafe fns.

[4.0.1] — 2026-09-22

Fixed

• plan ranked a dense id space wrong, by four orders of magnitude. The StringIndex estimate was the bytes an fst spends per trie node, read off the hash draw and scaled by the corpus's trie nodes. An fst does not merge by trie node — it merges equal right-languages, and how far it merges is a property of the density of the whole key set, which a hash draw of a hundred thousand keys destroys by construction. On a million decimal ids the estimate read 2 281 924 bytes where the blob weighs 301, and the ladder handed back a DictIndex three thousand times larger than the index the caller should have built.

The rate is now read off the run draw — consecutive keys of the sorted corpus, whose neighbours are the corpus's own, so the merges that happen in the corpus happen in the draw — and carried flat per key. Scored against the built blob on 19 corpora of a quarter million to nineteen million keys, the estimate lands within 1.1 % median, 6.7 % at the 90th percentile and 11.7 % at worst, against 5.2 / 36.0 / 53.1 for what it replaced, and the ranking is right on every one of the 19.

A dense id space is still the family it cannot price: ten million decimal ids merge to 356 bytes whole and no draw of a hundred thousand of them can see it, so the number reads about a hundredfold high. It is two orders under every other index either way, so the ranking holds and Plan::thin is set — a byte count under that flag is not one to quote.

[4.0.0] — 2026-09-21

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 33 % 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.11 → 9.28, dna 7.62 → 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 3 % 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.2 % off the word list at one end and 52.4 % 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.

[3.0.0] — 2026-09-13

Changed

• Breaking: DictIndex blocks put their headers first, and the format is BDX2. A block held each entry's header immediately before its own suffix; it now holds every header, one byte each, and then every suffix. The same bytes in a different order — a blob is the same length to the byte — but a scan rules most entries out by the shared-prefix length alone, which lives in the header, and 127 of those are two cache lines where they used to be spread over the seven of a 128-key block. On the dictionary id fell 9 % at 128 keys a block and 15 % at 256 (384 against 437 ns, 487 against 593), 2–4 % at 32 and 64, with key_into unchanged and every size identical. Measured A-B-A against a StringIndex control that this change cannot touch. A BDX1 blob is refused by name — the message says that the fix is to rebuild — so this is a format break, and an index on disk has to be built again. The Python comparison table has not been re-run for it; see the note on that table's reproducibility in docs/benchmarks.md.

• DictIndex trains a symbol table per shard of 65 536 keys. One table for the whole index is a compromise between neighbourhoods that share nothing — the suffixes of a million paths under /usr/share and of a million under /home are different languages, and one sampled budget had to cover both. A shard is a whole number of blocks, each shard's table is trained on 10 000 pieces from that shard alone, the tables are trained in parallel, and the blob carries them in order after the header, which names the shard in blocks. A lookup picks its table from the block number it already has: one division, and no memory access it did not already make. paths at a million keys goes 15.923 → 14.673 bytes a key, titles-ru 12.110 → 11.364, idents 7.270 → 6.658, titles-en at ten million 7.886 → 7.652 and the dictionary 2.852 → 2.838; what rises is domains (5.008 → 5.066) and a word.word grid (2.47 → 2.50), corpora whose shards are all one language and now pay for a table each. The ladder over 32 / 64 / 128 / 256 / 512 / 1024 keys a block becomes 3.23 / 3.03 / 2.90 / 2.84 / 2.81 / 2.79 bytes a key. Training is linear in the sample, so the shard and the budget trade against each other at a fixed build cost: over eight corpora, shards of 262 144 / 131 072 / 65 536 / 32 768 / 16 384 keys with the budget halving alongside sit 1.5 / 0.8 / 0.4 / 0.4 / 0.9 % above the smallest size each corpus reaches, and 65 536 is the cheap end of that flat bottom. Lookups do not move: A-B-A-B in one process on three corpora gives id +0.5 / −2.0 / −2.4 % against a control moving −0.7 / −2.5 / −0.4 %. Building costs 17–23 % more, and holds one symbol-table trainer per training thread — about 2 MB each — so on sixteen threads the dictionary's in-memory build peaks 32.1 → 51.6 MB and its streamed build 12.7 → 27.1. The trainers are bounded by a 64 MB budget and never by n: one holds 2.6 MB over a million keys and 3.0 over ten million, so past 21 of them they queue instead of multiplying, and a machine with 128 cores keeps the peak a property of the work rather than of its core count — 380 MB of trainer state would otherwise sit under a ten-million-key build that holds 391. The bound is free where it can be measured: capping the same build at 8 trainers ran −0.4 % against uncapped on sixteen threads, and only a cap of 4 cost anything (+2.9 %). On one thread the same two builds peak at 31.2 and 15.3, the second paying only for the eight tables.

• DictIndex splits every block into microblocks, and the default block is 256. A block was both the unit a head and its arrays are shared over and the unit a lookup scans, so the only way to store less was to scan more: 2.83 bytes a key cost 460 ns of key_into, 2.75 cost 853 and the format's floor of 2.70 cost 3 190. A block is now split into microblocks of 32 keys — a block of 32 or fewer is one microblock — and the first key of each microblock past the block's own head is a restart, front-coded against the restart before it. A block's data is its restart run followed by each microblock's run, and a lookup walks the restarts to the one microblock that can hold the probe: block / micro + micro − 2 entries scanned, 38 at the default where a block of 256 scanned 255. At the same size key_into halves and id does not move — 2.819 B/key at 512 a block answers key_into in 244–246 ns and id in 392–399, against the one-level format's 2.827 at 128 in 460–464 and 393 — and the floor moves with it: 2.80 at 1024 a block costs 287–289 ns of key_into where one level's 2.752 at 256 cost 853–859. Measured A-B-A-B against a build of the previous format in a worktree, StringIndex the control at 340–353 ns throughout (bench/results/dict-onelevel-ab-2026-09-12-arz-386b2e6.txt) — that session reads about 25 % above the ladder below, control included, so the two are compared each within itself. The ladder over 32 / 64 / 128 / 256 / 512 / 1024 keys a block is now 3.24 / 3.04 / 2.92 / 2.85 / 2.82 / 2.80 bytes a key, id 252–254 / 272–284 / 285–288 / 298–302 / 316–322 / 344–347 ns and key_into 154–155 / 169–172 / 184–188 / 207 / 227–232 / 263–272 (two runs in opposite order, bench/results/dict-micro32-2026-09-12-arz-386b2e6.txt). The default block moves 32 → 256, in Rust and in Python, which takes the default index from 3.24 to 2.85 bytes a key — under the 2.955 marisa-trie stores at its most compact setting on this corpus — for id 298–302 ns against 252–254 and key_into 207 against 154–155. The symbol table now trains on runs of a constant length rather than whole blocks: the 20 000-piece budget was spent block by block, so a larger block bought fewer neighbourhoods — 157 at 128 keys a block, 19 at 1024 — and a table trained on 19 of them is a lottery, which is how paths at 1024 keys a block came to store 0.52 bytes a key more than it needed to, more than the same corpus at 256. A run is 256 consecutive keys, the default block, whatever block the caller picked. Over twelve corpora at three block sizes 28 of the 36 sizes fall and the worst rises 0.05; the dictionary at the default block is sampled identically either way, so its numbers do not move. Building costs 6 % more, from the walk over the keys the old rule skipped. The format is BDX2: the header carries the microblock size and a fourth offset width, the blob gains a packed start per microblock where a block has more than one, and a BDX1 blob is refused by name with a message that says the fix is to rebuild. A streamed build now holds (mean head length + 20) / block + 8 / micro bytes a key rather than (mean head length + 20) / block, which at the new default is 0.36 against the old default's 0.9.

• DictIndex packs its per-block offsets, and the index is 8 % smaller at the default block. Where each block's head ends and where its entries start were a u32 and a u64 a block — 12 of the 20 bytes a block cost — while both only ever grow by one block's worth at a time. Each is now one u64 base every 64 blocks and a delta of the width the corpus asks for: 10 and 13 bits on the dictionary at the default block. Per-block metadata falls 0.625 → 0.348 bytes a key at block 32 and 0.156 → 0.089 at 128, so the index goes 3.52 → 3.24 and 2.89 → 2.83, and 4.35 → 3.79 at 16 keys a block. A head and a block's data are both read as the span between two entries, and neighbours share a base and the word their deltas are cut from, so the pair costs what one entry costs: id does not move at any block size, and key_into pays 1.7 % at block 32, 5.5 % at 128 and 6.3 % at 256 — two instructions an entry walked, with branch misses and cache misses flat. Measured against the same ladder on the tree before it (bench/results/dict-offsets-2026-09-12-arz-6c699c0.txt); the corpus tables in docs/benchmarks.md are re-measured too. The 4 GiB ceiling on the block heads is gone with it — the base is a full word, so IndexError::Format("dict: the block heads exceed 4 GiB; use a larger block") can no longer happen. The BDX2 header grows three bytes for the two widths and the superblock shift, and the block starts move behind the block data: their width is only known once the encoding is done, which is what lets a streamed build write every section once and in order. No release wrote the layout this replaces, so nothing outside this tree ever held a blob in it.

• The crate tarball is the Rust crate and nothing else. It now carries the sources, the examples, the integration tests with their golden blobs, README.md and docs/usage.md (both pulled into the crate docs), and the licence, changelog, security policy and citation. CI, the docs site, the Python package, its build files and its examples, the benchmark tooling and its 67 measurement logs stay in the repository: 169 → 71 files, and 712 KB of logs leave every cargo install and docs.rs build.

Added

• A command line: lexindex plan | build | inspect. Choosing between five indexes no longer needs a Rust file. lexindex plan keys.txt --reverse --prefix prints the ladder Plan's own Display writes — every candidate the needs allow, cheapest first, with the DictIndex block it priced and the "build both" / "too thin to quote" caveats. lexindex build keys.txt out.bin asks the same planner and builds the winner, writing the ladder it chose from to stderr; --index dict | string | compact | closed | perfect names one instead, and --block takes 1..=1024 or fast / balanced / compact. lexindex inspect out.bin prints the header one field per line, an overlay's base included, in about a millisecond whatever the blob weighs. A keys file is one key per line, UTF-8, in any order, - for standard input; an empty line is skipped and the count reported on stderr, and invalid UTF-8 is an error naming the line rather than a replacement character — the library takes &str, and an index built from lossy bytes would hold keys the file does not. The exit code is 0, 2 for a command line that does not parse, 1 for work that fails. No new dependency and no new public API: the argument parsing is hand-rolled in the binary, and the binary computes no number of its own — on the 479 823-word system dictionary the five build runs report 0.26 / 1.26 / 2.84 / 5.95 / 10.90 bytes a key, the figures the tables already carry, and plan puts them at 0.26 / 1.26 / 2.78 / 5.55 / 10.90 without building any of them (−0.7 / −0.1 / −2.1 / −6.7 / −0.02 %). --index auto costs a plan: over that dictionary it takes 287.6–287.9 ms against 116.9–117.4 for --index dict, the difference being the planner's 100 000-key sample, which builds all five candidates whatever the needs narrowed the ranking to (hyperfine, 5 runs each, A-B-A-B, σ ≤ 1.7 ms). Below 100 000 keys the plan builds the real indexes rather than modelling them, so --index auto there builds the corpus twice and naming the index is the way not to.

• An id can be retired without a membership test. Overlay::retire_id(id) — retire_id from Python — sets exactly the tombstone remove sets, with no key lookup in front of it. Over a CompactHashIndex base that lookup is the one write a false positive costs something on: a string the base has never seen can match a live id, and removing it retires that id along with the real key behind it. An application that stores the id it was handed when the key was added now has a removal nothing can mislead. An id at or above id_space(), or one already retired, is false and changes nothing. remove became that method with a lookup in front, so the tombstone and the live count are maintained in one place rather than two.

• plan prices every index before one is built. Five indexes with five corpus-specific size curves is a choice nobody should have to make from a README table, and the spread between them on one corpus is larger than the spread of any one of them across corpora. lexindex::plan(&keys, needs) sorts the keys once, measures what the formats are actually paid in — n, the mean key length, the LCP structure, the trie-node count — and returns a Plan that ranks every index the caller's Needs allow, with a Display that prints the ladder and says why each line is where it is. One build of a 100 000-key sample supplies the three numbers no statistic gives: what the symbol table squeezes a suffix into, the bytes an fst spends per trie node and the bits the perfect hash spends per key. Scored against the built blob on 23 corpora of half a million to ten million keys, DictIndex lands within 1.4 % median, 4.5 % at the 90th percentile and 5.1 % at worst, StringIndex within 3.5 / 9.6 / 30.3 — an fst merges equal suffixes, and how much it merges is a property of the whole key set rather than of a sample of it. Below the sample size nothing is modelled: the plan builds the candidates and reports what they weigh. Two candidates inside 1.3× of each other are reported as a tie worth building both ways, and a corpus whose mean suffix is under two bytes — ten million numbers, where the sampled ratio is 19 % off — is flagged rather than quoted. lexindex.plan(keys, prefix=True) from Python returns the same ranking as a dict of plain types, with the paragraph the Rust Plan prints under text.

• A block size can be named instead of measured out. DictProfile::Fast, Balanced and Compact — block="fast" | "balanced" | "compact" from Python, in the same argument as the number, so there is no second setting to contradict the first — stand for 32, 256 and 1024 keys a block: 3.23 / 2.84 / 2.79 bytes a key, id in 252–254 / 298–302 / 344–347 ns and key_into in 154–155 / 207 / 263–272. The names are what the curve is picked over, so a later release can move a name to a better point on it; block= still takes any number in 1..=1024.

• An Arrow slice no longer copies the whole column. A sliced Arrow array shares its parent's buffers, and ids_of_arrow copied them whole: 1 000 keys taken out of a 480 000-key column cost 9.4× the same keys in an array of their own, nearly all of it a 6.4 MB memcpy to read 13 KB. Only the offsets and the bytes a chunk names are copied now, and the validity bitmap is trimmed by whole bytes — the slice costs 1.2×, and the unsliced path is unchanged, still handing the buffer over whole in one memcpy. This also settles the Arrow C Data Interface question the 2.0 review left open: the copy is 0.6 % of ids_of_arrow on DictIndex and 5.8 % on CompactHashIndex, the fastest index there is, so a zero-copy PyCapsule path would buy that much for ~200 lines of Arrow FFI or a new dependency. It is not being built.

• bench/reproduce.sh, one command from a checkout to the tables the README cites. It refuses a dirty tree, because a number attributed to a commit whose code was not the one measured is not a number; pins the three competitor versions; verifies all 38 corpus files against their hashes; prints the machine; and ends by comparing the run's Python call floor against the published one, which is the only row in that table nothing in this library can move. Running it found two things it was written to find: the probe set was drawn from a set of words, whose iteration order changes every process, so no two runs of bench/compare.py had ever measured the same probes (now sorted before the seeded shuffle, as bench/corpora.py already did); and the same commit on the same machine six hours apart puts that floor at 49 ns and at 110 ns, which is the warning the last step now prints instead of letting the difference land silently in every row.

• Error bars for the lookup tables, and the counters behind them. Every timed number this project publishes is the minimum of a few alternated passes, which is the right estimator for a laptop and carries no width — so a frontier claim rested on an ordering nobody had bounded. Thirty independent passes a structure with a bootstrap interval around the median now say it: past 150 ns the p5–p95 band is 2.4–9.5 % and the minimum is within 1–4 % of the median, but under 50 ns the band is 45 % and the minimum sits 25–29 % low. The probe set turns out to be part of the working set — ClosedHashIndex doubles between 100 000 and 400 000 probes a pass while DictIndex 128 moves 7 % — and perf names the cause: the instruction count a lookup does not change, the cycle count does, and the data TLB starts missing past 200 000 probes. The ordering survives all three probe counts with disjoint intervals, which is what the tables claim; the absolute nanoseconds belong to the harness as much as to the structure. DictIndex 128's cost against 32 is now attributed too: 3226 instructions a lookup against 1671, with the same LLC misses — a block scan is linear in the block, so a bigger cache will not close it.

• Read scaling across threads, measured. Every index is immutable once built, so one load_mmap is shared by reference and answers from every core with no lock, no copy and no per-thread instance — an unclaimed property until now, because nobody had run the ladder. On ten million Wikipedia titles, eight cores give 6.7–7.9× and sixteen hardware threads 8.7–13.2× (the run this entry was written from; the ladder was measured again for the published table, which reads 6.7–8.1× and 9.4–13.5× — docs/benchmarks.md names that artifact), the SMT row being worth having because a point lookup is a chain of dependent loads and a second thread fills the stalls. StringIndex scales best (13.2×) for the same reason it is slowest on one thread: a transducer walk is nothing but dependent misses, and two cores have twice the memory-level parallelism one has. CompactHashIndex saturates first, at 8.7×, having run out of something other than cores — 268 M lookups a second over an index that fits in L3.

• What a cold mapping costs, measured for the first time. Every size this project publishes is the blob on disk, and the number that decides whether an index fits a container limit is the resident set. local/coldmmap drops a file's page cache with posix_fadvise, maps it, and reads /proc/self/smaps after 1 000 random lookups and after a further million. Three findings, on ten million Wikipedia titles. load_mmap is lazy as documented — 0.01 to 0.26 bytes a key resident before the first query. The first thousand queries then leave 4.69 of DictIndex's 7.88 bytes a key resident while touching only 0.82, the 5.7× being the kernel's readahead, which is buying latency with memory and is the right default: MADV_RANDOM cuts the resident set to what is touched and costs 1.7× on the cold lookups and 3.2× on the warm ones, so load_mmap does not set it. And cold start is where the smallest structure wins outright — CompactHashIndex answers its first thousand queries at 6.3 µs against DictIndex's 51.5 and StringIndex's 89.3, and on UUID keys at 5.9 µs against 125.3 and 231.0. Past the warm-up every structure is fully resident, so the size table is also the steady-state RSS and only the warm-up distinguishes them.

• Nine structures over the whole corpus set, bench/sweep.py. The first measurement this project has that can answer where each structure is smallest rather than how big it is on one word list — three DictIndex block sizes against three marisa-trie configurations, plus the keyless indexes and StringIndex, on every corpus at every size, and the same question in Rust against rsmarisa's three cache levels. What it shows is a frontier and not a crown. marisa-trie is the smallest key-storing structure on nine of the eleven million-key corpora, and the margin follows how much the keys share: 1.72× on filesystem paths, 1.49× on Russian Wikipedia titles, and within 4 % on DNA k-mers and domains. DictIndex is smaller where the keys share nothing — 1.32× on opaque base64url ids, 1.62× on UUIDs — which is the same reason it is smaller on English words, a corpus at the favourable end of that distribution rather than a typical one. Both facts are now in docs/benchmarks.md with the README's claim scoped to the corpus it was measured on.

The trade is not only size. DictIndex answers 1.8–2.9× faster than marisa's fastest configuration on ten of the eleven corpora — the eleventh is dense decimal ids, where marisa is 10 % ahead of the default block and 9 % behind a block of 128 — and builds 2.3–4.3× faster, so where marisa is 1.72× smaller on paths it is also 2.9× slower to answer and 4.3× slower to build. The two keyless indexes are flat at 0.26 and 1.26 bytes a key on all thirteen corpora at all three sizes, which makes them the only rows a reader can carry to their own keys without measuring. And StringIndex compiles ten million dense decimal ids into an FST of 356 bytes — a real number, and the ceiling of what shared structure can buy rather than a size claim.

• A pinned corpus set, bench/corpora.py. Every size this project has published is measured on one corpus, the Fedora word list, while bytes per key is a property of the keys at least as much as of the structure: StringIndex measures 0.68 on one corpus and 16.57 on another, and marisa-trie moves between 2.12 and 6.21 over the same span. Thirteen corpora now exist at 100 000 / 1 000 000 / 10 000 000 keys wherever the source has them — Wikipedia titles in three scripts, the URLs those titles form, Tranco domains, PyPI package names, this filesystem's paths, vendored Rust identifiers, the word list, and seeded UUIDs, dense decimal ids, opaque base64url ids and DNA 24-mers. The sizes are nested, so a difference between two of them is scale and not composition; the downloads are pinned to a dated dump or a permanent list id rather than to latest; and the SHA-256 of every download and every derived file is in bench/corpora.json, which python bench/corpora.py verify checks. The corpora are gitignored — 4.6 GB — and the manifest is what makes them checkable anyway. No benchmark is on the set yet.

• common_prefix and longest_prefix on both ordered indexes, in Rust and Python: every key that is a prefix of the query, shortest first, and the longest of them. This is the reverse of prefix and the query a longest-match tokeniser runs — a vocabulary and a position in a sentence give the entries that start there. It was the one operation marisa-trie, dawg2 and datrie all had and lexindex did not, which the comparison tables now carry as a column of its own. StringIndex answers it in a single walk down the transducer, O(query bytes) whatever the index holds — the fastest longest_prefix in the comparison at 422 ns, against datrie's 482, dawg2's 810 and marisa-trie's 965, and within 3 % of datrie on common_prefix (726 against 706) at a fifth of its bytes. DictIndex has no such walk and pays one order lookup per character boundary — 2 157 ns at 32 per block — except on longest_prefix, which stops at the first hit and so comes in under marisa at 863 ns. The documentation says which is which rather than implying they cost the same.

• DictIndex::build_to_file — the constructor for a corpus that does not fit in memory, and DictIndex.build_to_file(items, path, block=32) in Python. The keys arrive in any order, are sorted in runs spilled beside the output and merged back, and the block data goes into the file as it is encoded. The bytes are exactly what build followed by save would have written, which the tests assert at four block sizes over both the spilled and the single-run path. Measured over 479 823 words streamed from a file: peak RSS 32.1 → 12.7 MiB for the same 3.52 bytes per key on disk, at about 19 % more build time. What is still held is the block heads and the three per-block arrays — roughly (mean head length + 20) / block bytes per key, so a larger block holds less as well as storing less. The external sort it shares with StringIndex moved to its own module.

• DictIndex::build_sorted and build_sorted_with_block, for keys already in ascending byte order — a sorted file, a database cursor, the output of an external sort. Adjacent duplicates are dropped exactly as build drops them after sorting, so for the same key set the two produce byte-identical blobs. It is not the faster of the two and does not pretend to be: build's sort is pattern-defeating, recognises an ascending run and returns almost at once (31.9 against 32.1 ms over 479 823 words). What it buys is the check — an unsorted input returns an error instead of an index whose every binary search is wrong, which is what StringIndex::build_sorted has given since 0.11 and DictIndex did not.

Changed

• A batched DictIndex lookup is no longer a loop. ids_of — and with it ids_of_bytes and ids_of_arrow, the Python and Arrow batch paths — ran id once per key, and a single id is a chain of dependent loads: the binary search over the block samples, then the block's head, then its data. Past the last-level cache each one waits on the last. Thirty-two lookups now advance in lockstep — every lane takes one step of its binary search before any lane takes its second, and the blocks they land on are prefetched whole before any lane is scanned. On real word bigrams, half the probes members, shuffled, against a loop of id in the same process: 861 → 535 ns a key at 10 M keys and 32 per block (1.61×), 771 → 645 at 128 per block, 377 → 306 at 1 M, and 277 → 281 at 200 k — where the index is 0.6 MB, nothing stalls, and there is nothing to hide. Prefetching the heads as well was tried and measured 7 % slower; it is not in the code.

• DictIndex::keys_of walks a block once for the ids that ascend through it. It called key per id, and key re-enters the block at its head and decodes forward to the entry, so a run of ids inside one block decoded the same prefix chain again for every one of them. A cursor now stays open while the next id is in the same block and above the current one — which is exactly the shape prefix_id_range hands it — and falls back to key for anything else, so an arbitrary order is answered as before and a test pins both against key over shuffled, reversed and repeated ids. Measured over 20 000 three-byte prefixes on 479 823 words, 763 matches each: a prefix's keys through prefix_id_range + keys_of go 135 595 → 71 915 ns at 32 per block and 218 542 → 70 566 at

• That makes the id range the fastest way to enumerate a prefix here, ahead of prefix itself (103 716 ns, and it decodes an id for every match) and of marisa-trie (93 355) — the reverse of what docs/benchmarks.md recorded, which is corrected with the new artifact behind it. The columns the change cannot touch moved by up to 8 % between the two runs, the extension having been rebuilt in between, so the 1.9× and 3.1× are not that.

• A DictIndex encodes its blocks on every core. Once the symbol table is fixed a block depends on nothing outside itself, so contiguous ranges of blocks go to their own threads (std::thread::scope, no new dependency) and the parts are concatenated in order. The bytes do not depend on how many threads ran, which a test pins at 1/2/3/5/8/64 threads against the single-threaded blob — and the streaming builder checks from the other side, since its own encoding pass is serial. Measured on this 8-core machine, one core against sixteen: 126.2 → 75.2 ms over 909 776 real file paths and 34.0 → 24.6 ms over 479 823 words. The threads take a &[&str] view rather than the caller's &[S], which would have meant adding S: Sync to a signature that never asked for it; the view costs 16 bytes a key while the encoding runs, which on the paths corpus is less than the doubling the single data buffer did (41.6 against 42.4 MiB allocated) and on the shorter words costs 12.5 bytes a key.

• Building a DictIndex no longer copies every key. build_with_block collected items.into_iter().map(|s| s.as_ref().to_owned()), one owned String per key, before sorting. Sorting the caller's items through AsRef instead costs nothing and removes the copy, because the keys are copied into the blocks anyway. Measured with a counting allocator over 479 823 words, from a &[String] — which is what the Python constructor and every build(&keys) call pass: the build allocates 42.6 → 17.3 bytes per key and takes 54.0 → 32.1 ms. From an owned Vec<String> moved in, the allocation was never doubled (Vec::into_iter().map(…).collect() reuses the buffer in place and frees each source key as it copies) and the time goes 47.6 → 39.8 ms.

• The comparison table carries a lookup-latency column. Bytes per key on their own read as though the smallest structure were the best one. bench/compare.py now times one exact lookup per library over 100 000 probes, half of them plausible strangers, shuffled — every structure taking one pass per round so that none is measured with the caches still warm from its own build, and all of them resident while each one runs. Two costs are named instead of assumed: the Python call boundary is 49 ns, and .get on a miss is each library's own miss path rather than a try/except around __getitem__ — timed apart, a miss costs 0.85–0.91× a hit everywhere, while that wrapper written out by hand costs 1.61×, which matters because half the probes are misses. On this corpus the four keyless rows answer in 92–100 ns against a builtin dict's 260, and DictIndex at 128 per block is smaller and faster than every marisa-trie setting measured (2.89 B/key and 389 ns against 2.96–3.07 and 449–490).

• marisa-trie is benchmarked as a curve, not a point, and rsmarisa joins the table. Every marisa number this project published came from the default configuration, while marisa's own documentation says the right setting depends on the data — an open invitation to the objection that the baseline was untuned. Measured over the whole space on the same words: num_tries 1/2/3/4/5/8/16/32 gives 3.380/2.997/2.978/2.977/2.977/2.980/2.986/2.998, flat from three and worse past eight; cache_size TINY…HUGE gives 2.957/2.964/2.978/3.008/3.066; order and binary do not move it. Its best is 2.955, so DictIndex at 128 per block leads by 2.2 %, not the 3.0 % against the default, and the comparison tables carry three marisa rows.

rsmarisa — a pure-Rust port of marisa-trie, BSD-2-Clause, first published 2026-01-26 — is in the Rust table for the first time. docs/benchmarks.md had said 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 as well, since DictIndex shipped at 3.52 B/key in 2.0 and was never added to that table. Measured: DictIndex at 128 per block dominates rsmarisa at its most compact setting outright — 2.894 B/key against 3.003, 435 ns against 445 on members, 442 against 473 on misses, and 38 ms against 174 to build — while at 32 per block it is the fastest structure there (323 ns) and larger than either rsmarisa setting. A frontier, not a crown.

• The hash quality battery runs in CI. It was #[ignore]d behind bench-mphf and CI only ran clippy on that feature, so the battery compiled and never executed and the committed artifact was a hand-run. It is a weekly job now. Bit independence covered the slot hash at one key length while avalanche covered both hashes at five, and the notes claimed the wider scope for both; it now runs both hashes over 8/16/24/80-byte keys, sampling at most 128 input bits per pair so the cost stays flat in key length. The cell count goes 346 112 → 1 894 400, so the bound moves 6.0 → 6.5 (PARI/GP: a family-wise 10⁻³ over that many wants 6.211; 6.5 leaves 1.5 × 10⁻⁴). Worst observed: avalanche 4.49 unchanged, bit independence 4.23 → 4.54 over seven times the cells.

• The queries 2.1 added are fuzzed, and BDX1 is checked on a big-endian and a 32-bit target. The fuzz shim asked for id, lower_bound, key and a walk; prefix_id_range, prefix_count, prefix, range, range_count, successor, predecessor and iter_after were untouched by any target. All of them are held to bounds on malformed input now, and on a blob that passed every check the whole ordered surface is cross-checked against a linear walk. The weekly Miri jobs gained dict_index::: the format stores each block head's first eight bytes as a big-endian word inside an otherwise little-endian blob, which is exactly what the s390x job exists to catch, and it had never run there. Both targets pass — coverage for what ships, not a fix.

Fixed

• Documentation claims a reader could have checked against the table beside them. "StringIndex is the only structure that answers fuzzy and range queries at all" — DictIndex has answered range and prefix since 2.1, and only fuzzy and subsequence need the automaton; the capability matrix said it structurally too, merging prefix into one row with fuzzy so DictIndex read as having no prefix four lines above the paragraph saying it does. "marisa-trie remains the pick for exact membership and ordering and the smallest such index" — the table fifteen lines above it disagrees. SECURITY.md counted seven unsafe fns and nine unsafe blocks; it is nine and eleven, "on every index" was never right since ClosedHashIndex has nothing to map, and the fuzz inventory listed eight targets where there are nine. And nothing said why Overlay has no DictIndex or ClosedHashIndex base, which matters now that the smallest row in the table is the one that cannot take an edit: an addition takes the id after the base's last, which is not a rank, and a closed vocabulary has no membership to ask.

• The benchmark artifacts behind the tables are taken on a clean tree. The one the README cited recorded commit: 00857e2-dirty and lexindex: 2.0.0 while backing a 2.1.0 table, the hash battery's was c597099-dirty, and docs/benchmarks.md pointed at an artifact from 2026-09-09 that predated the rows above it. One run, one file, both pages citing it.

[2.1.0] — 2026-09-11

Added

• DictIndex answers prefix and range queries, in Rust and Python: prefix, prefix_iter, prefix_id_range, prefix_count, range, range_iter, range_count, iter_after, successor, predecessor — the ordered surface StringIndex already had, with the same names and the same answers (a test cross-checks the two index types on every one of them). The type had been documented as having none of this because it has no automaton, which conflated two things: a fuzzy query needs the automaton, a prefix does not. Keys sharing a prefix are adjacent in rank, so a prefix is one contiguous id range, and prefix_id_range finds it with two lower_bounds.

That makes counting a different operation rather than a faster one: prefix_count is 351 ns where marisa-trie takes 127 657, because marisa has to enumerate all 763 matches of an average three-byte prefix to count them — its ids are not lexicographic ranks, so it has no arithmetic to do instead. At block=128, where the index stores 2.89 bytes per key against marisa's 2.98, it is also ahead on autocomplete (2 435 ns for the first ten against 2 773) and level on full enumeration, while returning each match's rank as well.

• DictIndex::load_mmap and load_mmap_verified, in Rust and Python. The keys, the block data and the two offset arrays are held as the bytes they are serialised as, owned or mapped, an entry decoded where it is read; so a mapping borrows them and the load reads the header, the symbol table and the per-block samples — eight bytes a block, one byte per four keys at the default block. That last array is read rather than borrowed because two binary searches over it open every lookup and only <[u64]>::partition_point keeps those searches out of the branch predictor: it selects with hint::select_unpredictable, which needs an alignment a section of a blob does not have, and searching the bytes instead measured 110 ns against 26 for the pair. load_mmap skips the payload checksum and the walk over the arrays load makes, every access bounding what the arrays say instead — a crafted file answers wrong, never out of bounds — and load_mmap_verified runs both over the mapping. The BDX1 blob is unchanged, and reading a section where it lies rather than as a decoded array costs id 303 → 308 ns and key 200 → 209 on the dictionary at block = 32 (StringIndex control 342 → 337; min of five rounds alternated in one process, shuffled probes).

• A hash-quality battery under bench-mphf, and its committed output in bench/results/. Strict avalanche and bit independence over both hashes and five key lengths, the two-byte differential scan that caught the pre-2.0 collision family, and per-corpus distribution tables over ten key shapes — words, bigrams, a shared prefix, a shared suffix, a dense numeric tail, decimal integers, UUIDs, Cyrillic, DNA and paths. Everything reads as a standard-normal z against one bound of 6; a chi-square goes through Wilson–Hilferty rather than (x − k) / sqrt(2k), which understates the tail by two orders of magnitude at 255 degrees of freedom. Nothing in the battery is past the bound: the worst cell of 44 032 is 4.49, where the maximum of that many standard normals sits near 4.6, and the differential scan finds no double collision at all.

Fixed

• inspect is total on an overlay too. Its live-key count was base + additions − retired on numbers straight from the header, which a crafted blob could make wrap (or panic in a debug build); the counts are checked now, and a header whose counts do not add up is an IndexError, as is one claiming more additions than its section could hold. A base region that is itself an overlay — nothing this crate writes, since a base tag names an index — was parsed by the same routine without a bound, so a few megabytes of nested headers overflowed the stack; it is refused by name. The tombstone words an overlay's retired count comes from are read 64 KiB at a time rather than as one allocation the size of the section (125 MB over a billion ids), and the docs say what an overlay inspection reads. A parse_inspect fuzz target holds inspect to a return value on any bytes.

Changed

• DictIndex::key and key_into decode a handful of entries instead of the whole block. 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 form a strictly increasing staircase of that length, which a monotonic stack over the block's headers finds in the pass the walk already makes. Every header is still read — a header is what says where the next one begins — but the decode, the expensive half, runs on the staircase alone: 2.5 entries deep on average over the dictionary and a path list, 12 at the deepest with a block of 32 and 18 with a block of 1024, out of up to 1 023. key_into on the dictionary: 207 → 175 ns at the default block, 697 → 463 at 128 per block, 1 361 → 851 at 256 (id and lower_bound are untouched). The blob, the format and the API are unchanged, so an existing BDX1 file gets this by being read by the new version; past a staircase 32 deep the walk decodes every entry as before, which a block holding a chain like a, aa, aaa reaches and which is slower, not wrong.

• The weekly sanitizer workflow fuzzes parse_inspect too. The target shipped with the inspect fix but was never listed in the matrix, so the one entry point that reads a header of any of the five formats had no fuzz job of its own.

• Documentation: the DictIndex block size is measured across the curve rather than at three points — 4.35 bytes per key at 16 through 2.78 at 256, with id, key_into and lower_bound beside each — because 32 is the middle of that curve, not a limit, and build_with_block has always been the knob. At 128 the index stores 2.89 bytes per key, under the 2.98 marisa-trie takes on the same words, and unlike marisa it answers key(id) and lower_bound at all, a marisa id not being the lexicographic rank. The comparison tables carry both block sizes, and the older claim that beating marisa on an ordered index meant reimplementing marisa is scoped to the trie route it was written about. No code changed.

• Documentation: an OVL2 crosses 1.x → 2.0 only over a BIX4 base, since an overlay embeds its base verbatim (README, SECURITY.md, docs/design.md); the build_with_fingerprints entry below said the blob stays BMP6 — it is BMP7, like every 2.0 PerfectHashIndex blob; "three indexes" is five throughout; the DictIndex symbol table is called FSST-style, with a table format of its own, so that BDX1 is not mistaken for a reader or writer of the reference format; the perfect-hash comparison scopes its claim to its harness (lexindex takes pre-hashed keys); the build_to_file replay digest is called what it is, a 64-bit probabilistic check; DictIndex is 41 % below StringIndex, not "a third of" it (3.52 against 5.95); and the two links that pointed outside the docs tree (this file to docs/usage.md, docs/design.md to SECURITY.md) are absolute, so they resolve both on GitHub and on the docs site.

[2.0.0] — 2026-09-10

Changed

• Breaking: the key hash is replaced, and every hash blob written before 2.0 is refused by name. The per-word round of the 1.0 hash -- a 64-bit multiply and a rotate -- had a two-word collision family on ordinary text: a difference in the top bits of one word stays in the top bits of a 64-bit product, and the rotate dropped it into byte 3 of the next word, where that word's own difference cancelled it -- in both hashes, whatever their constants. Keys of 16 bytes or more differing at bytes 8i+7 and 8i+11 alone collided with probability 13–100 % (d↔t with e↔o; a case flip with e↔i; an ASCII/non-ASCII flip with a↔q, always), and CompactHashIndex and ClosedHashIndex merged such pairs into one id, silently: sering.dampening and sering.tamponing were one key, and 10⁹ generated word.word keys held nine such pairs. The round is now the full 64×64→128 product folded to 64 bits (lo ^ hi): a single-bit scan over every position pair of a 24-byte key finds no weak pair where the old round had 35, the same 10⁸ keys collide nowhere, the 10⁹ set builds to all 997 504 005 of its keys where the old hash lost nine, and the distribution gates (avalanche, low-bit χ², slot × fingerprint independence) read the same. Cost: the pair hash at 0.90–0.97× on 9–11-byte keys and 0.89× on 80-byte ones; in a lookup, process-alternated on the shuffled dictionary, CompactHashIndex::id moves by less than the harness's own layout noise — 71.4 → 74.3 ns with one build of the harness, 70.7 → 69.6 with another the same day, the hash's own latency 0.6 ns longer — batched ids_of 27.7 → 28.7 and 27.0 → 28.2 (a throughput path: 1.5 % more instructions), while the paths that compute one hash — ClosedHashIndex::id, id_unchecked — do not move. Magics move to BMP7 and BCH7 (BCL1 never shipped and keeps its name); BMP5, BMP6 and BCH6 join the refused list with a message naming lexindex < 2.0 and the rebuild, since a blob keyed on the old hash would answer wrong ids under the new one. BIX4 and OVL2 are untouched. Rebuilding from the keys is the migration. Found by the streaming builder's distinct-key count disagreeing with its input.
• The weekly libFuzzer job runs parse_closed as well, and every target now starts from the corpus the previous run left — an Actions cache per target — rather than from the seeds alone.

Added

• DictIndex (Python: DictIndex): an ordered dictionary with the key stored for every id — exact string ↔ rank both ways, lower_bound, in-order iteration, and no automata. The sorted keys front-coded in blocks of 32 (a build parameter, 1..=1024), the suffixes under a static symbol table — an in-crate FSST-style codec with a table format of its own, 300 lines, trained deterministically on the index's own suffixes — so a blob is a function of its keys. On the dictionary: 3.52 B/key against StringIndex's 5.95, id 300 ns against 345, key 197 against 505 (key_into decodes into a string the caller keeps); id compares the stored suffixes against the probe without decoding them. Blob BDX1, checked on load like the others and fuzzed after loading (parse_dict, in the weekly job); inspect names it; no feature needed, so an fst-only build has it too. bench/results/dict-2026-09-10-arz-64b0d35.txt.
• Arrow columns as batch input (Python): ids_of_arrow(column) and ids_into_arrow(column, out) on every index take an Arrow utf8/large_utf8 column — a pyarrow Array or ChunkedArray, a pandas ArrowDtype column, a polars Series — and read the keys straight from its offset and data buffers, so no Python string is built or borrowed per key. Packed like ids_of_bytes, MISSING_ID for a null (ClosedHashIndex raises on one). Through the buffer protocol, not the C Data Interface: no dependency, no unsafe, one copy of the buffers per call. On the shuffled dictionary, per key: CompactHashIndex 48 ns against 145 (ids_of) and 105 (ids_of_bytes), PerfectHashIndex 55 against 153 / 121, ClosedHashIndex 20 against 116 / 87, StringIndex 264 against 468 / 435. bench/results/arrow-2026-09-10-arz-b6ae463.txt.
• ClosedHashIndex (Python: ClosedHashIndex): the minimal perfect hash and nothing else, for a vocabulary known to be closed. id(key) -> u32, no Option -- a member's id, and for any other string some id in [0, n), which is what a perfect hash answers and all this index promises; ids_of, ids_of_bytes and ids_into alongside, and no contains, [] or in. The same hash as CompactHashIndex over the same keys, so the ids agree with its id_unchecked; without the fingerprint table the blob is 0.26 bytes per key on the 480 k-word dictionary, a fifth of the smallest fingerprinted index, and a lookup is one perfect-hash probe with no compare behind it: 40 ns against 68 for CompactHashIndex::id over the shuffled dictionary, batched ids_of 14 against 28 (local/closedbench, nine alternated rounds in one process, minimum). A new type rather than fingerprint_bits = 0, because a membership check that always says yes would be a signature that lies. Blob magic BCL1; inspect names it (BlobKind::ClosedHashIndex); a parse_closed fuzz target covers its framing. No load_mmap: the whole blob is the perfect hash, read into memory either way.
• CompactHashIndex::build_to_file and build_bits_to_file (Python: CompactHashIndex.build_to_file(items, path, fingerprint_bytes=1, *, fingerprint_bits=None)): the constructor for a corpus that does not fit in memory, written straight to a file. One pass hashes the keys to their 16-byte pairs, sorted in 256 MiB runs spilled beside the output and merged; the perfect hash is built from the merged file one first-level chunk at a time -- the first level's chunks are now pulled from a feed, a slice or a sequential reader, so the in-memory build runs the same placement and the file is byte for byte what build and save write -- and the fingerprints are written at their slots, in memory under 256 MiB of table and through range files past it. Measured at 100 M real-word pairs, one index per process: 302 MB peak against 8 834 MB for the same keys handed to build as a list (254 against 903 at 10 M); the streamed build took 52 s, 36 s of it generating the keys, against 10 s for the list build with its keys already made. At 10⁹ keys, where the list would need about 90 GB, the streamed build peaks at 0.94 GB — the perfect hash's own construction, 0.9 bytes per key, 0.6 of them the table being built and the keys its first level bumped — and takes ten minutes, six of them the generator. Returns the number of distinct keys; an iterable that raises aborts the build with the target untouched; nothing is left beside the output on any exit path.
• PerfectHashIndex::build_with_fingerprints, and build_to_file_with_fingerprints (Python: PerfectHashIndex(keys, fingerprints=True), build_to_file(..., fingerprints=True), has_fingerprints()): one more byte per key -- a fingerprint from the second hash, stored behind each block's offsets -- so a lookup of an absent key stops after one cache miss instead of two, the key itself never read, 255 times in 256. For a workload that is mostly misses: a stop list, a block list, a "seen before" check. Measured on the 480 k-word dictionary, one index per process, six alternations, minimum: an absent probe 166 → 74 ns, a member 163 → 171; batched ids_of over absent keys 70 → 47; the index 10.90 → 11.90 B/key. Ids are unchanged -- it is the same perfect hash -- and an Overlay compaction keeps the fingerprints (OverlayKeys::rebuild_like, with a default). The magic is BMP7 either way: the arena tag carries the bit, so the format needs no new name for it.
• Path forms of the strict loader, and checked forms of the mapping. StringIndex::load_untrusted is from_untrusted_bytes over a file (Python: StringIndex.load_untrusted, and Overlay.load_untrusted(path, base)). load_mmap_verified, on all three indexes, is load_mmap plus the payload checksum load makes -- one pass over the mapping at load, pages still shared, nothing copied -- for a file you wrote but did not carry yourself. load_mmap_untrusted, on StringIndex, runs the full validation over the mapping, for a stranger's file too large to copy. All three mapped forms carry load_mmap's obligation, and the two checked ones say why it weighs more for them: the check trusts what it saw once, so map a copy you own. docs/usage.md has the loader matrix. The stubs no longer say a mapped hash index is "validated as in from_bytes": its header is, its payload checksum is skipped by design.
• Overlay::compact_to_file(path) and compact_with_remap(). The first writes the rebuilt base straight to a file, streaming the live keys from where the base holds them -- StringIndex merges its ordered iterator with the sorted additions into build_sorted_to_file, PerfectHashIndex replays them into build_to_file -- so a base too large to hold twice can still be compacted; the second is compact plus the old-id → new-id table (u64::MAX for a retired id). Behind them, OverlayKeys::rebuild_to_file, with a default that materialises and rebuilds. Python: Overlay.compact_to_file(path) and compact_with_remap(), the table as native-endian uint64 bytes.
• bench/mphf_vs, a one-process harness that builds lexindex's perfect hash, ph 0.11's PHast and PHast+, and ptr_hash 2.1's three parameter sets over the same keys and looks them up in the same order. Its own crate outside the workspace, so the competitors are not dependencies of lexindex; behind it, Mphf is exported -- hidden, and only under the bench-mphf feature.
• Python ids_into(keys, out) on all three index types: ids_of_bytes written into a buffer the caller owns -- a numpy array, an array.array, a writable memoryview -- so a hot loop can reuse one allocation. A read-only, strided or wrongly typed buffer is a BufferError, one shorter than keys a ValueError.
• inspect(bytes) and inspect_file(path) (Python: inspect(path | bytes)): what a blob is, from its header alone -- the kind, the format, the key count, and the sizes a caller would otherwise have to load it to learn: the perfect hash's region, the key arena or fingerprint table, the side table, an overlay's additions and retired ids with its base inspected in turn. Over a path only the header and the footer are read, so an index of gigabytes inspects in microseconds; nothing is decoded or verified, and a blob from before 1.0 is an error naming the type to rebuild. BlobInfo, BlobKind and OverlayInfo are #[non_exhaustive], so a field can be added later without a major.
• StringIndex::build_to_file(items, path) (Python: StringIndex.build_to_file): build for a corpus that does not fit in memory. The keys come in any order; every 256 MiB of them is sorted and deduplicated in memory and spilled as one run beside the output, and the runs are merged -- one buffered reader each -- into build_sorted_to_file, so the blob is byte for byte what build then save writes. Peak memory is one run plus a 1 MiB buffer per run, whatever the key count; the transient disk is the distinct keys once, removed on every exit path. A run is an arena of key bytes and a span per key, not a String each, so the budget is what it says. Measured at 100 M real-word pairs: 414 MB peak against 11 985 MB for build over the same generator, 150 s against 211, blobs identical.

Removed

• IndexError::Serde. Nothing had constructed it since 1.0 replaced the epserde loader; a malformed perfect-hash blob is IndexError::Format. Removed outright rather than deprecated first: the key hash above already makes this release a major one.

Fixed

• StringIndex::from_untrusted_bytes costs the graph, not the language, and refuses a key that is not UTF-8. The 1.1.0 validator streamed every key to check its rank, so a blob packing an astronomical language into a few hundred bytes -- fst documents a billion strings in 896 -- was a denial of service against the one loader meant for a stranger's bytes; and it never looked at the bytes it streamed, so a transducer over non-UTF-8 keys, which fst permits and this crate's builder never writes, loaded and then answered None from key(id) for a live id. The validator now checks the transducer as a graph, in time proportional to its nodes and transitions: every reachable node once, transitions pointing strictly below their node and in increasing byte order, every accepted path valid UTF-8 -- the set of decoder states each node is reachable in is propagated parents-first, so a node shared between a character boundary and the inside of a character is caught -- and outputs that are ranks by construction: a final node carries none, each transition carries the count of keys its node spells before it, and the root's count must be the footer's length. On the 479 823-word dictionary it costs 22.9 ms against 0.7 ms for the owned load, down from 48.1 ms; on a 65 536-key transducer of a few dozen nodes it costs microseconds. The parse_string fuzz target now also asserts that key(rank) decodes back to the scanned key, and a property test builds raw fst maps over arbitrary bytes and requires the loader to accept exactly the UTF-8 ones.

• PerfectHashIndex::build_to_file could publish a file whose keys were not the source's. Pass two checked each replayed key by its slot hash and length only, so a source that replayed two keys sharing a 64-bit hash at equal length -- hash::COLLIDING_PAIR is such a pair -- in the other order, or one in place of the other, was accepted, and the file answered each with the other's id. Both passes now fold a second, independent 64-bit hash of every key into an ordered digest that is compared before the rename; a replay that differs in any key or any position is refused with IndexError::Build and the target is left untouched.

Changed

• The streamed build's merge workers share one handle per run: each reads its range of every run at its own offset (pread; seek_read on Windows), so the workers are as many as the ranges however many runs there are, where a budget of open readers had held them to three at 10^9 keys (60 runs). Byte-identical (blob digests at 10 M and 10^8 keys), same peak. 10^9 real-word pairs: merge 25–27 → 20 s (I/O-bound from there: 16 GB read and 16 GB written), the whole build 457 → 438 s; at 3·10^8 (18 runs, eight workers before as after) 3.5 s either way. bench/results/peak-compact-stream-pread-2026-09-10-arz-5678a0f.txt.
• Both hash builds compute their slots on every thread, and a fingerprint of a shipped width is one store: once the perfect hash is built, each thread overwrites its share of the sorted pairs' hashes with their slots — the order is the hash's, so a chunk's first pair continues the one before it exactly when the hashes are equal — and one pass then writes the fingerprints with the row a later key needs pulled into cache. write_fp at 8, 16 and 32 bits is a single store instead of a memcpy call whose length is only known at run time; that call was 2.4 ns of every key placed, in the streamed build's output and fingerprint pass as much as here. Byte-identical (blob digests at 10 M and 10^8 keys), same peak. 10 M real-word keys in memory: placement 102 → 16 + 41 ms, the whole build 580 → 526–530 ms. bench/results/peak-compact-listed-place-2026-09-10-arz-8cb6f73.txt.
• The streamed build places its fingerprints on every thread when they go to range files: the merge cuts as many ranges as the machine has threads, and the fingerprint pass then takes one merged segment per thread, staging its range records in a share of one allocation and writing them under each file's lock a stage at a time; a range record is the slot and the fingerprint at its own width, 5 bytes at the default instead of 12. The table that fits memory is still filled by one thread — below a byte, a row shares its byte with its neighbours. Byte-identical (blob digests at 10 M and 10^8 keys). At 10^9 real-word pairs the fingerprint pass takes 12 s against 46, the output 13.5 against 15, the whole build 457 s against 504 (six minutes of either being the example's key generator) at the same 943 MB peak; at 3·10^8 the pass takes 2.1 s against 10.3. bench/results/peak-compact-stream-fp-2026-09-10-arz-3ddad05.txt.
• The streamed build merges its runs on every thread: each run counts its pairs per top-bits bin as it is spilled; the merge cuts the hash space into ranges holding equal shares of the pairs, as many as threads, and merges each range out of every run into its own segment. The segments are read back as one stream decoded a buffer at a time rather than a record at a time, which is where the previous reader lost 5 ns a key behind the perfect hash's dyn iterator; and every buffer of the merge lives in one allocation released whole, so the build's high-water mark stays where it was. Byte-identical (blob digests at 10 M and 10^8 keys). At 10^9 real-word pairs: merge 59 → 25 s, fingerprint pass 49 → 46 s, the whole build 548 → 504 s with six minutes of either being the example's key generator, peak 942 → 943 MB; at 10^8, alternated twice: merge 4.2 → 1.3 s, total 46.4/47.4 → 43.7/43.6 s. bench/results/peak-compact-stream-merge-2026-09-10-arz-b687f89.txt.
• Both hash builds sort their pairs on every thread, and the streamed build merges runs and places fingerprints with less work per pair: a run — or the in-memory pair list — is partitioned in place by the top of the hash into one part per thread and each part is sorted on its own thread (the parts abut, so there is no merge and no second buffer); the run merge replaces the heap's top in place instead of popping and pushing, takes whole records straight out of its read buffer and writes a pair in one call, and a run is spilled a 64 KiB slab at a time rather than a pair per call (212 → 193 ms per 256 MiB run; the rest is the disk); the fingerprint pass sends its representatives through index_all a thousand at a time with each fingerprint row prefetched ahead. Byte-identical (blob digests at 10 M and 10^8 keys before and after). At 10^8 real-word pairs the streamed build's own share of a 51 s run — the rest is the example's key generator — falls from about 16 s to 12 s (run sort 0.63 → 0.31 s per 16.7 M pairs, merge 5.6 → 4.2 s, perfect hash 1.55 → 1.27 s, fingerprint pass 2.85 → 2.2 s); the in-memory CompactHashIndex::build at 10 M takes 575–591 ms against 762–783 (alternated, two rounds), its memory unchanged. bench/results/peak-compact-stream-time-2026-09-10-arz-0e177fd.txt.
• The perfect hash's construction holds a level's pieces only while the gaps beside them are placed: a chunk's seeds go into the level table as it is placed, its occupancy map into the level's once both neighbouring gaps have read it, and the keys it bumped are listed in chunk order as chunks finish, instead of every piece staying alive until a merge that copied all three again; the next level groups by level hash alone and keeps its input by retain, the holes are yielded into their encoder rather than listed, and a table on its way to a file is written section by section instead of through a to_bytes copy. Byte-identical (golden fixtures, and blob digests at 10 M and 10^8 keys before and after). The streamed CompactHashIndex build at 10^9 real-word pairs peaks at 942 MB, down from 1 717 (0.9 bytes per key: 0.6 after the first level, 0.87 at the second level's grouping), in 587 s against 604; the in-memory build's time is unchanged. bench/results/peak-compact-mem-2026-09-10-arz-71363e5.txt.

• CompactHashIndex::build and ClosedHashIndex::build feed the perfect hash straight from the sorted pairs, a chunk at a time as the file build does, rather than extracting the representatives' hashes and staged fingerprints first. Same blob. At 10 M real-word pairs the build adds 21.5 bytes per key above the key list, down from 25.0, and takes 774 ms against 843 (alternated, three rounds); at 2 M the chunk buffers the feed keeps, one per thread, are still visible and the peak is a wash (25.7 / 25.4 / 29.9 bytes per key at 8 / 16 / 32 fingerprint bits against 23.9 / 25.9 / 28.0). bench/results/peak-compact-inmem-2026-09-10-arz-e3e910a.txt.

• An arena past 4 GiB keeps its blocked offsets. The u32 block base that could not reach the data past 4 GiB widens to u64 (arena tags 0x31 / 0x32, bit 0x20) instead of the layout falling back to the flat u64 table: 1.56 bytes per key of offsets instead of 8 -- 0.78 GB instead of 4 for 500 M ten-byte keys. The flat table remains only for a 256-key run past 64 KiB. Below 4 GiB nothing changes, byte for byte, beyond the magic the key hash above moves; a reader from before 2.0 refuses the wide-base tags as an unknown encoding, the same way it refuses the fingerprinted ones. The threshold is injectable in the tests, so both layouts are exercised on a 40-byte arena. PerfectHashIndex::build now refuses a key longer than u32::MAX bytes with the error build_to_file already gave, instead of laying out a truncated length.

• One long key no longer widens the whole arena. A block whose 16 keys outgrew its one-byte offsets used to move every block to two-byte offsets (0.7 bytes per key more), and a key past 64 KiB the whole arena to the flat table (2.7 more). Now such a block keeps its place and stride, marks its first offset and puts its real offsets in an overflow table behind the data (arena tag bit 0x40): 76 bytes for one 10 kB key among a million short ones. An arena no block of which overflows is unchanged byte for byte; a corpus of long keys still takes the wider blocks, and the flat table remains for a handful of keys none of which any block holds -- once the one-byte blocks do not fit, the layout is the cheapest by the lengths. The file build writes the table behind the data too, and a reader from before 2.0 refuses the tag. Alongside, an absent probe under fingerprints is decided on the fingerprint byte before the slot's offsets are read, which took it from 91 to 75 ns: that path is about as long as the reorder buffer is wide, and its one cache miss overlaps the next probe's only while it stays that short.
• The perfect hash looks up 20 % faster. MPH2 has had one seed family since 1.1.0, but every lookup still decoded the seed byte into a family and a shift and took the key's offset from a family-dependent run of its hash bits -- a variable shift on the hot path. The value is now start + ((offset + stride × seed) mod slice) and nothing else; the family machinery is gone from the builder too. Blobs are unchanged and the golden 1.1.0 fixtures are byte-identical: the same seeds, 2.089 bits/key. In the sweep harness, 10 M bigram hashes, A-B-A-B against 1.1.1's tree: lookup 34.4 → 27.5 ns, build 50.6 → 46.1 ns/key single-threaded; in bench/mphf_vs against PHast and PtrHash, lookup 33 → 28.8 ns and build 47.7 → 44.8 ns/key (8.1 → 7.6 on 8 threads).
• Overlay::save streams. The base goes to the file through the new OverlayBase::write_base -- a default through base_to_bytes, overridden by the three indexes to write from the bytes they already hold -- then the additions and the tombstones, and the header last over its place once the lengths and the payload hash are known. Saving an overlay over a mapped base of a gigabyte no longer makes two copies of it. to_bytes assembles the same sections into one Vec, sized by the new OverlayBase::base_serialized_len; both produce the bytes 1.1 wrote.
• The sizes the perfect hash derives from its load factors -- buckets per level, the tail's buckets and range, the held share at a run's start -- are integer arithmetic over ratios (9/2, 13/2, 24/25, a fixed-point 0.966) rather than f64. The output is byte-identical, and the golden blobs say so; what changes is that the determinism promise no longer rests on every target rounding a division the same way, which IEEE 754 guarantees but no test could show.
• bench/compare.py records the competitors' installed versions (marisa-trie, dawg2, datrie) in its results file, next to lexindex's own.

Documentation

• docs/benchmarks.md gains the perfect hash's head-to-head with PtrHash and PHast, re-measured after the lookup change: at 2.09 bits it builds 1.8× faster than the PHast+ it follows and 4.2× faster than PtrHash's compact set, with the fastest lookup of the three; regular PHast is smaller (1.92 bits) at 14× the build.
• SECURITY.md lists 1.1.x as the supported line and no longer says an Overlay answers arbitrary bytes with an Err: its own framing does, but an overlay over a StringIndex hands the base region to the base's loader and inherits that loader's exception unless loaded through from_untrusted_bytes.
• Contradictions removed: StringIndex::from_bytes pointed at no check for a stranger's blob while from_untrusted_bytes is that check; build_to_file said its file need not match build + save byte for byte while a test holds it to exactly that, short of a hash collision; ids_of_bytes said its buffer is native-endian "like the blobs", which are little-endian everywhere; blob::hash_bytes said it is the perfect hash's slot hash, which is hash::hash_key; the crate doc said the perfect hash implements PTHash's construction, which 1.1.0 replaced with PHast's; the README's determinism note now says "within one lexindex version", as docs/design.md already did; the 1.1.0 entry below said from_untrusted_bytes had no Python binding, and it shipped one.

[1.1.0] — 2026-09-09

Fixed

• SECURITY.md said every loader answers arbitrary bytes with an Err; StringIndex can panic instead. The claim was true of the perfect-hash and overlay loaders and had never been true of the ordered one: fst's node decoder is safe Rust but not total, and the checksum in front of it is public, so a blob crafted to carry a matching one reaches that decoder with an invalid body. A libFuzzer target measured it — 44 bytes in ten minutes, panicking inside the rank spot-check the load itself runs — and docs/design.md and the from_bytes docstring had said so since 0.12.1 while the security policy still promised otherwise. The policy now states the exception, and names the four parsers a fuzz target actually covers rather than implying all five.

• An Overlay stored every added key twice. add owned each string once in a Vec<String>, so key(id) could index, and again as the key of a HashMap<String, u64>, so id(key) could hash. The additions now live once, as the length-prefixed records the blob format already uses, indexed by a map from the key's hash to the record's position — the layout the perfect-hash indexes have always had, down to the side list for the 64-bit collision that essentially never happens, pinned by a test over a real colliding pair since a branch guarding a 2.7e-8 event is otherwise never executed. Measured over a million ten-byte additions on a 100 000-word base with shuffled probes: the resident cost of holding an addition falls from 147 to 54 bytes, add runs about three times faster, and id on an addition is 278 ns against 295 before. Base keys are untouched, since the base answers first. The length sits inside the record rather than in a side table on purpose: a lookup is then the map and the bytes, two dependent accesses, and the version with a side table measured 40 % slower on shuffled probes.

• Overlay::key could answer someone else's key on a 32-bit target. An id above usize::MAX was narrowed with as before the bounds check, so it wrapped onto a real addition instead of returning None. Reachable only where usize is 32 bits and only for an id no add ever issued, which is why no test had caught it; the conversion is now try_from.

• PerfectHashIndex was documented as the "fastest exact string → dense id" in seven places. Its own benchmark says otherwise: id costs about what a std::HashMap lookup does, and the claim belongs to id_unchecked, which skips the membership comparison for a closed vocabulary.

Changed

• The perfect hash is rebuilt as PHast's map-or-bump, and its blob format moves to MPH2. 1.0's table was PtrHash-shaped — buckets placed largest-first, with the buckets in the way evicted and re-placed — and three quarters of its build was that eviction pass reading a random slot-owner table. The new builder never displaces anything: each bucket's one-byte seed slides its keys two values at a time along a 1024-value slice of the table, the seed whose values are lowest is taken, since low values are what the buckets still to come cannot use, and a bucket no seed places is bumped to a smaller table under a fresh hash, down to a tail of a few hundred keys placed exhaustively. Bumped keys reach the first table's holes through a rank bit vector over the lower tables' values and an Elias–Fano list of the holes, which is what keeps a bumped key at about eight bits instead of the sixteen a plain offset table costs. Buckets are placed in fixed chunks with the gaps between them placed serially afterwards, so the table is the same whatever the thread count, and within a chunk the buckets follow PHast's size-weighted priority scaled with the slice, which is what lets a small table place as well as a large one. Measured on 10 M real word-bigram hashes: 49 ns/key on one thread against 280 (85 ms on eight threads against 625), and 2.09 bits/key against 2.39 — CompactHashIndex at 1.26 B/key on the dictionary against 1.30; in-order lookups cost 4.2 ns/key. Small tables gain the most, and nobody had measured them before: 2.78 bits/key at 1 000 keys against 3.19, 2.19 at 10 000 against 2.37. Every BMP6 and BCH6 blob written from here on carries an MPH2 table, which 1.0 cannot read; the MPH1 tables 1.0 wrote still load. The 1.0 hash fixtures are now held to what a reader must promise them, and 1.1 fixtures take over the byte-identity pin.

• Both latency tables are re-measured on 1.1, and the Python one now says what it can support. The Rust table resolves the arena change cleanly: PerfectHashIndex::id went 1.103× → 1.010× of std::HashMap (290 → 274 ns on a control that got 3.4 % slower) while four rows whose code did not move shifted by at most 2 % — StringIndex, BTreeMap, the FxHash map, and id_unchecked, which is flat at 0.285× → 0.288× precisely because it never reads the arena. Two independent 12-run sessions agree on every lookup minimum within 3.1 %.

The Python table cannot support a version claim at all, which took an A-B-B-A against the released 1.0.0 wheel to establish: in one session every cell landed within 1.01–1.04× on random and 0.98–1.09× on words, and the widest gaps belong to dict and marisa-trie — code identical in both runs. That retires two readings the cross-session numbers had seemed to support, that PerfectHashIndex.id gained 9 % and that CompactHashIndex.ids_of lost 37 % on absent pair-corpus probes; today's 1.0.0 wheel measures the latter cell at 62.0 ns against the 44.8 the 1.0 table published. The Rust-level win is real and simply does not survive ~180 ns of per-call binding overhead. local/latency_py.py's publish gate moved from the absolute minima to the ratios for the same reason it exists: it had refused three tables whose ratios agreed to 1–8 %, with the dict column — the drift the ratio divides out — the worst offender in every one.

• The scale table is re-measured on 1.1, as the minimum of five runs per cell rather than the single run behind the 1.0 table, and the file it came from is committed. It is comparable cell by cell with the table it replaces, which the 1.0 one could not claim: StringIndex, whose build and lookup code has not changed since 0.5.1, holds within 2 % on both list rows and is therefore a usable control. Two cells moved on code 1.1 never touched — CompactHashIndex at 1 M reads 0.26 → 0.22 s and 223 → 162 ns, which is the old single sample's noise leaving — and one moved the wrong way and is published rather than smoothed: 10 M StringIndex from a generator went 6.5 → 7.7 s with five tight samples and an additive diff on that path. datrie's size in the comparison table is 30.91 B/key, not the 30.69 measured for 1.0.

• PerfectHashIndex addresses its keys in blocks: 13.62 → 10.94 bytes per key, and writes BMP6. The arena's n + 1 four-byte offsets are gone; sixteen slots now share a u32 base and carry one-byte cumulative offsets after it, 21 bytes per block, so a key is data[base + off[k] .. base + off[k + 1]] — two adjacent reads out of one header, 1.31 bytes per key instead of 4. A corpus whose 16-key runs do not fit in 255 bytes gets 256-slot blocks with two-byte offsets (2.02 B/key; the 1 M random-bigram corpus is one, 23.95 → 21.97), and one that fits neither, or exceeds 4 GiB, keeps the flat table — which is also what removes the old 4 GiB cliff, since a u32 base cannot reach past it. The encoding is chosen in the same pass that writes the data, from the lengths it saw, and recorded in the arena's tag byte.

Reading did not get slower; it got faster, because the whole index is 1.3 MB smaller on the 479 823-word dictionary and stays resident. Alternated A-B-A-B against the flat arena with CompactHashIndex::id_unchecked — same key hash, no arena — as the control: id 216 → 182 ns and key 52 → 38, with the control moving under 5 %. Batched ids_of was the one path that had to be paid for and the one that had to be fixed: a block header is 21 bytes, so its base and the offset pair regularly land in different cache lines, and prefetching only the base cost 9 %. Prefetching both puts it level. Build peak did not rise either — 55.1 MB against 56.3 — although the build now holds one transient u32 per key, since a block's offsets are only final once the block is.

Six layouts were measured before this one was written (local/arenalayout), and the obvious candidate lost: a length prefix in the data with a periodic sample costs +17 to +37 ns, because its "sequential" length reads are hops through the data region rather than through an array. Cumulative offsets are what removes the summing loop altogether.

• BMP5 blobs still load, and are held to it by a test: golden-1.0.0-perfect.bmp now has to answer every key with the id a fresh build assigns, refuse every non-member and map zero-copy, while golden-1.1.0-perfect.bmp takes over the byte-identity assertion. The new magic exists so that a 1.0 reader refuses a 1.1 blob by name instead of failing inside the arena with "unknown offset encoding".

• build_to_file now writes bytes identical to build + save, and is tested that way rather than by behaviour: both derive the arena's encoding from the same key lengths in the same slot order, so the only way the two writers can disagree is a bug in one of them.

• The PyPI classifier is Development Status :: 5 - Production/Stable; 1.0 shipped as 4 - Beta.

Added

• Benchmark results are files, not terminal output pasted into a table. bench/compare.py and bench/scale.py write bench/results/<table>-<date>-<host>-<commit>.json carrying the CPU model, kernel, rustc, Python, lexindex version, the load average at both ends of the run, and the commit — suffixed -dirty when the tree was not clean, because a result measured on uncommitted code is not attributable to the commit it names. Per cell the file keeps the minimum of the repeats with the median and every raw sample beside it, so a run taken on a busy machine is visible in the file instead of averaged into it. The README tables cite the file that filled them.

• from_untrusted_bytes in Python, on StringIndex and on Overlay. The gap it closes is sharper there than in Rust: pyo3_runtime.PanicException derives from BaseException, so the panic a crafted BIX4 blob raises slips straight past except ValueError. Both bindings are tested against the committed specimens — the 111-byte one for the index, and the same bytes sealed into a real OVL2 frame for the overlay, which the Rust side writes and pins because both checksums are the crate's and a blob spliced together from Python would be refused by a hash long before its base region was read. The overlay test asserts that the ordinary loader panics on that fixture, so a binding wired to the wrong loader fails rather than passing quietly. docs/usage.md no longer says the binding does not exist.

• An overlay is only as trustworthy as the base loader it is handed, and the loader's docstring now says so instead of claiming that "every base loader since 1.0" is safe on arbitrary bytes. It is not: StringIndex::from_bytes may panic on a crafted transducer, and an OVL2 frame passes every check it makes for itself before handing the base region over — so the 111-byte specimen sealed into an overlay panics through it, which a test now pins alongside the Err that from_untrusted_bytes returns for the same bytes. No new entry point: from_bytes_with already takes the loader as a closure, so the fix was to name the right one rather than to add a second door.

• A sixth fuzz target, parse_overlay_untrusted, parsing the embedded base as well as the frame — the seam neither existing target reaches, since the overlay derives the base region's bounds from its own header. OVL1 is what makes it fuzzable: no checksum for a mutation to break. 8.5 M executions in three minutes locally, 674 edges, no crashes. Every fuzz job now runs its seed corpus with -runs=0 before the timed run, because a target that dies on its own corpus reads exactly like a real finding — parse_string shipped that way once — and fuzz/Cargo.toml carries the rule that a target surviving a contained panic must replace libfuzzer-sys's aborting hook.

• The byte formats are proved on a big-endian target, in the weekly sanitizer workflow: Miri interprets s390x-unknown-linux-gnu, so no runner is needed, and blob::, arena:: and a new MPH1 fixture test run there in twelve seconds. Every scalar in every blob is little-endian by construction, but to_ne_bytes compiles, passes on x86 and would silently write a different file elsewhere — flipping the arena's count field to it passes cargo test and fails eight tests under the interpreter, which is how the job was checked rather than assumed. mphf:: as a whole is out of reach there (its blob tests build a 263 000-key table, hours under interpretation), so the new test reads the committed fixture and writes it back byte for byte instead.

• Dict-style lookup in Python: idx["apple"] raises KeyError on a miss, idx.get("apple") returns None or whatever default is passed, on all four classes. Nothing further — no __setitem__, no keys / values / items, no Mapping registration — because these indexes are immutable str -> int lookups and registering as mappings would promise iteration semantics three of the four do not have. One consequence is pinned by a test rather than left to be discovered: defining __getitem__ revives the legacy sequence protocol, so list(index) on the two hash indexes raises TypeError from the key type instead of iterating.

• Every Python class pickles. __reduce__ on StringIndex, PerfectHashIndex, CompactHashIndex and Overlay names the class's own from_bytes and hands it the blob — and, for an overlay, the class of the base underneath, since OVL2 records which base wrote it and its loader takes that class. An index therefore travels to a multiprocessing worker under spawn, which shares nothing, and the tests check exactly that rather than a same-process round trip. Pickling copies the bytes, a memory-mapped index included: a path would not survive a worker that cannot see the same filesystem, and a borrowed mapping would not survive the file changing. When both ends can see the file, save plus load_mmap still shares the pages instead of copying them, and docs/usage.md says so.

• StringIndex::from_untrusted_bytes, the loader for a blob someone else wrote. It walks the whole transducer instead of spot-checking it -- every reachable node decoded once, every transition required to point strictly below the node holding it, which is how fst lays nodes out and what makes the walk terminate on bytes that were not -- then streams every key and requires its value to be its rank, so a blob whose values are a permutation of the ranks is refused here and accepted by from_bytes. Decoding a malformed node still panics inside fst, because that decoder is the only one there is; the panic is caught at the load boundary and returned as IndexError::Format. Two caveats it documents: under panic = "abort" a crafted blob aborts rather than returning, and the rejection prints through the process-wide panic hook. tests/data/panicking-1.0.0-string.bix is a real 111-byte specimen, found by libFuzzer against from_bytes and kept so the security policy's exception stays a measured fact. The validation costs 50.8 ms against 1.2 ms for the owned load on the 479 823-word /usr/share/dict/words, or 106 ns per key. In Python it is StringIndex.from_untrusted_bytes, and Overlay.from_untrusted_bytes(data, StringIndex) for an overlay wrapping one.

• Order statistics on StringIndex: lower_bound, range_count, prefix_count and prefix_id_range, in Rust and Python. Ids are lexicographic ranks, so keys sharing a prefix occupy a contiguous id range -- prefix_id_range hands back that interval, which turns a prefix into an array slice or a bitset window instead of a set of ids to test one at a time. None of them decodes a key, so counting three million matches costs what counting three does: 420 ns for prefix_id_range on a three-byte prefix against 238 ns for id on a whole word, and 479 ns for lower_bound, on the 479 823-word /usr/share/dict/words. A property test checks all four against a sorted Vec searched by hand, on an alphabet with two-, three- and four-byte characters, since the ids follow byte order and a prefix bound is built by incrementing one.

• A parse_string fuzz target, replacing the one removed before 1.0 for re-finding a panic the crate could not then fix. It loads through from_untrusted_bytes and asserts the loaded index agrees with itself -- every key's id equals its rank, every point lookup agrees with the scan -- so the target now fails on a wrong answer, not only on a crash. It is in the weekly matrix.

• Feature badges on docs.rs: the "Available on crate feature mph/mmap only" markers that say which parts of the API a --no-default-features build does not have.

[1.0.0] — 2026-09-08

Changed — breaking

• The minimal perfect hash is now this crate's own, and every pre-1.0 hash-index blob is refused. PerfectHashIndex and CompactHashIndex were built on ptr_hash, whose pilot table is read unchecked and whose bounding fields are private, so a blob holding one could not be validated from outside the crate that owned it. The new backend writes every array length into its own header (MPH1) and derives them again on load, which is what a loader needs to bound every read it makes. BMP2/BMP3/BMP4 and BCH1–BCH5 therefore cannot be read at all: each embeds an image the crate no longer links. They are refused with a message naming the version that wrote them; the migration is to rebuild from the key list.

• from_bytes and load are safe fns on both hash indexes — in Rust and in Python, where there was never an unsafe marker to warn anyone. A crafted blob is now a wrong answer rather than undefined behaviour. load_mmap stays unsafe, for the one obligation that is actually about mapping: do not modify the file under the map.

• Ids are reproducible. Construction is deterministic and independent of thread count, so the same key set produces the same blob byte for byte. PerfectHashIndex::build's docstring previously promised the opposite, and CompactHashIndex::build_bits' still did — both say what is true now, and a property test over arbitrary key sets holds all three indexes to it.

• The overlay is checksummed: new format OVL2. OVL1 was the one blob in this library with no integrity check of its own — the base carried one for its own region and the additions and tombstones carried none — so a flipped bit in an addition that stayed valid UTF-8 loaded as a different key, and one in a tombstone word revived a removed id, silently. OVL2 puts every section length in the header, adds a header check and a hash over everything after it, and verifies both before reading any of it. OVL1 blobs still load, without the checks that format does not carry; saving one again writes OVL2 and it gains them. It is the only pre-1.0 format this version still reads — nothing about it was undecodable, so refusing it would have cost a rebuild for nothing.

• Both key hashes read eight bytes at a time. The byte-at-a-time FNV-1a chain that shipped through 0.12 cost one multiply per byte; the replacement costs one multiply-rotate per 8-byte word plus a splitmix64 finalizer with the key's length folded in. A-B-A-B in one process against the old implementation, with a control that touches the same keys: 1.5× on a 9.3-byte dictionary word, 1.7× on a 10.9-byte bigram, 6.2–6.6× on an 80-byte URI-like key. Every hash value therefore changed, which is the second reason no pre-1.0 blob can be read. Held to the same statistics as the hash it replaces before shipping: strict-avalanche worst |z| 4.50 against 4.75, low-bit chi-square over 480 k real words and 1 M bigrams within ±1, slot-against-fingerprint independence within ±1, and the false-positive rate re-measured at 2 M probes — 7 732 accepted against 7 812 expected at 8 fingerprint bits, z = −0.91.

• New blob formats: BMP5 and BCH6. BCH6 drops the overflow_cap field — it existed to bound ptr_hash's unchecked remap, and the new one covers its whole slot range — so its header is 40 bytes rather than 48.

Added

• cargo semver-checks as a CI job, and a versioning policy that says what it cannot see. It passed clean across this release: nothing in the public API shrank, and removing unsafe from a signature widens rather than breaks it. What makes 1.0 major is the on-disk format, which no API tool can inspect — so the policy in docs/design.md states that a blob format is part of the contract, and the CHANGELOG section above is the half of compatibility a human writes.

• The 1.0 blobs are pinned by their bytes, not by invariants. golden-1.0.0-compact.bch and golden-1.0.0-perfect.bmp are now asserted byte-identical to a fresh build from the same key list. No earlier release could do this: pre-1.0 ids were not reproducible across builds, so every golden test could only check the properties a correct load must satisfy. These two files are also what seeds the parse_compact and parse_perfect fuzz targets, and a seed that still parses but no longer resembles what the writer emits is the exact failure this release already hit once.

• SECURITY.md, as a threat model rather than a form letter. What the loaders guarantee (soundness, not correctness — a crafted blob answers wrong ids, never out-of-range ones), why load_mmap is the one unsafe fn and what its obligation is about, why the checksums are integrity and not authentication, and that the unseeded hashes make this no defence against an adversary who picks the keys. The README and docs/design.md link it rather than restate it.

• A blob compatibility policy (docs/design.md): the magic table, and the rule that a refusal must name the version that wrote the file. OVL1 is read where BMP*/BCH* are refused because it is decodable and they are not — compatibility is broken where it cannot be kept, not where keeping it is inconvenient.

• The whole library builds on 32-bit targets, wasm32 included — mph too. Two things had kept the hash indexes off them: ptr_hash pulled in sucds, which refuses any other pointer width, and the MPH's own u64 → usize narrowings had never been audited. The dependency left with the backend in this release, and the audit found one narrowing that mattered — the remap's entry count in Mphf::from_bytes, where a fabricated slots would have truncated into a plausible length instead of failing. Everything else on a load path was already try_from. The compile_error! that explained the restriction is gone, and CI cross-checks i686 and wasm32. Leave mmap off on wasm32: there is nothing there to memory-map.

• A libFuzzer target over the MPH's own blob (parse_mphf), and a seed for it. The two index targets reach that format only behind their own header, where a mutation has to keep two checksums and a length identity intact first — so in practice they fuzz the framing and never the body. The new target starts inside it, and asserts more than "does not crash": every id it gets back must land in [0, n), which is the property that makes from_bytes a safe fn.

Fixed

• The fuzz seed corpus had gone stale, and nothing said so. 1.0's blob formats made every committed seed a blob refused on its magic, so all three fuzz targets would have explored one branch and reported a clean run. The test that exists to catch exactly this is behind the fuzzing feature, which no CI job built — it does now, along with a clippy pass over the same feature, and the seeds are current.

Removed

• ptr_hash and epserde, and 129 crates with them. The mph feature now has no dependency at all; the crate's whole tree is fst plus memmap2. cargo audit goes from three allowed warnings to none — every one came from that tree.

Changed

• The blob-integrity primitives — the header hash and the streaming payload hash — moved from the mph-gated hash module to blob, which every format shares. StringIndex-only builds could not reach them before, which is why the overlay had none.

• Loading a PerfectHashIndex no longer hashes every key in the arena. That pass existed to recompute overflow_cap on each load and was O(n) on the blob's size.

• CompactHashIndex costs 1.30 B/key at the 8-bit default and 0.80 at 4 bits, against 1.27 and 0.77 on the old backend: the in-crate MPH is 2.390 bits/key where ptr_hash was 2.169. Measured on /usr/share/dict/words (479 823 keys).

• Every timed table in the README was re-measured on 1.0, in one idle session after the last code change. Three findings, and one non-finding stated as such:

• PerfectHashIndex::id_unchecked went from 0.451× to 0.287× of std::HashMap — 111 → 75 ns at 1 M bigrams, on a control that got 6.7% slower. Against a HashMap with FxHash it is now ~2× faster (75 against 156 ns), where through 0.12 this README said the latency advantage against a fast-hashed map was gone. That claim is retracted; the perfect hash and the 8-byte key hash are what changed, not the conditions.

• Builds cost more. CompactHashIndex at 1 M went 114 → 175 ms and PerfectHashIndex 291 → 378 ms: the in-crate backend builds 1.5–1.8× slower than ptr_hash did, which was accepted as the price of a header a loader can check. At 10 M the picture reverses in the scale table, because that build is eight-threaded and the older session was core-contended.
• From Python, PerfectHashIndex moved 1.04× where marisa-trie, StringIndex and CompactHashIndex all moved 1.18–1.20× on the same corpus — a ~14% gain relative to everything else in the room.
• The dict denominator moved again and the Python table is therefore not comparable cell by cell with the one it replaces: 327.9 ns then, 258.5 now, on identical keys and untouched code. Its absolute values are now printed in the table so the next session can see the denominator rather than guess at it. The mechanism remains unidentified after having been chased once already.

[0.12.1] — 2026-09-07

Fixed

• A crafted overlay blob could panic a safe loader. Overlay::from_bytes_with read the tombstone word count out of the blob and computed count * 8 on it unchecked. A 40-byte blob claiming 1 << 61 words panicked with an arithmetic overflow in a debug build; in release the product wrapped to zero, the length identity bytes.len() - at == count * 8 then passed, and the parser went on to collect 2^61 elements — a capacity-overflow panic where a clean IndexError::Format was owed. Reproduced in both profiles before the fix, and both regression tests fail against the old parser.

Every count the blob carries is now narrowed with usize::try_from and combined with checked_mul / checked_add, and the tombstones are read from the byte slice itself (chunks_exact(8)) after its length has been checked — so a number the blob merely claims can no longer size an allocation. The same as usize casts truncated base_len and the addition count on a 32-bit target, where Overlay<StringIndex> is available; StringArena already used try_from here and the overlay now matches it.

• Overlay::save was not atomic. It was std::fs::write, so a crash, a full disk or a kill mid-write left a truncated blob under the real name. It now goes through the same writer the three indexes use — temporary + O_EXCL + fsync + rename + directory fsync — which matters most here: the overlay is the crate's mutable layer, and so the file most often rewritten over a live one.

• A crafted blob could make len() disagree with the keys. Additions were checked against each other but never against the base, so a hand-made blob could add a key the base already held: len() counted it twice while id() could only ever answer the base's, leaving the addition's id unreachable. add consults the base first and revives its id rather than issuing a second one, so no blob this crate writes looks like that. The parser now rejects it over a base whose membership is exact — a new OverlayBase::EXACT_MEMBERSHIP, true for StringIndex and PerfectHashIndex. CompactHashIndex keeps the old behaviour, since its false positives would otherwise reject sound blobs, and the constant defaults to false so an outside implementation of the trait still compiles.

• PerfectHashIndex::build_to_file verified pass two by hash alone. The docs promised "a second pass that yields different keys is refused", which a 64-bit hash cannot deliver on its own: an equal-hash key of a different length reached copy_from_slice with mismatched lengths — a panic — on the direct path, and wrote a short record that desynchronised the spill's framing on the windowed one. Both paths now share one replay_span, which checks the slot's length as well. The length is free (pass one sized the slot from it); a second hash would have cost 8 B/key of build memory for an adversarial case, and was not worth it.

Added

• A libFuzzer target and a property test for the overlay's framing. parse_overlay joins parse_compact and parse_perfect, and a seeded-mutation property test works outward from a real blob — one byte flipped, the blob cut short, or one of its three claimed counts replaced by a hostile value — since random bytes never spell OVL1. Both deliberately stub out the base loader rather than re-parse the embedded blob: that is StringIndex::from_bytes's own property, and fuzzing it here would only rediscover the fst node-decoder panic that fuzz/Cargo.toml already records as out of this crate's scope.

Changed

• Overlay's Python loaders document whose trust contract they inherit. Overlay.from_bytes and Overlay.load validate the overlay's own framing for every base, then hand the rest to the base class's loader — checked for StringIndex, trust-your-own-blob for the two hash indexes. The signature cannot say that and Python has no unsafe marker, so the docstrings and the stubs do, and a test asserts the sentence is still there.

• The README's size claim is qualified to what was measured. "The smallest ordered string → id index available in pure Rust" was a universal claim over crates.io that a benchmark of four crates cannot establish; it now reads "the smallest of the pure-Rust ordered indexes measured below".

[0.12.0] — 2026-09-07

Added

• Free-threading audit, and the two fixes it turned up. PyO3 0.29 declares Py_MOD_GIL_NOT_USED for a #[pymodule] by default, so the extension has been telling free-threaded CPython it does not need the GIL without anyone having checked. Measured on 3.14t with eight threads: sharing any of the three index types is sound — they are immutable after building and nothing raised — but sharing a StringIndex iterator or an Overlay failed in seven threads out of eight with RuntimeError: Already borrowed, PyO3's borrow flag refusing two simultaneous &mut self calls.

Both are now #[pyclass(frozen)] with their mutable state behind a lock taken through PyO3's lock_py_attached, which detaches from the interpreter before blocking and so cannot deadlock against it. Sharing one of them serialises instead of raising: a shared iterator hands each key to exactly one thread, and concurrent Overlay.add calls each get their own id. gil_used = false is now spelled out in the source next to the reasoning that backs it, rather than left to a default. The suite runs on 3.14t as well as 3.14, and the two new concurrency tests fail against the previous build.

• ids_of_bytes on all three Python index classes — the batched id packed into a bytes buffer instead of a list. ids_of has to build one Python int per key, which for a batch headed straight into numpy is the whole cost; np.frombuffer(buf, dtype=index.ID_DTYPE) shares the memory instead. One native-endian fixed-width item per key, aligned with the input, with the new MISSING_ID class attribute where a key is absent — a buffer cannot carry None. ID_DTYPE and MISSING_ID are class attributes rather than one module constant because the width differs between the index types (StringIndex ids are 64-bit, the hash indexes' are 32-bit), so generic code can read them off the class. On the one index size where the sentinel would be a real id — exactly u32::MAX + 1 keys — the method refuses instead of silently aliasing.

Returned as bytes rather than as a buffer-protocol #[pyclass]. Both work under abi3-py311 (Py_bf_getbuffer has been in the limited API since 3.11), so the choice is surface, not portability: bytes adds no public class and no exported-buffer lifetime to get wrong, and it is immutable, which is what an answer should be. What it costs is one memcpy of 4 bytes per key.

Measured on 200 000 real-word keys, minimum of nine rounds, machine drift 3.0 % on a calibration loop with no memory traffic: ids_of 117.5 ns/key, ids_of_bytes 87.9 ns/key — a 1.34× ratio, saving 29.6 ns/key. That saving is the Python int construction and nothing else, which the decomposition shows rather than assumes: arr.tolist(), which builds the same ints from an array with no lookup at all, costs 31.6 ns/key — an upper bound, since it also walks the array. The plan predicted 15–25 ns/key and understated it.

• Overlay<I> — edits on top of any of the three indexes without rebuilding them. All three are immutable by construction: an FST and a minimal perfect hash are both built once from the whole key set, so adding one key has always meant rebuilding for the whole corpus. An overlay wraps a base index with a map of keys added since and a bitset of ids retired from it, so add and remove are O(1) and the base is untouched. Ids span both in one u64 space — base ids keep their values, additions continue above base.len() — and are stable: an id is never reissued, removal never renumbers anything, and re-adding a removed key revives its original id rather than issuing a second one for the same string. compact() rebuilds the base from the live keys when the additions have grown enough to be worth folding in, and is the one operation that renumbers.

What a base can do is expressed in the type rather than in a runtime error: key, keys and compact need OverlayKeys, which CompactHashIndex cannot implement because it stores no keys, so an overlay over it offers membership and nothing else. Removal over a probabilistic base carries that base's false-positive rate — a contains that was never true of a real key can retire an id — which is documented on remove and is why the property test excludes it.

The base may be shared: OverlayBase is implemented for Arc<I>, so an overlay can wrap an index the caller still holds and several overlays can sit on one base.

A lookup costs the base plus one bitset probe, and that is what it measures: at 10 M keys, with the tombstone bitset fully allocated (1.25 MB), Overlay<PerfectHashIndex>::id is 363.0 ns against the bare index's 354.9 ns on the same deserialised structure — 1.023×, +8.0 ns, minimum of nine A-B-A-B rounds with a machine drift of 1.5 %.

to_bytes/save serialise the base blob, the additions and the tombstones together; from_bytes_with/ load_with take the base's own loader as a closure. That is deliberate: StringIndex::from_bytes is safe while the perfect-hash loaders are unsafe fn, and a single generic loader would have had to be unsafe for all three to accommodate two of them. Neither len nor the live/dead split is stored — both are derived on load, so a blob cannot disagree with itself about how many keys it holds — and a malformed blob is rejected with a named Format error rather than half-loaded. The header records which base wrote the blob and the loader checks it before handing the bytes over, so a perfect-hash loader is never pointed at bytes written by something else.

Exposed to Python as lexindex.Overlay, taking any of the three index classes. A #[pyclass] cannot be generic, so the base is a runtime tag there and key/keys/compact raise TypeError on a CompactHashIndex base where Rust refuses to compile. Overlay.load(path, base) and Overlay.from_bytes(data, base) take the base class, since each index loads itself; the base tag turns the wrong class into an error instead of an unchecked read.

Fixed

• The grid column of the Python lookup table did not reproduce, and is restated. Re-measured one day after 0.11.0 published it, from two fresh 11-round passes agreeing to 4.3 % at worst and 0.5 % at the median. The corrected figures: marisa-trie 3.08×/2.75× (was 2.50×/2.16×), StringIndex.id 1.73×/1.37× (was 1.41×/1.06×), CompactHashIndex.id 0.71×/0.41× (was 0.61×/0.32×), its ids_of 0.45×/0.26× (was 0.38×/0.20×). PerfectHashIndex.id reproduced. The published ranges move with it: a missing key costs CompactHashIndex 0.33–0.41× a dict (was 0.32–0.36×), batched ids_of on members 0.31–0.45× (was 0.31–0.38×), and StringIndex 1.37–2.61× (was 1.06–2.61×). The words and random columns reproduce to within 1 % and stand.

Five runs on the new day — three round counts, idle and under load, on the released 0.11.0 wheel as well as the working tree — agree with each other and disagree with the old column by up to 30 %. That rules out the extension, the interpreter, the corpus generator and background load. What moved is the dict denominator, 251 ns then against 194–196 ns now on identical keys; the mechanism is not identified and the README says so rather than guessing. The protocol defect is identified: the two passes that validated the old column ran minutes apart inside one session, which bounds within-session noise and nothing else, so the second pass now has to come from a separate session.

[0.11.0] — 2026-09-06

Added

• StringIndex::build_sorted and build_sorted_to_file — build from keys that are already in ascending order, without materialising them. build has to collect its input into a Vec before it can sort it, so a caller who already has the keys ordered (a sorted file, a database cursor, an external sort) pays for a second copy of the corpus; these stream straight into the transducer, and build_sorted_to_file streams the finished index to disk as well, so neither the corpus nor the index has to fit in memory. Measured with examples/peak.rs on the same word-bigram grid: at 10 M keys the streaming build peaks at 49.6 MB against build's 721.9 (14.6×; 20.0 MB of build memory against 129.5 plus a 592 MB key list), and 100 M keys build with a 63.3 MB peak, of which 29.6 MB is the loaded word list — 32× under the 2 GB the task set as its bar. The peaks reproduce to the tenth of a megabyte across runs; the wall time does not, and is left out for that reason (the same 100 M build took 52 s on an idle machine and 101 s under a load average of 7). Adjacent duplicates are dropped exactly as build drops them after sorting, so the two produce byte-identical blobs for the same key set, which is what a test asserts rather than a similarity check: ids are ranks, so any disagreement would renumber every key after the first difference. An input that is not ascending is refused by the transducer builder rather than producing an index that answers wrongly.

• PerfectHashIndex::build_to_file — builds straight to a file without ever holding the keys, for a corpus that does not fit in memory. Measured on the same key set both ways (examples/peak.rs): the process peaks at 471 MB at 10 M keys against 1 272 MB for build handed a list of those keys, 87 against 146 at 1 M. Of the streamed build's 44.1 bytes per key, 23.5 are the output file itself — the arena is filled through a mapping, so its pages stay resident until the kernel writes them back; the anonymous part is 20.6 bytes per key and flat in n, which is what the design predicts (eight for the hash, four for the length, eight for the sorted copy that looks for collisions).

source is a factory, called twice, and that is the shape of the problem rather than an inconvenience: the arena stores keys in slot order, slot order needs the perfect hash, and the perfect hash needs every key's hash first. Pass one hashes and records lengths, the offset table follows from the lengths alone, pass two replays the corpus and writes each key into its place. A one-shot iterator cannot be passed by construction — the signature states the requirement instead of documenting it — and a source that replays different keys is refused rather than silently mis-built.

Keys must be distinct, unlike build, which sorts and deduplicates. A repeated hash in pass one is either a duplicate key or a genuine 64-bit collision, and which one it is changes n, the tail ids and therefore every offset already computed. Requiring distinct keys makes a repeat a collision by definition; a duplicate is caught by comparing the two written entries, and the file is never published.

The arena is filled one 32 MB window at a time, through a spill file, and the reason is worth a caller's attention because it costs disk space. Keys are stored in slot order, which is random with respect to file offset, so filling the arena in a single pass keeps the whole mapping dirty for the pass's whole duration — a 4 KB page holds ~178 keys at these lengths, so once the kernel starts writing pages back the pass re-dirties them and the build writes its own output dozens of times over. Measured that way on a real filesystem, page cache drained before every run, it cost 2.7× the wall time from 5 M keys up and did not finish at 100 M at all: killed after fifty minutes at 18 % CPU, having written 187.7 GiB for a 2.34 GB file. Pass two therefore appends each key to the region of a sibling spill file belonging to the window its slot falls in, and each window is read back sequentially, filled inside itself and flushed.

keys	one pass	windowed	bytes written / output size
5 M	12.2–16.4 s	4.2–5.2 s	55–75× → 1.00–1.01×
10 M	25.3–34.2 s	8.5–8.6 s	55–91× → 1.00×
20 M	60.6–61.4 s	17.7–17.9 s	68–72× → 1.00–1.01×
100 M	did not finish in 50 min	94.2–102.3 s	86× → 1.85×

What identifies the write order as the cause, rather than the filesystem or the machine, is a control that holds everything else fixed — the same file, the same offsets, the same bytes, in sequential against scattered order: 1.0 s against 155–167 s, at 140–151× the bytes. On a RAM filesystem the same reordering costs 1.7× and no I/O at all. 32 MB is the largest window that held 1.0× reproducibly; 64 MB measured 1.4–2.3× and 128 MB 2.9–23×. Re-reading the source once per window instead of spilling was measured and rejected: one pass over a 100 M source costs 32.8 s, and a 2.3 GB arena needs 74 windows.

The cost is transient disk space — about 2.2× the output size has to be free in the target directory until the build finishes, so a build can fail with ENOSPC on a volume sized exactly for its output. Below roughly 20 M keys the spill never reaches the disk at all, being written and consumed within seconds; an arena that fits in one window skips the spill entirely. The times are below what the single-pass fill measured writing into a RAM filesystem (4.2 / 8.5 / 17.7 against 5.2 / 10.7 / 22.6), because filling one window at a time is easier on the TLB as well as the disk.

StringIndex::build_sorted_to_file never had the problem — it writes in ascending key order through a buffered writer, measured at 1.02× at 100 M on the same filesystem the same day — and CompactHashIndex has no arena to fill.

• StringIndex.from_sorted and StringIndex.build_sorted_to_file in Python, the binding for the sorted streaming builds above. This is where the case is strongest: a Python list of 10 M keys is 1 076 MB of str objects before any index exists, so the caller who most needs a build that never materialises its input was the one who could not reach it. Handed a generator, the streamed build peaks at 11.6 MB against the list build's 1053.4 at 10 M (91×) and 4.2 against 105.4 at 1 M, measured with VmHWM reset after the corpus loader so the baseline is the steady state.

A Python iterable that raises halfway is indistinguishable, from Rust, from one that ended, so build_sorted_to_file asks a caller-supplied check inside the atomic write and before the rename that publishes the file. Without it a generator that blew up mid-corpus would have left a truncated but perfectly valid index at path, over whatever was there, with the exception arriving afterwards. A test asserts the file is byte-identical to what it was before the failed build, and that no temporary is left behind.

• PerfectHashIndex.build_to_file(source, path) in Python, the binding for the streaming build above. source is a zero-argument callable returning an iterable and it is called twice — the factory shape the Rust signature enforces, spelled the Python way (lambda: open(path)). A Python exception in either pass surfaces as that exception with the file at path left byte-identical, through the same in-write check the sorted build uses — a deterministic failure would otherwise stop both passes at the same key, and the two passes would agree on a truncated index. A second pass that yields different keys, or a repeated key, is refused with ValueError; handing it the iterable instead of a factory is the likely mistake, so that is a TypeError naming the fix.

• StringIndex.iter_after (Rust) — iter() resumed after a cursor key, which is the one range the existing API could not express: range_iter(lo, hi) needs an upper bound and prefix_iter("") cannot skip. It exists because the Python iterator needs it, and it is public because a caller paginating a scan across requests needs exactly the same thing.

Changed

• The whole build table at 100 M keys, which is the row the streamed perfect-hash build had to be fixed before anyone could take. One process per cell, on a real filesystem, page cache drained before every run:

build	keys	wall	peak RSS	blob
PerfectHashIndex::build_to_file	streamed	94.2 / 97.6 / 102.3 s	4 070–4 080 MB	23.44 B/key
CompactHashIndex::build (fp = 1)	list	18.3 s	8 371 MB	1.27 B/key
StringIndex::build_sorted_to_file, word grid	streamed	29.9 / 31.6 s	62.6 MB	4.39 B/key
StringIndex::build_sorted_to_file, sparse pairs	streamed	92.9 / 99.4 s	77.2 / 77.3 MB	12.51 B/key
the generator alone, building nothing	streamed	32.6 / 33.0 s	33.5 MB	—

Two design claims survive a tenfold extrapolation past the largest n previously measured. CompactHashIndex holds 1.27 bytes per key at 1 M, 10 M and 100 M, to three digits, and the memory its build adds above the key list is 25.0 B/key against 25.7 at 10 M — 2.7 % below, where the claim was flatness within 10 %. The streamed transducer build peaks at 0.6 bytes per key at 100 M, half of which is the loaded word list.

The two StringIndex corpora are listed separately on purpose: the 63.3 MB published for this build in 0.11 is the word grid, and the sparse-pair generator gives 77.2 MB and a 2.8× larger blob for the same n. Every trie number is a statement about its corpus, and a table that folded the two together would read as a contradiction.

The PerfectHashIndex row is also a correctness result: 100 M keys built across 74 arena windows, then every one of them checked — id answers, key(id) returns the key, and the ids are exactly the dense range [0, n).

From Python, through the same bench/scale.py cell the published table uses, a CompactHashIndex built from a generator of 100 M keys takes 35.9 / 36.1 s at a 2 452 MB peak — which retires the extrapolation the README's scale table used to end on (~35 s, ~3 GB) by measuring it. The point lookup does not move with n: 298–344 ns at 100 M against 302–330 at 10 M.

• docs/design.md records that ptr_hash construction is not deterministic. Two PerfectHashIndex::build calls over the same key set, in one process, serialise to different bytes. The index is equally correct and every key answers, but the ids are not stable across builds, so a blob cannot be checksummed against a rebuild and two nodes building the same corpus will not agree on ids. Found while writing a byte-identity test for build_to_file that could never have passed — byte-identity is not a property build itself has. Anything that needs stable ids must build once and distribute the blob.

build_to_file's own documentation said the opposite — that the file it writes is byte-identical to what build + save would have produced. It was written in this cycle and never shipped, so it is corrected here rather than listed as a fix. It now says what is true: the blob answers exactly the same, key for key, but the bytes and the ids differ. Two neighbouring claims that read as byte-identity are correct and were left alone: to_bytes against save (one index, two serialisation paths) and StringIndex::build_sorted against build (the transducer is deterministic, and a test asserts it).

• The Python lookup table, owed since 0.10 and finally taken (local/latency_py.py, new README section): dict, marisa-trie and all three indexes over three corpora and three member/miss mixes. CompactHashIndex.id answers a present key in 0.61–0.71× a dict's time and a missing one in 0.32–0.36×; batched ids_of in 0.31–0.38× and 0.20–0.29×. PerfectHashIndex.id trades level on members (1.05–1.33×) and wins on misses (0.83–0.96×); marisa-trie costs 1.85–4.29× and StringIndex 1.06–2.61×.

Three protocol defects had to be fixed before any of it was publishable, and the third invalidates the criterion the plan had been using. The harness gated on dict's round-to-round spread as its stability control, and that spread was 19–79 % while StringIndex sat at 7 % on the very same rounds — not machine noise, which moves every column alike, but dict itself: at these sizes its table straddles the L3 boundary (~16 MB at 480 k keys) where CompactHashIndex is 0.6 MB and fully resident. The least stable object in the table had been made its control. Second, the forms were alternated in a fixed order, so whichever ran first paid to pull the probe list back into cache after the previous set displaced it; they are rotated now. Third and decisive, an idle machine is not a quiet one: a cache-resident integer loop touching no memory drifts 13.7 % over twelve rounds, climbing monotonically as the CPU heats, so the "control spread under 2 %" bar was unreachable here whatever the load average said, and four sessions of blaming a sibling process were half wrong. The estimator is now the minimum over rounds and the criterion is agreement between two independent runs — worst 7.3 %, median 1.0 % on the published numbers. A fourth would-be defect was caught by that criterion rather than by inspection: the first run of a corpus, minutes after a build, disagreed by up to 24 % on two cells, so a settling period is real and the run is excluded.

• The ns/op table the 0.10 sessions could not take (local/latency/): every lookup form of both hash indexes over four member/non-member mixes and two key layouts, std::HashMap as the stability control, all forms alternated inside each round. Two findings reached the README. First, ~90 ns of every published lookup number is reaching the probe key: examples/bench.rs probes the original allocations in strided order, and handing the same index a contiguous probe list takes PerfectHashIndex::id_unchecked from 109 to 18 ns/op at 1 M while ids_of does not move at all (39.5 scattered against 38.2 contiguous — the software prefetch does for scattered keys what the hardware does for contiguous ones). Second, on misses std::HashMap wins until its table outgrows the cache — 32 ns against CompactHashIndex::id's 41 at 1 M, reversing to 105 against 56 at 10 M. The harness also reproduces the README's own table from different code: at 1 M scattered it measures 125.6 / 261.8 / 108.9 / 237.2 ns against the published ~151 / ~273 / ~111 / ~246.

• ids_of prefetches the key bytes, not just the tables it looks them up in — 2.6× on CompactHashIndex and 2.1× on PerfectHashIndex over 10 M real-word bigrams, A-B-A-B against the unmodified tree with the per-key id loops as controls (both flat: 200 → 203 ns/key and 427 → 416). Against that per-key loop the batch is now 2.9× and 3.6×, where it was 1.1× and 1.8×: batching a CompactHashIndex lookup used to buy essentially nothing.

The missing prefetch was the first one. A batch's String headers are contiguous but their bytes are wherever the allocator put them, so the hashing pass was one dependent cache miss per key with nothing overlapping it, and the careful prefetching downstream was hiding the cheaper halves of the problem. The per-key id cannot make this prefetch at all — it has no next key to look at — which is what the batched form is for.

The number depends on where the caller's keys live, and the docs now say so. Contiguous keys — a Vec built in probe order — are already visible to the hardware prefetcher: that batch runs at ~50 ns/key with or without the change (−6 % to +2 % across 1 M / 5 M / 10 M, no consistent direction), and the win there is the single FFI crossing. A 50/50 member/non-member batch measures the same as an all-member one, because what is being hidden is reaching the key at all.

• StringIndex.__iter__ (Python) streams the transducer instead of rank-walking every key — 2.9× faster over 1 M real-word bigrams (635 → 221 ns/key, three rounds each; the control, id() on the same index, held at 367 ns across both). It buffers 1 024 pairs per refill and resumes through iter_after, because a #[pyclass] cannot hold a stream that borrows the index across __next__.

The plan asked for 10× and 2.9× is what the ceiling allows, which the measurement says rather than the estimate that set the bar: on the Rust side the same walk is 569 → 97 ns/key (5.9×), and the binding adds ~127 ns/key of CPython str and tuple construction that no iteration strategy removes — prefix(""), which builds the whole list in one call with no per-item __next__ at all, costs more (399 ns/key) than the lazy iterator. So the rank-walk is gone entirely and what is left is object construction. Setting the bar as a round multiple, without a measured floor, is the same defect as the 2 GB bar in the entry above, from the other side.

Fixed

• The 0.10.0 build-memory figures were measured against a masked baseline and are corrected here, not silently swapped. examples/peak.rs reports VmHWM − (VmHWM at the moment the key list is ready), and VmHWM is a high-water mark: the transient of loading the word list and sorting the bigrams stayed in it, so every build had to climb past that transient before it registered. The example now resets the mark (echo 5 > /proc/self/clear_refs) once the key list is built. The understatement is a constant 11.0–11.8 MB in every cell — flat in n and in the structure, which is what identifies it as the corpus transient rather than anything about the builds. Re-measured with the corrected baseline on both sides (0.9.1 built from the same example), bytes per key above the key list:

build	published 0.10.0	corrected
PerfectHashIndex, 2 M	79.0 → 44.9 (−43 %)	83.0 → 50.8 (−38.8 %)
PerfectHashIndex, 10 M	84.7 → 50.8 (−40 %)	85.9 → 51.9 (−39.6 %)
CompactHashIndex 8-bit, 2 M	42.5 → 25.2 (−41 %)	48.2 → 30.9 (−35.9 %)
CompactHashIndex 8-bit, 10 M	47.6 → 24.6 (−48 %)	48.7 → 25.7 (−47.2 %)
CompactHashIndex 16-bit, 2 M	→ 27.3	48.2 → 33.0
CompactHashIndex 32-bit, 2 M	→ 29.2	48.2 → 34.9

The absolute savings are unchanged, because the constant cancels in a difference: 340 MB off a 10 M PerfectHashIndex build (published 338) and 230 MB off a 10 M CompactHashIndex build (published 230). What moves is every per-key figure and therefore every percentage, by 1–5 points. docs/design.md and the CompactHashIndex::build_bits docstring carry the corrected numbers; the 0.10.0 section below is left as it was published. One 0.10.0 claim gains rather than loses: the build peak was said to rise with the fingerprint width, and on the corrected baseline the 0.9.1 build does not move with it at all (48.2 B/key at 8, 16 and 32 bits), so the width-proportional staging is visible only in the new code.

• The README's dict build cost had the same defect from the Python side — local/positioning.py took its baseline right after _random_pairs returned, while the dict that generator uses to deduplicate was still counted in the high-water mark. It resets the mark too now: a dict costs 71–95 bytes per key above the key list on the three corpora in the README's table, not the 35–96 the range said, and 58–60 at 10 M.

[0.10.0] — 2026-09-04

Added

• Golden blobs from every published format (tests/data/, regenerated by local/gen_golden.py from the PyPI wheels of 0.5.1, 0.7.0, 0.8.0, 0.8.1 and 0.9.1) are loaded and queried by tests/golden.rs. Every other test in the repo writes a blob and reads it back with the same code, so all of them would keep passing if a dependency bump changed the epserde image embedded in an MPH blob. These cover BMP2/BMP3/BMP4 and BCH1/BCH3/BCH4/BCH5, including the documented refusal of a 0.5.1 BCH1.
• examples/peak.rs reports the peak resident memory (VmHWM) and wall time of a single build, one index per process, on the same real-word bigrams examples/bench.rs uses. The build-memory numbers below were measured with it.
• examples/bench.rs gained an FxHash baseline. std::collections::HashMap is a SipHash map, which is the wrong single number to compare a perfect hash against; the same map with the rustc/Firefox hash (written out in the example, not added as a dependency) is the honest one.
• libFuzzer targets for the blob framing parsers (fuzz/, run weekly by sanitize.yml, seeded from tests/data/). They cover the safe half of the MPH loaders — the code that validates magic, versions, lengths, both checksums, the collision side table, the fingerprint width and the arena's offset table before anything unsafe happens, which is the only place untrusted bytes reach code this crate owns. 29.0 M and 37.5 M executions with no crash on the first run.
• A positioning section in the README: which index to pick, and how much the corpus decides it. Five structures — a bare ptr_hash MPHF, CompactHashIndex, marisa-trie, StringIndex, PerfectHashIndex — over three corpora built from the same word list, at 479 823 / 1 M / 10 M keys. The structures that store no keys are flat at 1.27 and 0.27 bytes per key on every corpus; the ones that do swing 3–8× (marisa 2.12 to 6.21, StringIndex 0.68 to 16.57), so the section says which corpus each number comes from and what shared key structure buys.
• bench/scale.py measures a list and a generator separately. Passing a list puts the corpus in the peak, which is what a caller holding the keys pays; passing a generator is what CompactHashIndex's streaming build exists for and is the only way to see its own footprint.

Changed

• StringIndex::from_bytes no longer claims that checksum verification rules out a panic. It guards accidental corruption, which is all a public, deterministic checksum can do; a blob crafted to carry a matching one reaches fst's node decoder with an invalid body. A third fuzz target demonstrated it in ten minutes with 44 bytes that panic inside the load's own rank spot-check, and that target is deliberately not kept: docs/design.md already documented this as the accepted limit of the StringIndex trust boundary, so the defect was in the docstring, not in the code. fst is safe Rust throughout, so the worst case remains a panic or a wrong answer rather than an out-of-bounds read — which is why this loader stays safe while the perfect-hash ones are unsafe.

• PerfectHashIndex builds in 43 % less memory — 79.0 → 44.9 bytes per key above the input at 2 M real-word bigrams, and 84.7 → 50.8 at 10 M, where it is 338 MB off the peak of a single build. Four changes, none of which touch the blob: the slot table holds a u32 key index instead of a 16-byte Option<&str>; the (hash, index) partition that existed to find hash collisions is gone from the common path, replaced by a sorted scratch copy that also feeds the perfect hash and is dropped before the arena is built (a real collision falls back to the old partition, on a #[cold] path); the arena is assembled in one exactly-sized buffer with its offsets written in place, instead of collecting the data and the offsets separately and concatenating them, which held two copies of the corpus across the concatenation; and the arena takes its two totals from the build's own hashing pass rather than re-deriving them in slot order, which measured 4 M extra data-TLB misses at 2 M keys. The build also retires 5.6 % fewer instructions and takes 11 % fewer page faults than 0.9.1 (perf stat, three runs).

• CompactHashIndex builds in 41 % less memory — 42.5 → 25.2 bytes per key above the input at the 8-bit default, and 47.6 → 24.6 at 10 M (230 MB off a single build). The representatives' hashes and their truncated fingerprints are lifted out of the (hash, second hash) pairs before the perfect hash is built, so the pairs are dropped first rather than sitting next to ptr_hash's construction memory alongside a full 64-bit fingerprint per key. The documentation claimed 16 · n for the peak, which was the pairs alone: the measured high-water mark is 25.2 bytes per key at the 8-bit default, rising with the fingerprint width (27.3 at 16 bits, 29.2 at 32), and the docs now say so.
• README: "roughly twice as quick as HashMap" is now scoped to the SipHash map it was measured against. std::collections::HashMap hashes with SipHash; the same map with FxHash measured 196 / 200 ns against PerfectHashIndex::id_unchecked's 216 / 216 in two independent 12-run sessions. Against a fast-hashed map lexindex's lookup advantage is gone, and the README says so — what remains is the footprint and the serialisable, memory-mappable blob. The scale table is regenerated on this code with both key sources; the streamed CompactHashIndex at 10 M peaks at 304 MB against 988 for the same build handed a list.
• ptr_hash and epserde are bounded to a minor series (~1.1, ~0.8). Their layout is embedded verbatim in every MPH blob this crate has written, so a change there does not break a build — it stops old files from loading. Moving either is now a decision with a golden-blob test attached rather than something cargo update can do.
• A 32-bit build with the mph feature now fails with one sentence naming the feature to turn off. ptr_hash 1.1 depends on sucds unconditionally, and sucds compile_error!s on any pointer width other than 64, so the build used to die inside a transitive dependency with a dozen errors that named neither lexindex nor anything the caller could change — and a compile_error! of our own would never have been reached, because cargo compiles dependencies first. The minimal-perfect-hash dependencies are therefore declared under [target.'cfg(target_pointer_width = "64")'.dependencies]: off 64-bit they are simply not in the graph, the modules that name their types are not compiled, and the only diagnostic is ours. The dependency graph on 64-bit targets is unchanged (Cargo.lock untouched). The fst-only build has no such constraint — checked for i686-unknown-linux-gnu and wasm32-unknown-unknown — and README and the usage guide now say so.

[0.9.1] — 2026-09-04

Added

• serialized_len() on all three indexes: the byte length to_bytes / save would produce, without producing it (the minimal perfect hash is measured through a discarding sink).
• docs/usage.md is compiled as doctests, like the README, so its Rust block cannot drift from the API again — it had been calling load_mmap without unsafe since 0.9.0.

Changed

• The unsafe loaders are split into a safe framing parser and the unsafe epserde step. parse_frame validates everything a query will trust — magic, header and payload checksums, lengths, the side table, the fingerprint range or the arena — on any bytes, and the property tests now fuzz exactly that half (plus every truncation of a real blob); the MPH region is deserialised only afterwards, behind the caller's contract. The proptests that called the unsafe loaders on arbitrary bytes are gone: they exercised what the contract excludes.
• StringIndex owned loads spot-check the rank invariant: the first key's value must be 0 and the rank-walk to len - 1 must succeed. A full walk measured 0.7 → 40 ms on the 479 823-word dictionary (58× the owned load), so a permutation of the ranks is deliberately not detected — it cannot violate memory safety, and key(id) now uses checked arithmetic on the blob-supplied outputs, answering None instead of wrapping.
• UnicodeSubsequence no longer allocates a per-byte rewind table: the rewind target is found by walking back over UTF-8 continuation bytes, the same answer with no allocation per query.
• Docs: README's install snippet says 0.9 (0.9.0 shipped saying 0.8; the release preflight now checks it); "never a full scan" and "2^-b by construction" scoped honestly in the usage guide and the site index, which no longer calls the core "from-scratch"; a note on Unicode semantics (scalar values; no normalisation, case folding or grapheme segmentation); the MPH load_mmap # Safety sections state the trusted-blob precondition alongside the immutability one; bench/compare.py shuffles its keys instead of handing every library the pre-sorted dictionary, and no longer claims to measure lookup latency; the examples/bench.rs probe stride is documented as prime (full coverage for every n below it), not merely odd.

Fixed

• Width-dependent casts: the fingerprint-table length in build_bits, the arena's offset count and its per-key offsets are converted with usize::try_from instead of as casts, so a header-supplied value that does not fit the platform's usize fails cleanly instead of truncating (mph_len and the side-byte count already did). Defence in depth rather than a live bug: a 32-bit build of the mph feature does not compile today — ptr_hash pulls sucds, which refuses any target that is not 64-bit — and the fst-only build contains none of this code. The fst-only build is checked for i686-unknown-linux-gnu.
• release.yml: a workflow_dispatch run built neither wheels nor the sdist, because both depended on the tag-only preflight and a skipped dependency skips its dependants; they now run unless preflight actually failed. Tags are gated on the full CI matrix (fmt, clippy, tests on Linux/macOS/Windows, Python 3.11–3.14, MSRV, coverage) through workflow_call, and the native wheels are installed and exercised on their runner before anything is published.

[0.9.0] — 2026-08-28

Changed

• from_bytes and load are now unsafe fn on PerfectHashIndex and CompactHashIndex (breaking). A function that is unsound for some input belongs behind unsafe fn, and these accept arbitrary bytes: the blob framing is validated and checksummed — accidental corruption still fails cleanly — but the embedded minimal perfect hash is an epserde region whose pilot table ptr_hash reads unchecked, and the fields that would bound that read are private to ptr_hash, so no validation on this side can reject a crafted blob. Upstream reached the same conclusion independently: epserde 0.13 made deserialize_full an unsafe fn, and PtrHash declined a checked try_index() for the same reason. StringIndex::from_bytes/load stay safe — fst validates its own structure and guarantees invalid input cannot violate memory safety. The Python bindings keep their signatures and state the contract in their docstrings.
• load_mmap is now an unsafe fn on all three indexes (breaking). The mapped bytes are borrowed, not copied, so a write to the file from any process while the index is alive is undefined behaviour — which is exactly why memmap2::Mmap::map is itself unsafe. Wrapping it in a safe function hid a precondition that ordinary safe code (another handle writing the same path) can violate, so the obligation is now stated in a # Safety section and the call sites carry it. load is unchanged and remains safe. The Python load_mmap keeps its signature — Python has no way to express the obligation — and documents the same contract in its docstring.
• CompactHashIndex hashes each key once instead of twice. Both of its hashes are now produced by a single pass over the key's bytes, bit-for-bit identical to the two functions it replaces (a golden test asserts the equality on 2 000 keys, so no stored blob changes meaning). Measured in isolation: 21.3 → 18.2 ns/key on real-word bigrams, 126 → 77 ns/key on 80-byte URI-like keys.
• The Python CompactHashIndex constructor releases the GIL while hashing. Items are pulled in 4 096-key chunks and hashed with the GIL dropped, so other Python threads keep running through what was previously one long GIL-held stretch; memory behaviour is unchanged (still 16 bytes per key, strings released as they are consumed).

Fixed

• build_bits rejects a bad fingerprint_bits before touching the iterator. Since 0.8.1 the width was validated after the input had been collected, so an invalid width consumed (and hashed) the entire iterator first — and never returned at all for an endless one.

Documentation

• The README's Rust examples are now compiled and run as doctests. They had never been checked by anything, so an API change could silently invalidate the first code a reader sees. A #[cfg(doctest)] item includes the file, which runs the snippets without pulling the prose into the API docs.
• The fingerprint's false-positive rate is described as a design rate from two uncorrelated hashes rather than as exact probability from independent ones, matching the more careful wording already in the code.
• The point-lookup table is re-measured on this release's code (min of 12 runs, idle machine, four seconds between runs). The whole session runs ~19% faster than the 0.8.0 one — the std::HashMap control moved with it — so the table now says which spreads were observed per row and warns that the ratio to HashMap is session-dependent (id_unchecked measured 2.2× here, 1.7× before) rather than presenting it as a constant.

[0.8.1] — 2026-08-27

Fixed

• CompactHashIndex no longer merges two distinct keys that collide in the 64-bit slot hash when their truncated fingerprints also tie. The 0.8.0 build deduplicated on (hash, fingerprint_bits-wide fingerprint), so at narrow widths a genuine hash collision had a 2^-fingerprint_bits chance of silently collapsing into one id — the repository's own pinned collision pair reproduces it at 1 bit (len() == 501 for 502 distinct keys). The collision side table now stores the full 64-bit second hash regardless of the table width (the build pairs were already 16 bytes, so build memory is unchanged), and the side probe runs before the fingerprint table, which could otherwise answer for a side key whose truncated bits tie its representative's. Two distinct keys now merge only by colliding in both 64-bit hashes at once (≈ 2^-128 per pair), independent of fingerprint_bits. The blob magic moves to BCH5 (same layout): a collision-free 0.8.0 BCH4 is bit-identical and still loads, one holding a side table is refused with a message naming the rebuild — its truncated side fingerprints cannot be widened without the keys.
• Side-table ids are validated on load. Both perfect-hash loaders now require the side ids to be exactly the tail range [m, n) — structurally, not via the checksums, which vouch for transport rather than construction. A malformed blob could previously hand CompactHashIndex::id() an id at or past len().
• Header-length arithmetic is checked for 32-bit targets. The side-table byte count is computed with checked_mul and mph_len converted with a checked cast, so a fabricated length fails cleanly instead of wrapping or truncating on a 32-bit build (the published wheels are 64-bit, but the crate is not).

Changed

• The Python CompactHashIndex constructor streams. Items are hashed to their 16-byte pair one at a time as they come off the iterator (under the GIL) and each string is released immediately, so a generator-fed build no longer materialises the whole corpus on the binding side. The other two constructors still collect — those indexes store the keys.

[0.8.0] — 2026-08-27

Added

• A 64-bit hash collision can no longer fail a build — any key set now builds. Both perfect-hash indexes build the MPH over one representative per distinct hash value; colliding leftovers get tail ids served from a tiny side table, consulted only after the main lookup has already missed, so an index without collisions (every index below ~10^8 keys, in practice) pays one predictable branch and nothing more. PerfectHashIndex stays exact even for collided keys (the side probe compares stored keys); CompactHashIndex matches side keys by fingerprint, leaving only a pair colliding in both hashes at once (2^-(64+fingerprint_bits) per pair) to collapse as if it were a duplicate. Previously such key sets failed the build permanently — the hash is deterministic, so no retry could ever help; at 1 G keys that was a ~2.7 % build-failure rate.
• Whole-payload checksum on the perfect-hash blobs. Owned load/from_bytes now verify a streaming 64-bit hash over everything after the header, so a flipped byte anywhere — MPH region, arena, fingerprint table, side table — is rejected at load instead of perturbing answers (or aborting inside epserde) later. This makes the accidental-corruption story uniform across all three indexes: every owned load verifies the entire blob. (load_mmap still trusts the mapped file; a crafted blob remains outside the contract — the hashes are public and deterministic.)
• CompactHashIndex::build/build_bits stream. One pass keeps a 16-byte (hash, fingerprint) pair per key and never materialises the strings, so building from a lazy iterator peaks at 16 × n bytes over the input regardless of key length — and sorting pairs instead of strings halved build time (249 → 120 ms at 1 M real-word bigrams, same-session A/B), putting it ~2× below std::HashMap's build. Lookup cost is unchanged (A/B: 245.2 vs 245.2 ns); PerfectHashIndex::id_unchecked measured 8 % faster (193 → 178 ns) and the verified PerfectHashIndex::id ~3 % slower (343 → 353 ns — the side-table entry branch, on the one path that already pays a full key compare). Serialised sizes are unchanged to two decimals (+4/+12 bytes per blob, not per key).
• Windows and macOS test jobs in CI. The release workflow already shipped wheels for both; their platform-specific paths (save's rename-over-existing, permissions, mmap) now run the test suite on every push, not just a cross-build on tags.

Changed

• Blob formats: PerfectHashIndex writes BMP4, CompactHashIndex writes BCH4 — the v3 layouts plus the side table and the payload checksum; BMP4 also drops the stored overflow_cap, which every load has recomputed from the arena since 0.7.1 anyway. 0.7 blobs (BMP3/BCH3, and BMP2 from 0.5/0.6) still load; BCH1/BCH2 remain refused. Older lexindex versions cannot read v4 blobs.
• save streams. All three indexes write the blob section by section through the atomic writer instead of assembling a serialised copy first, halving peak save memory; the bytes written are identical to to_bytes.

Fixed

• save no longer follows a symlink planted at its temporary path. The atomic write opened its sibling temp with File::create, which follows an existing symlink — so an attacker able to write to the target directory could pre-create a symlink at the predictable <name>.<pid>.<seq>.tmp and redirect the write, truncating an arbitrary file the process could reach. The temp is now opened O_CREAT | O_EXCL (create_new), which refuses any pre-existing path, symlink included; on a name collision the write retries with the next counter (bounded, so a hostile racer cannot spin it). On Unix the parent directory is now fsynced after the rename so the publish is durable across power loss, and an existing file's permissions are preserved rather than reset to the umask default.
• StringIndex owned loads verify the FST checksum. from_bytes / load handed the body to fst::Map::new, which checks length and version but not the stored CRC, so a corrupt owned blob could load and only fail — or mislead — on a later query. Owned loads now call Fst::verify(), an O(n) CRC scan, and reject a bad blob at load; load_mmap still skips it to keep mapping constant-time (a mapped file is trusted intact, as before).
• PerfectHashIndex never trusts the header's overflow_cap. It is now recomputed from the arena on every load, BMP3 included, so a blob whose framing checksum was forged alongside a crafted cap still cannot steer a query past the true remap length. CompactHashIndex stores no keys and cannot recompute it, so it remains a trust-your-own-blob format (documented).

Added

• Golden hash-stability tests. hash_key and fingerprint_bits pin exact outputs for a fixed key set (ASCII and multibyte), so a silently changed constant — which would make every previously saved MPH blob load wrong — fails CI loudly instead. Changing a hash is a format break that must bump the magic, not the table.

Changed

• Trust-boundary wording made precise in README.md and docs/design.md: lexindex framing is bounds-checked and StringIndex owned loads verify the FST CRC, but the perfect-hash indexes' embedded epserde MPH (which ptr_hash reads unchecked) stays a trust-your-own-blob payload — the header checksum and recomputed overflow_cap guard accidental corruption, not a crafted blob.

[0.7.0] — 2026-08-27

Fixed

• Non-member queries can no longer read ptr_hash's remap out of bounds — a debug-build panic and, in release builds, undefined behaviour (get_unchecked past the remap vector), present in every version since the minimal-perfect-hash indexes shipped. ptr_hash's minimal index() remaps raw slots ≥ n through an internal vector that only covers slots up to the last member-occupied one, and reads it unchecked; a non-member key whose raw slot lands in the trailing free zone — a zone that exists for a few percent of built indexes, depending on construction entropy — indexed past it. Surfaced by CI as a flaky assertion failed: rank < self.count_ones() in the new 4-bit fingerprint test (reproduced locally in 23 runs; the backtrace pins ptr_hash::pack::Packed::index → cacheline-ef::index_unchecked). Both indexes now record the remap's exact length at build time (overflow_cap — the largest member raw slot − n, plus one) and answer None outright for raw slots past it: those slots are provably free, so no member can live there. The repro loop went from 1 failure in 23 runs to 0 in 120; a regression test rebuilds until the zone occurs and asserts the guard. Lookup cost is unchanged (A-B against the 0.6.0 binary, std::HashMap control: PH 330 vs 331 ns, CHI 244 vs 244); builds pay ~1% for measuring the cap (one streamed index_no_remap pass over the members).
• id_unchecked is bounded too. It documents skipping the membership comparison, not the bounds, but it called mph.index() directly and so kept the defect above for any caller who passed a key that was not in fact a member. It now resolves through the same guarded path and returns a valid slot for any input.
• subsequence matches characters, not bytes. fst's Subsequence automaton advances one byte at a time, so a query character matched if its bytes appeared anywhere in order: subsequence("é") ([C3 A9]) matched "àΩ" ([C3 A0 CE A9]), which contains neither character. Every non-ASCII subsequence query was affected. Replaced with an automaton that rewinds a partial character on mismatch — exactly correct rather than conservative, because UTF-8's lead and continuation byte classes are disjoint.
• save is atomic. All three indexes write a sibling temporary and rename it into place, so a crash or a full disk leaves the previous file intact instead of a truncated one that still has a valid magic. load no longer copies the file buffer a second time.

Changed

• Blob formats: PerfectHashIndex writes BMP3, CompactHashIndex writes BCH3 — the previous layouts plus the overflow_cap field and a 32-bit check over the lexindex header. The check is not decoration: overflow_cap bounds an otherwise unchecked read, so a header that lost bytes in transit must fail loudly rather than steer queries.
• Blobs written before 0.7 are healed or refused, never loaded unbounded. A BMP2 (PerfectHashIndex) blob is healed: its arena holds every key, so the bound is recomputed exactly at load, costing O(n) hashes once. A BCH1/BCH2 (CompactHashIndex) blob stores no keys, cannot be repaired, and is refused with a message naming the fix — loading it would reinstate the out-of-bounds read. Rebuild those indexes on 0.7.
• Construction failure is an error, not a panic. IndexError::Build replaces the unwrap_or_else fallback path when both parameter sets fail. Loading now also rejects a header claiming more than u32::MAX keys (ids are u32) and cross-checks the deserialised MPH's own key count against the header's.
• Python: any iterable of keys, any os.PathLike path. Constructors took only sequences, so building from a generator raised TypeError; paths took only str, so a pathlib.Path had to be stringified at every call site. The stubs claimed list[str] where tuples were always accepted, and were widened to match reality.
• Honest wording for measured behaviour. Perfect-hash ids are documented as not reproducible across builds (ptr_hash's construction is randomised — measured on 50 k keys, ~53 % keep their id when the same key set is rebuilt); the fingerprint false-positive rate is documented as a design rate against random non-members, not a defence against chosen queries (both hashes are deterministic and unseeded); an epserde blob is documented as portable only across machines of the same endianness and pointer width.
• bench/compare.py timed each competitor's first import as part of its build, which flattered lexindex — imported at module scope. Builds are now the median of five runs after a warm-up.

Added

• A weekly sanitize workflow: AddressSanitizer over the whole suite (the class of defect fixed above is invisible to a normal cargo test) and Miri over the fst-only build. CI also runs cargo test --release, and a release preflight refuses a tag whose version does not match Cargo.toml, pyproject.toml, CITATION.cff and a dated CHANGELOG.md section.

[0.6.0] — 2026-08-27

Added

• Sub-byte fingerprints: CompactHashIndex::build_bits / fingerprint_bits= (1..=64 bits). The fingerprint table is bit-packed, so size is exactly fingerprint_bits/8 bytes per key on top of the ~0.27 B/key minimal perfect hash, and the membership false-positive rate is exactly 2^-fingerprint_bits. On the 479 823-word dictionary: 0.77 B/key at 4 bits (6.25% FP, 3.9× smaller than marisa-trie), 1.02 at 6 bits (1.56%), 1.77 at 12 bits (0.024%) — the existing byte widths keep their exact sizes and rates (1.27 / 2.27 / 4.27 B/key at 8 / 16 / 32 bits). CompactHashIndex stays below marisa-trie's 2.98 B/key at every width up to 21 bits. The advertised rate is measured, not assumed: 2 M random non-member probes landed at 6.253 % (z = +0.18) for 4 bits and 1.555 % (z = −0.83) for 6. Python: keyword-only fingerprint_bits= on the constructor plus a fingerprint_bits property; fingerprint_bytes keeps its byte semantics unchanged. The docs gained a width-choice table (rate priced per non-member probe).

Changed

• Blob format: CompactHashIndex now writes BCH2 (width field counts bits, table is bit-packed). 0.5.x BCH1 blobs still load — including zero-copy under mmap — because their byte-aligned fingerprints are bit-identical to the packed layout at 8× the width; 0.5.x cannot read the new BCH2 blobs, hence the 0.6.0 version bump. The default 8-bit path is not taxed by the generality: byte-aligned widths take a straight byte-copy fast path when building, and A-B against the 0.5.1 binary (12 alternated runs, std::HashMap control) put both build (222 vs 225 ms/1 M keys) and lookup (166.4 vs 166.0 ns) inside the control's noise. A 4-bit index answers id() as fast as an 8-bit one (86.9 vs 87.7 ns on the dictionary) and streams ids_of faster (47.6 vs 55.1 ns/key — half the table, better cache residency).

[0.5.1] — 2026-08-27

Added

• Citation metadata (CITATION.cff + .zenodo.json): GitHub shows "Cite this repository", and once the repository is enabled in Zenodo's GitHub integration, each release from the next tag on is archived with a DOI. Metadata validated against the CFF 1.2.0 schema.

Changed

• The minimal perfect hash is built with ptr_hash's default_compact parameters (λ=3.9). Tighter pilot buckets take the MPH from 2.41 to 2.17 bits/key on the 479 823-word dictionary: CompactHashIndex fp=1 drops 1.301 → 1.272 bytes/key (2.34× smaller than marisa-trie's 2.98), fp=2 2.301 → 2.272, PerfectHashIndex 13.625 → 13.596. Query time is unchanged (A-B in one binary at 480 k and 5 M keys, plus process-level A-B-A-B with a std::HashMap control); builds pay ~+10 ms per million keys (~3–4%) — a build-once/query-many trade. Compact construction can occasionally fail (pilot eviction chains grow too long), so it falls back to the default parameters automatically. Both parameter sets serialise the same type, so blobs stay compatible in both directions — no format change.

• Batch ids_of on PerfectHashIndex and CompactHashIndex streams its MPH lookups. Per-key id() walks hash → slot → verify serially, stalling on a cache miss at every step. The batch path now drives ptr_hash's index_stream (software-prefetched slot resolution) and prefetches the verification data (arena offsets and spans, fingerprint bytes) a fixed distance ahead, so the memory latency of key i+16 overlaps the compare of key i. Measured against the per-key loop in the same binary: PerfectHashIndex.ids_of 1.55× on the 479 823-word dictionary and 1.83× on 5 M real-word bigrams; CompactHashIndex.ids_of 1.10× / 1.21× (its fingerprint compare was already a single byte load, so only the slot stream and fingerprint prefetch help). The Python ids_of of both classes routes through the streamed core with the GIL released; misses still come back as None, pinned by tests on both sides.

• The rank-walk (id → key) picks each FST transition by binary search instead of a linear scan. Transitions are stored in increasing byte order, which makes their subtree-minimum ranks non-decreasing — the walk's invariant already guaranteed the order, the scan just wasn't using it. Near the root of a dictionary FST a node fans out ~50 ways, so the saving concentrates exactly where every reverse lookup must pass: StringIndex.keys_of over the whole 479 823-word dictionary drops from 775 to 423 ns/key (1.83×), measured back-to-back against the published 0.5.0 wheel on the same machine, with the reconstructed keys verified equal to the sorted dictionary in both. Everything reverse benefits — key, keys_of, dict(index) iteration.

• The speed benchmark (examples/bench.rs) now uses real dictionary-word bigrams, the same key generator as bench/scale.py, and refuses to run without a word list rather than substitute synthetic keys — the same rule bench/compare.py has always enforced. The old entity-000…N keys arrived pre-sorted and hash-degenerate, flattering every build time. On real keys the README table moved both ways and was re-measured whole (one session, min of 12 runs): every build reads higher because sorting real input is part of the job, while the lookup gap over std::HashMap widened from ~1.25× to ~1.5× (realistic short keys make the byte-wise FNV hash cheaper relative to SipHash). A CompactHashIndex::id row was added — measured ~238 ns, it beats HashMap while keeping its fingerprint membership check.

Fixed

• The hash-collision build error no longer suggests a retry that cannot work. Both MPH builds said "64-bit key-hash collision; rebuild or use StringIndex" — but the hash is deterministic and unseeded (that is what makes a serialised MPH reloadable), so rebuilding the same key set fails identically, forever. The message now says so and points at StringIndex or changing the keys.

Documentation

• The collision odds behind "build fails on a 64-bit hash collision" are now quantified instead of called astronomically rare: n(n-1)/2^65, computed exactly (Maxima and PARI/GP agreeing) — 6.2×10⁻⁹ for the dictionary, 2.7×10⁻⁶ at 10 M keys, 2.7×10⁻⁴ at 100 M, ~2.7% at 1 G. Honest below ~10 M; a real design consideration at 10⁸–10⁹, where StringIndex has no such failure mode.

• The 256^-k false-positive rate is now statistically verified, not just asserted. On the 0.5.0 code, dictionary members with two non-member populations: 2 M random strings measured 0.384% at fp=1 (z = −1.5 against the exact 0.390 625%) and 33/2 M at fp=2 (z = +0.5); 50 000 held-out real words measured 0.310% (z = −2.9). At or below theory in every case — the advertised rate is a ceiling in practice.

• The usage guide now explains what limit buys — and what it cannot ("What limit buys"), replacing 0.5.0's single headline number with the measured behaviour. The speedup is the work not done, so it spans three regimes: prefix/range scale with matches ÷ limit (measured ~3 000× for prefix("s", limit=10) on an idle machine — the 669× in the 0.5.0 notes was the same query on a loaded one, i.e. conservative), subsequence gains ~80× because early stop saves the expensive traversal itself, and fuzzy gains only ~6× because the eagerly-built Levenshtein automaton is a fixed cost limit cannot skip. Also documented: the ~3 µs per-call floor (asking for 1 match costs the same as 10), and that consuming all matches gains nothing by construction.

[0.5.0] — 2026-08-26

Upgrading: rebuild any saved PerfectHashIndex blob — its format changed (see below) and 0.5.0 rejects the old one rather than misreading it. StringIndex and CompactHashIndex blobs load unchanged. Rust consumers need a 1.85 toolchain. Python users need nothing beyond pip install -U.

Added

• Bounded and lazy queries on StringIndex. Python prefix / range / fuzzy / subsequence take a limit, and Rust gains prefix_iter / range_iter / fuzzy_iter / subsequence_iter returning lazy iterators. An autocomplete asking for ten matches now walks ten keys instead of materialising every match: on the 479 823-word dictionary, prefix("s", limit=10) is 0.026 ms against 17.59 ms — 669× faster — and allocates 10 tuples rather than 45 064. prefix("a", limit=10) is 310×, fuzzy("hello", 2, limit=5) 3.7×.
• The eager forms are now .collect() over the lazy ones, so there is one walk implementation rather than two. Measured with both variants compiled into one binary and alternated A-B-A-B (the machine was loaded, and in-process alternation is what makes the comparison meaningful): the change is not a regression — five runs gave −7.4 %, −0.3 %, −2.7 %, −1.6 %, −1.9 %.

• fuzzy_iter still builds its automaton eagerly, so a too-large edit distance errors up front rather than on first use.

• lexindex.__version__ in the Python package, read from the installed distribution metadata (so it cannot drift from pyproject.toml) with a 0.0.0+unknown fallback when imported from a source tree that was never installed.

Changed

• PerfectHashIndex is 23% smaller: its key arena now uses 4-byte offsets. The arena addresses each stored key by an offset into a flat buffer, and those offsets were u64 — 8 bytes per key to address a 4.9 MB buffer. They were the single largest part of the structure: 8.0 of its 17.625 bytes per key on the 479 823-word dictionary. Offsets are now 4 bytes, taking the index to 13.625 B/key (−22.7%).
• The width is chosen per arena, not capped. An arena above 4 GiB still gets 8-byte offsets, recorded in a header byte, so no corpus that built before will fail to build now.
• Lookups got faster, not slower. Halving the offset table halves the cache footprint of the two reads every verified lookup makes, which more than pays for the width branch — and the branch is on a field fixed for the life of the index, so it predicts. PerfectHashIndex::id, the only path that touches the arena, measured −3.7% (386.8 → 372.4 ns, min of 12 runs on an idle machine). The controls that cannot touch the arena — id_unchecked, StringIndex, std::HashMap, std::BTreeMap — moved +0.0%, +0.2%, +0.7% and −0.3%, which is what makes the −3.7% readable as the change rather than the machine.
• Building is cheaper too, since the offset table is assembled in memory before it is written: the peak RSS of a PerfectHashIndex build on the dictionary falls a further 38.1 → 29.9 MB on top of the saving below, for ~87 → 29.9 MB (−66%) across the release.

• Breaking: the PerfectHashIndex blob magic is now BMP2; blobs written by 0.1–0.4 must be rebuilt. StringIndex (BIX4) and CompactHashIndex (BCH1) blobs are untouched, as are their sizes.

• build no longer copies the corpus to sort it. All three constructors collected their input into an owned Vec<String> before sorting and deduplicating, even though every key is copied again into the structure being built. They now sort the caller's items in place, comparing through AsRef<str>. PerfectHashIndex additionally held a third copy: its slot table cloned each key only for the arena to copy it once more, and now borrows instead. On the 479 823-word dictionary (peak RSS of the build itself, one process per variant, order alternated across four pairs; timings A-B-A-B with both implementations in one binary):

	peak RSS	build
StringIndex	29.9 → 8.0 MB (−73%)	1.04×
PerfectHashIndex	72.5 → 38.1 MB (−47%)	1.99×

Rust callers get the same saving: passing &[String] or an iterator of &str now costs one pointer per key instead of a copy of the corpus. Ids, key order and every serialised size are unchanged — this only removes intermediates. - test_build_releases_the_gil grew its key count: at 400 000 keys the build now takes 49 ms rather than 268, which tripped the test's own "too fast to tell anything" guard. It refused to pass vacuously, which is what that guard is for.

• The Python bindings borrow the caller's strings instead of copying them. The constructors and ids_of read their keys as PyBackedStr — a view into the Python str — where they previously extracted an owned Vec<String>. build already copies the keys it keeps, so that intermediate vector was pure overhead: on the 479 823-word dictionary the peak RSS of a build drops from 44.6 MB to 29.9 MB (−33%), and the build itself is 1.08× faster, ids_of 1.05× (both implementations compiled into one extension and alternated A-B-A-B; four independent process pairs for the memory figure, which agreed to within 0.3 MB).

• No API change. PyBackedStr accepts exactly what String did; the observable contract — accepted types, rejected types and every error message — was diffed against a build of the previous code and is identical. This change left every serialised size untouched; the only size that moves in this release is PerfectHashIndex, from the arena change above.

• PerfectHashIndex.key / keys_of no longer copy each key twice. Its keys live in an arena, so key returns a &str; both methods then copied that into a String only for PyO3 to copy it again into a Python str and drop it. They now build the Python string straight from the arena slice. keys_of is 1.29× faster (250 -> 194 ns/key on the 479 823-word dictionary, A-B-A-B in one extension) and allocates nothing per key; the single-key key is 1.03×, the rest of its cost being the Python call itself. keys_of still runs its lookups under Python::detach — only the string construction, which needs the GIL either way, happens with it held.

• The Python bindings release the GIL (Python::detach) around building, bulk queries (prefix / range / fuzzy / subsequence), batch lookups (ids_of / keys_of) and persistence (save / load / load_mmap / to_bytes / from_bytes), so a threaded caller keeps making progress instead of freezing the interpreter. Previously a background thread got 1 scheduler tick during a 268 ms build of the 479 823-word dictionary; it now runs throughout.

• Single-key accessors (id, key, contains, id_unchecked, successor, predecessor, __len__) deliberately keep the GIL: they take well under a microsecond, so releasing and reacquiring it would cost more than the work it protects. Their code is untouched, and this change altered no serialised byte of any index.

• The minimum supported Rust version is now 1.85, declared as rust-version in Cargo.toml and enforced by a CI job that derives its toolchain from that field, so the declaration cannot drift from what is actually built. The crate moved to edition 2024, whose floor is exactly 1.85; cargo fix --edition required no source changes in any feature configuration, so the only user-visible effect is the toolchain requirement itself.

• Rust consumers on a toolchain older than 1.85 must upgrade — cargo will refuse to build lexindex rather than fail obscurely.
• Python users are unaffected. The published wheels are abi3 and carry no toolchain requirement; requires-python is unchanged at >=3.11.

[0.4.0] — 2026-07-06

Added

• Ordered navigation on StringIndex — successor(query) (smallest key >= query) and predecessor(query) (largest key <= query), each O(query length) by seeking the FST (no scan), plus lazy iteration: for key, id in index in Rust StringIndex::iter() decodes one key per step by the rank-walk, so it never materialises the whole key set the way prefix("") would.
• Batched lookups — ids_of(keys) and keys_of(ids) on StringIndex and PerfectHashIndex, plus ids_of(keys) on CompactHashIndex. Each loops in Rust and crosses the Python↔Rust boundary once instead of per key, so a bulk string → id / id → string mapping avoids the per-call FFI overhead. Returns a list aligned with the input, None where a key/id is absent. Named ids_of/keys_of (not keys) so a class is never mistaken for a mapping — dict(index) builds {key: id} from the iterator instead.
• musllinux_1_2 wheels (x86_64 + aarch64) for Alpine / musl-based containers, alongside the existing manylinux, macOS, and Windows wheels.
• Scale benchmark (bench/scale.py) measuring build time, peak memory, and lookup latency from 1M to 100M real keys.

Fixed

• CompactHashIndex::from_bytes guards the fingerprint-table length check with a checked multiply, so a corrupt blob with a fabricated huge n fails cleanly instead of overflowing usize (a debug-build panic; release builds already wrapped to a clean error). Documented the trust boundary shared by both minimal-perfect-hash blobs: from_bytes / load validate the lexindex framing but deserialise the embedded MPH via epserde, which does not bound-check a corrupted MPH region — feed only blobs you produced (the same contract as load_mmap). StringIndex blobs are fully validated and unaffected.

Testing

• Property-based tests (proptest, dev-dependency only): the rank-walk id ↔ key round-trip over random prefix-nested and multibyte key sets; the PerfectHashIndex bijection onto [0, n); CompactHashIndex never false-negatives a member; and every from_bytes deserialiser rejects arbitrary or (for lexindex-owned bytes) single-byte-flipped input cleanly — never panics or reads out of bounds. Line coverage rose to 97.0%.

[0.3.0] — 2026-07-05

Added

• CompactHashIndex — the smallest string → dense id map, and smaller than any installable alternative. A minimal perfect hash (ptr_hash) plus a k-byte fingerprint per key, storing no keys at all. On the real /usr/share/dict/words (479 823 words) it serialises to 1.30 bytes/key at fingerprint_bytes=1 and 2.30 at 2 — 2.3× smaller than marisa-trie (2.98) and far below every trie benchmarked. The trade-offs are explicit: membership is probabilistic (a non-member reads as present with probability 256^-fingerprint_bytes — measured 0.36 % at 1 byte, 0.001 % at 2) and there is no reverse id → key (the keys are not stored). Reach for it when a fixed vocabulary's footprint is paramount and rare false positives are acceptable; use PerfectHashIndex for exact membership + reverse, or StringIndex for ordered/fuzzy queries. Exposed to Python as CompactHashIndex(items, fingerprint_bytes=1) with id / id_unchecked / contains / to_bytes / from_bytes / save / load / load_mmap; in Rust behind the default mph feature.

Changed

• StringIndex dropped its stored reverse map — id → key is now reconstructed from the FST by a rank-walk. Each id is the key's rank, i.e. the FST's output, so key(id) walks the automaton from the root, at each node taking the last transition whose accumulated output stays ≤ id, and returns the path once the outputs sum to exactly id (O(key length), no auxiliary structure). This deletes the front-coded reverse dictionary added in 0.2.0: the serialised blob is now just [magic][fst]. The effect on real-world size is large — on /usr/share/dict/words the StringIndex blob shrinks from 12.61 to 5.95 bytes/key (−53 %), because 0.2.0's front-coded map only reached its advertised "~6 B/key" on structured keys that share long prefixes, not on a natural vocabulary. Full prefix / range / fuzzy / subsequence are retained.
• Breaking: the on-disk blob magic is now BIX4; StringIndex blobs written by 0.1.x / 0.2.0 must be rebuilt. PerfectHashIndex blobs are unchanged.
• Benchmarks are now measured on real English words, not a synthetic entity-{i} catalog. Sequential structured keys collapse the FST to a near-regular automaton and report a misleading ~0 bytes/key; bench/compare.py refuses synthetic keys and compares size and build against marisa-trie, DAWG and datrie on /usr/share/dict/words.

[0.2.0] — 2026-07-05

Added

• Zero-copy load_mmap on StringIndex and PerfectHashIndex (new default mmap feature, backed by memmap2): memory-map a saved blob and borrow the index from the mapped pages instead of reading it into RAM, so a multi-gigabyte index loads instantly and its pages are shared across processes. StringIndex maps the whole blob (FST + front-coded dictionary); PerfectHashIndex maps the key arena (the bulk) and reads only the small MPH into memory. Exposed to Python as StringIndex.load_mmap / PerfectHashIndex.load_mmap. Reads are byte-wise (no alignment requirement); the mapped file must stay immutable while an index borrows it. --no-default-features (the fst-only build) omits it.
• MkDocs documentation site at https://ilgrad.github.io/lexindex/ (Material + mkdocstrings API reference), and a mmap_zero_copy example that times the owned load against the zero-copy load_mmap.
• CI now enforces a 95% line-coverage floor (cargo llvm-cov) on the Rust core.

Changed

• StringIndex's reverse map (id → key) is now a front-coded string dictionary instead of a flat arena of raw bytes + one 8-byte offset per key. Because ids are the sorted rank, keys are stored sorted and delta-encoded against their bucket predecessor ((shared-prefix length, suffix), one pointer per 8-key bucket), so on a structured sorted catalog the serialised StringIndex blob shrinks from ~27 to ~6 bytes/key — below the raw key bytes. PerfectHashIndex (unordered MPH slots, which cannot share prefixes) keeps the flat arena and is unchanged.
• Breaking: StringIndex::key(id) now returns Option<String> (reconstructed on the fly) rather than Option<&str>; the Python StringIndex.key is unaffected (still returns str | None).
• Breaking: the on-disk blob magic is now BIX2; StringIndex blobs written by 0.1.0 must be rebuilt (PerfectHashIndex blobs are unchanged).

[0.1.0] — 2026-06-28

First public release — compact, immutable string<->id indexes for huge catalogs; a standalone Rust + Python library that also pairs with betula-cluster (map string ids to cluster ids and back).

Added

• StringIndex — ordered, FST-backed index: exact string <-> id, plus prefix, range, fuzzy (bounded Levenshtein edit distance), and subsequence iteration — all automaton-driven over the FST, never a full scan. Serialises to a flat, relocatable blob (save / load / to_bytes / from_bytes) with fully length- and offset-validated parsing (safe on untrusted input).
• PerfectHashIndex — minimal-perfect-hash dictionary (ptr_hash): verified-membership id, a faster id_unchecked for closed vocabularies (~1.25× faster than std::HashMap on point lookup), reverse lookup, and persistence (save / load) via epserde, keyed on a version-stable hash (FNV-1a + splitmix64) so a serialised MPH reloads and queries identically on any build.
• Python bindings (PyO3 abi3 extension, CPython 3.11+): pip install lexindex, zero runtime dependencies, typed (py.typed + stubs).
• Feature gating — mph (default) provides PerfectHashIndex (pulls ptr_hash + epserde); --no-default-features is an fst-only build, free of the informational RustSec advisories on the ptr_hash dependency tree. fst's levenshtein is always on for fuzzy search.
• Benchmark — cargo run --release --example bench compares both indexes against std::HashMap / BTreeMap (build time, lookup latency, serialised size).