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?

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:33:48

On 2015-03-13 15:55, Giacomo Drago wrote:
> On 2015-03-13 13:00, Marcelo Zimbres wrote:
>> "Hi
>> 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.
>
> Of course, I will do it ASAP.
>

Hi Marcelo,

I tried to do some benchmarks with boost::container::node_allocator. I 
found little or no examples on how to use it. I tried to provide it as 
the fourth parameter of std::map and I got weird compiler errors, so I 
fell back to boost::container::map.

This is what I get with integer keys:

             Size: 50000
std::map:
        Random insertion: 16.916 ms
        Random find: 24.702 ms
        Iteration: 7.528 ms
        Random erase: 40.328 ms
boost::container::map<..., boost::container::node_allocator<...>>:
        Random insertion: 13.085 ms
        Random find: 11.189 ms
        Iteration: 5.301 ms
        Random erase: 34.896 ms
experimental::flat_map:
        Random insertion: 347.988 ms
        Random find: 11.603 ms
        Iteration: 7.723 ms
        Random erase: 494.447 ms
boost::container::flat_map:
        Random insertion: 644.319 ms
        Random find: 5.481 ms
        Iteration: 0.106 ms
        Random erase: 624.03 ms

             Size: 200000
std::map:
        Random insertion: 120.064 ms
        Random find: 142.521 ms
        Iteration: 22.736 ms
        Random erase: 212.725 ms
boost::container::map<..., boost::container::node_allocator<...>>:
        Random insertion: 106.19 ms
        Random find: 86.353 ms
        Iteration: 19.375 ms
        Random erase: 169.475 ms
experimental::flat_map:
        Random insertion: 5207.11 ms
        Random find: 72.71 ms
        Iteration: 36.488 ms
        Random erase: 6861.92 ms
boost::container::flat_map:
        Random insertion: 10995 ms
        Random find: 50.254 ms
        Iteration: 0.317 ms
        Random erase: 10924.4 ms

This what I get with a 4-integer struct as the key:

             Size: 50000
std::map:
        Random insertion: 15.269 ms
        Random find: 19.85 ms
        Iteration: 7.1 ms
        Random erase: 45.85 ms
boost::container::map<..., boost::container::node_allocator<...>>:
        Random insertion: 18.278 ms
        Random find: 31.747 ms
        Iteration: 4.911 ms
        Random erase: 33.039 ms
experimental::flat_map:
        Random insertion: 551.777 ms
        Random find: 12.955 ms
        Iteration: 7.921 ms
        Random erase: 688.911 ms
boost::container::flat_map:
        Random insertion: 1040.7 ms
        Random find: 7.71 ms
        Iteration: 0.161 ms
        Random erase: 870.031 ms

             Size: 200000
std::map:
        Random insertion: 128.527 ms
        Random find: 137.222 ms
        Iteration: 21.572 ms
        Random erase: 206.251 ms
boost::container::map<..., boost::container::node_allocator<...>>:
        Random insertion: 124.658 ms
        Random find: 152.009 ms
        Iteration: 23.368 ms
        Random erase: 193.538 ms
experimental::flat_map:
        Random insertion: 7969.37 ms
        Random find: 92.236 ms
        Iteration: 41.396 ms
        Random erase: 10724.9 ms
boost::container::flat_map:
        Random insertion: 19883.7 ms
        Random find: 57.496 ms
        Iteration: 0.459 ms
        Random erase: 17759.1 ms

The size of the keys seems to make quite a difference. And of course, 
one has to consider the overhead given by the pointers in a linked 
structure, however allocations are performed.

What are your thoughts?

Giacomo