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.