Boost logo

Boost :

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

Said that, thank you for talking about the importance of allocators:
I'll keep that in mind for future benchmarks.


Boost list run by bdawes at, gregod at, cpdaniel at, john at