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-14 20:35:47

OK, it is time for me to decide whether to submit this or not. Can this 
flat_map reasonably make it into Boost? If not, I'll push it on GitHub 
after polishing the source code.

I thank you all for your kind feedback!

Giacomo

On 2015-03-13 07:51, Giacomo Drago wrote:
> 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.
>
> Explaining how it works requires time and it's not really necessary if
> there is no interest in the first place (e.g. "thanks, but we have no
> use for this"). Let's get straight to the benchmarks and to some
> conclusions.
>
>              #elems: 50000
> std::map:
>      Random insertion: 18.605 ms
>      Random find: 24.382 ms
>      Iteration: 5.658 ms
>      Random erase: 37.166 ms
> experimental::flat_map:
>      Random insertion: 400.141 ms
>      Random find: 12.352 ms
>      Iteration: 7.099 ms
>      Random erase: 467.051 ms
> boost::container::flat_map:
>      Random insertion: 611.678 ms
>      Random find: 6.293 ms
>      Iteration: 0.038 ms
>      Random erase: 615.311 ms
>
>              #elems: 200000
> std::map:
>      Random insertion: 146.394 ms
>      Random find: 163.506 ms
>      Iteration: 21.973 ms
>      Random erase: 225.314 ms
> experimental::flat_map:
>      Random insertion: 5068.93 ms
>      Random find: 65.618 ms
>      Iteration: 34.244 ms
>      Random erase: 6851.09 ms
> boost::container::flat_map:
>      Random insertion: 10696.9 ms
>      Random find: 43.896 ms
>      Iteration: 0.254 ms
>      Random erase: 10604 ms
>
>
> Of course one doesn't expect the random insertion to have a performance
> that is comparable to the one of a tree-based map, like std::map.
> However, my experimental::flat_map provides a better trade-off than
> boost's flat_map for me, as random insertion is massively faster and in
> the big picture of the application I am developing this is making a hell
> of a difference.
>
> Am I making any sense? Shall I polish the implementation, publish it,
> and submit a proposal? I'd really appreciate your feedback.
>
> Kind Regards
> Giacomo
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>