4 ms·
> 85,000 unique identifiers (1.4Mb). Basically all the data fit in the CPU cache, so what was being measured was mostly the number of steps needed for each alg
by bsdetector 11y ago
> 85,000 unique identifiers (1.4Mb).
Basically all the data fit in the CPU cache, so what was being measured was mostly the number of steps needed for each algorithm.
For most real uses, the cache is a large part of the performance. If you are using the data in order, the trie may be faster because the next entry will likely already be cached. If you are using data in random order or doing other work in between lookups, the hashtable may be faster because it only has to fetch 1 or 2 lines into the cache instead of several.
- panic 11y agoBasically 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).
- munificent 11y ago> For most real uses, the cache is a large part of the performance. In this case, the author is using this for a programming language compiler, so a small working set is a reasonable real-world size.