Extend usage of user hint in _Hashtable

Message ID 458f5d38-8b36-30f7-53b8-bd7a291f70a0@gmail.com
State New
Headers
Series Extend usage of user hint in _Hashtable |

Commit Message

François Dumont Nov. 28, 2021, 9:27 p.m. UTC
  libstdc++: In _Hashtable, use insertion hint as much as possible.

     Make use in unordered containers of the user provided hint iterator 
as much as possible.

     Hint is now used:
     - As a hint for allocation, in order to limit memory fragmentation when
     allocator is making use of it.
     - 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.

     Moreover, in _M_count_tr and _M_equal_range_tr reuse the first 
matching node key
     to check for other matching nodes to avoid any temporary 
instantiations.

     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.
             (_Hash_code_base<>::_M_hash_code(const 
_Hash_node_value<>&)): New.
             (_Hashtable_base<>::_M_equals<>(const _Kt&, const 
_Hash_node_value<>&)): New.
             (_Hashtable_base<>::_M_equals<>(const _Kt&, __hash_code, 
const _Hash_node_value<>&)):
             Adapt, use latter.
             (_Hashtable_base<>::_M_equals_tr<>(const _Kt&, const 
_Hash_node_value<>&)): New.
             (_Hashtable_base<>::_M_equals_tr<>(const _Kt&, __hash_code, 
const _Hash_node_value<>&)):
             Adapt, use latter.
(_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_node_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(const_iterator, _Kt&&, 
_Arg&&, const _NodeGenerator&)):
             (_Hashtable<>::_M_reinsert_node(const_iterator, 
node_type&&)): Add const_iterator.
             Add const_iterator 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.

Ok to commit ?

François
  

Patch

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 6e2d4c10cfe..5010cefcd77 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -301,9 +301,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.
@@ -818,6 +820,18 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return nullptr;
 	}
 
+      // Gets a hint after which a node should be allocated given a bucket.
+      __node_ptr
+      _M_get_node_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);
@@ -846,26 +860,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(false_type __uks, _Args&&... __args)
-	{ return _M_emplace(cend(), __uks, std::forward<_Args>(__args)...); }
+	_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)...); }
 
-      // 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(false_type /*__uks*/, _Args&&... __args)
+	{ return _M_emplace_multi(cend(), std::forward<_Args>(__args)...); }
 
       template<typename... _Args>
 	iterator
-	_M_emplace(const_iterator, false_type __uks, _Args&&... __args);
+	_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 __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<
@@ -888,7 +916,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
 		  true_type /* __uks */)
 	{
-	  return _M_insert_unique(
+	  return _M_insert_unique(cend(),
 	    _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
 	    std::forward<_Arg>(__arg), __node_gen);
 	}
@@ -902,14 +930,15 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 			   __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,
+	_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;
+	  return _M_insert_unique(__hint,
+	    _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
+	    std::forward<_Arg>(__arg), __node_gen).first;
 	}
 
       // Insert with hint when keys are not unique.
@@ -973,7 +1002,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())
@@ -983,6 +1012,14 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    __glibcxx_assert(get_allocator() == __nh.get_allocator());
 
 	    const key_type& __k = __nh._M_key();
+	    if (__hint._M_cur && this->_M_equals(__k, *__hint._M_cur))
+	      {
+		__ret.node = std::move(__nh);
+		__ret.position = iterator(__hint._M_cur);
+		__ret.inserted = false;
+	      }
+	    else
+	      {
 		__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))
@@ -999,6 +1036,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		    __ret.inserted = true;
 		  }
 	      }
+	  }
 	return __ret;
       }
 
@@ -1012,7 +1050,11 @@  _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_equals(__k, *__hint._M_cur))
+	  __code = this->_M_hash_code(*__hint._M_cur);
+	else
+	  __code = this->_M_hash_code(__k);
 	auto __ret
 	  = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
 	__nh._M_ptr = nullptr;
@@ -1105,8 +1147,12 @@  _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_equals(__k, *__hint))
+		__code = this->_M_hash_code(*__hint);
+	      else
+		__code = this->_M_hash_code(__src.hash_function(), *__pos._M_cur);
 	      auto __nh = __src.extract(__pos);
 	      __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
 	      __nh._M_ptr = nullptr;
@@ -1332,7 +1378,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);
 
@@ -1340,7 +1386,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);
@@ -1732,10 +1779,11 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	// All equivalent values are next to each other, if we find a
 	// non-equivalent value after an equivalent one it means that we won't
 	// find any new equivalent value.
+	const key_type& __nk = _ExtractKey{}(__n->_M_v());
 	iterator __it(__n);
 	size_type __result = 1;
 	for (++__it;
-	     __it._M_cur && this->_M_equals_tr(__k, __code, *__it._M_cur);
+	     __it._M_cur && this->_M_equals(__nk, __code, *__it._M_cur);
 	     ++__it)
 	  ++__result;
 
@@ -1819,8 +1867,9 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	// All equivalent values are next to each other, if we find a
 	// non-equivalent value after an equivalent one it means that we won't
 	// find any new equivalent value.
+	const key_type& __nk = _ExtractKey{}(__n->_M_v());
 	auto __beg = __ite++;
-	while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
+	while (__ite._M_cur && this->_M_equals(__nk, __code, *__ite._M_cur))
 	  ++__ite;
 
 	return { __beg, __ite };
@@ -1847,8 +1896,9 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	// All equivalent values are next to each other, if we find a
 	// non-equivalent value after an equivalent one it means that we won't
 	// find any new equivalent value.
+	const key_type& __nk = _ExtractKey{}(__n->_M_v());
 	auto __beg = __ite++;
-	while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
+	while (__ite._M_cur && this->_M_equals(__nk, __code, *__ite._M_cur))
 	  ++__ite;
 
 	return { __beg, __ite };
@@ -1997,17 +2047,20 @@  _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 (__hint._M_cur && this->_M_equals(__k, *__hint._M_cur))
+	  return { iterator(__hint._M_cur), false };
+
 	__hash_code __code = this->_M_hash_code(__k);
 	size_type __bkt = _M_bucket_index(__code);
 	if (__node_ptr __p = _M_find_node(__bkt, __k, __code))
 	  // There is already an equivalent node, no insertion
-	  return std::make_pair(iterator(__p), false);
+	  return { iterator(__p), false };
 
 	// Insert the node
 	auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
@@ -2023,15 +2076,20 @@  _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)...  };
+	_Scoped_node __node
+	{ this, __hint._M_cur, std::forward<_Args>(__args)...  };
+
 	const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
+	__hash_code __code;
+	if (__hint._M_cur && this->_M_equals(__k, *__hint._M_cur))
+	  __code = this->_M_hash_code(*__hint._M_cur);
+	else
+	  __code = this->_M_hash_code(__k);
 
-	__hash_code __code = this->_M_hash_code(__k);
 	auto __pos
 	  = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
 	__node._M_node = nullptr;
@@ -2132,10 +2190,14 @@  _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_equals_tr(__k, *__hint._M_cur))
+	  return { iterator(__hint._M_cur), false };
+
 	__hash_code __code = this->_M_hash_code_tr(__k);
 	size_type __bkt = _M_bucket_index(__code);
 
@@ -2143,11 +2205,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_node_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;
@@ -2169,11 +2233,16 @@  _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.
-	__hash_code __code
-	  = this->_M_hash_code(_ExtractKey{}(__node._M_node->_M_v()));
+	const auto& __k = _ExtractKey{}(__node._M_node->_M_v());
+	__hash_code __code;
+	if (__hint._M_cur && this->_M_equals(__k, *__hint._M_cur))
+	  __code = this->_M_hash_code(*__hint._M_cur);
+	else
+	  __code = this->_M_hash_code(__k);
 
 	auto __pos
 	  = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 0b5443fc187..7b9e0476159 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -115,12 +115,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*
-	{
-	  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&& __arg, const _NodeGenerator& __node_gen)
+	{
+	  return __node_gen(__hint,
+			    std::forward<_Kt>(__k),
 			    std::forward<_Arg>(__arg).second);
 	}
     };
@@ -128,11 +130,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>
@@ -150,22 +153,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();
@@ -180,13 +184,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;
     };
 
@@ -199,15 +205,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;
@@ -761,6 +767,7 @@  namespace __detail
 
       typename __hashtable::_Scoped_node __node {
 	__h,
+	__h->_M_get_node_hint(__bkt),
 	std::piecewise_construct,
 	std::tuple<const key_type&>(__k),
 	std::tuple<>()
@@ -788,6 +795,7 @@  namespace __detail
 
       typename __hashtable::_Scoped_node __node {
 	__h,
+	__h->_M_get_node_hint(__bkt),
 	std::piecewise_construct,
 	std::forward_as_tuple(std::move(__k)),
 	std::tuple<>()
@@ -876,7 +884,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);
@@ -885,7 +893,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)...)
@@ -1250,6 +1258,14 @@  namespace __detail
 	  return _M_hash()(__k);
 	}
 
+      __hash_code
+      _M_hash_code(const _Hash_node_value<_Value, true>& __n) const
+      { return __n._M_hash_code; }
+
+      __hash_code
+      _M_hash_code(const _Hash_node_value<_Value, false>& __n) const
+      { return _M_hash_code(_ExtractKey{}(__n._M_v())); }
+
       __hash_code
       _M_hash_code(const _Hash&,
 		   const _Hash_node_value<_Value, true>& __n) const
@@ -1641,18 +1657,23 @@  namespace __detail
       { }
 
       bool
-      _M_equals(const _Key& __k, __hash_code __c,
+      _M_equals(const _Key& __k,
 		const _Hash_node_value<_Value, __hash_cached::value>& __n) const
       {
 	static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
 	  "key equality predicate must be invocable with two arguments of "
 	  "key type");
-	return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v()));
+	return _M_eq()(__k, _ExtractKey{}(__n._M_v()));
       }
 
+      bool
+      _M_equals(const _Key& __k, __hash_code __c,
+		const _Hash_node_value<_Value, __hash_cached::value>& __n) const
+      { return _S_equals(__c, __n) && _M_equals(__k, __n); }
+
       template<typename _Kt>
 	bool
-	_M_equals_tr(const _Kt& __k, __hash_code __c,
+	_M_equals_tr(const _Kt& __k,
 		     const _Hash_node_value<_Value,
 					    __hash_cached::value>& __n) const
 	{
@@ -1660,9 +1681,16 @@  namespace __detail
 	    __is_invocable<const _Equal&, const _Kt&, const _Key&>{},
 	    "key equality predicate must be invocable with two arguments of "
 	    "key type");
-	  return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v()));
+	  return _M_eq()(__k, _ExtractKey{}(__n._M_v()));
 	}
 
+      template<typename _Kt>
+	bool
+	_M_equals_tr(const _Kt& __k, __hash_code __c,
+		     const _Hash_node_value<_Value,
+					    __hash_cached::value>& __n) const
+	{ return _S_equals(__c, __n) && _M_equals_tr(__k, __n); }
+
       bool
       _M_node_equals(
 	const _Hash_node_value<_Value, __hash_cached::value>& __lhn,
@@ -1880,7 +1908,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
@@ -1907,22 +1935,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)
+	  {
+	    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 2261e6685ea..9f621cdbaeb 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -436,12 +436,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 201411
       /**
diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h
index ac4a890d25a..10d81905acb 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -497,12 +497,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
 
       ///@{