4 ms·
The benchmark is kind of dodgy. - 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 d
by jsnell 10y ago
The benchmark is kind of dodgy.
- 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.
- trishume 10y agoSo basically none of the results are remotely relevant to real use. Except maybe that unordered_map is faster on large data sets than map. 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.
- user5994461 10y agomap is a red and black tree, unordered_map is a hash table. Operations have the typical complexity of the data structure. Nothing fancy.
- trishume 10y agoExactly. I predicted every benchmark result except for the trie one, which surprised me a ton (wut??!! but pointer chasing costs!), apparently though that was just bad benchmarking putting the only path ever tested in cache.
- nightcracker 10y agoThere's an incredibly simple algorithm for such an access pattern. Store all values in a vector, without regards for order. Then when an element is requested, find it's index i with a linear scan and swap elements i and i/2. 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.
- jnordwick 10y agoReminds me of the tricks self-balancing trees do, rotating the most accessed elements towards the root.
- pacaro 10y agoIn particular splay trees do this by rotating elements to the top whenever they are accessed (IIRC) and while they aren't formally balanced, they tend to be "balanced enough" -- if you only ever access a few elements, they will be clustered at the top and the structure of the rest of the tree doesn't matter
- jnordwick 10y agoWe've done few variations of those for representing parts of a trading book where you often have a few price points (the inside) are hit more often and their performance is more important. Self-balancing data structures are very cool.
- user5994461 10y agoAnd enable OpenMP afterwards, to process the 1 million strings in parallel using all the available cores.
- R_haterade 10y agoI'm learning Omp right now, and I'm excited about it, but my sarcasm filter is off today--are you serious about this? 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.