Repository navigation
lexindex v4.1.0
Added
-
HashedDictIndex: aDictIndexwhoseidis a hash. A dictionary answersidby 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_bitsbits wide.idis two hashes of the key and two reads and
never touches the dictionary;key(id), prefix, range and iteration go todict(), whose ids are
the same ranks. On the campaign's protocol, besideDict256 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_unchecked3.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 at2^-fingerprint_bits,CompactHashIndex's rate; at zero bits
idis the dictionary's exact search, and the hash isid_uncheckedalone — a member's rank, and
some rank belownfor 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 isBHD1: a
48-byte header, the dictionary'sBDX3blob byte for byte — checked byDictIndex's own loader —
then the perfect hash, the rank table and the side table.load_mmapborrows 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), withids_of,in,
indexing and.dict, and the batch formsDictIndexhas —ids_of_bytes,ids_intoand the
Arrow pairids_of_arrowandids_into_arrow— writinguint64ids andMISSING_IDfor a
miss. The C ABI opensBHD1blobs 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.plandoes not price it yet, and
Overlaydoes not take it: its ids are ranks. -
The command line in the wheel.
plan,build,inspectanddumpwere reachable only
throughcargo 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 alexindexcommand and aspython -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-polarsis 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"), andid_unchecked,containsandkeybeside it.
They are plugin expressions rather than amap_batchescallback, 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 thelexindexcrate 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_dictloads arbitrary bytes as aHashedDictIndex
and holds every rankid,id_uncheckedandids_ofanswer below the key count; it runs in CI's
fuzz matrix besideparse_dict, andtests/data/golden-4.1.0-hashed.bhdpins 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 fuzzesmain.
.clusterfuzzlite/is the build an OSS-Fuzz project would use, and it builds all ten targets with
the instrumentation intact: 2 448 counters inparse_compact, where an LTO build keeps a few
hundred. -
The C ABI under the sanitizers. The weekly AddressSanitizer run compiled
tests/capi.rsto
nothing, since it needs thecapifeature, 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 PATTERNruns the campaign's processes whose label matches,
into an artifact namedfrontier-<scale>-subset-*;frontier_lextakeshashed0,hashed8and
hashed16, andbench/tables.pyrenders a campaign'sHashedDictIndextable withview=hashed.
Fixed
bench/frontier/run.shrefused to run at 4.0.1: it buildsfrontier_lexwith--locked, and
that crate's lock file still named lexindex 4.0.0 — asbench/mphf_vs's did. CI now fails when a
trackedCargo.locknames another version of lexindex thanCargo.tomldoes, 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-releasedwith 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.mdrendered four of the public names.Overlay(public since 0.12),DictIndex
(2.0),plan(3.0),inspectand 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/resultsfile 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 — whatfingerprint_bitsdecides — 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.mdlisted the fuzzed formats as of 1.1, withoutMPH3, the perfect hash's format since
4.0.0; it namesMPH3andBHD1now. Itsunsafeinventory 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 fourunsafe impls ofSendandSync, the
unsafe traitbehind zeroed huge-page tables, and the C ABI's five internalunsafe fns.