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?

"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." Would it be easy for you to provide benchmarks of std::map with boost::container::node_allocator available in latest boost release? According to my own benchmarks it can improve performance a lot, mainly when memory is likely to be fragmented. Regards, Marcelo 2015-03-13 6:11 GMT-03:00 Giacomo Drago :

On 2015-03-13 08:27, Dominique Devienne wrote:

...

On Fri, Mar 13, 2015 at 9:22 AM, Ion Gaztañaga wrote:

...

Just a question. Are your insertions one by one or by range?

Might also be interesting to know if your perf numbers are based on a primitive key or a UDT, and whether the relative performance changes depending on key/value sizes. --DD

Insertions are one by one, and they are random with respect to the order of the keys. Same applies for lookups and erasures. No cheating.

I will try with different keys that are not PDOs and have non-trivial comparators, but I expect the benchmarks to reflect my previous findings. The bottom line is that it makes fewer comparisons and swaps when inserting and removing, and more comparisons when looking up. Elements are not *quite* sorted into the storage vector, of course.

The main use case I see for this data structure - and I am already using it even though not in a production environment - is that you may need a very space-efficient associative, sorted container that is not so painfully slow when it comes to insert/erase elements.

I'll send more benchmarks. Any interest in the general design and the source code (not "boostified" yet)?

Best Giacomo

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost