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

[François Dumont]

     Here is the proposal to remove shrinking feature from hash policy. 
I have also considered your remark regarding usage of lower_bound so 
_M_bkt_for_elements doesn't call _M_next_bkt (calling lower_bound) 
anymore. For 2 of the 3 calls it was only a source of redundant 
lower_bound invocations, in the last case I call _M_next_bkt explicitly.

2012-11-13  François Dumont  <fdumont@gcc.gnu.org>

     * include/bits/hashtable_policy.h (_Prime_rehash_policy): Remove
     automatic shrink.
     (_Prime_rehash_policy::_M_bkt_for_elements): Do not call
     _M_next_bkt anymore.
     (_Prime_rehash_policy::_M_next_bkt): Move usage of
     _S_growth_factor ...
     (_Prime_rehash_policy::_M_need_rehash): ... here.
     * include/bits/hashtable.h (_Hashtable<>): Adapt.

Tested under linux x86_64, normal and debug modes.

Regarding performance, I have done a small evolution of the 54075.cc 
test proposed last time. It is now checking performance with and without 
cache of hash code. Result is:

54075.cc                     std::unordered_set 300000 Foo insertions 
without cache       9r    9u    0s 13765616mem    0pf
54075.cc                     std::unordered_set 300000 Foo insertions 
with cache      14r   13u    0s 18562064mem    0pf
54075.cc                     std::tr1::unordered_set 300000 Foo 
insertions without cache       9r    8u    1s 13765616mem    0pf
54075.cc                     std::tr1::unordered_set 300000 Foo 
insertions with cache      14r   13u    0s 18561952mem    0pf

     So the difference of performance in this case only seems to come 
from caching the hash code or not. In reported use case default behavior 
of std::unordered_set is to cache hash codes and std::tr1::unordered_set 
not to cache it. We should perhaps review default behavior regarding 
caching the hash code. Perhaps cache it if the hash functor can throw 
and not cache it otherwise, not easy to find out what's best to do.

François


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.
>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: hash_policy.patch
Type: text/x-patch
Size: 6026 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20121113/81fcca48/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 54075.cc
Type: text/x-c++src
Size: 2280 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20121113/81fcca48/attachment-0001.bin>