Currently, each internal node has a node_base that determines the offset within the node vector where its children are located. Since internal nodes are ordered by tiers, the max distance between a parent and its children is 2^(STRIDE*2). With STRIDE of 6 this means 4096, which would easily fit in a u16, which is smaller than the u32 that it currently has. Applying this to both leaves and nodes may compress the trie, improving cache locality. During lookup, instead of getting a value and summing it with another, this would mean summing both these numbers to an accumulator, which can also be more efficient. Inserts would be more efficient as well since less bases would need to be updated (only subsequent brothers, as opposed to all subsequent nodes). The cost would be that it would be a bit harder on remove.
Currently, each internal node has a
node_basethat determines the offset within the node vector where its children are located. Since internal nodes are ordered by tiers, the max distance between a parent and its children is2^(STRIDE*2). WithSTRIDEof 6 this means 4096, which would easily fit in au16, which is smaller than theu32that it currently has. Applying this to both leaves and nodes may compress the trie, improving cache locality. During lookup, instead of getting a value and summing it with another, this would mean summing both these numbers to an accumulator, which can also be more efficient. Inserts would be more efficient as well since less bases would need to be updated (only subsequent brothers, as opposed to all subsequent nodes). The cost would be that it would be a bit harder on remove.