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

Tue, 29 Aug 2023 12:52:18 -0700 

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

Reply via email to