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!
On 2015-03-13 07:51, Giacomo Drago wrote:
> 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
> 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
> #elems: 50000
> Random insertion: 18.605 ms
> Random find: 24.382 ms
> Iteration: 5.658 ms
> Random erase: 37.166 ms
> Random insertion: 400.141 ms
> Random find: 12.352 ms
> Iteration: 7.099 ms
> Random erase: 467.051 ms
> Random insertion: 611.678 ms
> Random find: 6.293 ms
> Iteration: 0.038 ms
> Random erase: 615.311 ms
> #elems: 200000
> Random insertion: 146.394 ms
> Random find: 163.506 ms
> Iteration: 21.973 ms
> Random erase: 225.314 ms
> Random insertion: 5068.93 ms
> Random find: 65.618 ms
> Iteration: 34.244 ms
> Random erase: 6851.09 ms
> 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
> Unsubscribe & other changes:
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk