Expand description
hakmem
Space-filling curves, rank/select and edit distance, built from bit tricks with laws.
docs · design · cookbook · benchmarks
Space-filling curves, rank/select, bit-parallel edit distance, and the
bit tricks they are made of. no_std, no dependencies, stable Rust, no
unsafe outside the intrinsics.
| job | hakmem | what people use |
|---|---|---|
| 2D Hilbert keys from coordinates, 1024 points | 1.3 µs | fast_hilbert 12.2 µs |
| 2D Morton keys from coordinates, 1024 points | 0.17 µs | zorder 1.9 µs, 0.89 with its BMI2 path |
| a rectangle as 16 sorted ranges of keys | 0.3 µs Morton, 1.1 µs Hilbert | |
| can a block of keys hold a point of the rectangle | 10 to 100 ns | |
| rank over 2^20 bits, 1024 queries | 1.3 µs | sux 2.0 µs |
| Levenshtein, 64-byte pattern over 1 KiB of text | 2.4 µs | strsim 44 µs |
One thread of a Zen 5; the column rows pick AVX2 or AVX-512 at run time and need no build flags. Where this crate loses, and it does, the tables below say so.
Every function comes with the laws it obeys, exported as property
functions and checked on every width from u8 to u128 and
[u64; N], with and without the hardware paths, exhaustively at 8 and
16 bits. CI also checks what the compiler makes of the loops that
matter, down to which function each instruction was inlined from
(Checks). Named after
HAKMEM (MIT AI Memo 239,
1972), items 161–180 of which are the first catalogue of these tricks.
They still work; now a compiler checks.
Every line of Rust in this README is a doctest, so if it lies, CI goes red.
§Spatial keys
Morton and Hilbert codes in 2D and 3D, a point at a time or a column
at a time (encode_columns, decode_columns, from_morton_in_place),
and the query side of a sorted key column: a rectangle as a few ranges
to seek (cover), and whether a block of keys, a row group or a
granule by its least and greatest key, can hold anything in it
(intersects).
use hakmem::prelude::*;
let points = [(10u64, 10u64), (11, 12), (500, 500), (12, 11)];
let mut keys: Vec<u64> = points
.iter()
.map(|&(x, y)| Hilbert2::encode(x, y).index())
.collect();
keys.sort_unstable();
// The block 8..=15 × 8..=15 in at most four ranges, a seek each.
let mut ranges = [(0u64, 0u64); 4];
let hits: usize = Hilbert2::cover(8..=15, 8..=15, &mut ranges)
.iter()
.map(|&(a, b)| keys.partition_point(|&k| k <= b) - keys.partition_point(|&k| k < a))
.sum();
assert_eq!(hits, 3);
// Columns in, keys out; the kernel is chosen at run time.
let (xs, ys) = ([3u64, 40_000, 1 << 31], [5u64, 7, 12]);
let mut codes = [0u64; 3];
Morton2::<u64>::encode_columns(&xs, &ys, &mut codes);
assert_eq!(Morton2::from_code(codes[1]).decode(), (40_000, 7));§Succinct bit vectors
Rank and select over any &[u64], in storage you provide: the rank9
directory, and a select inventory that stores positions outright where
the set bits are sparse.
use hakmem::rank9::Rank9;
let bits = [0b1011u64, u64::MAX, 0];
let mut counts = vec![0; Rank9::counts_len(bits.len())];
let mut select = vec![0; Rank9::select_len(bits.len())];
let dir = Rank9::build(&bits, &mut counts, &mut select);
assert_eq!((dir.rank(64), dir.select(3)), (3, Some(64)));§Fuzzy text
Levenshtein distance by Myers’ bit-parallel column, 64 cells a word,
patterns longer than a register on Wide<N>; and search that reports
where each match starts, which the column alone does not know.
use hakmem::myers::{distance, distance_in, search};
assert_eq!(distance_in::<u64>(b"kitten", b"sitting"), Some(3));
assert_eq!(distance(b"kitten", b"sitting"), Some(3)); // carrier by length
// The typo is deliberate.
let text = b"the quick brown fox and the quikc brown fox";
let found: Vec<_> = search::<u64>(b"quick brown fox", text, 2)
.unwrap()
.occurrences()
.map(|o| (o.start(), o.distance()))
.collect();
assert_eq!(found, [(4, 0), (28, 2)]);§Bits and bytes
PEXT and PDEP with a portable definition behind them, select in a word, runs, scans, and sixteen byte lanes (SSSE3, NEON, or SWAR) whose masks hand over to the word tricks: simdjson’s first stage, as parts.
use hakmem::lanes::{Lanes, U8x16};
use hakmem::{Bits, Words};
assert_eq!(0b1001u32.compact(0b1010), 0b10); // PEXT
assert_eq!(0b0111_0110u64.select(2), Some(4));
assert_eq!([0xFFu64 << 56, u64::MAX].find_run(16), Some(56));
let block = U8x16::load(b"{\"a\": [1, 2]} ");
let quotes = block.cmp_eq(U8x16::splat(b'"')).to_bitmask();
assert_eq!(quotes.prefix_xor(), 0b0110); // inside the string§Everything else, one screen
Every fast codebase has a bits.rs: one-liners from Hacker’s Delight,
each under a comment that says // do not touch. This crate started as
that file with the comment replaced by a proof obligation: every trick
has a name, a type, a domain where it is defined, and the laws it
obeys. The jobs above are what those tricks add up to; here is the rest.
use hakmem::{Bits, Hilbert2, Hilbert3, Morton2};
// Runs: bit p set iff bits p..p+3 are all set (Hacker's Delight 6-5).
let x: u64 = 0b0111_0110;
assert_eq!(x.run_starts(3).first_set(), Some(4));
assert_eq!(x.rank(4), 2);
assert_eq!(x.positions().collect::<Vec<_>>(), [1, 2, 4, 5, 6]);
// Kogge–Stone fills slide along a stride through a propagation mask.
assert_eq!(1u8.fill_up(0b0000_0111, 1), 0b0000_0111);
// SWAR byte lanes: exact zero/equal/less-than tests, eight at a time.
assert_eq!(0x41_0A_42_09u32.bytes_lt(0x20), 0x00_80_00_80);
assert!(0x0012_0034u32.has_zero_byte());
// Morton neighbours without decoding.
let m = Morton2::<u32>::encode(3, 5);
assert_eq!(m.step_x().decode(), (4, 5));
// Hilbert indices: the decode is two suffix XORs over the Morton code.
assert_eq!(Hilbert2::<u8>::encode_order(3, 1, 2).index(), 12);
assert_eq!(Hilbert2::from_index(13u8).decode_order(2), (2, 1));
// In 3D the frames form A₄ = AGL(1, 4): the decode is a scan over GF(4).
assert_eq!(Hilbert3::<u64>::encode(1000, 2000, 3000).decode(), (1000, 2000, 3000));
// 8×8 bit matrices: three delta swaps per transpose.
use hakmem::permute::board8::transpose;
assert_eq!(transpose(1 << (8 * 1 + 5)), 1 << (8 * 5 + 1));
use hakmem::permute::board8::{Dir, slide};
let rook = 1u64; // a1, attacking north up to the blocker on a5
assert_eq!(slide(rook, !(1u64 << 32), Dir::North), 0x0000_0001_0101_0100);
// Hacker's Delight ch. 2 and HAKMEM 175, named and lawful.
assert_eq!(0b1011_0110u32.clear_lowest_run(), 0b1011_0000);
assert_eq!(37u32.round_up_pow2(), Some(64));
assert_eq!(0b0011u8.next_same_popcount(), Some(0b0101)); // Gosper's hack
assert_eq!(0b0111_0110u32.longest_run(), 3);
// simdjson's find_escaped: quotes preceded by an odd run of backslashes.
let (escaped, _carry) = 0b01_1101_1010u16.find_escaped(false);
assert_eq!(escaped, 0b10_0000_0100);
// Patterns wider than a register: `Wide<N>` is `[u64; N]` as one word,
// and the same Myers code runs on it unchanged.
use hakmem::Wide;
use hakmem::myers::distance_in;
let long = [b'a'; 200];
assert_eq!(distance_in::<Wide<4>>(&long, &long[..190]), Some(10));
// 2D runs: a w×h block in a bitmap of rows, by two halving chains
// (binary erosion by a rectangle; first-fit for tile allocators).
let rows = [0b0111_1000u8, 0b0111_1100, 0b0011_1100, 0];
let mut scratch = [0u8; 4];
assert_eq!(hakmem::grid::find_block(&rows, 2, 2, &mut scratch), Some((0, 3)));§Status
Young, and one person’s: I am working through the broadword
literature by giving each trick a type, a law and a test, and the crate
is what that leaves behind. What is here is checked harder than most
crates check anything; what is not here yet, and the API’s habit of
moving, are the reasons to pin a version. Definitions were chosen for
lawfulness first and speed second, and it shows in places: the
portable select loses to a plain loop for small k, the portable
compact to one over sparse masks.
The API will change between minor versions (0.2 broke 0.1 without
apology). It changes on purpose, though: public-api/ is checked in,
one file per target, and diffed in CI, and cargo-semver-checks says whether the version
number admits it.
What I do take seriously is finding bugs. Every combinator ships
with laws; the laws run on every carrier, with and without the
hardware paths, exhaustively at 8 and 16 bits, and under Miri for
the intrinsics (GFNI under Miri only, the runners being a mix of CPUs);
CI builds all of it as sandboxed Nix derivations on
x86_64 and aarch64. A wrong result is a bug and I want to hear about
it. A slow one may be known; the design notes linked at the end list
what is.
If you need a stable dependency today, take the two or three lines you need from Hacker’s Delight; that is where this crate started, and their MSRV is 1972. If you want them named, typed and checked, read on.
§Examples
examples/ holds four programs written the way a user would write them,
each checking itself against the slow way: geo_index (a million
points in row groups, a rectangle query that skips most of them),
primes (the primes below ten million as a bitmap with rank and
select), json_structure (the first stage of simdjson, carries across
64-byte blocks) and fuzzy (the nearest words to a typo, and a phrase
found with its typos). cargo run --release --example geo_index.
§Benchmarks against the crates people use
Criterion, AMD Zen 5, one thread, cargo bench --bench incumbents. Numbers are from a sandboxed run; rerun on your machine
before believing them. Bold marks the winner, also when it is not
this crate. What the tables do not hide: without BMI2 the
select is slower than the broadword crate’s, and Wide<N> pays N
limb operations per step.
The same benches run in CI on a shared GitHub runner after every change
to src/, benches/ or the Cargo files, and the
benchmarks page keeps
every run. Absolute times there move with the runner; the ratio to the
best incumbent inside one run does not, and that ratio is what the page
tracks.
select in a u64 (1024 words) | portable | +bmi2 |
|---|---|---|
hakmem Bits::select | 5.24 µs | 1.21 µs |
broadword::select1_raw | 4.60 µs | 4.54 µs |
compact in a u64 (1024 words) | portable | +bmi2,+pclmulqdq |
|---|---|---|
hakmem Bits::compact | 11.2 µs | 1.30 µs |
| broadword definition, dense mask (about 32 set bits) | 11.1 µs | 8.00 µs |
| loop over the set bits, dense mask | 21.3 µs | 19.5 µs |
| loop over the set bits, sparse mask (about 8 set bits) | 4.36 µs | 3.75 µs |
| rank / select over 2^20 bits, 1024 queries | rank dense | rank sparse | select dense | select sparse |
|---|---|---|---|---|
hakmem Rank9 | 1.33 µs | 1.33 µs | 5.26 µs | 1.7 µs |
sux rank9 / select9 | 2.02 µs | 2.03 µs | 5.52 µs | 1.44 µs |
sucds Rank9Sel | 1.90 µs | 1.89 µs | 8.83 µs | 11.3 µs |
vers-vecs RsVec | 2.83 µs | 2.82 µs | 7.63 µs | 10.5 µs |
Dense is half the bits set, sparse one in 64. Rank is the same rank9
directory everywhere; the differences are bounds checks and layout.
Select keeps an inventory entry per 512 set bits and, by how many
blocks those 512 span, stores either packed 16-bit block counts (one or
two SWAR compares) or the positions themselves (no search at all), the
shape of Vigna’s select9 with the cases cut at block boundaries. The
remaining gap to sux on the sparse slice is within run-to-run noise of
the bounds checks this crate keeps: it has no unsafe outside the
intrinsics, sux indexes unchecked. The price of the inventory is three
words per eight words of bits on top of rank9’s two.
The portable compact is constant time: a loop over the set bits wins
below about 17 of them (12 when a PCLMULQDQ scan is available) and loses
above, the same trade as the portable select.
| Levenshtein, pattern m × text n | hakmem u64 | hakmem u128 | triple_accel | triple_accel_exp | strsim |
|---|---|---|---|---|---|
| 16 × 64 | 153 ns | 224 ns | 852 ns | 590 ns | 711 ns |
| 32 × 256 | 602 ns | 829 ns | 19.6 µs | 6.10 µs | 5.74 µs |
| 64 × 256 | 614 ns | 860 ns | 21.4 µs | 6.80 µs | 11.4 µs |
| 64 × 1024 | 2.37 µs | 3.26 µs | 235 µs | 221 µs | 44.1 µs |
| 128 × 1024 | n/a | 3.24 µs | 249 µs | 231 µs | 90.0 µs |
Longer patterns, Wide<N> | hakmem Wide<4> | hakmem Wide<8> | triple_accel | triple_accel_exp | strsim |
|---|---|---|---|---|---|
| 128 × 1024 | 7.41 µs | 19.3 µs | 245 µs | 231 µs | 109 µs |
| 256 × 1024 | 8.06 µs | 20.4 µs | 274 µs | 257 µs | 176 µs |
| 512 × 1024 | n/a | 22.3 µs | 326 µs | 307 µs | 352 µs |
Why the gap: Myers’ bit-parallel column costs ~12 word operations per
text byte for the whole pattern (64 cells per word), the state lives in
registers, nothing is allocated and no UTF-8 is decoded; the others pay
per cell, and triple_accel’s full-distance API searches upward over
the band width, which is a poor fit when the lengths differ a lot.
Longer patterns use Wide<N> (N × 64 bits as one word): each step
then costs N limb operations, still well below per-cell DP.
triple_accel’s own design point is two strings of similar length that
differ in a few edits, with a known bound k (levenshtein_simd_k;
below, k is twice the edits). There it catches up and, past a couple
of words, wins:
| same length, few edits | hakmem | triple_accel_simd_k | triple_accel_exp | strsim |
|---|---|---|---|---|
| 64, 4 edits (u64) | 165 ns | 980 ns | 1.03 µs | 2.74 µs |
| 128, 8 edits (u128) | 494 ns | 1.86 µs | 1.94 µs | 11.7 µs |
512, 8 edits (Wide<8>) | 13.5 µs | 7.13 µs | 7.39 µs | 177 µs |
512, 32 edits (Wide<8>) | 13.8 µs | 10.1 µs | 7.39 µs | 178 µs |
hakmem always computes the full distance; a banded variant (Ukkonen
cut-off over the active blocks) is the obvious next step for long
similar strings and is not implemented.
Morton code in 2D, u32 coordinates (1024 points) | encode, portable | encode, +bmi2 | decode, portable | decode, +bmi2 |
|---|---|---|---|---|
hakmem Morton2, columns | 0.17 µs | 0.17 µs | 0.22 µs | 0.22 µs |
hakmem Morton2, per point | 1.81 µs | 0.47 µs | 1.39 µs | 0.44 µs |
zorder, with its BMI2 path where the CPU has it | 0.89 µs | 0.47 µs | 0.95 µs | 0.44 µs |
zorder, portable | 1.88 µs | 1.87 µs | 1.36 µs | 1.36 µs |
morton-encoding (also lindel’s Morton) | 37 µs | 36 µs | 36 µs | 36 µs |
Morton code in 2D, u16 coordinates (1024 points) | encode, portable | encode, +bmi2 | decode, portable | decode, +bmi2 |
|---|---|---|---|---|
hakmem Morton2<u32>, columns | 0.09 µs | 0.09 µs | 0.11 µs | 0.11 µs |
hakmem Morton2<u32>, per point | 1.52 µs | 0.58 µs | 1.15 µs | 0.39 µs |
morton | 1.52 µs | 1.52 µs | 1.15 µs | 1.16 µs |
The columns win because they choose AVX2 at run time and spread a
coordinate’s nibbles with one PSHUFB. A point at a time, a Morton code
is a shift ladder or one PDEP each way, and it ties with the crates
that do the same: the decode is Word::unzip, two PEXT of the code
with BMI2, and without it, on a u32 key, one ladder over a u64
holding both halves, which is morton‘s trick. Every per-point row
writes its coordinates at the coordinates’ width; the columns write
them as wide as the key, since that is their API, and lead anyway. The
one column this crate does
not take is the per-point form without build flags, where zorder
checks for BMI2 on every call and this crate uses what the build
proves: ask once instead, with the columns or dispatch!
(Hardware paths).
Hilbert curve, 32 levels, u32 coordinates (1024 points) | decode, portable | decode, +pclmulqdq | encode, portable | encode, +bmi2,+pclmulqdq |
|---|---|---|---|---|
hakmem Hilbert2 | 2.6 µs | 1.7 µs | 10.9 µs | 5.4 µs |
fast_hilbert (512-byte transition table) | 12.8 µs | 12.7 µs | 11.5 µs | 11.4 µs |
lindel (Skilling) | 66 µs | 71 µs | 70 µs | 76 µs |
Morton2, for the price of the frames | 1.6 µs | 0.56 µs | 1.6 µs | 0.46 µs |
| Hilbert curve in 3D, 21 levels (1024 points) | decode, portable | decode, +bmi2 | encode, portable | encode, +bmi2 |
|---|---|---|---|---|
hakmem Hilbert3 | 10.6 µs | 8.8 µs | 18.3 µs | 13.2 µs |
| rawrunprotected’s tables, 96 bytes each way | 17.5 µs | 14.9 µs | 19.0 µs | 15.0 µs |
Morton3 | 2.1 µs | 0.78 µs | 2.0 µs | 0.72 µs |
In 3D the frames form the alternating group A₄, which is
AGL(1, 4), so the 2D encode’s scan is the 3D decode; the 3D encode
is not a scan and is the twelve-state machine memoised into
a table of 96 bytes built at compile time from the same
arithmetic. It is the incumbent’s machine, ahead of it by a table padded
to 128 entries (the masked index needs no bounds check) and a loop the
compiler vectorises over points; in batches a vpermi2b walks it for
64 keys at a time.
The 2D decode is two suffix XORs over the Morton code and a Morton
decode, straight-line. The encode is a Kogge–Stone scan over the
per-level frame maps, affine maps over GF(4) once levels are paired,
four rounds of about 24 word operations after the pairing: the
adder’s carry chain with GF(4) in place of GF(2), and no instruction
for it. The construction is rawrunprotected’s (threadlocalmutex.com,
2016); this is it on any carrier, with laws. fast_hilbert walks a state table three levels a
step, eleven dependent loads for 32 levels; the scan has no loads and
no carried chain, which is why it gains from +bmi2 (the BMI
instructions) where the table walk cannot. Recipe 13 of the cookbook
has the derivation and the group that makes the encode the heavier
direction.
Batches of keys convert in place: fill a slice with Morton codes from
whatever layout the points are in, then turn them into Hilbert indices
in one call (from_morton_in_place, and to_morton_in_place back;
the _order forms for a curve of fewer levels). With AVX-512 VBMI a
step is one vpermi2b per register of keys (2D, three levels through
128 entries, the frame modulo a reflection; 3D, the 96-byte encode or
decode table); with AVX2 alone the 3D machine modulo its translations,
two PSHUFB a level; NEON uses tbl; elsewhere it is the per-key
conversion. Coordinates never enter these kernels. For the 3D curve on
u64 they may, as three columns (Hilbert3::<u64>::encode_columns,
decode_columns): with VBMI and GFNI that skips the Morton code both
ways, 1.2 and 1.0 ns a point against 1.7 and 1.8, and elsewhere it is
the Morton code and the batch above.
use hakmem::prelude::*;
let points = [(3u64, 5u64), (40_000, 7), (1 << 31, 12)];
let mut keys: Vec<u64> = points
.iter()
.map(|&(x, y)| Morton2::encode(x, y).code())
.collect();
Hilbert2::<u64>::from_morton_in_place(&mut keys);
assert_eq!(keys[1], Hilbert2::<u64>::encode(40_000, 7).index());
keys.sort_unstable(); // curve order, as a packed R-tree builds itBatch conversion, 1024 points, target-cpu=native on Zen 5 | in place | per key | incumbent |
|---|---|---|---|
2D encode, u64 keys, 32 levels | 1.6 µs | 6.1 µs | fast_hilbert 12.2 µs |
2D encode, u16 coordinates, u32 keys, 16 levels | 0.90 µs | 6.3 µs | fast_hilbert 8.5 µs |
2D encode from two columns, u64 keys (Hilbert2::encode_columns) | 1.3 µs | 6.1 µs | fast_hilbert 12.2 µs |
3D encode, u64 keys, 21 levels | 1.8 µs | 13.1 µs | rawrunprotected’s tables 15.2 µs |
3D decode, u64 keys, 21 levels | 1.8 µs | 8.8 µs | rawrunprotected’s tables 15.1 µs |
The query side: Hilbert2::cover and Morton2::cover turn a rectangle
into at most as many ranges of keys as the output slice holds, sorted
and inclusive, every cell of the rectangle in one. With room for the
exact cover they hold nothing else; with less they hold the least
extra a budget of ranges of the deepest cover that fits can hold. A
scan of the sorted keys seeks once per range. No allocation, and the
depth is counted rather than searched for: 0.3 µs a rectangle for 16
Morton ranges on the full u64 grid, 1.1 µs for 16 Hilbert ranges.
The other way round, intersects(keys, x, y), all three ranges, says whether a block of
keys (a granule, a row group, a file, by its least and greatest key)
can hold a point of the rectangle: one descent where a node is an
interval of keys and a square of cells at once. 40 to 90 ns when the
answer is yes, 100 when a granule just misses, 10 when it is nowhere
near.
§Cookbook
hakmem::cookbook explains how the shipped kernels were composed:
the simdjson inside-string mask, first-fit runs across words, the
Myers column step, Morton neighbours, strlen in one word, sliding
attacks, each as problem, decomposition, the laws that justify it,
and cost, with doctests. The last recipe is the one deliberately left
unbuilt (banded Myers over Wide<N>), sketched so you can.
§Hardware paths
The batch conversions (from_morton_in_place, to_morton_in_place,
encode_columns, decode_columns, the last two on Morton2 and
Hilbert2 too) choose their kernel at run time on
x86_64: AVX-512 VBMI and GFNI (the X86V4 level), else AVX2 (X86V3), else the per-key form,
with no build flags and still no_std; the portable feature turns
that off. The methods on words and lanes use what the build proves:
build with
-C target-feature=+bmi2,+pclmulqdq (or -C target-cpu=native) and
pext/pdep/select/prefix_xor/suffix_xor become single
instructions; without
them every combinator has a portable definition with the same
contract. A hot loop that should not depend on the build asks once
instead (hakmem::isa, design notes section 3):
use hakmem::isa::Isa;
fn gather<I: Isa>(cpu: I, xs: &[u64], mask: u64) -> u64 {
xs.iter().fold(0, |a, &x| a ^ cpu.pext(x, mask))
}
// One CPUID, then the loop compiled for the level it found: PEXT here
// even in a build without flags.
let n = hakmem::dispatch!(|cpu| gather(cpu, &[0b1011, 0b0110], 0b0110));
assert_eq!(n, 0b01 ^ 0b11);Anything the loop calls has to inline into it, or it is compiled
without the level’s features and each primitive in it is a call. pext and pdep fall back to Hacker’s Delight’s
parallel-suffix compress and expand (7-4, 7-5), log₂ w rounds of one
prefix-XOR scan each, constant time. The portable cargo feature turns
the hardware paths off even when the target feature is present, for the
microarchitectures where the instruction exists but is microcoded
(PDEP/PEXT on AMD Zen 1 and 2).
For the lanes, +ssse3 (NEON on aarch64) makes U8x16 a vector
register, and +gfni makes every byte map, affine and the shifts,
rotates and bit reversal built on it, one gf2p8affineqb; without it
a byte map is two nibble lookups. Under a token the level’s own
carrier is I::U8x16, made with I::U8x16::load(cpu, bytes): a value
of it is the proof the CPU has its instructions, which is why the
constructor asks for the token.
§Laws
Every combinator ships with the laws it obeys (hakmem::laws), checked
by property tests on all carriers with and without the hardware paths,
and exhaustively for widths up to 16 bits. A backend that fails a law
is a bug, never a documented caveat.
Every combinator is total over its carrier where a total definition
exists: rank(i) past the width counts every bit, run_starts(0)
starts everywhere and run_starts(k) above the width nowhere, a fill
with a stride of zero or past the width is the identity, low_ones at
the width is all ones. Where an argument has a domain the definition
cannot absorb (shift amounts, run lengths above the width in
Words::find_run, overlapping delta_swap masks, bytes_ge above
128, grid sizes), the domain is in the method’s docs, checked with
debug_assert! in debug builds, and unspecified in release. Run your
tests in debug once.
no_std, zero dependencies, stable Rust. The one allocating convenience
(Rank9Buf) sits behind the default alloc feature; with
default-features = false nothing in the crate allocates.
§Checks
Every cell is one Nix derivation built in a sandbox without network,
on every push to main. The badges are written by CI after each run
(.github/status.sh) and read from the site.
A lot of cells for a crate of one-liners; the one-liner wrong for one
input in 65 536 is the bug they exist for.
| check | x86_64 | aarch64 |
|---|---|---|
| tests, portable |  |  |
tests, +bmi2,+pclmulqdq,+avx2 |  | n/a |
tests, +bmi2 with feature portable |  | n/a |
| tests, debug build (asserts, overflow checks) |  |  |
| doctests (this README), portable |  |  |
doctests, +bmi2 |  | n/a |
| clippy, portable |  |  |
clippy, +bmi2 |  | n/a |
clippy, +bmi2 with feature portable |  | n/a |
| rustdoc, warnings as errors |  |  |
public API matches public-api/ |  |  |
instructions, +bmi2,+pclmulqdq,+ssse3,+avx2 (codegen/) |  | n/a |
instructions, no flags (codegen/) |  | n/a |
inlining in the benches’ binaries, no flags (codegen/) |  | n/a |
inlining in the benches’ binaries, x86-64-v3 (codegen/) |  | n/a |
innermost bench loops by hakmem function, llvm-mca cycles, no flags (codegen/) |  | n/a |
innermost bench loops by hakmem function, llvm-mca cycles, x86-64-v3 (codegen/) |  | n/a |
bare metal and kernels: x86_64-unknown-none, aarch64-unknown-none{,-softfloat} |  | n/a |
| MSRV 1.89 build of the packaged tarball |  |  |
what cargo publish uploads matches release/package.txt, the version its changelog heading |  |  |
| cargo-deny (licences, bans, sources) |  |  |
| cargo-audit (advisories, offline) |  |  |
| treefmt |  |  |
| Miri over the intrinsics, both paths |  | n/a |
§How the checks got here
Each row answers a question a green test suite did not. The laws came
first: every combinator against a bit-loop model, on every carrier, with
and without the hardware paths. The public-api/ files are one per
target since the instruction-set tokens made x86_64 and aarch64
export different things. The instruction cells hold the README’s claims
to the compiler’s output, and the first one found select paying for
its popcount in software under the flags the README recommended.
The last four rows came from a regression nothing saw. Routing Word
through the tokens left pext‘s #[inline] behind, and the 2D Hilbert
decode ran eight times slower in a build without flags, with every
check green: the tracked benches build with target-cpu=native, where
PEXT is one instruction however it inlines, and the instruction cells
compile one codegen unit, where everything inlines. perf found it.
Now two cells read the benches’ linked binaries, built the way a
dependency is, and check in the hakmem functions that survived there as
functions of their own; two more take every loop a bench times apart by
the hakmem function behind each instruction, with llvm-mca’s cycles.
Put the missing #[inline] back and both fail with the line that says
why. Clippy’s missing_inline_in_public_items now asks before the fact,
and on its first run it found Rank9::rank and select out of reach of
any caller outside the crate: 6 to 39 % back.
Design: docs/design.md,
the decisions behind the API, the hardware policy, how the laws are
verified, and where every combinator comes from.
Changes: CHANGELOG.md.
Re-exports§
pub use prelude::*;
Modules§
- affine
- Affine maps on the bits of a byte:
x ↦ A·x ⊕ bover GF(2). - bits
- The one trait to import: every combinator, on every carrier.
- cookbook
- How the shipped kernels were composed, so you can compose your own.
- curve
- The curves behind one interface, for code that should not care which.
- dilated
- Dilated integers and Morton (Z-order) codes.
- grid
- Two-dimensional runs: rectangular blocks in a bitmap of rows.
- hilbert
- Hilbert curves as two scans over the Morton code: parities one way, the carry chain two bits wide the other.
- hilbert3
- 3D Hilbert curves: the decode as a Kogge–Stone scan over
AGL(1, 4), the encode as the twelve-state machine in the same arithmetic, both without tables. - isa
- Instruction sets as values: pick one where a hot loop starts, pass it down, and the primitives inside compile to its instructions.
- lanes
- Byte lanes: the SIMD half of the algebra, on stable Rust.
- laws
- The algebra’s laws as exported property functions.
- myers
- Bit-parallel edit distance (Myers 1999, Hyyrö’s formulation).
- permute
- Permutations built from delta swaps.
- prelude
- Everything most code needs, one
useaway. - rank9
- Rank and select in O(1) over a slice of words: Vigna’s rank9 directory (2008) for rank, and a select inventory in the shape of his select9 over the same block counts.
- set
- Set view: a word as a set of positions
0..BITS. - slice
- Bit-set operations over a slice of words: the index-free layer between single-word combinators and a real succinct structure.
- wide
- A multi-limb carrier:
N × 64bits that behave as one word. - word
- The carrier: a fixed-width word viewed as a container of bits.
- x86
x86-64 - The leaves: one instruction each, as safe
#[target_feature]functions tagged with exactly the features they use.
Macros§
- dispatch
- Detects the level once (or takes one) and runs the body with a token of it, compiled once per level.