Re: [PATCH][Hashtable] Performance optimization through use of insertion hint

["François Dumont" <frs.dumont@gmail.com>]

Hi

Any feedback regarding this patch ?

François

On 24/07/2023 13:02, François Dumont wrote:
> libstdc++: [_Hashtable] Make more use of insertion hint
>
>
>     When inserting an element into an empty bucket we currently insert 
> the new node
>     after the before-begin node so in first position. The drawback of 
> doing this is
>     that we are forced to update the bucket that was containing this 
> before-begin
>     node to point to the newly inserted node. To do so we need at best 
> to do a modulo
>     to find this bucket and when hash code is not cached also compute it.
>
>     To avoid this side effect it is better to insert after the last 
> node. Adding
>     a member to keep track of this last node would be an abi breaking 
> change. Still we
>     can ask the user to maintain and provide this last node as an 
> insertion hint.
>
>     Adapt range insertion methods to try to detect the last node and 
> then use it as
>     the insertion hint.
>
>     libstdc++-v3/ChangeLog:
>
>             * include/bits/hashtable_policy.h:
>             (_Insert_base::try_emplace): Adapt to use hint.
>             (_Insert_base::_M_insert_range): Try to detect container 
> last node and use it
>             as hint for insertions.
>             (_Hash_code_base::_M_hash_code(const _Hash&, const 
> _Hash_node_value<>&)): Remove.
>             (_Hash_code_base::_M_hash_code<_H2>(const _H2&, const 
> _Hash_node_value<>&)): Remove.
>             * include/bits/hashtable.h
>             (_Hashtable<>::_M_insert_bucket_begin): Add hint parameter 
> and use it when inserting
>             into an empty bucket if hint is the last container node.
>             (_Hashtable<>::_InsertInfo): New struct.
>             (_Hashtable<>::_M_get_insert_info): New, return latter.
>             (_Hashtable<>::_M_insert_multi_node): Add _InsertInfo 
> parameter.
>             (_Hashtable<>::_M_insert_unique_node): Add __node_ptr hint 
> parameter.
>             (_Hashtable<>::_M_emplace_unique(__node_ptr, _Args&&...)): 
> New.
>             (_Hashtable<>::_M_emplace_multi(__node_ptr, _Args&&...)): 
> New.
>             (_Hashtable<>::_M_emplace()): Adapt to use latters.
>             (_Hashtable<>::_M_insert_unique): Add __node_ptr parameter.
>             (_Hashtable<>::_M_insert_unique_aux): Add __node_ptr 
> parameter.
>             (_Hashtable<>::_M_insert(__node_ptr, _Arg&&, const 
> _NodeGenerator&, true_type)):
>             Use latter.
>             (_Hashtable<>::_M_reinsert_node(const_iterator, 
> node_type&&)):
>             Add hint parameter, adapt to use it.
>             (_Hashtable<>::_M_reinsert_node_multi): Use hint parameter 
> if available to extract
>             hash code.
>             (_Hashtable<>::_M_compute_hash_code(const _Hash&, 
> __node_ptr, __node_ptr,
>             const key_type&)): New.
> (_Hashtable<>::_M_compute_hash_code<_H2>(const _H2&, __node_ptr, 
> __node_ptr,
>             const key_type&)): New.
>             (_Hashtable<>::_M_merge_unique): Adapt to use latter. 
> Implement small size
>             optimization.
>             (_Hashtable<>::_M_get_insert_info(const _Hash&, 
> __node_ptr, __node_ptr,
>             const key_type&)): New.
> (_Hashtable<>::_M_get_insert_info<_H2>(const _H2&, __node_ptr, 
> __node_ptr,
>             const key_type&)): New.
>             (_Hashtable<>::_M_merge_multi): Adapt to use latter.
>             * include/bits/unordered_map.h 
> (unordered_map<>::insert(node_type&&)): Pass cend as
>             hint.
>             (unordered_map<>::insert(const_iterator, node_type&&)): 
> Adapt to use hint.
>             * include/bits/unordered_set.h 
> (unordered_set<>::insert(node_type&&)): Pass cend as
>             hint.
>             (unordered_set<>::insert(const_iterator, node_type&&)): 
> Adapt to use hint.
>             * 
> testsuite/23_containers/unordered_multimap/insert/hint.cc: Adapt 
> implementation
>             specific tests.
>
> Tested under linux x86_64.
>
> Here is the performance results of this patch, before:
>
> unordered_multiset_hint.cc-thread    hash code NOT cached 2000000 
> insertions w/o hint      94r   94u    0s 191999712mem    0pf
> unordered_multiset_hint.cc-thread    hash code NOT cached 2000000 
> insertions with perfect hint      95r   94u    0s 191999712mem 0pf
> unordered_multiset_hint.cc-thread    hash code NOT cached 2000000 
> insertions with bad hint      94r   94u    0s 191999712mem    0pf
> unordered_multiset_hint.cc-thread    hash code NOT cached 2000000 
> range insertions      88r   88u    0s 191999712mem    0pf
> unordered_multiset_hint.cc-thread    hash code cached 2000000 
> insertions w/o hint      91r   91u    0s 191999712mem    0pf
> unordered_multiset_hint.cc-thread    hash code cached 2000000 
> insertions with perfect hint      92r   93u    0s 191999712mem 0pf
> unordered_multiset_hint.cc-thread    hash code cached 2000000 
> insertions with bad hint      93r   93u    0s 191999712mem    0pf
> unordered_multiset_hint.cc-thread    hash code cached 2000000 range 
> insertions      88r   88u    0s 191999712mem    0pf
> unordered_set_hint.cc-thread    hash code NOT cached 2000000 
> insertions w/o hint      94r   95u    0s 191999712mem    0pf
> unordered_set_hint.cc-thread    hash code NOT cached 2000000 
> insertions with perfect hint      94r   95u    0s 191999712mem 0pf
> unordered_set_hint.cc-thread    hash code NOT cached 2000000 
> insertions with bad hint      94r   94u    0s 191999712mem    0pf
> unordered_set_hint.cc-thread    hash code NOT cached 2000000 range 
> insertions      90r   90u    0s 191999712mem    0pf
> unordered_set_hint.cc-thread    hash code cached 2000000 insertions 
> w/o hint      68r   68u    0s 223999264mem    0pf
> unordered_set_hint.cc-thread    hash code cached 2000000 insertions 
> with perfect hint      67r   67u    0s 223999264mem 0pf
> unordered_set_hint.cc-thread    hash code cached 2000000 insertions 
> with bad hint      68r   68u    0s 223999264mem    0pf
> unordered_set_hint.cc-thread    hash code cached 2000000 range 
> insertions      62r   62u    0s 223999264mem    0pf
>
> After:
>
> unordered_multiset_hint.cc-thread    hash code NOT cached 2000000 
> insertions w/o hint      93r   93u    0s 191999712mem    0pf
> unordered_multiset_hint.cc-thread    hash code NOT cached 2000000 
> insertions with perfect hint      58r   59u    0s 191999712mem 0pf
> unordered_multiset_hint.cc-thread    hash code NOT cached 2000000 
> insertions with bad hint      93r   94u    0s 191999712mem    0pf
> unordered_multiset_hint.cc-thread    hash code NOT cached 2000000 
> range insertions      52r   51u    0s 191999712mem    0pf
> unordered_multiset_hint.cc-thread    hash code cached 2000000 
> insertions w/o hint      96r   95u    0s 191999712mem    0pf
> unordered_multiset_hint.cc-thread    hash code cached 2000000 
> insertions with perfect hint      61r   62u    0s 191999712mem 0pf
> unordered_multiset_hint.cc-thread    hash code cached 2000000 
> insertions with bad hint      94r   94u    0s 191999712mem    0pf
> unordered_multiset_hint.cc-thread    hash code cached 2000000 range 
> insertions      52r   52u    0s 191999712mem    0pf
> unordered_set_hint.cc-thread    hash code NOT cached 2000000 
> insertions w/o hint      96r   95u    0s 191999712mem    0pf
> unordered_set_hint.cc-thread    hash code NOT cached 2000000 
> insertions with perfect hint      58r   59u    0s 191999712mem 0pf
> unordered_set_hint.cc-thread    hash code NOT cached 2000000 
> insertions with bad hint      94r   94u    0s 191999712mem    0pf
> unordered_set_hint.cc-thread    hash code NOT cached 2000000 range 
> insertions      52r   52u    0s 191999712mem    0pf
> unordered_set_hint.cc-thread    hash code cached 2000000 insertions 
> w/o hint      70r   69u    0s 223999264mem    0pf
> unordered_set_hint.cc-thread    hash code cached 2000000 insertions 
> with perfect hint      67r   67u    0s 223999264mem 0pf
> unordered_set_hint.cc-thread    hash code cached 2000000 insertions 
> with bad hint      67r   67u    0s 223999264mem    0pf
> unordered_set_hint.cc-thread    hash code cached 2000000 range 
> insertions      63r   62u    0s 223999264mem    0pf
>
> Ok to commit ?
>
> François