On Fri, 1 Sept 2023 at 09:59, Jonathan Wakely <jwak...@redhat.com> wrote: > > On Tue, 29 Aug 2023 at 20:52, François Dumont via Libstdc++ > <libstd...@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 > >
