[PATCH][Hashtable 6/6] PR 68303 small size optimization

[François Dumont]

On 17/07/20 2:58 pm, Jonathan Wakely wrote:
> On 17/11/19 22:31 +0100, François Dumont wrote:
>> This is an implementation of PR 68303.
>>
>> I try to use this idea as much as possible to avoid computation of 
>> hash codes.
>>
>> Note that tests are not showing any gain. I guess hash computation 
>> must be quite bad to get a benefit from it. So I am only activating 
>> it when hash code is not cached and/or when computation is not fast.
>
> If the tests don't show any benefit, why bother making the change?

I eventually managed to demonstrate this optimization through a 
performance test case.

>
> Does it help the example in the PR?

No, the code attached to the PR just show what the user has done to put 
in place this optim on his side.

What I needed was a slow hash code computation compared to the equal 
operation. I realized that I had to use longer string to achieve this.

Moreover making this optim dependant on _Hashtable_traits::__hash_cached 
was just wrong as we cannot use the cached hash code here as the input 
is a key instance, not a node.

I introduce _Hashtable_hash_traits<_Hash> to offer a single 
customization point as this optim depends highly on the difference 
between a hash code computation and a comparison. Maybe I should put it 
at std namespace scope to ease partial specialization ?

Performance test results before the patch:

unordered_small_size.cc      std::unordered_set<int>: 1st insert      
40r   32u    8s 264000112mem    0pf
unordered_small_size.cc      std::unordered_set<int>: find/erase      
22r   22u    0s -191999808mem    0pf
unordered_small_size.cc      std::unordered_set<int>: 2nd insert      
36r   36u    0s 191999776mem    0pf
unordered_small_size.cc      std::unordered_set<int>: erase key       
25r   25u    0s -191999808mem    0pf
unordered_small_size.cc      std::unordered_set<string>: 1st insert    
  404r  244u  156s -1989936256mem    0pf
unordered_small_size.cc      std::unordered_set<string>: find/erase    
  315r  315u    0s 2061942272mem    0pf
unordered_small_size.cc      std::unordered_set<string>: 2nd insert    
  233r  233u    0s -2061942208mem    0pf
unordered_small_size.cc      std::unordered_set<string>: erase key     
  299r  298u    0s 2061942208mem    0pf

after the patch:

unordered_small_size.cc      std::unordered_set<int>: 1st insert      
41r   33u    7s 264000112mem    0pf
unordered_small_size.cc      std::unordered_set<int>: find/erase      
24r   25u    1s -191999808mem    0pf
unordered_small_size.cc      std::unordered_set<int>: 2nd insert      
34r   34u    0s 191999776mem    0pf
unordered_small_size.cc      std::unordered_set<int>: erase key       
25r   25u    0s -191999808mem    0pf
unordered_small_size.cc      std::unordered_set<string>: 1st insert    
  399r  232u  165s -1989936256mem    0pf
unordered_small_size.cc      std::unordered_set<string>: find/erase    
  196r  197u    0s 2061942272mem    0pf
unordered_small_size.cc      std::unordered_set<string>: 2nd insert    
  221r  222u    0s -2061942208mem    0pf
unordered_small_size.cc      std::unordered_set<string>: erase key     
  178r  178u    0s 2061942208mem    0pf

     libstdc++: Optimize operations on small size hashtable [PR 68303]

     When hasher is identified as slow and the number of elements is 
limited in the
     container use a brute-force loop on those elements to look for a 
given key using
     the key_equal functor. For the moment the default threshold below 
which the
     container is considered as small is 20.

     libstdc++-v3/ChangeLog:

             PR libstdc++/68303
             * include/bits/hashtable_policy.h
             (_Hashtable_hash_traits<_Hash>): New.
             (_Hash_code_base<>::_M_hash_code(const 
_Hash_node_value<>&)): New.
             (_Hashtable_base<>::_M_key_equals): New.
             (_Hashtable_base<>::_M_equals): Use latter.
             (_Hashtable_base<>::_M_key_equals_tr): New.
             (_Hashtable_base<>::_M_equals_tr): Use latter.
             * include/bits/hashtable.h
             (_Hashtable<>::__small_size_threshold()): New, use 
_Hashtable_hash_traits.
             (_Hashtable<>::find): Loop through elements to look for key 
if size is lower
             than __small_size_threshold().
             (_Hashtable<>::_M_emplace(true_type, _Args&&...)): Likewise.
             (_Hashtable<>::_M_insert_unique(_Kt&&, _Args&&, const 
_NodeGenerator&)): Likewise.
(_Hashtable<>::_M_compute_hash_code(const_iterator, const key_type&)): New.
             (_Hashtable<>::_M_emplace(const_iterator, false_type, 
_Args&&...)): Use latter.
             (_Hashtable<>::_M_find_before_node(const key_type&)): New.
             (_Hashtable<>::_M_erase(true_type, const key_type&)): Use 
latter.
             (_Hashtable<>::_M_erase(false_type, const key_type&)): 
Likewise.
             * src/c++11/hashtable_c++0x.cc: Include 
<bits/functional_hash.h>.
             * testsuite/util/testsuite_performane.h
             (report_performance): Use 9 width to display memory.
             * 
testsuite/performance/23_containers/insert_erase/unordered_small_size.cc:
             New performance test case.

Tested under Linux x86_64.

Ok to commit ?

François

-------------- next part --------------
A non-text attachment was scrubbed...
Name: pr68303.patch
Type: text/x-patch
Size: 20515 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20210816/d0e7714c/attachment-0001.bin>