[PATCH][Hashtable] Performance optimization through use of insertion hint
Jonathan Wakely
jwakely@redhat.com
Fri Sep 1 08:59:50 GMT 2023
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
>
> 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