Re: [boost] [flat_map] Any interest in a flat_map variant that is much faster on insertion/erase at the price of a slower lookup?

Subject: Re: [boost] [flat_map] Any interest in a flat_map variant that is much faster on insertion/erase at the price of a slower lookup?
From: Giacomo Drago (giacomo_at_[hidden])
Date: 2015-03-16 06:52:14

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