In an access pattern where the same elements are requested over and over this very quickly brings those elements to the front, giving really fast access times. This super simple data structure would totally blow the rest out of the water on this benchmark, and should illustrate the issue with it quite well.
Don't blindly throw work at multiple cores low down in algorithms. Amdahl's law tells you that the pay off is likely low, and if the program already makes proper use of the cores you're just going to slow things down.
That program is just a benchmark to map millions of string to integers, it's valid to optimize processing.
What about the inability to exit a parallel region--I was under the impression that once you start a parallel for, you can't exit it until it's run through the entire iteration.
Another thing I noticed is it starts with the example of a type column on a database, then proceeds to use graphs with a logarithmic scale on the x axis but not the y axis, so you can basically only see two data points, which are for millions of strings. He also only uses long strings, where I would expect the type column to be the opposite
This means even if the benchmarks were valid, I still wouldn't know what to use if I wanted to map 2-10 different short strings to numbers I wouldn't know what the right answer is. Of course the real right answer for that case, which I'd guess is a perfect hash function, wasn't tested.
Operations have the typical complexity of the data structure. Nothing fancy.
- It looks up the same key on every iteration, so every level of the trie stays in the cache, no matter how large the nominal data set size is.
- The setup appears to be such that even though the key is 128 bytes, it's probably not going to share a prefix longer than 4-5 bytes.
- The code is constructing a temporary string of the 128 byte key for every lookup in the hash table (by going from a string to char-pointer to string), but not for the trie.
So it first eliminates the problems of a trie (especially the cache inefficiency) by an unrealistic test setup, and then has a bug introducing probably a factor of 2 unnecessary overhead to the hash table.