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: Marcelo Zimbres (mzimbres_at_[hidden])
Date: 2015-03-15 18:33:33

"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.

Regards,
Marcelo

[1] https://github.com/mzimbres/rtcpp/blob/master/fig/std_set_insertion.png

2015-03-15 15:14 GMT-03:00 Giacomo Drago <giacomo_at_[hidden]>:
> On 2015-03-15 16:15, Phil Endecott wrote:
>>
>> Giacomo Drago wrote:
>>>
>>> OK, it is time for me to decide whether to submit this or not.
>>
>>
>> Tell us how it works!
>>
>> (If you don't want to tell us how it works, then no, this is
>> not suitable for Boost.)
>>
>
> Of course I want, it is not secret, but usually people can express a (lack
> of) interest in something without knowing "how it works," like: "No, we
> don't need a time machine that brings you to the same time you are when you
> use it." By telling this, you save some time to the self-deluded inventor,
> and to yourselves.
>
> Anyway, I finally managed to find some time to publish the source code with
> a brief explanation: https://github.com/giacomodrago/flat_map
>
> Feel free to challenge whatever part of it. ;) Please don't remark (at least
> not now) the absence of proper iterators or exception safety, and any other
> implementation detail, because at the moment I still have to figure out
> whether this data structure is a reasonable idea in the first place. There's
> time for polishing it. Of course, if a bug is affecting the benchmarks,
> please tell me: I am sorry, it is not done on purpose.
>
> Best
> Giacomo
>
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost