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