[PATCH][Hashtable] Performance optimization through use of insertion hint
Jonathan Wakely
jwakely@redhat.com
Fri Sep 1 09:00:23 GMT 2023
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
> >
More information about the Libstdc++
mailing list