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