Fixie tries

The Array Mapped Trie is an interesting data structure that's really hard to represent in code. Even this rust version is forced to use unsafe and manual allocation to pull it off.

Most libraries seem to resort to using a dynamic array, like a Go slice:

    type bitmapNode struct {
        childBitmap uint64
        children []node
        bitpos uint64
    }

But that wastes space (there's no need to store the length/capacity) and may add a level of indirection, so doesn't really represent the actual data structure at all.

The original paper includes this note: http://lampwww.epfl.ch/papers/idealhashtrees.pdf

> As Nilsson and Tikkanen [1998] remark, performance critically depends on the memory allocation system and careful organization is rewarded.

There are all kinds of clever workarounds to this problem, like using part of the pointer for additional meaning, or, perhaps the most fruitful, using different mechanisms for different sized nodes. For example: https://db.in.tum.de/~leis/papers/ART.pdf and https://www.usenix.org/system/files/conference/fast17/fast17...

These adaptive radix trees have 4 node types: Node4, Node16, Node48, and Node256. Node4 uses two sorted arrays of up to 4 items, Node16 uses an idea similar to the array mapped trie, using a bitfield and compressed arrays, Node48 and Node256 are more like traditional tries, since at that size the memory loss is worth the trade off.

What's frustrating about these data structures is just how hard they are to implement. Pointers, structural types, arrays and bytes seem wholly inadequate to the task and your code becomes a mishmash of low-level, specialized instructions, hacky unsafe memory access, and byzantine bit-shifting. This note in the code just about sums it up:

    // It should be possible to implement this for arbitrary types
    // implementing BitAnd and friends, but my attempts to do so were
    // constantly thwarted.
    macro_rules! trivial_fixed_length_key_impl {
        ($($name:ident,)*) => {
            $(#[allow(trivial_numeric_casts)] impl FixedLengthKey for $name {
                const LEVELS: usize = 2 * mem::size_of::<Self>();
                #[inline]
                fn nibble(&self, idx: usize) -> u8 {
                    ((*self >> (4*(Self::LEVELS-idx-1))) & 15) as u8
                }
                #[inline]
                fn empty() -> Self { 0 }
                #[inline]
                fn concat_nibble(&mut self, nibble: u8) {
                    *self = (*self << 4) | (nibble as Self)
                }
            })*
        }
    }

It's a circle-sized data-structure trying to fit in a square-sized programming worldview.

I wonder if we end up with hash tables, not because they're technically superior, but because all of our programming languages make them easy to implement and reason about, and when try to leave that box, we constantly bang our head against a wall, and end up with code that always just looks like gobbledy gook.

The latter linked paper is particularly damning in this respect, as it introduces this esoteric world of persistent memory, which doesn't even really exist yet, and yet will supposedly dominate computing for the next decade. Are we going to get new versions of programming languages to take advantage of this technology, or are we going to continue down the path of becoming wholly reliant on super-intelligent compilers to do paradigm translation?

Do we really want a world where only computers know how to program computers anymore?