[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2

[François Dumont]

On 11/09/2012 11:50 AM, Paolo Carlini wrote:
> Hi again,
>
> +    // To get previous bound we use _S_growth * 2 to avoid 
> ocillations in the
> +    // number of buckets when looping on insertion/removal of elements.
>      const unsigned long* __prev_bkt
> -      = std::lower_bound(__prime_list + 1, __next_bkt, __n / 
> _S_growth_factor);
> +      = std::lower_bound(__prime_list + 1, __next_bkt,
> +             __n / _S_growth_factor / _S_growth_factor);
>
> Looks like, here you are dividing by _S_Growth ^ 2? Is it intended? 
> But anyway, in my opinion the very my _M_prev_resize idea (thus rehash 
> shrinking, right?) is proving quite fragile and we also got negative 
> comments from the users about shrinking, which is new. Before pursuing 
> it further, I think we should double check what the other 
> implementations do, are they also shrinking? Because otherwise we 
> could, at least for the time being, remove the related bits and save 
> ourselves many headaches...
>
> Paolo.
>
     AFAIK not many other implementation are doing shrinking. I heard 
that Google had an implementation with a min load factor resulting in 
the hash container to shrink automatically.

     At the time I introduced shrinking I only see advantages. A mistake 
I made is to introduce it without reviewing hash policy interface with 
the hashtable. Having to play with _M_prev_resize in hashtable is 
abnormal and could be avoided by using different methods. But I agree 
that this concept is new and maybe unexpected to usual users of hash 
containers. It should be transparent but those using reserve/rehash to 
pre-size the container might not appreciate it to finally shrink once 
this size has been reached.

     So I am going to prepare a patch that will remove this aspect of 
the hash policy.I should be able to get it ready for Tuesday.

François