A static map from strings to u64 values using binary fuse filter construction. It can be several times smaller and faster than the equivalent HashMap.
The data structure is ideal when you have a known set of string keys at construction time and need fast, memory-efficient lookups afterward.
This is a Rust port of lemire/constmap, and tracks its v1.1.0 release.
This implementation is based on the binary fuse filter algorithm described in:
Thomas Mueller Graf and Daniel Lemire, Binary Fuse Filters: Fast and Smaller Than Xor Filters, ACM Journal of Experimental Algorithmics, Volume 27, 2022. DOI: 10.1145/3510449
See also the earlier xor filter paper:
Thomas Mueller Graf and Daniel Lemire, Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters, ACM Journal of Experimental Algorithmics, Volume 25, 2020. DOI: 10.1145/3376122
Given a set of (key, value) pairs, constmap builds a compact array such that for any key in the set, data[h0(key)] XOR data[h1(key)] XOR data[h2(key)] == value. Lookup is extremely fast: one xxhash call plus three array accesses and two XORs. The data structure is immutable after construction.
use constmap::ConstMap;
let keys = vec!["apple", "banana", "cherry"];
let values = vec![100u64, 200, 300];
let map = ConstMap::new(&keys, &values).unwrap();
assert_eq!(map.map("apple"), 100);
assert_eq!(map.map("banana"), 200);Note: Looking up a key that was not in the original set returns an undefined value.
VerifiedConstMap stores an additional fingerprint per key so that lookups of unknown keys return NOT_FOUND instead of garbage, at the cost of roughly doubling memory usage (~18 bytes/key instead of ~9).
use constmap::{VerifiedConstMap, NOT_FOUND};
let keys = vec!["apple", "banana", "cherry"];
let values = vec![100u64, 200, 300];
let map = VerifiedConstMap::new(&keys, &values).unwrap();
assert_eq!(map.map("apple"), 100);
assert_eq!(map.map("unknown"), NOT_FOUND);VerifiedConstMap keeps its values and its fingerprints in two separate arrays, so a
lookup of a present key reads three fingerprint words and then three value words: six
cache lines, in two different places. PairedVerifiedConstMap is the same map with each
value stored next to its fingerprint, so the three reads bring in both at once and a
lookup touches three cache lines instead of six:
use constmap::{PairedVerifiedConstMap, NOT_FOUND};
let map = PairedVerifiedConstMap::new(&keys, &values).unwrap();
assert_eq!(map.map("apple"), 100);
assert_eq!(map.map("unknown"), NOT_FOUND);It has exactly the semantics, memory footprint and API of VerifiedConstMap (map,
map_many, map_many_into, save_to_file, load_from_file), and an existing
VerifiedConstMap converts with vm.paired(). The difference is which keys it is
fast for:
- Present keys: fewer cache lines, so faster. Random lookups over a million keys
run 21% faster than
VerifiedConstMap::mapon an Apple M4 Max and 9% on an Intel Xeon Gold 6548N (table under Performance gains). - Absent keys: slower.
VerifiedConstMap::mapstops after reading the fingerprint array, which is half the size of the whole map and so far more likely to be cache-resident, whereas the paired map always brings the value in alongside the fingerprint, so its working set for misses is twice as large. - Batches:
map_manyoverlaps the memory accesses of eight keys, which hides some of the extra latency either way, but the paired layout still wins on present keys: 18% faster cold on the M4 Max and 34% on the Xeon (table under Batched lookups).
Use PairedVerifiedConstMap when most of the keys you look up are present, and
VerifiedConstMap when most are absent. Its serialized format has its own magic bytes
(PMAP0001) and is not interchangeable with VerifiedConstMap's.
On x86-64 and AArch64, each 16-byte slot is loaded and the three slots XORed as 128-bit vectors (SSE2 and NEON respectively, both part of their architecture's baseline, so there is no runtime feature detection). Other targets use plain scalar code.
If you have many keys to resolve at once, map_many takes a slice of keys and returns
a Vec of values, where result[i] corresponds to keys[i]:
let values = cm.map_many(&["apple", "banana", "cherry"]); // [100, 200, 300]VerifiedConstMap and PairedVerifiedConstMap have the same method, and still report
absent keys as NOT_FOUND:
let values = vm.map_many(&["banana", "grape"]); // [200, NOT_FOUND]If you resolve batch after batch, map_many_into writes into a buffer you own instead
of allocating a new one each time. It fills dst[..keys.len()], leaves the rest of
dst untouched, and panics if dst is shorter than keys:
let mut dst = vec![0u64; 4096];
for batch in batches {
cm.map_many_into(&mut dst, batch);
use_values(&dst[..batch.len()]);
}Both are exactly equivalent to calling map on each key in turn. They are faster
because a batch hashes a block of eight keys before gathering any values, which lets
the three array accesses of all eight keys be in flight at once instead of each key's
loads waiting behind the previous key's hashing. A lookup is memory-latency-bound
whenever the map is larger than last-level cache, so that overlap is where the gain
comes from.
Both key types accept anything that is AsRef<str>, so &[&str] and &[String] work
without conversion.
A 2000-key batch against a 1,000,000-key map, ns/key. Cold rotates through 64 distinct random batches so the touched cache lines are not already resident; hot replays one batch, so the touched region of the array stays cache-resident and hashing dominates instead.
loop over map |
map_many_into |
|||
|---|---|---|---|---|
| Apple M4 Max | ConstMap cold |
5.1 | 4.0 | 20% |
ConstMap hot |
4.8 | 3.6 | 25% | |
VerifiedConstMap cold |
11.4 | 8.3 | 27% | |
VerifiedConstMap hot |
7.1 | 5.2 | 27% | |
PairedVerifiedConstMap cold |
7.7 | 6.3 | 18% | |
PairedVerifiedConstMap hot |
5.2 | 3.9 | 25% | |
| Xeon Gold 6548N | ConstMap cold |
15.8 | 12.5 | 21% |
ConstMap hot |
9.0 | 7.6 | 16% | |
VerifiedConstMap cold |
20.3 | 21.1 | none | |
VerifiedConstMap hot |
11.8 | 9.6 | 19% | |
PairedVerifiedConstMap cold |
18.4 | 14.1 | 23% | |
PairedVerifiedConstMap hot |
11.1 | 8.6 | 23% |
The one place batching does not pay is VerifiedConstMap in the cold regime on the
Xeon, where repeated runs put the difference at anywhere from 2% faster to 4% slower --
that is, inside the run-to-run spread. That map probes two arrays per lookup, and on a
fresh batch it is bound by memory latency the batching cannot hide. The same case on
the M4 Max still gains 27%. This matches what the Go implementation measures on the
same two machines.
Raising the block size from 8 to 16 recovers that case on the Xeon (about 17% faster cold) but costs about 8% hot there, and is clearly worse hot on the M4 Max. Eight wins or nearly wins everywhere, so eight is what the block size is.
Unlike the Go implementation, there is no hand-written batched hashing routine. Go
needs one because a per-key call to xxhash.Sum64String reloads the five XXH64 primes
and pays a call for every key; in Rust xxh64 inlines directly into the block loop, so
that half of the Go version's gain is already there and there is nothing left to
hoist.
All three map types can be serialized to disk and loaded back later, avoiding the cost of reconstruction. Each binary format includes a FNV-1a checksum to detect corruption.
// Save to file.
cm.save_to_file("mymap.cmap")?;
// Load from file.
let cm = ConstMap::load_from_file("mymap.cmap")?;
// Same for VerifiedConstMap and PairedVerifiedConstMap, each in its own format.
vm.save_to_file("myverifiedmap.vmap")?;
let vm = VerifiedConstMap::load_from_file("myverifiedmap.vmap")?;
pm.save_to_file("mypairedmap.pmap")?;
let pm = PairedVerifiedConstMap::load_from_file("mypairedmap.pmap")?;For streaming use, write_to and read_from work with any Write / Read:
let mut buf = Vec::new();
cm.write_to(&mut buf)?;
let cm = ConstMap::read_from(&mut &buf[..])?;The two formats carry different magic bytes, so handing a file of one kind to the other kind's reader is reported rather than silently misinterpreted.
write_to and read_from move the data array in 64 KiB chunks rather than one u64
at a time. That matters most when the underlying writer or reader is an unbuffered
File, as it is here: a call per word means a syscall per word. For 1,000,000 keys
(a 9.04 MB file, 18.1 MB for the verified map):
| Operation | Apple M4 Max | Xeon Gold 6548N |
|---|---|---|
ConstMap::save_to_file |
1020 ms -> 11.1 ms | 497 ms -> 12.2 ms |
ConstMap::load_from_file |
361 ms -> 10.1 ms | 307 ms -> 11.5 ms |
VerifiedConstMap::save_to_file |
2049 ms -> 20.7 ms | 1080 ms -> 24.3 ms |
VerifiedConstMap::load_from_file |
727 ms -> 19.0 ms | 611 ms -> 23.0 ms |
Wrapping the file in a BufReader does not help: the chunking already batches the
syscalls, and the extra copy costs slightly more than it saves. On the write side a
BufWriter measured about the same, occasionally a little faster; either is fine.
The verified format pads its header to 32 bytes so that both u64 arrays begin on a
64-bit boundary: data at offset 32, and checks at 32 + 8*data.len(), which is a
multiple of eight because the first array is a whole number of words. A reader that
maps or otherwise aliases the file can treat either array as a [u64] without a
misaligned access.
The formats are shared with constmap (Go), fastconstmap (C, with Python bindings) and jbinfuse (Java): a map saved by any of the four loads in the other three, on a little-endian host (which is every mainstream one: x86-64, ARM64, RISC-V, Apple silicon). The four share the key hash (XXH64), the mixing, the seed sequence and the layout, so for the same input this crate, the Go package and jbinfuse write byte-identical files, and fastconstmap writes the same bytes apart from one header word:
VerifiedConstMap(VMAP0001) andPairedVerifiedConstMap(PMAP0001) are identical across the four. fastconstmap stores its key count in the header word this crate leaves as zero padding; every reader ignores the word.ConstMapfiles from fastconstmap carry the magicCMAP0003: this crate'sCMAP0001plus that 4-byte key count after the data length.read_fromaccepts both and ignores the count.
let vm = VerifiedConstMap::load_from_file("built-by-python.vmap")?; // from VerifiedConstMap.save
let cm = ConstMap::load_from_file("built-by-go.cmap")?; // from ConstMap.SaveToFileFiles written by fastconstmap 0.9 and earlier (CMAP0002, VCMP0002) used a
different key hash (XXH3) and cannot be loaded here; read_from says so rather
than reporting an invalid file. fastconstmap 0.10 and later still read them, and a
map rebuilt from its keys there writes the shared format.
jbinfuse (me.lemire.fastfilter:jbinfuse on Maven Central, from version 0.1.0) can
also query a saved map in place, from a memory-mapped file for example, without
copying it, whichever implementation wrote it.
The interoperability is tested: tests/interop/ holds files written by the Go
package and fastconstmap from a fixed input, which tests/interop.rs loads and
checks, and it checks that this crate writes exactly the bytes the Go package wrote.
jbinfuse tests itself against the same files, written by this crate and
fastconstmap, and against the Go package.
Construction time is higher (as expected for any compact data structure), but lookups
are optimized for speed. Against std::collections::HashMap<String, u64> with
1,000,000 keys:
| Data structure | Apple M4 Max | Xeon Gold 6548N |
|---|---|---|
ConstMap |
7.0 ns | 18.8 ns |
VerifiedConstMap |
12.3 ns | 26.4 ns |
PairedVerifiedConstMap |
9.8 ns | 23.7 ns |
HashMap |
54.6 ns | 94.6 ns |
The speed varies depending on your system, the size of your dataset, the keys, the
order of the lookups and so forth. If constmap can reside in CPU cache while the
HashMap cannot, then it will be significantly faster.
The memory usage should always be significantly better with ConstMap as long as you
have many thousands of keys -- and unlike a HashMap, it does not store the keys at
all, so the key text can be dropped after construction.
Lookup benchmarks query every key exactly once, in random order, from a buffer built in
that order (make_query_order in benches/constmap_bench.rs). Both halves of that are
deliberate, and both change the answer a lot.
Random order is what exercises the map. Walking the keys in the order they were constructed is a pattern no caller has, and it lets the hardware prefetcher hide work a real lookup must do.
A buffer built in query order is what keeps the measurement about the map. The key text is allocated in index order, so merely permuting the slice would leave every string body where it was and add a scattered, dependency-carrying load to each lookup -- you cannot hash a key before reading its bytes. That cost is real, but it belongs to whatever produced the keys, not to the map.
Querying the whole key set, rather than a small sample, is deliberate too. A small sample keeps the key text in cache, but it also leaves most of the map untouched and cache-resident, which flatters every implementation and hides exactly the compactness that is the point.
One pass over the whole key set, so every lookup is a first touch. Memory is counted by
a global allocator installed for the test binary, so the figures are bytes the process
actually asked for, not an estimate from capacities; the HashMap column is a
HashMap<&str, u64>, measuring the table alone rather than a second copy of the key
text. Run it with:
cargo test --release -- --ignored --nocapture scaling_tableApple M4 Max:
| keys | ConstMap |
VerifiedConstMap |
HashMap |
ConstMap bytes/key |
VerifiedConstMap bytes/key |
HashMap bytes/key |
|---|---|---|---|---|---|---|
| 10,000 | 6.8 ns | 9.2 ns | 14.7 ns | 10.2 | 20.5 | 41.0 |
| 100,000 | 6.5 ns | 8.3 ns | 16.9 ns | 9.5 | 19.0 | 32.8 |
| 1,000,000 | 9.2 ns | 15.0 ns | 53.4 ns | 9.0 | 18.1 | 52.4 |
| 10,000,000 | 23.5 ns | 31.1 ns | 100.8 ns | 9.0 | 18.0 | 41.9 |
Intel Xeon Gold 6548N:
| keys | ConstMap |
VerifiedConstMap |
HashMap |
|---|---|---|---|
| 10,000 | 10.0 ns | 12.8 ns | 21.4 ns |
| 100,000 | 12.3 ns | 20.2 ns | 43.2 ns |
| 1,000,000 | 22.6 ns | 26.7 ns | 110.6 ns |
| 10,000,000 | 50.1 ns | 78.2 ns | 166.3 ns |
The margin grows with the key count, which is the expected shape: at ten thousand keys
everything fits in cache and the compactness buys little, while at a million and beyond
it is most of the story. The HashMap bytes/key figure wobbles because the table grows
in powers of two.
cargo benchThree groups:
lookup-- single-key throughput forConstMap,VerifiedConstMap,PairedVerifiedConstMapandHashMapbatch--map_many_intoagainst the loop overmapit replaces, cold and hot, for both map typesserialize--save_to_file/load_from_filefor both map types
cargo testLicensed under either of
- Apache License, Version 2.0 (LICENSE-APACHE)
- MIT license (LICENSE-MIT)
at your option.