lexindex

Compact, immutable string↔id indexes for huge catalogs, with a Rust core and Python bindings. Build once over a set of strings (entity names, document keys, vocabulary terms, cluster labels); query many times. Pairs naturally with betula-cluster — map string ids to cluster ids and back — but stands on its own.

Three complementary, build-once / query-many structures — pick by what you need to ask:

• StringIndex — an ordered index backed by a finite-state transducer (fst). Exact string → id and id → string, plus prefix, range, predecessor / successor (nearest key ≤ / ≥ a query), fuzzy (bounded Levenshtein edit distance), subsequence, and lazy full iteration — all driven by automata over the FST, with no separate key list to scan (exact/prefix/range seek directly; a broad fuzzy or subsequence pattern may still traverse most of the automaton) — in a compressed, serialisable, memory-mappable form. The only structure here that answers ordered and typo-tolerant queries. Use it for autocomplete, fuzzy search, browse, and ordered scans of a large catalog.
• CompactHashIndex — the smallest string → dense id map: a minimal perfect hash (ptr_hash) plus a small fingerprint per key, storing no keys at all. 1.27 bytes/key on real dictionary words — 2.3× smaller than marisa-trie, down to 0.77 bytes/key at a 4-bit fingerprint (fingerprint_bits=4, 6.25% false-positive rate) — below every trie benchmarked (see Benchmarks) — at the cost of probabilistic membership (a tunable 2^-bits false-positive rate) and no reverse lookup. Use it when a fixed vocabulary's footprint is paramount and rare false positives are acceptable.
• PerfectHashIndex — a minimal-perfect-hash dictionary with verified membership (id) and reverse lookup (key); the arena stores full keys, so it is exact but larger. For a known-closed vocabulary, id_unchecked skips the membership comparison and is faster than std::HashMap. Use it as a fixed-vocabulary token↔id map on a hot path when you need exact membership and id → key.

All three assign dense ids in [0, n) and serialise to a flat blob (save / load, or zero-copy load_mmap) — build once, persist, then reload and query many times. All are immutable after building. The mph feature (on by default) provides the two hash indexes; --no-default-features is fst-only and the only configuration that builds for 32-bit targets, wasm32-unknown-unknown included — the minimal perfect hash's dependency chain requires a 64-bit pointer width, and a 32-bit build with mph says so at compile time.

Python

pip install lexindex

from lexindex import CompactHashIndex, PerfectHashIndex, StringIndex

idx = StringIndex(["apple", "apricot", "banana", "cherry"])
idx.id("banana")             # 2  (sorted rank)
idx.key(0)                   # "apple"  — reconstructed from the FST, no stored reverse map
idx.prefix("ap")             # [("apple", 0), ("apricot", 1)]
idx.fuzzy("aple", 1)         # [("apple", 0)]  — typo-tolerant
idx.successor("ba")          # ("banana", 2)   — nearest key >= query
idx.predecessor("ba")        # ("apricot", 1)  — nearest key <= query
list(idx)                    # [("apple", 0), ...]  — lazy iteration in sorted order
idx.ids_of(["apple", "x"])   # [0, None]  — batched: one FFI call, not one per key
idx.save("catalog.bix")      # persist; StringIndex.load("catalog.bix") reloads it

c = CompactHashIndex(["GET", "POST", "PUT", "DELETE"])  # smallest string->id (~1.3 B/key at scale;
#   fingerprint_bits=4 halves that to ~0.8 at a 6.25% false-positive rate)
c.id("POST")                 # dense id in [0, n); probabilistic membership, no id->key
c.id_unchecked("POST")       # fastest lookup for a known-closed vocabulary

d = PerfectHashIndex(["GET", "POST", "PUT", "DELETE"])
d.id("POST")                 # dense id in [0, n); membership verified, returns None if absent
d.key(d.id("POST"))          # "POST"  — exact reverse lookup (keys stored)

No runtime dependencies; a single abi3 wheel covers CPython 3.11+. See examples/quickstart.py for all three indexes end to end, and the documentation site.

Pairs with betula-cluster

lexindex owns the string id ↔ dense id mapping; betula-cluster clusters the numeric rows. Use the lexindex dense id as the embedding-matrix row index and you can go both ways — string id → cluster and cluster → string ids:

idx = PerfectHashIndex(doc_ids)                  # string id <-> dense [0, n) id
matrix[idx.id(doc_id)] = embedding[doc_id]       # row index == lexindex id
labels = betula_cluster.fit_predict(matrix, n_clusters=k)
cluster = labels[idx.id("doc-00042")]            # string id -> cluster
members = [idx.key(int(r)) for r in (labels == cluster).nonzero()[0]]  # cluster -> string ids

Runnable: examples/bridge_clustering.py.

Rust

[dependencies]
lexindex = "0.11"
# fst-only (drop the ptr_hash dependency):
# lexindex = { version = "0.11", default-features = false }

Usage

use lexindex::StringIndex;

let idx = StringIndex::build(["apple", "apricot", "banana", "cherry"])?;

assert_eq!(idx.id("banana"), Some(2));     // string → id (sorted rank)
assert_eq!(idx.key(0).as_deref(), Some("apple")); // id → string
assert!(idx.contains("cherry"));

// prefix / range iteration, lexicographically ordered
let fruit: Vec<_> = idx.prefix("ap").into_iter().map(|(k, _)| k).collect();
assert_eq!(fruit, ["apple", "apricot"]);

// typo-tolerant fuzzy lookup (Levenshtein edit distance ≤ 1) and subsequence match
let near: Vec<_> = idx.fuzzy("aple", 1)?.into_iter().map(|(k, _)| k).collect();
assert_eq!(near, ["apple"]);
let sub: Vec<_> = idx.subsequence("ap").into_iter().map(|(k, _)| k).collect();
assert_eq!(sub, ["apple", "apricot"]);

// serialise to a flat blob, then reload — or `load_mmap` to borrow it zero-copy from the file
idx.save("catalog.bix")?;
// SAFETY: nothing may modify the file while a mapped index borrows it (see `load_mmap`).
let idx = unsafe { StringIndex::load_mmap("catalog.bix") }?; // no read into RAM; pages shared
# drop(idx);
# std::fs::remove_file("catalog.bix").ok();
# Ok::<(), lexindex::IndexError>(())

use lexindex::PerfectHashIndex;            // requires the default `mph` feature

let dict = PerfectHashIndex::build(["GET", "POST", "PUT", "DELETE"])?;
let id = dict.id("POST").unwrap();             // fastest exact lookup, dense id in [0, n)
assert_eq!(dict.key(id), Some("POST"));
assert_eq!(dict.id("PATCH"), None);            // membership is verified, not just hashed

// persist the MPH and reload it (the dense ids are preserved across save/load)
dict.save("verbs.bmp")?;
// `load` is unsafe: the embedded perfect hash cannot be validated, so only blobs this library
// wrote are in contract. See "Design notes" below.
let dict = unsafe { PerfectHashIndex::load("verbs.bmp") }?;
assert_eq!(dict.id("POST"), Some(id));
# std::fs::remove_file("verbs.bmp").ok();
# Ok::<(), lexindex::IndexError>(())

use lexindex::CompactHashIndex;           // requires the default `mph` feature

// The smallest string->id map: an 8-bit fingerprint/key ⇒ ~1.3 B/key, ~0.4% membership
// false-positive (build_bits(keys, 4) ⇒ ~0.8 B/key at 6.25%).
let dict = CompactHashIndex::build(["GET", "POST", "PUT", "DELETE"], 1)?;
let id = dict.id("POST").unwrap();             // Some(slot); a non-member may rarely read as present
assert!(dict.contains("GET"));
let raw = dict.id_unchecked("POST");           // no fingerprint check — for a known-closed vocabulary
assert_eq!(raw, id);
// no key(id): CompactHashIndex stores no keys. Use PerfectHashIndex when you need id → string.
# Ok::<(), lexindex::IndexError>(())

Design notes

• StringIndex is the FST alone — id → key is reconstructed by a rank-walk, with no stored reverse map. Ids are the sorted rank of each key, which is exactly the FST's output value, 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. That is O(key length) and needs no auxiliary structure, so the serialised blob is just [magic "BIX4"][fst] — half the size of the 0.2.0 front-coded layout on real words (12.6 → 5.95 B/key) and simpler to reason about. from_bytes/load validate the magic, verify the FST's stored checksum and spot-check the rank invariant (first value 0, rank-walk to n - 1 succeeds — a full walk would cost 58× the load), so a truncated or corrupted owned blob is rejected at load rather than queried; load_mmap skips that O(n) scan to keep mapping constant-time, so a mapped file is trusted to be intact.
• No Unicode normalisation, case folding, collation or grapheme segmentation. Keys and queries are compared as UTF-8 byte strings, and "character" means a Unicode scalar value: é and e\u{301} are two different keys, an emoji ZWJ sequence is several characters to fuzzy and subsequence, and ordering is byte order, not any locale's. Normalise (NFC/NFKC, casefold) before building and before querying if the application needs it.
• Perfect-hash ids are not reproducible across builds. ptr_hash's construction is randomised, so building the same key set twice assigns different slots — measured on 50 k keys, only ~53 % of them keep their id. Ids are stable across save/load of one built index, so persist the blob, not the key list, whenever an id is written down anywhere else. StringIndex ids are the sorted rank and are reproducible by construction.
• CompactHashIndex stores no keys — only a minimal perfect hash and one small fingerprint per slot. id(key) hashes the key to a slot (the MPH), then compares the key's b-bit fingerprint — from a second hash with a different basis and multiplier — against the stored one; a match is a hit. The two hashes are uncorrelated for well-distributed keys, so a non-member survives both with probability about 2^-b: a design rate measured against, not a proof, and no guarantee at all against queries chosen by an adversary (both hashes are deterministic and unseeded). It is the tunable false-positive rate (fingerprint_bits ∈ 1..=64, bit-packed). Dropping the key arena is what takes it below marisa-trie; the price is that membership is probabilistic and there is no id → key. The blob is [magic "BCH5"][n][fp_bits][overflow_cap][mph_len][side_len][payload][check][mph][bit-packed fingerprints][side] — the payload hash is verified on owned loads, so a corrupted blob fails cleanly. Its build streams: only a 16-byte (hash, second hash) pair is kept per key, never the strings. 0.7 blobs (BCH3) still load, as does a collision-free 0.8.0 BCH4 (bit-identical); a BCH4 holding a side table is refused — its side fingerprints were truncated — with a message naming the rebuild. 0.5/0.6 blobs (BCH1/BCH2) are refused: they predate the recorded remap bound and store no keys to recompute it from, so loading one would reinstate an out-of-bounds read — rebuild instead.
• PerfectHashIndex keys the MPH on a deterministic 64-bit hash of each string (so queries take &str without allocating), then verifies the hit against the stored key — an MPH returns a slot for any input, so verification is what turns it into a real membership test, and the stored keys give exact id → key. Two distinct keys colliding in the 64-bit hash cannot fail the build: the MPH is built over one representative per distinct hash value and the colliding leftovers are served — still exactly — from a tiny side table consulted only after the stored-key comparison has missed, so the hot path pays nothing. The expected number of colliding pairs is n(n-1)/2^65 ≈ 2.7×10⁻⁸ at 1 M keys, 2.7×10⁻⁴ at 100 M — the table is almost always empty. The hash is version-stable (FNV-1a
  • a splitmix64 finalizer, not std's DefaultHasher), so a saved MPH (the ptr_hash structure serialised via epserde, alongside the arena) reloads and queries identically on any build — the precondition for persistence. CompactHashIndex shares the same version-stable slot hash plus a second, uncorrelated one for the fingerprint, and resolves hash collisions the same way — its side table keeps the second hash at its full 64 bits whatever fingerprint_bits is set to, so only a pair colliding in both 64-bit hashes at once (≈ 2^-128 per pair) would merge.
• Zero-copy load_mmap (the default mmap feature, memmap2) memory-maps a saved blob and borrows the index directly from the mapped pages — no read into RAM, so a multi-gigabyte index is ready instantly and the OS shares its pages across processes. StringIndex maps the whole FST; CompactHashIndex maps its fingerprint table; PerfectHashIndex maps the key arena (the bulk) and reads only the tiny MPH into memory. Every read is byte-wise, so there is no alignment gotcha. It is an unsafe fn — deliberately, since the mapped bytes are borrowed rather than copied, so a write to the file from any process while the index is alive is undefined behaviour and nothing in the library can check for it. lexindex blobs are written once and never updated in place, so publishing new versions under new paths discharges the obligation; the Python binding, which has no way to express it in the type system, states the same contract in its docstring.
• Loading a perfect-hash index is unsafe too — from_bytes and load, not just load_mmap. The blob framing is validated and checksummed, so accidental corruption is rejected cleanly, but the embedded MPH is an epserde region whose pilot table ptr_hash reads unchecked, and the fields that would bound that read are private to ptr_hash — no amount of checking downstream can make a crafted blob safe. A function that is unsound for some input belongs behind unsafe fn, so both perfect-hash indexes say so in their signatures rather than in a doc paragraph. Upstream agrees: epserde 0.13 made deserialize_full an unsafe fn, and PtrHash declined a checked try_index() on the same grounds. StringIndex keeps safe from_bytes/load — fst validates its own structure and guarantees invalid input cannot violate memory safety.
• mph is opt-in-by-default: with --no-default-features the crate depends only on fst (and keeps StringIndex). Enabling mph pulls ptr_hash and its dependency tree, which currently carries a few informational RustSec advisories (unmaintained / unsound) on transitive crates — cargo audit reports them as warnings, not vulnerabilities. The fst-only build is free of them.

Benchmarks

Serialised size on real English words

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

Two honest crowns, both scoped to what is measured above — libraries a Python or Rust project can actually install. Research-grade C++ (CoCo-trie, XCDAT, PDT, SuRF) has no bindings to benchmark and is not claimed against. CompactHashIndex is the smallest string → dense id map here — 2.3× below marisa-trie at the default 8-bit fingerprint, 3.9× at 4 bits — when you can accept a bounded false-positive rate (about 2^-fingerprint_bits by design — the fingerprint comes from a second hash, uncorrelated with the slot hash for well-distributed keys — measured 6.2530 % at 4 bits and 1.5553 % at 6 over 2 M non-member probes, z = +0.18 / −0.83 against theory; ≈0.4 % at 8 bits, ≈0.0015 % at 16) and don't need id → key. It is not a security primitive: both hashes are deterministic and unseeded, so an adversary who chooses the queries can find false positives at will. It stays below marisa's 2.98 B/key at every width up to 21 bits — the width guide tables the trade-off. StringIndex is the only structure that answers fuzzy and range queries at all, at 4× below a plain DAWG. marisa-trie remains the pick when you need exact membership and ordering and the smallest such index — lexindex doesn't claim that particular cell (see below for why).

Against other Rust string indexes

marisa-trie is C++. Among ordered string indexes you can cargo add, none is smaller than StringIndex — the double-array tries trade space for lookup speed, and no succinct LOUDS trie (marisa / XCDAT / CoCo-trie-style) exists in Rust to depend on. So StringIndex at 5.95 B/key is the smallest ordered string → id index available in pure Rust — second only to a C++ library, and the only one of them that does fuzzy and range. Same real words:

_{Measured with crawdad 0.4, yada 0.5, fst 0.4 over the same word list; size = serialised bytes (serialize_to_vec().len()) ÷ key count. Not lexindex dependencies — reproduce in a throwaway crate.}

Reaching marisa's 2.98 needs its recursive succinct-trie label nesting, which the byte-oriented fst automaton is ~1.6× away from by construction (even a bare fst::Set, which stores no ids at all, is 4.85) — so beating it on the ordered index means reimplementing marisa from scratch, not a bounded tweak. CompactHashIndex takes the size crown the other way: by dropping the keys entirely.

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

Every size above is one corpus at one n, and the ranking is stable across neither. The reason is structural: a trie's size depends on how much the keys share, and a fingerprint index's does not. The same structures over three corpora built from the same word list, one process per cell (local/positioning.py):

At 10 M the trie numbers move again — marisa 4.14 on random pairs against 2.36 on the grid, StringIndex 12.44 against 2.00 — while CompactHashIndex stays at 1.27 and the bare MPHF at 0.27, because their size is a function of n and the fingerprint width alone. The grid is a full cross product and is the most favourable set a trie can be handed; it is what the scale table below uses, and on it StringIndex at 0.68 B/key undercuts even a keyless perfect hash. Treat that as the ceiling of what shared structure can buy, not as a headline.

So, in decision order:

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

Lookup speed from Python, against dict and marisa-trie

local/latency_py.py — one process per corpus, every structure built up front, the seven lookup forms rotated inside each round so none keeps the position that pays to warm the probe list, minimum over 11 rounds. Ratios are quotients of the minima against dict on the same probe set, which is the quantity that reproduces: two independent runs agree to 7.3 % at worst and 1.0 % at the median (grid: 2.1 % / 0.8 %).

Below 1.00× is faster than dict. So: a CompactHashIndex answers a present key in about two-thirds the time of a dict and a missing one in about a third, batched ids_of in a quarter to a third — while occupying 1.27 bytes per key on disk against the dict's 71–95 bytes per key in RAM. PerfectHashIndex trades level with dict on members and wins on misses; marisa-trie costs 1.9–4.3× and StringIndex 1.1–2.6×, and both swing with the corpus exactly as their sizes do. Absolute figures for the word corpus, for scale: dict 327.9 ns, CompactHashIndex 200.8, its ids_of 102.0, marisa 605.8.

_{Read the ratios, not the absolutes. This machine drifts 3–11 % within a single run and 13.7 % over twelve rounds while idle — measured with a cache-resident integer loop that touches no memory, whose time climbs monotonically as the CPU heats — so absolute nanoseconds here are a statement about one laptop's thermal envelope. The ratios divide that out. Two caveats in dict's favour, both deliberate: CPython caches a string's hash inside the object, so a repeated probe over the same str skips rehashing where lexindex hashes the bytes every call (~23 ns of the gap at 1 M); and every column pays the same per-call binding overhead, which flatters the slower ones. The first run of a corpus, taken minutes after a build, disagreed with the two settled runs by up to 24 % on two cells and is excluded — the machine needs to settle, and cross-run agreement is what says when it has.}

Point-lookup latency vs the standard library

cargo run --release --example bench — 1 M real dictionary-word bigrams (word_i.word_j, the same key generator as bench/scale.py; mean key 10.9 bytes). Keys are never synthetic entity-000…N sequences — those arrive pre-sorted and hash-degenerate and flatter every number. Measured on the 0.9.0 code in one session (min of 12 runs, idle machine, four seconds between runs so clocks settle). Absolute numbers are machine-dependent — this session runs ~19% faster than the one that produced the 0.8.0 table, std::HashMap control included — so compare the ratios, and only within a column.

_{Run-to-run lookup spread over the 12 runs: 1.9% for the HashMap control, 2.3% for id_unchecked, 5.4% BTreeMap, 7.1% CompactHashIndex::id, 8.0% PerfectHashIndex::id, 11.0% StringIndex — the control's tightness is what says the session was quiet. The ratio to HashMap is itself session-dependent: id_unchecked measured 2.2× here and 1.7× in the 0.8.0 session on the same machine, so read it as "roughly twice", not as a constant. 0.9's fused two-hash pass was verified separately by an interleaved A/B against the 0.8.1 binary in one session: CompactHashIndex::id 165 → 158 ns (−4.3%), build 117 → 116 ms, with HashMap, BTreeMap and both PerfectHashIndex rows flat. CompactHashIndex's build halved back in 0.8: it sorts 16-byte (hash, second hash) pairs instead of strings, keeping it below HashMap's build. Real keys move lookups in lexindex's favour versus synthetic ones (byte-wise FNV vs HashMap's SipHash), while every build reads higher because real input is not pre-sorted and sorting is part of the build.}

HashMap here is the std one, which hashes with SipHash — hardened against hash-flooding and correspondingly slow on short keys. That is the map most Rust code actually uses, so it is the right default comparison, but it is not the fastest map available: the same HashMap with a non-cryptographic hasher is much quicker, and cargo run --release --example bench prints that row too (FxHash, written out in the example rather than added as a dependency). Measured on the 0.10 code in two independent 12-run sessions on a shared machine — so only the within-session ratio means anything, and the control's run-to-run spread was 9–10% against the 1.9% of the table above — HashMap + FxHash came out at 196 / 200 ns, PerfectHashIndex::id_unchecked at 216 / 216 and the SipHash HashMap at 341 / 347. Against a fast-hashed map, in other words, lexindex's latency advantage is gone; what it still offers is the footprint and the serialisable, memory-mappable blob. (The table above still stands: 0.10 changed how the indexes are built and 0.11 added new build paths and a faster batched ids_of, but neither touched a byte of the blob or an instruction of the single-key lookups measured here.)

Two things the table above cannot show, both measured on 0.11 with an independent harness (local/latency/, one process, all forms alternated per round, min of 12):

• Roughly 90 ns of every number in it is reaching the probe key, not looking it up. The bench probes keys[i * STEP % n] — the original allocations in strided order, which is what a long-lived key list looks like. Hand the same index a probe list allocated in probe order and PerfectHashIndex::id_unchecked falls from 109 to 18 ns/op at 1 M, CompactHashIndex::id from 126 to 33, while PerfectHashIndex::id barely moves (262 → 192; it fetches a stored key either way). The batched ids_of is layout-insensitive by construction — 39.5 scattered against 38.2 contiguous — because its software prefetch does for scattered keys what the hardware does for contiguous ones. So read any sub-100 ns lookup figure, here or anywhere, as a statement about the caller's key layout as much as about the index.
• On a miss-heavy workload std::HashMap wins, until its table outgrows the cache. An absent key costs the SipHash map 32 ns at 1 M against CompactHashIndex::id's 41 — it fails on an empty bucket after one cache line, while a fingerprint index runs the whole perfect hash and reads a fingerprint before it can say no. At 10 M the map's table no longer fits and the order reverses (105 ns against 56 for ids_of). lexindex's lookup advantage is on members, and at scale.

Honest reading: for a fixed / closed vocabulary, PerfectHashIndex::id_unchecked is the fastest of the structures in the table above — roughly twice as quick as the SipHash HashMap (1.7–2.2× depending on the session; no probing, no membership comparison) and compact + serialisable. CompactHashIndex::id keeps a probabilistic membership check and still beats that HashMap on lookup (~1.6× here), and builds faster than it too. Full verification (id) pays one extra cache line + a key comparison; StringIndex trades more latency for ordered / prefix / range / fuzzy queries the hash maps cannot answer at all. So: CompactHashIndex when footprint dominates and a rare false positive is fine; PerfectHashIndex::id for exact membership + reverse; StringIndex when order or fuzzy/prefix matters; HashMap when you just need a general in-RAM map with nothing persisted.

Scaling to millions of keys

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

_{* bigram keys share far more prefixes than single words — at 1 M the generator draws on only 1 000 distinct words, which is why StringIndex compresses to an unrepresentative 0.68 B/key there; the honest single-word figure is in the size table above. One session on the 0.10 code, one process per cell. The machine was shared (another job held a core throughout), so the times are slower across the board than an idle session would give — StringIndex's build is the control here, since its code has not changed since 0.5.1 and it reads 1.6× slower than it did on an idle box. Read the peak RSS and bytes/key columns, which are not clock-dependent, and read the times only against each other. Peak RSS in the list rows is dominated by the Python key list; the generator rows are the index's own cost, which is why CompactHashIndex falls 3.3× there and StringIndex barely moves — it has to keep the keys. The extrapolation this table used to end on — ~35 s and ~3 GB for a streamed CompactHashIndex at 100 M — has since been measured instead of left standing: 35.9 / 36.1 s at a 2 452 MB peak, the same 1.27 B/key, and a point lookup that does not move with n (298–344 ns against 302–330 at 10 M). That is a separate and quieter session on 0.11 code, which is why it is stated here rather than added as a row above. Hash collisions do not change the picture at any n: since 0.8 both perfect-hash indexes absorb them into a side table instead of failing the build, and the fst build has no collision failure mode at all.}

License

MIT © Ilia Gradina