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

[François Dumont]

Attached patch applied.

2012-11-16  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.
     * testsuite/performance/23_containers/insert_erase/41975.cc: Add
     _USE_TR1 to force build using std::tr1 container.
     * testsuite/performance/23_containers/insert/unordered_set.cc:
     Likewise.
     * testsuite/performance/23_containers/insert/54075.cc: New.

Note that I have used std::random_device in 54075 test. I also preferred 
to test both std and std::tr1 containers in a single run without relying 
on a macro check. As long as we try to align std containers performance 
on tr1 ones it is better maybe later we could limit it to test only 
std:: container per default.

I have also added several use cases and here is the result:

54075.cc                     std::tr1::unordered_set without hash code 
cached 300000 Foo insertions      10r    9u    1s 13765616mem    0pf
54075.cc                     std::tr1::unordered_set without hash code 
cached 10 times insertion of 300000 Foo      21r   21u 0s        0mem    
0pf
54075.cc                     std::tr1::unordered_set with hash code 
cached 300000 Foo insertions      15r   14u    0s 18561984mem    0pf
54075.cc                     std::tr1::unordered_set with hash code 
cached 10 times insertion of 300000 Foo      23r   23u 0s        0mem    
0pf
54075.cc                     std::tr1::unordered_multiset without hash 
code cached 300000 Foo insertions       9r    8u    1s 13761968mem    0pf
54075.cc                     std::tr1::unordered_multiset without hash 
code cached 10 times insertion of 300000 Foo     113r 107u    7s 
126686848mem    0pf
54075.cc                     std::tr1::unordered_multiset with hash code 
cached 300000 Foo insertions     100r  100u    0s 18561984mem    0pf
54075.cc                     std::tr1::unordered_multiset with hash code 
cached 10 times insertion of 300000 Foo     111r 107u    4s 
174686864mem    0pf
54075.cc                     std::unordered_set without hash code cached 
300000 Foo insertions       9r    8u    1s 13761936mem 0pf
54075.cc                     std::unordered_set without hash code cached 
10 times insertion of 300000 Foo      34r   34u 0s        0mem    0pf
54075.cc                     std::unordered_set with hash code cached 
300000 Foo insertions      10r   10u    1s 18562000mem 0pf
54075.cc                     std::unordered_set with hash code cached 10 
times insertion of 300000 Foo      37r   37u 0s        0mem    0pf
54075.cc                     std::unordered_multiset without hash code 
cached 300000 Foo insertions       8r    9u    0s 13761936mem    0pf
54075.cc                     std::unordered_multiset without hash code 
cached 10 times insertion of 300000 Foo      34r   34u 0s        0mem    
0pf
54075.cc                     std::unordered_multiset with hash code 
cached 300000 Foo insertions      10r   10u    0s 18562000mem    0pf
54075.cc                     std::unordered_multiset with hash code 
cached 10 times insertion of 300000 Foo      37r   37u 0s        0mem    
0pf

     There is one surprising result; std::tr1::unordered_multiset is 
quite bad, I haven't check yet why and it is not my priority, I take it 
as a good news for the moment. The other important result is this one:
54075.cc                     std::tr1::unordered_set without hash code 
cached 10 times insertion of 300000 Foo      21r   21u 0s        0mem    0pf
54075.cc                     std::unordered_set without hash code cached 
10 times insertion of 300000 Foo      34r   34u 0s        0mem    0pf

     We can see that inserting the same elements again, that is to say 
detecting the collisions, is slower in the new implementation. It is the 
problem I had already signaled in bugzilla entry. In the new 
implementation when we need to look for bucket elements we have to check 
the hash code of each element to see if we are still in the same bucket, 
in the former there was a nullptr to signal the end of the bucket. I 
think I am going to try to add an empty node to mark the end of the 
bucket. It will introduce a memory tradeoff of one empty node for each 
non-empty bucket but it will also limit the impact of caching the hash 
code or node because we won't need to use it so often.

François



On 11/14/2012 11:54 AM, Paolo Carlini wrote:
> Hi,
>
> On 11/13/2012 10:40 PM, François Dumont wrote:
>> 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.
> Patch is Ok with me, please wait another day or two for comments and 
> then apply it.
>
> You can also add the performance testcase, of course, note however 
> that ::random isn't a standard C function, thus we shouldn't use it 
> unconditionally, either manage with std::rand from <cstdlib> or do 
> something completely different (maybe even <random> since you are 
> writing C++11 code anyway!). I would also recommend extending quite a 
> bit the runtime, 10x would be still completely sensible (but I guess, 
> without using much more memory)
>
> Paolo.
>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashtable.patch
Type: text/x-patch
Size: 12989 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20121116/6066674c/attachment.bin>