The source code of the trie program I wrote is here: https://github.com/benhoyt/countwords/blob/master/rust/optimized-trie/main.rs https://github.com/benhoyt/co

The source code of the trie program I wrote is here: https://github.com/benhoyt/countwords/blob/master/rust/optimized-trie/main.rs https://github.com/benhoyt/countwords/blob/master/rust/optim... The comments explain why I think it's slower. The TL;DR is that using a trie requires more memory accesses than a hash table (per byte of input), and those memory accesses slow the whole enterprise down. But, not all memory accesses are created equal. So perhaps a more clever representation that exploits locality better would do better. "Obvious" techniques for shrinking memory usage made a big difference and brought the performance of the trie program closer to C: https://github.com/benhoyt/countwords/pull/2 https://github.com/benhoyt/countwords/pull/2