* [PATCH 1/5][_Hashtable] Make more use of user provided hint
@ 2022-06-20 16:57 François Dumont
0 siblings, 0 replies; only message in thread
From: François Dumont @ 2022-06-20 16:57 UTC (permalink / raw)
To: libstdc++; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 2197 bytes --]
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
[-- Attachment #2: 1_hashtable_hint.patch --]
[-- Type: text/x-patch, Size: 22014 bytes --]
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 1b21b795f89..8318da168e3 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -302,9 +302,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Allocate a node and construct an element within it.
template<typename... _Args>
- _Scoped_node(__hashtable_alloc* __h, _Args&&... __args)
+ _Scoped_node(__hashtable_alloc* __h,
+ __node_ptr __hint, _Args&&... __args)
: _M_h(__h),
- _M_node(__h->_M_allocate_node(std::forward<_Args>(__args)...))
+ _M_node(__h->_M_allocate_node(__hint,
+ std::forward<_Args>(__args)...))
{ }
// Destroy element and deallocate node.
@@ -829,6 +831,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return nullptr;
}
+ // Gets a hint after which a node should be allocated given a bucket.
+ __node_ptr
+ _M_get_hint(size_type __bkt, __node_ptr __hint = nullptr) const
+ {
+ __node_base_ptr __node;
+ if (__node = _M_buckets[__bkt])
+ return __node != &_M_before_begin
+ ? static_cast<__node_ptr>(__node) : __hint;
+
+ return __hint;
+ }
+
// Insert a node at the beginning of a bucket.
void
_M_insert_bucket_begin(size_type, __node_ptr);
@@ -860,26 +874,40 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename... _Args>
std::pair<iterator, bool>
- _M_emplace(true_type __uks, _Args&&... __args);
+ _M_emplace_unique(const_iterator, _Args&&... __args);
+
+ template<typename... _Args>
+ iterator
+ _M_emplace_multi(const_iterator, _Args&&... __args);
+
+ template<typename... _Args>
+ std::pair<iterator, bool>
+ _M_emplace(true_type /*__uks*/, _Args&&... __args)
+ { return _M_emplace_unique(cend(), std::forward<_Args>(__args)...); }
template<typename... _Args>
iterator
- _M_emplace(false_type __uks, _Args&&... __args)
- { return _M_emplace(cend(), __uks, std::forward<_Args>(__args)...); }
+ _M_emplace(false_type /*__uks*/, _Args&&... __args)
+ { return _M_emplace_multi(cend(), std::forward<_Args>(__args)...); }
- // Emplace with hint, useless when keys are unique.
template<typename... _Args>
iterator
- _M_emplace(const_iterator, true_type __uks, _Args&&... __args)
- { return _M_emplace(__uks, std::forward<_Args>(__args)...).first; }
+ _M_emplace(const_iterator __hint, true_type /*__uks*/,
+ _Args&&... __args)
+ {
+ return _M_emplace_unique(__hint,
+ std::forward<_Args>(__args)...).first;
+ }
template<typename... _Args>
iterator
- _M_emplace(const_iterator, false_type __uks, _Args&&... __args);
+ _M_emplace(const_iterator __hint, false_type /*__uks*/,
+ _Args&&... __args)
+ { return _M_emplace_multi(__hint, std::forward<_Args>(__args)...); }
template<typename _Kt, typename _Arg, typename _NodeGenerator>
std::pair<iterator, bool>
- _M_insert_unique(_Kt&&, _Arg&&, const _NodeGenerator&);
+ _M_insert_unique(const_iterator, _Kt&&, _Arg&&, const _NodeGenerator&);
template<typename _Kt>
static __conditional_t<
@@ -899,9 +927,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Arg, typename _NodeGenerator>
std::pair<iterator, bool>
- _M_insert_unique_aux(_Arg&& __arg, const _NodeGenerator& __node_gen)
+ _M_insert_unique_aux(const_iterator __hint,
+ _Arg&& __arg, const _NodeGenerator& __node_gen)
{
- return _M_insert_unique(
+ return _M_insert_unique(__hint,
_S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
std::forward<_Arg>(__arg), __node_gen);
}
@@ -913,7 +942,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
using __to_value
= __detail::_ConvertToValueType<_ExtractKey, value_type>;
- return _M_insert_unique_aux(
+ return _M_insert_unique_aux(cend(),
__to_value{}(std::forward<_Arg>(__arg)), __node_gen);
}
@@ -928,14 +957,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__to_value{}(std::forward<_Arg>(__arg)), __node_gen, __uks);
}
- // Insert with hint, not used when keys are unique.
+ // Insert with hint when keys are unique.
template<typename _Arg, typename _NodeGenerator>
iterator
- _M_insert(const_iterator, _Arg&& __arg,
- const _NodeGenerator& __node_gen, true_type __uks)
+ _M_insert(const_iterator __hint, _Arg&& __arg,
+ const _NodeGenerator& __node_gen, true_type /* __uks */)
{
- return
- _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first;
+ using __to_value
+ = __detail::_ConvertToValueType<_ExtractKey, value_type>;
+ return _M_insert_unique_aux(__hint,
+ __to_value{}(std::forward<_Arg>(__arg)), __node_gen).first;
}
// Insert with hint when keys are not unique.
@@ -999,7 +1030,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#if __cplusplus > 201402L
/// Re-insert an extracted node into a container with unique keys.
insert_return_type
- _M_reinsert_node(node_type&& __nh)
+ _M_reinsert_node(const_iterator __hint, node_type&& __nh)
{
insert_return_type __ret;
if (__nh.empty())
@@ -1009,20 +1040,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_assert(get_allocator() == __nh.get_allocator());
const key_type& __k = __nh._M_key();
- __hash_code __code = this->_M_hash_code(__k);
- size_type __bkt = _M_bucket_index(__code);
- if (__node_ptr __n = _M_find_node(__bkt, __k, __code))
+ if (__hint._M_cur
+ && this->_M_key_equals(__k, *__hint._M_cur)) [[__unlikely__]]
{
__ret.node = std::move(__nh);
- __ret.position = iterator(__n);
+ __ret.position = iterator(__hint._M_cur);
__ret.inserted = false;
}
else
{
- __ret.position
- = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
- __nh._M_ptr = nullptr;
- __ret.inserted = true;
+ __hash_code __code = this->_M_hash_code(__k);
+ size_type __bkt = _M_bucket_index(__code);
+ if (__node_ptr __n = _M_find_node(__bkt, __k, __code))
+ {
+ __ret.node = std::move(__nh);
+ __ret.position = iterator(__n);
+ __ret.inserted = false;
+ }
+ else
+ {
+ __ret.position
+ = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
+ __nh._M_ptr = nullptr;
+ __ret.inserted = true;
+ }
}
}
return __ret;
@@ -1038,7 +1079,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_assert(get_allocator() == __nh.get_allocator());
const key_type& __k = __nh._M_key();
- auto __code = this->_M_hash_code(__k);
+ __hash_code __code;
+ if (__hint._M_cur
+ && this->_M_key_equals(__k, *__hint._M_cur)) [[__unlikely__]]
+ __code = this->_M_hash_code(*__hint._M_cur);
+ else
+ {
+ __code = this->_M_hash_code(__k);
+ __hint = cend();
+ }
+
auto __ret
= _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
__nh._M_ptr = nullptr;
@@ -1131,8 +1181,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
{
auto __pos = __i++;
- __hash_code __code
- = this->_M_hash_code(__src.hash_function(), *__pos._M_cur);
+ const key_type& __k = _ExtractKey{}(*__pos);
+ __hash_code __code;
+ if (__hint && this->_M_key_equals(__k, *__hint)) [[__unlikely__]]
+ __code = this->_M_hash_code(*__hint);
+ else
+ {
+ __code = this->_M_hash_code(__src.hash_function(), *__pos._M_cur);
+ __hint = nullptr;
+ }
+
auto __nh = __src.extract(__pos);
__hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
__nh._M_ptr = nullptr;
@@ -1355,7 +1413,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// _M_before_begin.
__node_ptr __ht_n = __ht._M_begin();
__node_ptr __this_n
- = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
+ = __node_gen(nullptr, __fwd_value_for<_Ht>(__ht_n->_M_v()));
this->_M_copy_code(*__this_n, *__ht_n);
_M_update_bbegin(__this_n);
@@ -1363,7 +1421,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__node_ptr __prev_n = __this_n;
for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
{
- __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
+ __this_n
+ = __node_gen(__prev_n, __fwd_value_for<_Ht>(__ht_n->_M_v()));
__prev_n->_M_nxt = __this_n;
this->_M_copy_code(*__this_n, *__ht_n);
size_type __bkt = _M_bucket_index(*__this_n);
@@ -2065,11 +2124,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_emplace(true_type /* __uks */, _Args&&... __args)
+ _M_emplace_unique(const_iterator __hint, _Args&&... __args)
-> pair<iterator, bool>
{
// First build the node to get access to the hash code
- _Scoped_node __node { this, std::forward<_Args>(__args)... };
+ _Scoped_node __node { this, __hint._M_cur, std::forward<_Args>(__args)... };
const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
if (size() <= __small_size_threshold())
{
@@ -2079,12 +2138,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return { __it, false };
}
- __hash_code __code = this->_M_hash_code(__k);
- size_type __bkt = _M_bucket_index(__code);
+ __hash_code __code;
+ size_type __bkt;
if (size() > __small_size_threshold())
- if (__node_ptr __p = _M_find_node(__bkt, __k, __code))
- // There is already an equivalent node, no insertion
- return { iterator(__p), false };
+ {
+ if (__hint._M_cur
+ && this->_M_key_equals(__k, *__hint._M_cur)) [[__unlikely__]]
+ return { iterator(__hint._M_cur), false };
+
+ __code = this->_M_hash_code(__k);
+ __bkt = _M_bucket_index(__code);
+ if (__node_ptr __p = _M_find_node(__bkt, __k, __code))
+ // There is already an equivalent node, no insertion
+ return { iterator(__p), false };
+ }
+ else
+ {
+ __code = this->_M_hash_code(__k);
+ __bkt = _M_bucket_index(__code);
+ }
// Insert the node
auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
@@ -2100,14 +2172,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_emplace(const_iterator __hint, false_type /* __uks */,
- _Args&&... __args)
+ _M_emplace_multi(const_iterator __hint, _Args&&... __args)
-> iterator
{
// First build the node to get its hash code.
- _Scoped_node __node { this, std::forward<_Args>(__args)... };
- const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
+ _Scoped_node __node
+ { this, __hint._M_cur, std::forward<_Args>(__args)... };
+ const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
auto __res = this->_M_compute_hash_code(__hint, __k);
auto __pos
= _M_insert_multi_node(__res.first._M_cur, __res.second,
@@ -2126,9 +2198,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_compute_hash_code(const_iterator __hint, const key_type& __k) const
-> pair<const_iterator, __hash_code>
{
+ if (__hint._M_cur
+ && this->_M_key_equals(__k, *__hint._M_cur)) [[__unlikely__]]
+ return { __hint, this->_M_hash_code(*__hint._M_cur) };
+
if (size() <= __small_size_threshold())
{
- if (__hint != cend())
+ if (__hint._M_cur) [[__unlikely__]]
{
for (auto __it = __hint; __it != cend(); ++__it)
if (this->_M_key_equals(__k, *__it._M_cur))
@@ -2198,17 +2274,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Find the node before an equivalent one or use hint if it exists and
// if it is equivalent.
__node_base_ptr __prev
- = __builtin_expect(__hint != nullptr, false)
- && this->_M_equals(__k, __code, *__hint)
- ? __hint
- : _M_find_before_node(__bkt, __k, __code);
+ = __builtin_expect(__hint != nullptr &&
+ this->_M_equals(__k, __code, *__hint), false)
+ ? __hint
+ : _M_find_before_node(__bkt, __k, __code);
if (__prev)
{
// Insert after the node before the equivalent one.
__node->_M_nxt = __prev->_M_nxt;
__prev->_M_nxt = __node;
- if (__builtin_expect(__prev == __hint, false))
+ if (__prev == __hint) [[__unlikely__]]
// hint might be the last bucket node, in this case we need to
// update next bucket.
if (__node->_M_nxt
@@ -2237,10 +2313,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_insert_unique(_Kt&& __k, _Arg&& __v,
+ _M_insert_unique(const_iterator __hint,
+ _Kt&& __k, _Arg&& __v,
const _NodeGenerator& __node_gen)
-> pair<iterator, bool>
{
+ if (__hint._M_cur
+ && this->_M_key_equals_tr(__k, *__hint._M_cur)) [[__unlikely__]]
+ return { iterator(__hint._M_cur), false };
+
if (size() <= __small_size_threshold())
for (auto __it = begin(); __it != end(); ++__it)
if (this->_M_key_equals_tr(__k, *__it._M_cur))
@@ -2254,11 +2335,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return { iterator(__node), false };
_Scoped_node __node {
- __node_builder_t::_S_build(std::forward<_Kt>(__k),
+ __node_builder_t::_S_build(_M_get_hint(__bkt, __hint._M_cur),
+ std::forward<_Kt>(__k),
std::forward<_Arg>(__v),
__node_gen),
this
};
+
auto __pos
= _M_insert_unique_node(__bkt, __code, __node._M_node);
__node._M_node = nullptr;
@@ -2280,12 +2363,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
-> iterator
{
// First allocate new node so that we don't do anything if it throws.
- _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
+ _Scoped_node __node
+ { __node_gen(__hint._M_cur, std::forward<_Arg>(__v)), this };
// Second compute the hash code so that we don't rehash if it throws.
auto __res = this->_M_compute_hash_code(
__hint, _ExtractKey{}(__node._M_node->_M_v()));
-
auto __pos
= _M_insert_multi_node(__res.first._M_cur, __res.second,
__node._M_node);
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index f2696ae9b07..83a9ff2bb3d 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -153,12 +153,14 @@ namespace __detail
template<>
struct _NodeBuilder<_Select1st>
{
- template<typename _Kt, typename _Arg, typename _NodeGenerator>
- static auto
- _S_build(_Kt&& __k, _Arg&& __arg, const _NodeGenerator& __node_gen)
- -> typename _NodeGenerator::__node_type*
+ template<typename _NodePtr,
+ typename _Kt, typename _Arg, typename _NodeGenerator>
+ static _NodePtr
+ _S_build(_NodePtr __hint,
+ _Kt&& __k, _Arg&& __arg, const _NodeGenerator& __node_gen)
{
- return __node_gen(std::forward<_Kt>(__k),
+ return __node_gen(__hint,
+ std::forward<_Kt>(__k),
std::forward<_Arg>(__arg).second);
}
};
@@ -166,11 +168,12 @@ namespace __detail
template<>
struct _NodeBuilder<_Identity>
{
- template<typename _Kt, typename _Arg, typename _NodeGenerator>
- static auto
- _S_build(_Kt&& __k, _Arg&&, const _NodeGenerator& __node_gen)
- -> typename _NodeGenerator::__node_type*
- { return __node_gen(std::forward<_Kt>(__k)); }
+ template<typename _NodePtr,
+ typename _Kt, typename _Arg, typename _NodeGenerator>
+ static _NodePtr
+ _S_build(_NodePtr __hint,
+ _Kt&& __k, _Arg&&, const _NodeGenerator& __node_gen)
+ { return __node_gen(__hint, std::forward<_Kt>(__k)); }
};
template<typename _NodeAlloc>
@@ -188,22 +191,23 @@ namespace __detail
typename __hashtable_alloc::__node_alloc_traits;
public:
- using __node_type = typename __hashtable_alloc::__node_type;
+ using __node_ptr = typename __hashtable_alloc::__node_ptr;
- _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h)
+ _ReuseOrAllocNode(__node_ptr __nodes, __hashtable_alloc& __h)
: _M_nodes(__nodes), _M_h(__h) { }
+
_ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete;
~_ReuseOrAllocNode()
{ _M_h._M_deallocate_nodes(_M_nodes); }
template<typename... _Args>
- __node_type*
- operator()(_Args&&... __args) const
+ __node_ptr
+ operator()(__node_ptr __hint, _Args&&... __args) const
{
if (_M_nodes)
{
- __node_type* __node = _M_nodes;
+ __node_ptr __node = _M_nodes;
_M_nodes = _M_nodes->_M_next();
__node->_M_nxt = nullptr;
auto& __a = _M_h._M_node_allocator();
@@ -218,13 +222,15 @@ namespace __detail
_M_h._M_deallocate_node_ptr(__node);
__throw_exception_again;
}
+
return __node;
}
- return _M_h._M_allocate_node(std::forward<_Args>(__args)...);
+
+ return _M_h._M_allocate_node(__hint, std::forward<_Args>(__args)...);
}
private:
- mutable __node_type* _M_nodes;
+ mutable __node_ptr _M_nodes;
__hashtable_alloc& _M_h;
};
@@ -237,15 +243,15 @@ namespace __detail
using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>;
public:
- using __node_type = typename __hashtable_alloc::__node_type;
+ using __node_ptr = typename __hashtable_alloc::__node_ptr;
_AllocNode(__hashtable_alloc& __h)
: _M_h(__h) { }
template<typename... _Args>
- __node_type*
- operator()(_Args&&... __args) const
- { return _M_h._M_allocate_node(std::forward<_Args>(__args)...); }
+ __node_ptr
+ operator()(__node_ptr __hint, _Args&&... __args) const
+ { return _M_h._M_allocate_node(__hint, std::forward<_Args>(__args)...); }
private:
__hashtable_alloc& _M_h;
@@ -813,6 +819,7 @@ namespace __detail
typename __hashtable::_Scoped_node __node {
__h,
+ __h->_M_get_hint(__bkt),
std::piecewise_construct,
std::tuple<const key_type&>(__k),
std::tuple<>()
@@ -840,6 +847,7 @@ namespace __detail
typename __hashtable::_Scoped_node __node {
__h,
+ __h->_M_get_hint(__bkt),
std::piecewise_construct,
std::forward_as_tuple(std::move(__k)),
std::tuple<>()
@@ -939,7 +947,7 @@ namespace __detail
template<typename _KType, typename... _Args>
std::pair<iterator, bool>
- try_emplace(const_iterator, _KType&& __k, _Args&&... __args)
+ try_emplace(const_iterator __hint, _KType&& __k, _Args&&... __args)
{
__hashtable& __h = _M_conjure_hashtable();
auto __code = __h._M_hash_code(__k);
@@ -948,7 +956,7 @@ namespace __detail
return { iterator(__node), false };
typename __hashtable::_Scoped_node __node {
- &__h,
+ &__h, __hint._M_cur,
std::piecewise_construct,
std::forward_as_tuple(std::forward<_KType>(__k)),
std::forward_as_tuple(std::forward<_Args>(__args)...)
@@ -1966,7 +1974,7 @@ namespace __detail
// Allocate a node and construct an element within it.
template<typename... _Args>
__node_ptr
- _M_allocate_node(_Args&&... __args);
+ _M_allocate_node(__node_ptr __hint, _Args&&... __args);
// Destroy the element within a node and deallocate the node.
void
@@ -1993,22 +2001,32 @@ namespace __detail
template<typename _NodeAlloc>
template<typename... _Args>
auto
- _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args)
+ _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(__node_ptr __hint,
+ _Args&&... __args)
-> __node_ptr
{
- auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
+ auto& __alloc = _M_node_allocator();
+ typename __node_alloc_traits::pointer __nptr;
+ if (__hint) [[__unlikely__]]
+ {
+ typedef typename __node_alloc_traits::const_pointer _CPtr;
+ auto __hptr = std::pointer_traits<_CPtr>::pointer_to(*__hint);
+ __nptr = __node_alloc_traits::allocate(__alloc, 1, __hptr);
+ }
+ else
+ __nptr = __node_alloc_traits::allocate(__alloc, 1);
+
__node_ptr __n = std::__to_address(__nptr);
__try
{
::new ((void*)__n) __node_type;
- __node_alloc_traits::construct(_M_node_allocator(),
- __n->_M_valptr(),
+ __node_alloc_traits::construct(__alloc, __n->_M_valptr(),
std::forward<_Args>(__args)...);
return __n;
}
__catch(...)
{
- __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
+ __node_alloc_traits::deallocate(__alloc, __nptr, 1);
__throw_exception_again;
}
}
diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h
index 5a3e6f61af2..f9e4504ecc7 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -441,12 +441,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
/// Re-insert an extracted node.
insert_return_type
insert(node_type&& __nh)
- { return _M_h._M_reinsert_node(std::move(__nh)); }
+ { return _M_h._M_reinsert_node(cend(), std::move(__nh)); }
/// Re-insert an extracted node.
iterator
- insert(const_iterator, node_type&& __nh)
- { return _M_h._M_reinsert_node(std::move(__nh)).position; }
+ insert(const_iterator __hint, node_type&& __nh)
+ { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; }
#define __cpp_lib_unordered_map_try_emplace 201411L
/**
diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h
index 740bbafd4c9..9731c9aa84c 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -502,12 +502,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
/// Re-insert an extracted node.
insert_return_type
insert(node_type&& __nh)
- { return _M_h._M_reinsert_node(std::move(__nh)); }
+ { return _M_h._M_reinsert_node(cend(), std::move(__nh)); }
/// Re-insert an extracted node.
iterator
- insert(const_iterator, node_type&& __nh)
- { return _M_h._M_reinsert_node(std::move(__nh)).position; }
+ insert(const_iterator __hint, node_type&& __nh)
+ { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; }
#endif // C++17
///@{
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2022-06-20 16:57 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-06-20 16:57 [PATCH 1/5][_Hashtable] Make more use of user provided hint François Dumont
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).