On 2015-03-15 22:33, Marcelo Zimbres wrote:
"The size of the keys seems to make quite a difference. And of course, one has to consider the overhead given by the pointers in a linked structure, however allocations are performed.
What are your thoughts?"
Hi Giacomo,
thanks for providing these benchmarks with booost::container::node_allocator. My point is that the performance of std::map depends so much on the allocation strategy used that it is almost unfair to compare its benchmark when using the standard allocator. One can draw conclusions about its bad performance when the real problem may be on the allocator used. I see for example that for size 50000 the boost::container::map with the node allocator performs better than your experimental map in all cases (specially on random insertion and erase).
You may want to have a look on this plot [1] of my own benchmarks of std::set. It will give you an idea of how much the allocator influences the performance.
Thank you for your feedback. While I see your point, I think one does not choose a flat_map over a linked structure only for having faster lookups. We are talking about an associative container with no memory overhead, and, possibly, faster lookups. When I am in need of an associative, sorted container, in 95% of the cases I would opt for the vanilla std::map, with or without a better allocator. But we are addressing specific needs here. The comparison I am making is between boost's flat_map and my "experimental" flat_map, with a linked-structure map providing just the baseline to understand what are the trade-offs involved. Furthermore, comparing insertion/erasure performance of std::map (with or without boost::container::node_allocator) with insertion/erasure in whatever flat map is...uhm...pointless. It's... well... another Big-O. Everybody knows the linked structure to have blazing fast insertions and erasures when compared to a vector where you have to move elements around. I also point you to the size 50000 benchmark when the key is a 4-integer PDO. Said that, thank you for talking about the importance of allocators: I'll keep that in mind for future benchmarks. Best Giacomo