[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: [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

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