[PATCH 1/5][_Hashtable] Make more use of user provided hint

[François Dumont]

libstdc++: [_Hashtable] Make more use of insertion hint

Make use of the user provided hint iterator in unordered containers 
operations.

Hint is used:
- As a hint for allocation to potentially reduce memory fragmentation.
- For unordered_set/unordered_map we check if it does not match the key 
of the
element to insert, before computing the hash code.
- For unordered_multiset/unordered_multimap, if equals to the key of the 
element
to insert, the hash code is taken from the hint so that we can take 
advantage of
the potential hash code cache.

libstdc++-v3/ChangeLog:

     * include/bits/hashtable_policy.h (_NodeBuilder<>::_S_build): Add 
_NodePtr template
     parameter.
     (_ReuseOrAllocNode::operator()): Add __node_ptr parameter.
     (_AllocNode::operator()): Likewise.
     (_Insert_base::try_emplace): Adapt to use hint.
     (_Hashtable_alloc<>::_M_allocate_node(__node_ptr, _Args&&...)): Add 
__node_ptr parameter.
     * include/bits/hashtable.h
     (_Hashtable<>::_Scope_node<>(__hashtable_alloc*, __node_ptr, 
_Args&&...)):
     Add __node_ptr parameter.
     (_Hashtable<>::_M_get_hint(size_type, __node_ptr)): New.
     (_Hashtable<>::_M_emplace_unique(const_iterator, _Args&&...)): New.
     (_Hashtable<>::_M_emplace_multi(const_iterator, _Args&&...)): New.
     (_Hashtable<>::_M_emplace()): Adapt to use latter.
     (_Hashtable<>::_M_insert_unique): Add const_iterator parameter.
     (_Hashtable<>::_M_insert(const_iterator, _Arg&&, const 
_NodeGenerator&, true_type)):
     Use latter.
     (_Hashtable<>::_M_reinsert_node(const_iterator, node_type&&)):
     Add const_iterator parameter, adapt to use it.
     (_Hashtable<>::_M_reinsert_node_multi): Make more use of hint 
parameter.
     * 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.

Tested under Linux x86_64.

François
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 1_hashtable_hint.patch
Type: text/x-patch
Size: 22014 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20220620/2d87dbca/attachment-0001.bin>