A trie, also known as a digital tree or prefix tree, is a type of search tree used for locating specific keys from within a set. These keys are most often strings, with links between nodes defined not by the entire key, but by individual characters. In order to access a key (to recover its value, change it, or remove it), the trie is traversed depth-first, following the links between nodes, which represent each character in the key.
In
we’ve taken a look at how it performs relative to std::unordered_set. while results were clearly favorable, I’ve got some great comments raising concerns with regards to cache locality and pointer chasing and memory usage.
Competitive programmers usually don’t use node pointers as links between trie nodes and, instead, use node pool to store all node information and integer offsets instead of pointers.
If we don’t expect more than 256 nodes, we can use 1 byte chars instead of 8 byte pointers, reducing node size by 8X. This also removes the need for node heap allocations and deallocations. What’s not to like about this?
I got so carried away with optimizations that I even replaced vector with an array of the exact size, so that we can also create constexpr tries.
Finally, let’s run the same benchmarks
Oh no, looks like even though it easily outperforms std::unordered_set, it’s slower than our naive Trie implementation :(
As always, let’s not jump to any conclusions. It’s important to measure everything in your specific context - use-case, compiler, hardware, their interaction or a number of other factors may affect production performance. So keep experimenting! You can use Compiler Explorer as a starting point - it’s very easy to use static_assert for testing with no instructions executed at runtime.