Compact tries for fixed-width keys
Switch branches/tags
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.cargo
benches
examples
src
tests
.gitignore
.travis.yml
Cargo.toml
README.md
benchmark.sh

README.md

By their very nature, maps were always works in progress, and Gentle – his resolve strengthened by thinking of them that way – decided after many months of delay to turn his hand to making one.

— Imajica

An implementation of "fixie tries", inspired by Tony Finch's qp-tries but for fixed-length keys, storing the key implicitly in the trie where possible. Even though qp-tries were the inspiration, the approach is actually closer to array mapped tries (AMT/HAMT).

You can (and should) run the benchmarks with benchmark.sh. This should tell you at least a little about how fixie tries fare, both in speed and memory consumption, on your system, at least for the cases of random insertions of certain sizes.

There are countless trie variants, so although I'm giving this one a new name, it probably already exists in some form.

This is x86_64-specific, because we stuff the branch bitmap in the upper 16 bits of a pointer; pointers on this platform are actually 48-bit, so no harm done, but this doesn't necessarily hold on other platforms. And there wouldn't be enough room for the bitmap if pointers were 32-bit.

(The mask for pointers is 0x0000_ffff_ffff_fffe.)

Part of my interest in doing this was to see if it was possible to write this kind of stuff in Rust, and it seems to be possible and mostly pleasant.

This implementation is mostly an experiment; in particular, the current approach is unfriendly to the allocator, making a lot of tiny allocations. Slab allocation or similar would probably make sense.

It might be nice to do something like direct pointing from poptries on top, where the first n bits are covered by a 2ⁿ array of tries.

I discuss this structure in more detail in an article on my blog.