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

[François Dumont]

On 01/09/2023 10:59, Jonathan Wakely wrote:
> On Tue, 29 Aug 2023 at 20:52, François Dumont via Libstdc++
> <libstdc++@gcc.gnu.org> wrote:
>> Hi
>>
>> Any feedback regarding this patch ?
> This is a fairly large patch

I've decided to split it, at least in 2.

So just ignore this one, I'll submit new ones once abi issue is fixed.

>   and before we make any more changes to
> unordered containers we have an ABI break to fix:
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111050
>
>
>> 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