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-13 09:00:52

"Hi

My library is not ready for a formal review process, and I'd like to
ask whether there is some potential interest first, thus saving
everybody a lot of time.

I have been working on a flat_map
(http://www.boost.org/doc/libs/1_57_0/doc/html/boost/container/flat_map.html)
variant that keeps some of the distinctive features of the original
one (contiguous storage/cache friendliness, zero memory
overhead/shrink_to_fit support, vector-based representation, etc...)
but makes insertion and erasure of the elements much faster, at the
price of a slower lookup and in-order traversal."

Would it be easy for you to provide benchmarks of std::map with
boost::container::node_allocator available in latest boost release?
According to my own benchmarks it can improve performance a lot,
mainly when memory is likely to be fragmented.

Regards,
Marcelo

2015-03-13 6:11 GMT-03:00 Giacomo Drago <giacomo_at_[hidden]>:
> On 2015-03-13 08:27, Dominique Devienne wrote:
>>
>> On Fri, Mar 13, 2015 at 9:22 AM, Ion Gaztañaga <igaztanaga_at_[hidden]>
>> wrote:
>>>
>>>
>>> Just a question. Are your insertions one by one or by range?
>>>
>>
>> Might also be interesting to know if your perf numbers are based on a
>> primitive key or a UDT, and whether the relative performance changes
>> depending on key/value sizes. --DD
>
>
>
> Insertions are one by one, and they are random with respect to the order of
> the keys. Same applies for lookups and erasures. No cheating.
>
> I will try with different keys that are not PDOs and have non-trivial
> comparators, but I expect the benchmarks to reflect my previous findings.
> The bottom line is that it makes fewer comparisons and swaps when inserting
> and removing, and more comparisons when looking up. Elements are not *quite*
> sorted into the storage vector, of course.
>
> The main use case I see for this data structure - and I am already using it
> even though not in a production environment - is that you may need a very
> space-efficient associative, sorted container that is not so painfully slow
> when it comes to insert/erase elements.
>
> I'll send more benchmarks. Any interest in the general design and the source
> code (not "boostified" yet)?
>
> Best
> Giacomo
>
>
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost