Re: [PATCH] Hashtable PR96088

["François Dumont" <frs.dumont@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 4519 bytes --]

Hi

     Just a rebase of this patch.

François

On 17/10/20 6:21 pm, François Dumont wrote:
> I eventually would like to propose the following resolution.
>
> For multi-key containers I kept the same resolution build the node 
> first and compute has code from the node key.
>
> For unique-key ones I change behavior when I can't find out hash 
> functor argument type. I am rather using the iterator key type and 
> just hope that the user's functors are prepared for it.
>
> For now I am using functor argument_type which is deprecated. I just 
> hope that the day we remove it we will have a compiler built-in to get 
> any functor argument type given an input type.
>
>     libstdc++: Limit allocation on iterator insertion in Hashtable [PR 
> 96088]
>
>     Detect Hash functor argument type to find out if it is different 
> to the
>     container key_type and if a temporary instance needs to be 
> generated to invoke
>     the functor from the iterator value_type key part. If this 
> temporary generation
>     can throw a key_type instance is generated at Hashtable level and 
> use to call
>     the functors and, if needed, move it to the storage.
>
>     libstdc++-v3/ChangeLog:
>
>             PR libstdc++/96088
>             * include/bits/hashtable_policy.h (_Select2nd): New.
>             (_NodeBuilder<>): New.
>             (_ReuseOrAllocNode<>::operator()): Use varriadic template 
> args.
>             (_AllocNode<>::operator()): Likewise.
>             (_Hash_code_base<>::_M_hash_code): Add _KType template 
> parameter.
>             (_Hashtable_base<>::_M_equals): Add _KType template 
> parameter.
>             * include/bits/hashtable.h
>             (_Hashtable<>::__node_builder_t): New.
>             (_Hashtable<>::_M_find_before_node): Add _KType template 
> parameter.
>             (_Hashtable<>::_M_find_node): Likewise.
>             (_Hashtable<>::_Hash_arg_t): New.
>             (_Hashtable<>::_S_forward_key): New.
> (_Hashtable<>::_M_insert_unique<>(_KType&&, _Arg&&, const 
> _NodeGenerator&)):
>              New.
>             (_Hashtable<>::_M_insert): Use latter.
>             * testsuite/23_containers/unordered_map/96088.cc: New test.
>             * testsuite/23_containers/unordered_multimap/96088.cc: New 
> test.
>             * testsuite/23_containers/unordered_multiset/96088.cc: New 
> test.
>             * testsuite/23_containers/unordered_set/96088.cc: New test.
>             * testsuite/util/replacement_memory_operators.h
>             (counter::_M_increment): New.
>             (counter::_M_decrement): New.
>             (counter::reset()): New.
>
> Tested under Linux x86_64.
>
> Ok to commit ?
>
> François
>
> On 01/09/20 2:36 pm, François Dumont wrote:
>> Hi
>>
>>     I started working on PR96088 problem in Hashtable implementation.
>>
>>     In the case of multi-key containers the problem is easy to 
>> manage. Now that we have _Scoped_node we can easily allocate the node 
>> first and then extract the key from it to compute hash code. It is 
>> quite safe as computating a hash code is rarely going to throw 
>> especially if there is no allocation anymore to invoke the hasher.
>>
>>     In the unique-key case it is more tricky. First I only consider 
>> the hasher invocation, the equal_to shall be consistent with it. My 
>> approach is to consider that if the operation needed transform the 
>> inserted element key part into the hasher argument can throw then I 
>> better generate a key_type instance myself and move it to the node if 
>> it is eventually to be inserted. Note that any allocation needed to 
>> call the hasher from the key_type is user fault.
>>
>>     Of course the tricky part here is to find out what is the hasher 
>> argument_type. For the moment I support hasher with a nested 
>> argument_type typedef and function pointer. But, as pointed out by 
>> the tests which are failing for the moment I am missing the support 
>> for a classic functor. I am pretty sure that if I support it I will 
>> still be missing some use cases (like std::function). So I am looking 
>> for help on how to determine it. Or maybe the whole approach it wrong ?
>>
>> For now I am still working on it, thanks,
>>
>> François
>>
>


[-- Attachment #2: pr96088.patch --]
[-- Type: text/x-patch, Size: 30078 bytes --]

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 6c6c5edde0b..234b40c13b7 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -274,6 +274,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	__detail::_ReuseOrAllocNode<__node_alloc_type>;
       using __alloc_node_gen_t =
 	__detail::_AllocNode<__node_alloc_type>;
+      using __node_builder_t =
+	__detail::_NodeBuilder<_ExtractKey>;
 
       // Simple RAII type for managing a node containing an element
       struct _Scoped_node
@@ -736,18 +738,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       // Find and insert helper functions and types
       // Find the node before the one matching the criteria.
-      __node_base_ptr
-      _M_find_before_node(size_type, const key_type&, __hash_code) const;
-
-      __node_ptr
-      _M_find_node(size_type __bkt, const key_type& __key,
-		   __hash_code __c) const
-      {
-	__node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
-	if (__before_n)
-	  return static_cast<__node_ptr>(__before_n->_M_nxt);
-	return nullptr;
-      }
+      template<typename _KType>
+	__node_base_ptr
+	_M_find_before_node(size_type, const _KType&, __hash_code) const;
+
+      template<typename _KType>
+	__node_ptr
+	_M_find_node(size_type __bkt, const _KType& __key,
+		     __hash_code __c) const
+	{
+	  __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
+	  if (__before_n)
+	    return static_cast<__node_ptr>(__before_n->_M_nxt);
+	  return nullptr;
+	}
 
       // Insert a node at the beginning of a bucket.
       void
@@ -794,9 +798,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	iterator
 	_M_emplace(const_iterator, false_type __uks, _Args&&... __args);
 
+      template<typename _KType, typename _Arg, typename _NodeGenerator>
+	std::pair<iterator, bool>
+	_M_insert_unique(_KType&&, _Arg&&, const _NodeGenerator&);
+
+      // Detect nested argument_type.
+      template<typename _KType, typename _Tp, typename = __void_t<>>
+	struct _Hash_arg_t
+	{ typedef _KType argument_type; };
+
+      // Nested argument_type.
+      template<typename _KType, typename _Tp>
+	struct _Hash_arg_t<_KType, _Tp,
+			  __void_t<typename _Tp::argument_type>>
+	{ typedef typename _Tp::argument_type argument_type; };
+
+      // Function pointer.
+      template<typename _KType, typename _Arg>
+	struct _Hash_arg_t<_KType, std::size_t(*)(const _Arg&)>
+	{ typedef _Arg argument_type; };
+
+      template<typename _KType,
+	       typename _ArgType
+		 = typename _Hash_arg_t<_KType, _Hash>::argument_type>
+	static typename conditional<
+	  __is_nothrow_convertible<_KType, _ArgType>::value,
+	  _KType&&,
+	  key_type>::type
+	_S_forward_key(_KType&& __k)
+	{ return std::forward<_KType>(__k); }
+
+      static const key_type&
+      _S_forward_key(const key_type& __k)
+      { return __k; }
+
+      static key_type&&
+      _S_forward_key(key_type&& __k)
+      { return std::move(__k); }
+
       template<typename _Arg, typename _NodeGenerator>
 	std::pair<iterator, bool>
-	_M_insert(_Arg&&, const _NodeGenerator&, true_type __uks);
+	_M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
+		  true_type /* __uks */)
+	{
+	  return _M_insert_unique(
+	    _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
+	    std::forward<_Arg>(__arg), __node_gen);
+	}
 
       template<typename _Arg, typename _NodeGenerator>
 	iterator
@@ -1621,30 +1669,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename _ExtractKey, typename _Equal,
 	   typename _Hash, typename _RangeHash, typename _Unused,
 	   typename _RehashPolicy, typename _Traits>
-    auto
-    _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-	       _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
-    _M_find_before_node(size_type __bkt, const key_type& __k,
-			__hash_code __code) const
-    -> __node_base_ptr
-    {
-      __node_base_ptr __prev_p = _M_buckets[__bkt];
-      if (!__prev_p)
-	return nullptr;
+    template<typename _KType>
+      auto
+      _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+		 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+      _M_find_before_node(size_type __bkt, const _KType& __k,
+			  __hash_code __code) const
+      -> __node_base_ptr
+      {
+	__node_base_ptr __prev_p = _M_buckets[__bkt];
+	if (!__prev_p)
+	  return nullptr;
 
-      for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);;
-	   __p = __p->_M_next())
-	{
-	  if (this->_M_equals(__k, __code, *__p))
-	    return __prev_p;
+	for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);;
+	     __p = __p->_M_next())
+	  {
+	    if (this->_M_equals(__k, __code, *__p))
+	      return __prev_p;
 
-	  if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
-	    break;
-	  __prev_p = __p;
-	}
+	    if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
+	      break;
+	    __prev_p = __p;
+	  }
 
-      return nullptr;
-    }
+	return nullptr;
+      }
 
   template<typename _Key, typename _Value, typename _Alloc,
 	   typename _ExtractKey, typename _Equal,
@@ -1858,22 +1907,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename _ExtractKey, typename _Equal,
 	   typename _Hash, typename _RangeHash, typename _Unused,
 	   typename _RehashPolicy, typename _Traits>
-    template<typename _Arg, typename _NodeGenerator>
+    template<typename _KType, typename _Arg, typename _NodeGenerator>
       auto
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
-      _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen,
-		true_type /* __uks */)
+      _M_insert_unique(_KType&& __k, _Arg&& __v,
+		       const _NodeGenerator& __node_gen)
       -> pair<iterator, bool>
       {
-	const key_type& __k = _ExtractKey{}(__v);
 	__hash_code __code = this->_M_hash_code(__k);
 	size_type __bkt = _M_bucket_index(__code);
 
 	if (__node_ptr __node = _M_find_node(__bkt, __k, __code))
 	  return { iterator(__node), false };
 
-	_Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
+	_Scoped_node __node {
+	  __node_builder_t::_S_build(std::forward<_KType>(__k),
+				     std::forward<_Arg>(__v),
+				     __node_gen),
+	  this
+	};
 	auto __pos
 	  = _M_insert_unique_node(__bkt, __code, __node._M_node);
 	__node._M_node = nullptr;
@@ -1894,12 +1947,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		false_type /* __uks */)
       -> iterator
       {
-	// First compute the hash code so that we don't do anything if it
-	// throws.
-	__hash_code __code = this->_M_hash_code(_ExtractKey{}(__v));
-
-	// Second allocate new node so that we don't rehash if it throws.
+	// First allocate new node so that we don't do anything if it throws.
 	_Scoped_node __node{ __node_gen(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()));
+
 	auto __pos
 	  = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
 	__node._M_node = nullptr;
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index f5ce7209957..378f800ab9e 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -94,6 +94,48 @@ namespace __detail
       { return std::get<0>(std::forward<_Tp>(__x)); }
   };
 
+  struct _Select2nd
+  {
+    template<typename _Tp>
+      auto
+      operator()(_Tp&& __x) const noexcept
+      -> decltype(std::get<1>(std::forward<_Tp>(__x)))
+      { return std::get<1>(std::forward<_Tp>(__x)); }
+  };
+
+  template<typename _ExKey>
+    struct _NodeBuilder;
+
+  template<>
+    struct _NodeBuilder<_Select1st>
+    {
+      template<typename _KType, typename _Arg, typename _NodeGenerator>
+	static auto
+	_S_build(_KType&& __k, _Arg&& __arg,
+		 const _NodeGenerator& __node_gen)
+	-> decltype(__node_gen(std::piecewise_construct,
+			       std::forward_as_tuple(std::forward<_KType>(__k)),
+			       std::forward_as_tuple(_Select2nd{}(
+						std::forward<_Arg>(__arg)))))
+	{
+	  return __node_gen(std::piecewise_construct,
+			    std::forward_as_tuple(std::forward<_KType>(__k)),
+			    std::forward_as_tuple(_Select2nd{}(
+						std::forward<_Arg>(__arg))));
+	}
+    };
+
+  template<>
+    struct _NodeBuilder<_Identity>
+    {
+      template<typename _KType, typename _Arg, typename _NodeGenerator>
+	static auto
+	_S_build(_KType&& __k, _Arg&&,
+		 const _NodeGenerator& __node_gen)
+	-> decltype(__node_gen(std::forward<_KType>(__k)))
+	{ return __node_gen(std::forward<_KType>(__k)); }
+    };
+
   template<typename _NodeAlloc>
     struct _Hashtable_alloc;
 
@@ -117,9 +159,9 @@ namespace __detail
       ~_ReuseOrAllocNode()
       { _M_h._M_deallocate_nodes(_M_nodes); }
 
-      template<typename _Arg>
+      template<typename... _Args>
 	__node_type*
-	operator()(_Arg&& __arg) const
+	operator()(_Args&&... __args) const
 	{
 	  if (_M_nodes)
 	    {
@@ -131,7 +173,7 @@ namespace __detail
 	      __try
 		{
 		  __node_alloc_traits::construct(__a, __node->_M_valptr(),
-						 std::forward<_Arg>(__arg));
+						 std::forward<_Args>(__args)...);
 		}
 	      __catch(...)
 		{
@@ -140,7 +182,7 @@ namespace __detail
 		}
 	      return __node;
 	    }
-	  return _M_h._M_allocate_node(std::forward<_Arg>(__arg));
+	  return _M_h._M_allocate_node(std::forward<_Args>(__args)...);
 	}
 
     private:
@@ -161,10 +203,10 @@ namespace __detail
       _AllocNode(__hashtable_alloc& __h)
       : _M_h(__h) { }
 
-      template<typename _Arg>
+      template<typename... _Args>
 	__node_type*
-	operator()(_Arg&& __arg) const
-	{ return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); }
+	operator()(_Args&&... __args) const
+	{ return _M_h._M_allocate_node(std::forward<_Args>(__args)...); }
 
     private:
       __hashtable_alloc& _M_h;
@@ -1211,13 +1253,14 @@ namespace __detail
       _Hash_code_base() = default;
       _Hash_code_base(const _Hash& __hash) : __ebo_hash(__hash) { }
 
-      __hash_code
-      _M_hash_code(const _Key& __k) const
-      {
-	static_assert(__is_invocable<const _Hash&, const _Key&>{},
+      template<typename _KType>
+	__hash_code
+	_M_hash_code(const _KType& __k) const
+	{
+	  static_assert(__is_invocable<const _Hash&, const _KType&>{},
 	    "hash function must be invocable with an argument of key type");
-	return _M_hash()(__k);
-      }
+	  return _M_hash()(__k);
+	}
 
       std::size_t
       _M_bucket_index(__hash_code __c, std::size_t __bkt_count) const
@@ -1597,15 +1640,18 @@ namespace __detail
       : __hash_code_base(__hash), _EqualEBO(__eq)
       { }
 
-      bool
-      _M_equals(const _Key& __k, __hash_code __c,
-		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()));
-      }
+      template<typename _KType>
+	bool
+	_M_equals(const _KType& __k, __hash_code __c,
+		  const _Hash_node_value<_Value,
+					 __hash_cached::value>& __n) const
+	{
+	  static_assert(
+	    __is_invocable<const _Equal&, const _KType&, 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()));
+	}
 
       bool
       _M_node_equals(
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc
new file mode 100644
index 00000000000..4d399353120
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc
@@ -0,0 +1,240 @@
+// { dg-do run { target c++11 } }
+
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<std::pair<const char*, int>> lst = {
+    {"long_str_for_dynamic_allocating", 1}
+};
+
+void
+test01()
+{
+  __gnu_test::counter::reset();
+  std::unordered_map<std::string, int> um;
+  um.insert(lst.begin(), lst.end());
+  VERIFY( um.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+  um.insert(lst.begin(), lst.end());
+  VERIFY( um.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 4 );
+}
+
+void
+test02()
+{
+  __gnu_test::counter::reset();
+  std::unordered_map<std::string, int,
+		     std::hash<std::string_view>,
+		     std::equal_to<std::string_view>> um;
+  um.insert(lst.begin(), lst.end());
+  VERIFY( um.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+  um.insert(lst.begin(), lst.end());
+  VERIFY( um.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+std::size_t
+hash_string_f(const std::string& str)
+{
+  std::hash<std::string> h;
+  return h(str);
+}
+
+void
+test11()
+{
+  typedef std::size_t (*hash_string_t)(const std::string&);
+  __gnu_test::counter::reset();
+  hash_string_t hasher = &hash_string_f;
+  std::unordered_map<std::string, int,
+		     hash_string_t,
+		     std::equal_to<std::string>> um(0, hasher);
+  um.insert(lst.begin(), lst.end());
+  VERIFY( um.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+  um.insert(lst.begin(), lst.end());
+  VERIFY( um.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 4 );
+}
+
+std::size_t
+hash_string_view_f(const std::string_view& str)
+{
+  std::hash<std::string_view> h;
+  return h(str);
+}
+
+void
+test12()
+{
+  typedef std::size_t (*hash_stringview_t)(const std::string_view&);
+  __gnu_test::counter::reset();
+  hash_stringview_t hasher = &hash_string_view_f;
+  std::unordered_map<std::string, int,
+		     hash_stringview_t,
+		     std::equal_to<std::string_view>> um(0, hasher);
+  um.insert(lst.begin(), lst.end());
+  VERIFY( um.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+  um.insert(lst.begin(), lst.end());
+  VERIFY( um.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+struct hash_string_functor
+{
+  std::size_t
+  operator()(const std::string& str) const noexcept
+  {
+    std::hash<std::string> h;
+    return h(str);
+  }
+};
+
+void
+test21()
+{
+  __gnu_test::counter::reset();
+  std::unordered_map<std::string, int,
+		     hash_string_functor,
+		     std::equal_to<std::string>> um;
+  um.insert(lst.begin(), lst.end());
+  VERIFY( um.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 4 );
+
+  um.insert(lst.begin(), lst.end());
+  VERIFY( um.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 6 );
+}
+
+struct hash_string_view_functor
+{
+  std::size_t
+  operator()(const std::string_view& str) const noexcept
+  {
+    std::hash<std::string_view> h;
+    return h(str);
+  }
+};
+
+void
+test22()
+{
+  __gnu_test::counter::reset();
+  std::unordered_map<std::string, int,
+		     hash_string_view_functor,
+		     std::equal_to<std::string_view>> um;
+  um.insert(lst.begin(), lst.end());
+  VERIFY( um.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+  um.insert(lst.begin(), lst.end());
+  VERIFY( um.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+void
+test03()
+{
+  std::vector<std::pair<std::string, int>> v;
+  v.insert(v.end(), lst.begin(), lst.end());
+
+  auto __offset = __gnu_test::counter::count();
+  {
+    __gnu_test::counter::reset();
+    std::unordered_map<std::string, int,
+		       std::hash<std::string_view>,
+		       std::equal_to<std::string_view>> um;
+    um.insert(v.begin(), v.end());
+    VERIFY( um.size() == 1 );
+
+    VERIFY( __gnu_test::counter::count() - __offset == 3 );
+    VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+    um.insert(v.begin(), v.end());
+    VERIFY( um.size() == 1 );
+
+    VERIFY( __gnu_test::counter::count() - __offset == 3 );
+    VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+  }
+
+  {
+    __gnu_test::counter::reset();
+    std::unordered_map<std::string, int,
+		       std::hash<std::string_view>,
+		       std::equal_to<std::string_view>> um;
+    um.insert(std::make_move_iterator(v.begin()),
+	      std::make_move_iterator(v.end()));
+    VERIFY( um.size() == 1 );
+
+    VERIFY( __gnu_test::counter::count() - __offset == 2 );
+    VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+  }
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test11();
+  test12();
+  test21();
+  test22();
+  test03();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/96088.cc
new file mode 100644
index 00000000000..ffc98e25540
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/96088.cc
@@ -0,0 +1,65 @@
+// { dg-do run { target c++17 } }
+
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <unordered_map>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<std::pair<const char*, int>> lst = {
+    {"long_str_for_dynamic_allocating", 1}
+};
+
+void
+test01()
+{
+  __gnu_test::counter::reset();
+  std::unordered_multimap<std::string, int,
+			  std::hash<std::string_view>,
+			  std::equal_to<std::string_view>> foo;
+  foo.insert(lst.begin(), lst.end());
+  VERIFY( foo.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+void
+test02()
+{
+  __gnu_test::counter::reset();
+  std::unordered_multimap<std::string, int> foo;
+  foo.insert(lst.begin(), lst.end());
+  VERIFY( foo.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/96088.cc
new file mode 100644
index 00000000000..4951b100a54
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/96088.cc
@@ -0,0 +1,65 @@
+// { dg-do run { target c++17 } }
+
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <unordered_set>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<const char*> lst = {
+  "long_str_for_dynamic_allocating"
+};
+
+void
+test01()
+{
+  __gnu_test::counter::reset();
+  std::unordered_multiset<std::string,
+			  std::hash<std::string_view>,
+			  std::equal_to<std::string_view>> foo;
+  foo.insert(lst.begin(), lst.end());
+  VERIFY( foo.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+void
+test02()
+{
+  __gnu_test::counter::reset();
+  std::unordered_multiset<std::string> foo;
+  foo.insert(lst.begin(), lst.end());
+  VERIFY( foo.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc
new file mode 100644
index 00000000000..da4794cfb22
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc
@@ -0,0 +1,240 @@
+// { dg-do run { target c++11 } }
+
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <unordered_set>
+#include <vector>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<const char*> lst = {
+  "long_str_for_dynamic_allocating"
+};
+
+void
+test01()
+{
+  __gnu_test::counter::reset();
+  std::unordered_set<std::string> us;
+  us.insert(lst.begin(), lst.end());
+  VERIFY( us.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+  us.insert(lst.begin(), lst.end());
+  VERIFY( us.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 4 );
+}
+
+void
+test02()
+{
+  __gnu_test::counter::reset();
+  std::unordered_set<std::string,
+		     std::hash<std::string_view>,
+		     std::equal_to<std::string_view>> us;
+  us.insert(lst.begin(), lst.end());
+  VERIFY( us.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+  us.insert(lst.begin(), lst.end());
+  VERIFY( us.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+std::size_t
+hash_string_f(const std::string& str)
+{
+  std::hash<std::string> h;
+  return h(str);
+}
+
+void
+test11()
+{
+  typedef std::size_t (*hash_string_t)(const std::string&);
+  __gnu_test::counter::reset();
+  hash_string_t hasher = &hash_string_f;
+  std::unordered_set<std::string,
+		     hash_string_t,
+		     std::equal_to<std::string>> us(0, hasher);
+  us.insert(lst.begin(), lst.end());
+  VERIFY( us.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+  us.insert(lst.begin(), lst.end());
+  VERIFY( us.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 4 );
+}
+
+std::size_t
+hash_string_view_f(const std::string_view& str)
+{
+  std::hash<std::string_view> h;
+  return h(str);
+}
+
+void
+test12()
+{
+  typedef std::size_t (*hash_stringview_t)(const std::string_view&);
+  __gnu_test::counter::reset();
+  hash_stringview_t hasher = &hash_string_view_f;
+  std::unordered_set<std::string,
+		     hash_stringview_t,
+		     std::equal_to<std::string_view>> us(0, hasher);
+  us.insert(lst.begin(), lst.end());
+  VERIFY( us.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+  us.insert(lst.begin(), lst.end());
+  VERIFY( us.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+struct hash_string_functor
+{
+  std::size_t
+  operator()(const std::string& str) const noexcept
+  {
+    std::hash<std::string> h;
+    return h(str);
+  }
+};
+
+void
+test21()
+{
+  __gnu_test::counter::reset();
+  std::unordered_set<std::string,
+		     hash_string_functor,
+		     std::equal_to<std::string>> us;
+  us.insert(lst.begin(), lst.end());
+  VERIFY( us.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 4 );
+
+  us.insert(lst.begin(), lst.end());
+  VERIFY( us.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 6 );
+}
+
+struct hash_string_view_functor
+{
+  std::size_t
+  operator()(const std::string_view& str) const noexcept
+  {
+    std::hash<std::string_view> h;
+    return h(str);
+  }
+};
+
+void
+test22()
+{
+  __gnu_test::counter::reset();
+  std::unordered_set<std::string,
+		     hash_string_view_functor,
+		     std::equal_to<std::string_view>> us;
+  us.insert(lst.begin(), lst.end());
+  VERIFY( us.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+  us.insert(lst.begin(), lst.end());
+  VERIFY( us.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 3 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+void
+test03()
+{
+  std::vector<std::string> v;
+  v.insert(v.end(), lst.begin(), lst.end());
+
+  auto __offset = __gnu_test::counter::count();
+  {
+    __gnu_test::counter::reset();
+    std::unordered_set<std::string,
+		       std::hash<std::string_view>,
+		       std::equal_to<std::string_view>> us;
+    us.insert(v.begin(), v.end());
+    VERIFY( us.size() == 1 );
+
+    VERIFY( __gnu_test::counter::count() - __offset == 3 );
+    VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+    us.insert(v.begin(), v.end());
+    VERIFY( us.size() == 1 );
+
+    VERIFY( __gnu_test::counter::count() - __offset == 3 );
+    VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+  }
+
+  {
+    __gnu_test::counter::reset();
+    std::unordered_set<std::string,
+		       std::hash<std::string_view>,
+		       std::equal_to<std::string_view>> us;
+    us.insert(std::make_move_iterator(v.begin()),
+	      std::make_move_iterator(v.end()));
+    VERIFY( us.size() == 1 );
+
+    VERIFY( __gnu_test::counter::count() - __offset == 2 );
+    VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+  }
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test11();
+  test12();
+  test21();
+  test22();
+  test03();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/util/replacement_memory_operators.h b/libstdc++-v3/testsuite/util/replacement_memory_operators.h
index a90ffd47524..a76962ebedd 100644
--- a/libstdc++-v3/testsuite/util/replacement_memory_operators.h
+++ b/libstdc++-v3/testsuite/util/replacement_memory_operators.h
@@ -29,6 +29,7 @@ namespace __gnu_test
   struct counter
   {
     std::size_t _M_count;
+    std::size_t _M_increments, _M_decrements;
     bool	_M_throw;
 
     counter() : _M_count(0), _M_throw(true) { }
@@ -40,10 +41,20 @@ namespace __gnu_test
     }
 
     static void
-    increment() { get()._M_count++; }
+    increment()
+    {
+      counter& cntr = get();
+      cntr._M_count++;
+      cntr._M_increments++;
+    }
 
     static void
-    decrement() { get()._M_count--; }
+    decrement()
+    {
+      counter& cntr = get();
+      cntr._M_count--;
+      cntr._M_decrements++;
+    }
 
     static counter&
     get()
@@ -57,6 +68,13 @@ namespace __gnu_test
 
     static void
     exceptions(bool __b) { get()._M_throw = __b; }
+
+    static void
+    reset()
+    {
+      counter& cntr = get();
+      cntr._M_increments = cntr._M_decrements = 0;
+    }
   };
 
   template<typename Alloc, bool uses_global_new>