Basically all the data fit in the CPU cache True, but it's the relatively-slow L3 cache (the L2 cache is at most 1MB for the processor being used for testing).

Basically all the data fit in the CPU cache True, but it's the relatively-slow L3 cache (the L2 cache is at most 1MB for the processor being used for testing). I think the biggest problem with this trie implementation is the amount of pointer-chasing due to the low branching factor. The step function does four (!) loads for every character, each depending on the result of the previous load. Real tries have much larger branching factors (and compress each node to avoid wasting tons of memory).