Hacker News Reader

Comment by bluGill | Hacker News Reader

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.

View on HN

Because in your benchmark all std::map nodes were allocated in succession, most likely being placed in adjacent memory locations...

This likely won't be true in a real application with a non-trivial allocation pattern.

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.

That might or might not be true in the real world. Often in my applications I'm creating at startup and then referencing later.

Still a custom map that allocated a bunch of nodes would be a useful optimization.

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.

That is not a plausible result, sorry. Perhaps you're using the painfully slow MSVC debug mode vector?

Reply on news.ycombinator.com