On 01/09/2023 10:59, Jonathan Wakely 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
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
