Subject: [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-13 03:51:54
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
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
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk