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

[Jonathan Wakely <jwakely@redhat.com>]

On Fri, 1 Sept 2023 at 09:59, Jonathan Wakely <jwakely@redhat.com> 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 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

Or at least decide what to do about it...


>
>
> >
> > 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
> >