This article reminds me of performance advice I was starting to see in the 2000s decade. Basically it was to not introduce a bunch of pointer heavy data structures to get lower algorithmic complexity. Stuff it all into a vector. You will use some algorithms that the computer science textbook will say it's slower, but if it fits all in cache it doesn't matter. The cache misses following pointers all over town hurts you more.
While this advice isn't wrong, it is misleading. In my benchmarks std::map beats vector after 9 elements. Less than that and linear search is better but branch prediction and cache loading is very good.
Run your own benchmarks on your own data of course. Also map is not considered the best key value store.
Actually it really depends, because allocators can also be kind of smart (and you don't have to use the default allocator).
And then, on the other hand - I really doubt GP's map beats a vector, with all of those pointers bins and stuff, in a non-contrived benchmark with 10 elements.
Finally - it's not either-or: There are better hash maps whose memory is sequentially allocated and/or are otherwise cache-aware. And there are data structures geared towards parallel execution on multiple threads; and towards SIMD; etc. etc.
I’ve definitely been on teams where they ran the numbers, and found that they were mostly working with smaller containers, and std::vector was the way to go.
If you’re down to that sort of decision-making, you have to measure.
asveikau · · focus · HN ↗
bluGill · · focus · HN ↗
Run your own benchmarks on your own data of course. Also map is not considered the best key value store.
mandarax8 · · focus · HN ↗
This likely won't be true in a real application with a non-trivial allocation pattern.
einpoklum · · focus · HN ↗
And then, on the other hand - I really doubt GP's map beats a vector, with all of those pointers bins and stuff, in a non-contrived benchmark with 10 elements.
Finally - it's not either-or: There are better hash maps whose memory is sequentially allocated and/or are otherwise cache-aware. And there are data structures geared towards parallel execution on multiple threads; and towards SIMD; etc. etc.
bluGill · · focus · HN ↗
Still a custom map that allocated a bunch of nodes would be a useful optimization.
danbolt · · focus · HN ↗
If you’re down to that sort of decision-making, you have to measure.
someonebaggy · · focus · HN ↗