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

[François Dumont]

Hi

     Is there a chance for this patch to be integrated for next gcc 
release ?

François


On 23/09/21 6:36 am, François Dumont wrote:
> Ping ?
>
> On 16/08/21 9:03 pm, François Dumont wrote:
>> 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: 19625 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20211221/0218af37/attachment.bin>