hashtable_policy.h (_Insert_base): Consider hint in insert methods.

2013-06-29  François Dumont  <fdumont@gcc.gnu.org>

	* include/bits/hashtable_policy.h (_Insert_base): Consider hint in
	insert methods.
	* include/bits/hashtable.h: Likewise.
	* testsuite/23_containers/unordered_multimap/insert/hint.cc: New.
	* testsuite/performance/23_containers/insert/unordered_multiset_hint.cc:
	New.
	* testsuite/23_containers/unordered_set/instantiation_neg.cc:
	Adjust dg-error line number.
	* testsuite/23_containers/unordered_set/
	not_default_constructible_hash_neg.cc: Likewise.
	* doc/xml/manual/containers.xml: Document hinting in unordered
	containers.

From-SVN: r200564

7 files changed, 592 insertions, 30 deletions

diff --git a/libstdc++-v3/doc/xml/manual/containers.xml b/libstdc++-v3/doc/xml/manual/containers.xml
index 920b491..9791953 100644
--- a/libstdc++-v3/doc/xml/manual/containers.xml
+++ b/libstdc++-v3/doc/xml/manual/containers.xml
@@ -354,6 +354,60 @@
   <info><title>Unordered Associative</title></info>
   <?dbhtml filename="unordered_associative.html"?>
 
+  <section xml:id="containers.unordered.insert_hints" xreflabel="Insertion Hints">
+    <info><title>Insertion Hints</title></info>
+
+    <para>
+     Here is how the hinting works in the libstdc++ implementation of unordered
+     containers, and the rationale behind this behavior.
+    </para>
+    <para>
+      In the following text, the phrase <emphasis>equivalent to</emphasis> refer
+      to the result of the invocation of the equal predicate imposed on the
+      container by its <code>key_equal</code> object, which defaults to (basically)
+      <quote>==</quote>.
+    </para>
+    <para>
+      Unordered containers can be seen as a <code>std::vector</code> of
+      <code>std::forward_list</code>. The <code>std::vector</code> represents
+      the buckets and each <code>std::forward_list</code> is the list of nodes
+      belonging to the same bucket. When inserting an element in such a data
+      structure we first need to compute the element hash code to find the
+      bucket to insert the element to, the second step depends on the uniqueness
+      of elements in the container.
+    </para>
+    <para>
+      In the case of <code>std::unordered_set</code> and
+      <code>std::unordered_map</code> you need to look through all bucket's
+      elements for an equivalent one. If there is none the insertion can be
+      achieved, otherwise the insertion fails. As we always need to loop though
+      all bucket's elements, the hint doesn't tell us if the element is already
+      present, and we don't have any constraint on where the new element is to
+      be inserted, the hint won't be of any help and will then be ignored.
+    </para>
+    <para>
+      In the case of <code>std::unordered_multiset</code>
+      and <code>std::unordered_multimap</code> equivalent elements must be
+      linked together so that the <code>equal_range(const key_type&amp;)</code>
+      can return the range of iterators pointing to all equivalent elements.
+      This is where hinting can be used to point to another equivalent element
+      already part of the container and so skip all non equivalent elements of
+      the bucket. So to be useful the hint shall point to an element equivalent
+      to the one being inserted. The new element will be then inserted right
+      after the hint. Note that because of an implementation detail inserting
+      after a node can require updating the bucket of the following node. To
+      check if the next bucket is to be modified we need to compute the
+      following node's hash code. So if you want your hint to be really efficient
+      it should be followed by another equivalent element, the implementation
+      will detect this equivalence and won't compute next element hash code.
+    </para>
+    <para>
+      It is highly advised to start using unordered containers hints only if you
+      have a benchmark that will demonstrate the benefit of it. If you don't then do
+      not use hints, it might do more harm than good.
+    </para>
+  </section>
+
   <section xml:id="containers.unordered.hash" xreflabel="Hash">
     <info><title>Hash Code</title></info>
 
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 8ce264e..9b586b0 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -225,7 +225,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       using __node_base = typename __hashtable_base::__node_base;
       using __bucket_type = typename __hashtable_base::__bucket_type;
       using __ireturn_type = typename __hashtable_base::__ireturn_type;
-      using __iconv_type = typename __hashtable_base::__iconv_type;
 
       using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey,
 					     _Equal, _H1, _H2, _Hash,
@@ -680,7 +679,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // Insert node with hash code __code. Take ownership of the node,
       // deallocate it on exception.
       iterator
-      _M_insert_multi_node(__hash_code __code, __node_type* __n);
+      _M_insert_multi_node(__node_type* __hint,
+			   __hash_code __code, __node_type* __n);
 
       template<typename... _Args>
 	std::pair<iterator, bool>
@@ -688,7 +688,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       template<typename... _Args>
 	iterator
-	_M_emplace(std::false_type, _Args&&... __args);
+	_M_emplace(std::false_type __uk, _Args&&... __args)
+	{ return _M_emplace(cend(), __uk, std::forward<_Args>(__args)...); }
+
+      // Emplace with hint, useless when keys are unique.
+      template<typename... _Args>
+	iterator
+	_M_emplace(const_iterator, std::true_type __uk, _Args&&... __args)
+	{ return _M_emplace(__uk, std::forward<_Args>(__args)...).first; }
+
+      template<typename... _Args>
+	iterator
+	_M_emplace(const_iterator, std::false_type, _Args&&... __args);
 
       template<typename _Arg>
 	std::pair<iterator, bool>
@@ -696,7 +707,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       template<typename _Arg>
 	iterator
-	_M_insert(_Arg&&, std::false_type);
+	_M_insert(_Arg&& __arg, std::false_type __uk)
+	{ return _M_insert(cend(), std::forward<_Arg>(__arg), __uk); }
+
+      // Insert with hint, not used when keys are unique.
+      template<typename _Arg>
+	iterator
+	_M_insert(const_iterator, _Arg&& __arg, std::true_type __uk)
+	{ return _M_insert(std::forward<_Arg>(__arg), __uk).first; }
+
+      // Insert with hint when keys are not unique.
+      template<typename _Arg>
+	iterator
+	_M_insert(const_iterator, _Arg&&, std::false_type);
 
       size_type
       _M_erase(std::true_type, const key_type&);
@@ -716,8 +739,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       template<typename... _Args>
 	iterator
-	emplace_hint(const_iterator, _Args&&... __args)
-	{ return __iconv_type()(emplace(std::forward<_Args>(__args)...)); }
+	emplace_hint(const_iterator __hint, _Args&&... __args)
+	{
+	  return _M_emplace(__hint, __unique_keys(),
+			    std::forward<_Args>(__args)...);
+	}
 
       // Insert member functions via inheritance.
 
@@ -1642,7 +1668,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 			  _Traits>::iterator
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-      _M_emplace(std::false_type, _Args&&... __args)
+      _M_emplace(const_iterator __hint, std::false_type, _Args&&... __args)
       {
 	// First build the node to get its hash code.
 	__node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...);
@@ -1658,7 +1684,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    __throw_exception_again;
 	  }
 
-	return _M_insert_multi_node(__code, __node);
+	return _M_insert_multi_node(__hint._M_cur, __code, __node);
       }
 
   template<typename _Key, typename _Value,
@@ -1710,7 +1736,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 			_Traits>::iterator
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_insert_multi_node(__hash_code __code, __node_type* __node)
+    _M_insert_multi_node(__node_type* __hint, __hash_code __code,
+			 __node_type* __node)
     {
       const __rehash_state& __saved_state = _M_rehash_policy._M_state();
       std::pair<bool, std::size_t> __do_rehash
@@ -1725,13 +1752,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  const key_type& __k = this->_M_extract()(__node->_M_v());
 	  size_type __bkt = _M_bucket_index(__k, __code);
 
-	  // Find the node before an equivalent one.
-	  __node_base* __prev = _M_find_before_node(__bkt, __k, __code);
+	  // Find the node before an equivalent one or use hint if it exists and
+	  // if it is equivalent.
+	  __node_base* __prev
+	    = __builtin_expect(__hint != nullptr, false)
+	      && this->_M_equals(__k, __code, __hint)
+		? __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))
+	      	// hint might be the last bucket node, in this case we need to
+	      	// update next bucket.
+	      	if (__node->_M_nxt
+	      	    && !this->_M_equals(__k, __code, __node->_M_next()))
+	      	  {
+	      	    size_type __next_bkt = _M_bucket_index(__node->_M_next());
+	      	    if (__next_bkt != __bkt)
+	      	      _M_buckets[__next_bkt] = __node;
+	      	  }
 	    }
 	  else
 	    // The inserted node has no equivalent in the
@@ -1786,7 +1828,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 			  _Traits>::iterator
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-      _M_insert(_Arg&& __v, std::false_type)
+      _M_insert(const_iterator __hint, _Arg&& __v, std::false_type)
       {
 	// First compute the hash code so that we don't do anything if it
 	// throws.
@@ -1795,7 +1837,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	// Second allocate new node so that we don't rehash if it throws.
 	__node_type* __node = _M_allocate_node(std::forward<_Arg>(__v));
 
-	return _M_insert_multi_node(__code, __node);
+	return _M_insert_multi_node(__hint._M_cur, __code, __node);
       }
 
   template<typename _Key, typename _Value,
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 1c76af0..2ae0efa 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -612,7 +612,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       using __unique_keys = typename __hashtable_base::__unique_keys;
       using __ireturn_type = typename __hashtable_base::__ireturn_type;
-      using __iconv_type = typename __hashtable_base::__iconv_type;
 
       __hashtable&
       _M_conjure_hashtable()
@@ -626,8 +625,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       }
 
       iterator
-      insert(const_iterator, const value_type& __v)
-      { return __iconv_type()(insert(__v)); }
+      insert(const_iterator __hint, const value_type& __v)
+      {
+	__hashtable& __h = _M_conjure_hashtable();
+	return __h._M_insert(__hint, __v, __unique_keys());
+      }
 
       void
       insert(initializer_list<value_type> __l)
@@ -711,8 +713,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       }
 
       iterator
-      insert(const_iterator, value_type&& __v)
-      { return insert(std::move(__v)).first; }
+      insert(const_iterator __hint, value_type&& __v)
+      {
+	__hashtable& __h = this->_M_conjure_hashtable();
+	return __h._M_insert(__hint, std::move(__v), __unique_keys());
+      }
     };
 
   /// Specialization.
@@ -745,9 +750,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       }
 
       iterator
-      insert(const_iterator, value_type&& __v)
-      { return insert(std::move(__v)); }
-     };
+      insert(const_iterator __hint, value_type&& __v)
+      {
+	__hashtable& __h = this->_M_conjure_hashtable();
+	return __h._M_insert(__hint, std::move(__v), __unique_keys());
+      }
+    };
 
   /// Specialization.
   template<typename _Key, typename _Value, typename _Alloc,
@@ -769,7 +777,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       using __unique_keys = typename __base_type::__unique_keys;
       using __hashtable = typename __base_type::__hashtable;
       using __ireturn_type = typename __base_type::__ireturn_type;
-      using __iconv_type = typename __base_type::__iconv_type;
 
       using __base_type::insert;
 
@@ -792,8 +799,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       template<typename _Pair, typename = _IFconsp<_Pair>>
 	iterator
-	insert(const_iterator, _Pair&& __v)
-	{ return __iconv_type()(insert(std::forward<_Pair>(__v))); }
+	insert(const_iterator __hint, _Pair&& __v)
+	{
+	  __hashtable& __h = this->_M_conjure_hashtable();
+	  return __h._M_emplace(__hint, __unique_keys(),
+				std::forward<_Pair>(__v));
+	}
    };
 
   /**
@@ -1470,10 +1481,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     using __ireturn_type = typename std::conditional<__unique_keys::value,
 						     std::pair<iterator, bool>,
 						     iterator>::type;
-
-    using __iconv_type = typename  std::conditional<__unique_keys::value,
-						    _Select1st, _Identity
-						    >::type;
   private:
     using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>;
     using _EqualHelper =  _Equal_helper<_Key, _Value, _ExtractKey, _Equal,
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc
new file mode 100644
index 0000000..f7bde04
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc
@@ -0,0 +1,123 @@
+// Copyright (C) 2013 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/>.
+
+// { dg-options "-std=gnu++11" }
+
+// Insert with hint, specific to this library implementation.
+
+#include <iterator>
+#include <unordered_map>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  typedef std::unordered_multimap<int, int> Map;
+  typedef typename Map::value_type Pair;
+
+  Map m;
+
+  auto it1 = m.insert(Pair(0, 0));
+  VERIFY( it1 != m.end() );
+  VERIFY( it1->first == 0 );
+  VERIFY( it1->second == 0 );
+
+  auto it2 = m.insert(it1, Pair(0, 2));
+  VERIFY( it2 != m.end() );
+  VERIFY( it2 != it1 );
+  VERIFY( it2->second == 2 );
+  VERIFY( it2 == std::next(it1) );
+
+  Pair p(0, 1);
+  it2 = m.insert(it1, p);
+  VERIFY( it2 == std::next(it1) );
+}
+
+struct hasher
+{
+  std::size_t operator()(int val) const
+  { return val / 2; }
+};
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+
+  typedef std::unordered_multimap<int, int, hasher> Map;
+  typedef typename Map::value_type Pair;
+
+  Map m;
+
+  auto it1 = m.insert(Pair(0, 0));
+  auto it2 = m.insert(it1, Pair(1, 0));
+  VERIFY( m.bucket(it1->first) == m.bucket(it2->first) );
+  VERIFY( m.bucket_size(m.bucket(it1->first)) == 2 );
+
+  auto it3 = m.insert(it2, Pair(2, 0));
+  VERIFY( m.bucket(it3->first) != m.bucket(it2->first) );
+  VERIFY( m.bucket_size(m.bucket(it3->first)) == 1 );
+
+  auto it4 = m.insert(it1, Pair(0, 1));
+  VERIFY( it4 == std::next(it1) );
+  VERIFY( m.bucket_size(m.bucket(it1->first)) == 3 );
+  VERIFY( m.bucket_size(m.bucket(it3->first)) == 1 );
+
+  Pair p(1, 1);
+  it4 = m.insert(it2, p);
+  VERIFY( it4 == std::next(it2) );
+  VERIFY( m.bucket_size(m.bucket(it1->first)) == 4 );
+  auto range = m.equal_range(0);
+  VERIFY( std::distance(range.first, range.second) == 2 );
+  range = m.equal_range(1);
+  VERIFY( std::distance(range.first, range.second) == 2 );
+}
+
+void test03()
+{
+  bool test __attribute__((unused)) = true;
+
+  typedef std::unordered_multimap<int, int> Map;
+  typedef typename Map::value_type Pair;
+
+  Map m;
+
+  auto it1 = m.insert(Pair(0, 0));
+  VERIFY( it1 != m.end() );
+  VERIFY( it1->first == 0 );
+  VERIFY( it1->second == 0 );
+
+  auto it2 = m.emplace_hint(it1, std::piecewise_construct,
+				 std::make_tuple(0),
+				 std::make_tuple(2));
+  VERIFY( it2 != m.end() );
+  VERIFY( it2 != it1 );
+  VERIFY( it2->second == 2 );
+  VERIFY( it2 == std::next(it1) );
+
+  Pair p(0, 1);
+  it2 = m.emplace_hint(it1, p);
+  VERIFY( it2 == std::next(it1) );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc
index f22c8be..dcea974 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc
@@ -19,7 +19,7 @@
 // with this library; see the file COPYING3.  If not see
 // <http://www.gnu.org/licenses/>.
 
-// { dg-error "with noexcept" "" { target *-*-* } 254 }
+// { dg-error "with noexcept" "" { target *-*-* } 253 }
 
 #include <unordered_set>
 
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc
index 7590344..e1b96a4 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc
@@ -19,7 +19,7 @@
 // with this library; see the file COPYING3.  If not see
 // <http://www.gnu.org/licenses/>.
 
-// { dg-error "default constructible" "" { target *-*-* } 272 }
+// { dg-error "default constructible" "" { target *-*-* } 271 }
 
 #include <unordered_set>
 
diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_multiset_hint.cc b/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_multiset_hint.cc
new file mode 100644
index 0000000..4e96ec1
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_multiset_hint.cc
@@ -0,0 +1,336 @@
+// Copyright (C) 2013 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/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <testsuite_performance.h>
+
+#include <sstream>
+#include <string>
+#include <vector>
+#include <unordered_set>
+
+namespace
+{
+  const int sz = 2000000;
+  const std::string pattern = "test string #";
+  const int nb_copies = 100;
+
+  // Special std::string hasher based on std::hash<std::string> but not tag as
+  // slow so that hash code is not cached. It is easier to show impact of
+  // hinting in this context.
+  struct hasher
+  {
+    std::size_t
+    operator()(const std::string& str) const noexcept
+    {
+      //std::istringstream istr(str.substr(pattern.size()));
+      //std::size_t str_index;
+      //istr >> str_index;
+      //return str_index;
+      std::hash<std::string> std_hasher;
+      return std_hasher(str);
+    }
+  };
+
+  using ums_t = std::unordered_multiset<std::string, hasher>;
+
+  void
+  insert_with_perfect_hint1(const std::vector<std::string>& strs,
+			    ums_t& ms)
+  {
+    std::vector<typename ums_t::iterator> hints;
+    hints.reserve(strs.size());
+    for (auto str : strs)
+      hints.push_back(ms.insert(str));
+
+    for (int j = 1; j != nb_copies; ++j)
+      for (std::size_t i = 0; i != strs.size(); ++i)
+	ms.insert(hints[i], strs[i]);
+  }
+
+  void
+  insert_with_perfect_hint2(const std::vector<std::string>& strs,
+			    ums_t& ms)
+  {
+    std::vector<typename ums_t::iterator> hints;
+    hints.reserve(strs.size());
+    for (auto str : strs)
+      hints.push_back(ms.insert(str));
+
+    for (std::size_t i = 0; i != strs.size(); ++i)
+      for (int j = 1; j != nb_copies; ++j)
+	ms.insert(hints[i], strs[i]);
+  }
+
+  // Always insert with the result of the previous insertion. The result of
+  // the previous insertion will never be followed by an equivalent node
+  // resulting in a re-computation of its hash code which is expensive.
+  void
+  insert_with_good_hint(const std::vector<std::string>& strs,
+			ums_t& ms)
+  {
+    std::vector<typename ums_t::iterator> hints;
+    hints.reserve(strs.size());
+    for (auto str : strs)
+      hints.push_back(ms.insert(str));
+
+    for (int j = 1; j != nb_copies; ++j)
+      for (std::size_t i = 0; i != strs.size(); ++i)
+	hints[i] = ms.insert(hints[i], strs[i]);
+  }
+
+  // Note that the following use case is particularly bad especially compared to
+  // the solution without hint because without hint the first insertion will put
+  // it first in the bucket and following insertions will detect it and insert
+  // just before. By giving a hint insertion will be done just after forcing to
+  // check if it has no impact on the following bucket.
+  void
+  insert_with_bad_hint(const std::vector<std::string>& strs,
+		       ums_t& ms)
+  {
+    std::vector<typename ums_t::iterator> hints;
+    hints.reserve(strs.size());
+    for (auto str : strs)
+      hints.push_back(ms.insert(str));
+
+    for (std::size_t i = 0; i != strs.size(); ++i)
+      for (int j = 1; j != nb_copies; ++j)
+	hints[i] = ms.insert(hints[i], strs[i]);
+  }
+
+  void
+  insert_without_hint1(const std::vector<std::string>& strs,
+		       ums_t& ms)
+  {
+    std::vector<typename ums_t::iterator> hints;
+    hints.reserve(strs.size());
+    for (auto str : strs)
+      hints.push_back(ms.insert(str));
+
+    for (int j = 1; j != nb_copies; ++j)
+      for (std::size_t i = 0; i != strs.size(); ++i)
+	hints[i] = ms.insert(strs[i]);
+  }
+
+  // This version is the best one if you insert all equivalent elements at the
+  // same time. It demonstrates that most of the time it is better not to give
+  // any hint unless you have written a benchmark for your application showing
+  // that it does have a positive effect.
+  void
+  insert_without_hint2(const std::vector<std::string>& strs,
+		       ums_t& ms)
+  {
+    std::vector<typename ums_t::iterator> hints;
+    hints.reserve(strs.size());
+    for (auto str : strs)
+      hints.push_back(ms.insert(str));
+
+    for (std::size_t i = 0; i != strs.size(); ++i)
+      for (int j = 1; j != nb_copies; ++j)
+	hints[i] = ms.insert(strs[i]);
+  }
+
+  void
+  insert_with_any_hint1(const std::vector<std::string>& strs,
+			ums_t& ms)
+  {
+    std::vector<typename ums_t::iterator> hints;
+    hints.reserve(strs.size());
+    for (auto str : strs)
+      hints.push_back(ms.insert(ms.begin(), str));
+
+    std::size_t offset = strs.size() / 2;
+    for (int j = 1; j != nb_copies; ++j)
+      for (std::size_t i = 0; i != strs.size(); ++i)
+	{
+	  ms.insert(hints[(i + offset) % hints.size()], strs[i]);
+	  ++offset;
+	}
+  }
+
+  void
+  insert_with_any_hint2(const std::vector<std::string>& strs,
+			ums_t& ms)
+  {
+    std::vector<typename ums_t::iterator> hints;
+    hints.reserve(strs.size());
+    for (auto str : strs)
+      hints.push_back(ms.insert(ms.begin(), str));
+
+    std::size_t offset = strs.size() / 2;
+    for (std::size_t i = 0; i != strs.size(); ++i)
+      for (int j = 1; j != nb_copies; ++j)
+	{
+	  ms.insert(hints[(i + offset) % hints.size()], strs[i]);
+	  ++offset;
+	}
+  }
+}
+
+int main()
+{
+  using namespace __gnu_test;
+
+  const int nb_iter = 10;
+
+  std::vector<std::string> strs;
+  strs.reserve(sz / nb_copies);
+
+  for (int i = 0; i != sz / nb_copies; ++i)
+    {
+      std::ostringstream osstr;
+      osstr << pattern << i;
+      strs.push_back(osstr.str());
+    }
+
+  ums_t ms;
+  // Use a large load factor to make the context ideal for using hint because we
+  // will have many elements per bucket.
+  ms.max_load_factor(10.0f);
+  ms.reserve(sz);
+
+  // Warm up.
+  {
+    for (auto str : strs)
+      for (int j = 0; j != nb_copies; ++j)
+	ms.insert(str);
+  }
+
+  time_counter time_no_hint1, time_any_hint1, time_bad_hint, time_perfect_hint1;
+  time_counter time_no_hint2, time_any_hint2, time_good_hint, time_perfect_hint2;
+  resource_counter resource_no_hint1, resource_any_hint1, resource_bad_hint,
+    resource_perfect_hint1;
+  resource_counter resource_no_hint2, resource_any_hint2, resource_good_hint,
+    resource_perfect_hint2;
+
+  for (int i = 0; i != nb_iter; ++i)
+    {
+      // Bad hint
+      {
+	ms.clear();
+	start_counters(time_bad_hint, resource_bad_hint);
+	insert_with_bad_hint(strs, ms);
+	stop_counters(time_bad_hint, resource_bad_hint);
+      }
+
+      // No hint
+      {
+	ms.clear();
+	start_counters(time_no_hint1, resource_no_hint1);
+	insert_without_hint1(strs, ms);
+	stop_counters(time_no_hint1, resource_no_hint1);
+      }
+
+      // Any hint
+      {
+	ms.clear();
+	start_counters(time_any_hint1, resource_any_hint1);
+	insert_with_any_hint1(strs, ms);
+	stop_counters(time_any_hint1, resource_any_hint1);
+      }
+
+      // Good hint
+      {
+	ms.clear();
+	start_counters(time_good_hint, resource_good_hint);
+	insert_with_good_hint(strs, ms);
+	stop_counters(time_good_hint, resource_good_hint);
+      }
+
+      // No hint
+      {
+	ms.clear();
+	start_counters(time_no_hint2, resource_no_hint2);
+	insert_without_hint2(strs, ms);
+	stop_counters(time_no_hint2, resource_no_hint2);
+      }
+
+      // Perfect hint
+      {
+	ms.clear();
+	start_counters(time_perfect_hint2, resource_perfect_hint2);
+	insert_with_perfect_hint2(strs, ms);
+	stop_counters(time_perfect_hint2, resource_perfect_hint2);
+      }
+
+      // Any hint
+      {
+	ms.clear();
+	start_counters(time_any_hint2, resource_any_hint2);
+	insert_with_any_hint2(strs, ms);
+	stop_counters(time_any_hint2, resource_any_hint2);
+      }
+
+      // Perfect hint
+      {
+	ms.clear();
+	start_counters(time_perfect_hint1, resource_perfect_hint1);
+	insert_with_perfect_hint1(strs, ms);
+	stop_counters(time_perfect_hint1, resource_perfect_hint1);
+      }
+    }
+
+  std::ostringstream ostr;
+  ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies
+       << " insertions w/o hint";
+  report_performance(__FILE__, ostr.str().c_str(),
+		     time_no_hint1, resource_no_hint1);
+
+  ostr.str("");
+  ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies
+       << " insertions with any hint";
+  report_performance(__FILE__, ostr.str().c_str(),
+		     time_any_hint1, resource_any_hint1);
+
+  ostr.str("");
+  ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies
+       << " insertions with good hint";
+  report_performance(__FILE__, ostr.str().c_str(),
+		     time_good_hint, resource_good_hint);
+
+  ostr.str("");
+  ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies
+       << " insertions with perfect hint";
+  report_performance(__FILE__, ostr.str().c_str(),
+		     time_perfect_hint1, resource_perfect_hint1);
+
+  ostr.str("");
+  ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies
+       << " insertions w/o hint";
+  report_performance(__FILE__, ostr.str().c_str(),
+		     time_no_hint2, resource_no_hint2);
+
+  ostr.str("");
+  ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies
+       << " insertions with any hint";
+  report_performance(__FILE__, ostr.str().c_str(),
+		     time_any_hint2, resource_any_hint2);
+
+  ostr.str("");
+  ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies
+       << " insertions with bad hint";
+  report_performance(__FILE__, ostr.str().c_str(),
+		     time_bad_hint, resource_bad_hint);
+
+  ostr.str("");
+  ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies
+       << " insertions with perfect hint";
+  report_performance(__FILE__, ostr.str().c_str(),
+		     time_perfect_hint2, resource_perfect_hint2);
+  return 0;
+}