Re: New hashtable power 2 rehash policy

[FranÃois Dumont <frs dot dumont at gmail dot com>]

On 14/05/2016 19:06, Daniel KrÃgler wrote:
> 2016-05-14 18:13 GMT+02:00 FranÃois Dumont <frs.dumont@gmail.com>:
>
> > New patch attached, tested under linux x86_64.
> >
> > FranÃois
> 1) The function __clp2 is declared using _GLIBCXX14_CONSTEXPR, which
> means that it is an inline function if and *only* if
> _GLIBCXX14_CONSTEXPR really expands to constexpr, otherwise it is
> *not* inline, which is probably not intended and could easily cause
> ODR problems. I suggest to mark it unconditionally as inline,
> regardless of _GLIBCXX14_CONSTEXPR.

Maybe _GLIBCXX14_CONSTEXPR should take inline value previous to C++14 mode.

For the moment I simply added the inline as done in other situations.

> 2) Furthermore I suggest to declare __clp2 as noexcept - this is
> (intentionally) *not* implied by constexpr.
>
> 3) Is there any reason, why _Power2_rehash_policy::_M_next_bkt
> shouldn't be noexcept?
>
> 4) Similar to (3) for _Power2_rehash_policy's member functions
> _M_bkt_for_elements, _M_need_rehash, _M_state, _M_reset
For noexcept I throught we were only adding it if necessary. We might 
have to go through a lot of code to find all places where noexcept could 
be added. Jonathan will give his feedback.

For the moment I have added it on all those methods.

Thanks for feedback, updated and tested patch attached.

FranÃois

diff --git a/libstdc++-v3/include/bits/c++config b/libstdc++-v3/include/bits/c++config
index 57024e4..78353ae 100644
--- a/libstdc++-v3/include/bits/c++config
+++ b/libstdc++-v3/include/bits/c++config
@@ -106,8 +106,10 @@
 #ifndef _GLIBCXX14_CONSTEXPR
 # if __cplusplus >= 201402L
 #  define _GLIBCXX14_CONSTEXPR constexpr
+#  define _GLIBCXX14_USE_CONSTEXPR constexpr
 # else
 #  define _GLIBCXX14_CONSTEXPR
+#  define _GLIBCXX14_USE_CONSTEXPR const
 # endif
 #endif
 
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 2c24c19..caff085 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -31,6 +31,8 @@
 #ifndef _HASHTABLE_POLICY_H
 #define _HASHTABLE_POLICY_H 1
 
+#include <bits/stl_algobase.h> // for std::min.
+
 namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
@@ -457,6 +459,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   /// smallest prime that keeps the load factor small enough.
   struct _Prime_rehash_policy
   {
+    using __has_load_factor = std::true_type;
+
     _Prime_rehash_policy(float __z = 1.0) noexcept
     : _M_max_load_factor(__z), _M_next_resize(0) { }
 
@@ -501,6 +505,132 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     mutable std::size_t	_M_next_resize;
   };
 
+  /// Range hashing function assuming that second arg is a power of 2.
+  struct _Mask_range_hashing
+  {
+    typedef std::size_t first_argument_type;
+    typedef std::size_t second_argument_type;
+    typedef std::size_t result_type;
+
+    result_type
+    operator()(first_argument_type __num,
+	       second_argument_type __den) const noexcept
+    { return __num & (__den - 1); }
+  };
+
+  /// Compute closest power of 2.
+  _GLIBCXX14_CONSTEXPR
+  inline std::size_t
+  __clp2(std::size_t n) noexcept
+  {
+#if __SIZEOF_SIZE_T__ >= 8
+    std::uint_fast64_t x = n;
+#else
+    std::uint_fast32_t x = n;
+#endif
+    // Algorithm from Hacker's Delight, Figure 3-3.
+    x = x - 1;
+    x = x | (x >> 1);
+    x = x | (x >> 2);
+    x = x | (x >> 4);
+    x = x | (x >> 8);
+    x = x | (x >>16);
+#if __SIZEOF_SIZE_T__ >= 8
+    x = x | (x >>32);
+#endif
+    return x + 1;
+  }
+
+  /// Rehash policy providing power of 2 bucket numbers. Avoids modulo
+  /// operations.
+  struct _Power2_rehash_policy
+  {
+    using __has_load_factor = std::true_type;
+
+    _Power2_rehash_policy(float __z = 1.0) noexcept
+    : _M_max_load_factor(__z), _M_next_resize(0) { }
+
+    float
+    max_load_factor() const noexcept
+    { return _M_max_load_factor; }
+
+    // Return a bucket size no smaller than n (as long as n is not above the
+    // highest power of 2).
+    std::size_t
+    _M_next_bkt(std::size_t __n) const noexcept
+    {
+      _GLIBCXX14_USE_CONSTEXPR size_t __max_width
+	= std::min<size_t>(sizeof(size_t), 8);
+      _GLIBCXX14_USE_CONSTEXPR auto __max_bkt
+	= std::size_t(1) << (__max_width * __CHAR_BIT__ - 1);
+
+      std::size_t __res = __clp2(__n);
+
+      if (__res == 0)
+	__res = __max_bkt;
+
+      if (__res == __max_bkt)
+	// Set next resize to the max value so that we never try to rehash again
+	// as we already reach the biggest possible bucket number.
+	// Note that it might result in max_load_factor not being respected.
+	_M_next_resize = std::size_t(-1);
+      else
+	_M_next_resize
+	  = __builtin_ceil(__res * (long double)_M_max_load_factor);
+
+      return __res;
+    }
+
+    // Return a bucket count appropriate for n elements
+    std::size_t
+    _M_bkt_for_elements(std::size_t __n) const noexcept
+    { return __builtin_ceil(__n / (long double)_M_max_load_factor); }
+
+    // __n_bkt is current bucket count, __n_elt is current element count,
+    // and __n_ins is number of elements to be inserted.  Do we need to
+    // increase bucket count?  If so, return make_pair(true, n), where n
+    // is the new bucket count.  If not, return make_pair(false, 0).
+    std::pair<bool, std::size_t>
+    _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
+		   std::size_t __n_ins) const noexcept
+    {
+      if (__n_elt + __n_ins >= _M_next_resize)
+	{
+	  long double __min_bkts = (__n_elt + __n_ins)
+					/ (long double)_M_max_load_factor;
+	  if (__min_bkts >= __n_bkt)
+	    return std::make_pair(true,
+	      _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1,
+						__n_bkt * _S_growth_factor)));
+
+	  _M_next_resize
+	    = __builtin_floor(__n_bkt * (long double)_M_max_load_factor);
+	  return std::make_pair(false, 0);
+	}
+      else
+	return std::make_pair(false, 0);
+    }
+
+    typedef std::size_t _State;
+
+    _State
+    _M_state() const noexcept
+    { return _M_next_resize; }
+
+    void
+    _M_reset() noexcept
+    { _M_next_resize = 0; }
+
+    void
+    _M_reset(_State __state) noexcept
+    { _M_next_resize = __state; }
+
+    static const std::size_t _S_growth_factor = 2;
+
+    float		_M_max_load_factor;
+    mutable std::size_t	_M_next_resize;
+  };
+
   // Base classes for std::_Hashtable.  We define these base classes
   // because in some cases we want to do different things depending on
   // the value of a policy class.  In some cases the policy class
@@ -776,8 +906,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits,
-	   bool _Constant_iterators = _Traits::__constant_iterators::value,
-	   bool _Unique_keys = _Traits::__unique_keys::value>
+	   bool _Constant_iterators = _Traits::__constant_iterators::value>
     struct _Insert;
 
   /// Specialization.
@@ -786,65 +915,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
-		   _RehashPolicy, _Traits, true, true>
+		   _RehashPolicy, _Traits, true>
     : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 			   _H1, _H2, _Hash, _RehashPolicy, _Traits>
     {
       using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
 					_Equal, _H1, _H2, _Hash,
 					_RehashPolicy, _Traits>;
-      using value_type = typename __base_type::value_type;
-      using iterator = typename __base_type::iterator;
-      using const_iterator =  typename __base_type::const_iterator;
-
-      using __unique_keys = typename __base_type::__unique_keys;
-      using __hashtable = typename __base_type::__hashtable;
-      using __node_gen_type = typename __base_type::__node_gen_type;
-
-      using __base_type::insert;
 
-      std::pair<iterator, bool>
-      insert(value_type&& __v)
-      {
-	__hashtable& __h = this->_M_conjure_hashtable();
-	__node_gen_type __node_gen(__h);
-	return __h._M_insert(std::move(__v), __node_gen, __unique_keys());
-      }
-
-      iterator
-      insert(const_iterator __hint, value_type&& __v)
-      {
-	__hashtable& __h = this->_M_conjure_hashtable();
-	__node_gen_type __node_gen(__h);
-	return __h._M_insert(__hint, std::move(__v), __node_gen,
-			     __unique_keys());
-      }
-    };
-
-  /// Specialization.
-  template<typename _Key, typename _Value, typename _Alloc,
-	   typename _ExtractKey, typename _Equal,
-	   typename _H1, typename _H2, typename _Hash,
-	   typename _RehashPolicy, typename _Traits>
-    struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
-		   _RehashPolicy, _Traits, true, false>
-    : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-			   _H1, _H2, _Hash, _RehashPolicy, _Traits>
-    {
-      using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
+      using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
 					       _Equal, _H1, _H2, _Hash,
-					_RehashPolicy, _Traits>;
+					       _Traits>;
+
       using value_type = typename __base_type::value_type;
       using iterator = typename __base_type::iterator;
       using const_iterator =  typename __base_type::const_iterator;
 
       using __unique_keys = typename __base_type::__unique_keys;
+      using __ireturn_type = typename __hashtable_base::__ireturn_type;
       using __hashtable = typename __base_type::__hashtable;
       using __node_gen_type = typename __base_type::__node_gen_type;
 
       using __base_type::insert;
 
-      iterator
+      __ireturn_type
       insert(value_type&& __v)
       {
 	__hashtable& __h = this->_M_conjure_hashtable();
@@ -866,9 +960,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   template<typename _Key, typename _Value, typename _Alloc,
 	   typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
-	   typename _RehashPolicy, typename _Traits, bool _Unique_keys>
+	   typename _RehashPolicy, typename _Traits>
     struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
-		   _RehashPolicy, _Traits, false, _Unique_keys>
+		   _RehashPolicy, _Traits, false>
     : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 			   _H1, _H2, _Hash, _RehashPolicy, _Traits>
     {
@@ -912,28 +1006,46 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	}
    };
 
+  template<typename _Policy>
+    using __has_load_factor = typename _Policy::__has_load_factor;
+
   /**
    *  Primary class template  _Rehash_base.
    *
    *  Give hashtable the max_load_factor functions and reserve iff the
-   *  rehash policy is _Prime_rehash_policy.
+   *  rehash policy supports it.
   */
   template<typename _Key, typename _Value, typename _Alloc,
 	   typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
-	   typename _RehashPolicy, typename _Traits>
+	   typename _RehashPolicy, typename _Traits,
+	   typename =
+	     __detected_or_t<std::false_type, __has_load_factor, _RehashPolicy>>
     struct _Rehash_base;
 
-  /// Specialization.
+  /// Specialization when rehash policy doesn't provide load factor management.
   template<typename _Key, typename _Value, typename _Alloc,
 	   typename _ExtractKey, typename _Equal,
-	   typename _H1, typename _H2, typename _Hash, typename _Traits>
+	   typename _H1, typename _H2, typename _Hash,
+	   typename _RehashPolicy, typename _Traits>
     struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-			_H1, _H2, _Hash, _Prime_rehash_policy, _Traits>
+		      _H1, _H2, _Hash, _RehashPolicy, _Traits,
+		      std::false_type>
+    {
+    };
+
+  /// Specialization when rehash policy provide load factor management.
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash,
+	   typename _RehashPolicy, typename _Traits>
+    struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+			_H1, _H2, _Hash, _RehashPolicy, _Traits,
+			std::true_type>
     {
       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
 				     _Equal, _H1, _H2, _Hash,
-				     _Prime_rehash_policy, _Traits>;
+				     _RehashPolicy, _Traits>;
 
       float
       max_load_factor() const noexcept
@@ -946,7 +1058,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       max_load_factor(float __z)
       {
 	__hashtable* __this = static_cast<__hashtable*>(this);
-	__this->__rehash_policy(_Prime_rehash_policy(__z));
+	__this->__rehash_policy(_RehashPolicy(__z));
       }
 
       void
diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
index a5e6520..506ac6a 100644
--- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc
+++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
@@ -60,8 +60,16 @@ namespace __detail
       = sizeof(__prime_list) / sizeof(unsigned long) - 1;
     const unsigned long* __next_bkt =
       std::lower_bound(__prime_list + 5, __prime_list + __n_primes, __n);
+
+    if (__next_bkt == __prime_list + __n_primes)
+      // Set next resize to the max value so that we never try to rehash again
+      // as we already reach the biggest possible bucket number.
+      // Note that it might result in max_load_factor not being respected.
+      _M_next_resize = std::size_t(-1);
+    else
       _M_next_resize =
 	__builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
+
     return *__next_bkt;
   }
 
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/26132.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/26132.cc
index 092ee28..5c01fa7 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/26132.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/26132.cc
@@ -23,15 +23,16 @@
 #include <testsuite_hooks.h>
 
 // libstdc++/26132
-void test01()
+template<typename _USet>
+  void test()
   {
     bool test __attribute__((unused)) = true;
 
     for (float lf = 1.0; lf < 101.0; lf *= 10.0)
       for (int size = 1; size <= 6561; size *= 3)
 	{
-	std::unordered_set<int> us1;
-	typedef std::unordered_set<int>::size_type size_type;
+	  _USet us1;
+	  typedef typename _USet::size_type size_type;
 
 	  us1.max_load_factor(10.0);
 
@@ -50,8 +51,20 @@ void test01()
 	}
   }
 
+template<typename _Value>
+  using unordered_set_power2_rehash =
+  std::_Hashtable<_Value, _Value, std::allocator<_Value>,
+		  std::__detail::_Identity,
+		  std::equal_to<_Value>,
+		  std::hash<_Value>,
+		  std::__detail::_Mask_range_hashing,
+		  std::__detail::_Default_ranged_hash,
+		  std::__detail::_Power2_rehash_policy,
+		  std::__detail::_Hashtable_traits<false, true, true>>;
+
 int main()
 {
-  test01();
+  test<std::unordered_set<int>>();
+  test<unordered_set_power2_rehash<int>>();
   return 0;
 }
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/load_factor.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/load_factor.cc
index 8a42ed4..0c3b7f8 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/load_factor.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/load_factor.cc
@@ -18,13 +18,15 @@
 // { dg-options "-std=gnu++11" }
 
 #include <unordered_set>
+
 #include <testsuite_hooks.h>
 
-void test01()
+template<typename _USet>
+  void test()
   {
     bool test __attribute__((unused)) = true;
     {
-    std::unordered_set<int> us;
+      _USet us;
       for (int i = 0; i != 100000; ++i)
 	{
 	  us.insert(i);
@@ -32,7 +34,7 @@ void test01()
 	}
     }
     {
-    std::unordered_set<int> us;
+      _USet us;
       us.max_load_factor(3.f);
       for (int i = 0; i != 100000; ++i)
 	{
@@ -41,7 +43,7 @@ void test01()
 	}
     }
     {
-    std::unordered_set<int> us;
+      _USet us;
       us.max_load_factor(.3f);
       for (int i = 0; i != 100000; ++i)
 	{
@@ -51,8 +53,20 @@ void test01()
     }
   }
 
+template<typename _Value>
+  using unordered_set_power2_rehash =
+  std::_Hashtable<_Value, _Value, std::allocator<_Value>,
+		  std::__detail::_Identity,
+		  std::equal_to<_Value>,
+		  std::hash<_Value>,
+		  std::__detail::_Mask_range_hashing,
+		  std::__detail::_Default_ranged_hash,
+		  std::__detail::_Power2_rehash_policy,
+		  std::__detail::_Hashtable_traits<false, true, true>>;
+
 int main()
 {
-  test01();
+  test<std::unordered_set<int>>();
+  test<unordered_set_power2_rehash<int>>();
   return 0;
 }
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc
new file mode 100644
index 0000000..50a9dc9
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc
@@ -0,0 +1,42 @@
+// Copyright (C) 2016 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 <unordered_set>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  std::__detail::_Power2_rehash_policy policy;
+  VERIFY( policy._M_next_bkt(1) == 1 );
+  VERIFY( policy._M_next_bkt(2) == 2 );
+  VERIFY( policy._M_next_bkt(3) == 4 );
+  VERIFY( policy._M_next_bkt(5) == 8 );
+  VERIFY( policy._M_next_bkt(33) == 64 );
+  VERIFY( policy._M_next_bkt((std::size_t(1) << (sizeof(std::size_t) * 8 - 2)) + 1)
+	  == (std::size_t(1) << (sizeof(std::size_t) * 8 - 1)) );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc
index 46faa6d..2dac583 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc
@@ -18,13 +18,15 @@
 // { dg-options "-std=gnu++11" }
 
 #include <unordered_set>
+
 #include <testsuite_hooks.h>
 
-void test01()
+template<typename _USet>
+void test()
 {
   bool test __attribute__((unused)) = true;
-  std::unordered_set<int> us;
-  typedef typename std::unordered_set<int>::size_type size_type;
+  _USet us;
+  typedef typename _USet::size_type size_type;
   bool rehashed = false;
   for (int i = 0; i != 100000; ++i)
   {
@@ -55,8 +57,20 @@ void test01()
   VERIFY( rehashed );
 }
 
+template<typename _Value>
+  using unordered_set_power2_rehash =
+  std::_Hashtable<_Value, _Value, std::allocator<_Value>,
+		  std::__detail::_Identity,
+		  std::equal_to<_Value>,
+		  std::hash<_Value>,
+		  std::__detail::_Mask_range_hashing,
+		  std::__detail::_Default_ranged_hash,
+		  std::__detail::_Power2_rehash_policy,
+		  std::__detail::_Hashtable_traits<false, true, true>>;
+
 int main()
 {
-  test01();
+  test<std::unordered_set<int>>();
+  test<unordered_set_power2_rehash<int>>();
   return 0;
 }
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/insert/hash_policy.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/hash_policy.cc
index 2419af1..7dcaf39 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/insert/hash_policy.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/hash_policy.cc
@@ -20,15 +20,23 @@
 #include <unordered_set>
 #include <vector>
 #include <limits>
+
 #include <ext/throw_allocator.h>
+
 #include <testsuite_hooks.h>
 
+template<template<typename _Value, typename _Hash,
+		  typename _Pred, typename _Alloc>
+	   typename _USet>
   void test01()
   {
     bool test __attribute__((unused)) = true;
 
+    // Make sure whatever happen we restore throw allocator limit at exit.
+    __gnu_cxx::limit_condition::adjustor_base adj;
+
     typedef std::numeric_limits<std::size_t> nl_size_t;
-  std::unordered_set<int, std::hash<int>, std::equal_to<int>,
+    _USet<int, std::hash<int>, std::equal_to<int>,
 	  __gnu_cxx::throw_allocator_limit<int> > us;
     const int nb = 100;
     int scheduled_throw_counter = 0;
@@ -63,12 +71,18 @@ void test01()
       }
   }
 
+template<template<typename _Value, typename _Hash,
+		  typename _Pred, typename _Alloc>
+	   typename _USet>
   void test02()
   {
     bool test __attribute__((unused)) = true;
 
+    // Make sure whatever happen we restore throw allocator limit at exit.
+    __gnu_cxx::limit_condition::adjustor_base adj;
+
     typedef std::numeric_limits<std::size_t> nl_size_t;
-  std::unordered_set<int, std::hash<int>, std::equal_to<int>,
+    _USet<int, std::hash<int>, std::equal_to<int>,
 		       __gnu_cxx::throw_allocator_limit<int> > us;
     const int nb = 100;
     int scheduled_throw_counter = 0;
@@ -105,9 +119,23 @@ void test02()
       }
   }
 
+template<typename _Value, typename _Hash,
+	 typename _Pred, typename _Alloc>
+  using unordered_set_power2_rehash =
+  std::_Hashtable<_Value, _Value, _Alloc,
+		  std::__detail::_Identity,
+		  _Pred,
+		  _Hash,
+		  std::__detail::_Mask_range_hashing,
+		  std::__detail::_Default_ranged_hash,
+		  std::__detail::_Power2_rehash_policy,
+		  std::__detail::_Hashtable_traits<false, true, true>>;
+
 int main()
 {
-  test01();
-  test02();
+  test01<std::unordered_set>();
+  test01<unordered_set_power2_rehash>();
+  test02<std::unordered_set>();
+  test02<unordered_set_power2_rehash>();
   return 0;
 }
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc
index 95cc1cd..eb253a5 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc
@@ -22,12 +22,15 @@
 #include <ext/throw_allocator.h>
 #include <testsuite_hooks.h>
 
-void test01()
+template<template<typename _Value, typename _Hash,
+		  typename _Pred, typename _Alloc>
+	   typename _USet>
+  void test()
   {
     bool test __attribute__((unused)) = true;
 
     typedef std::numeric_limits<std::size_t> nl_size_t;
-  std::unordered_set<int, std::hash<int>, std::equal_to<int>,
+    _USet<int, std::hash<int>, std::equal_to<int>,
 	  __gnu_cxx::throw_allocator_limit<int> > us;
     int val = 0;
     for (; val != 100; ++val)
@@ -49,7 +52,7 @@ void test01()
 
     while (true)
       {
-      __gnu_cxx::limit_condition::set_limit(counter++);
+	__gnu_cxx::limit_condition::limit_adjustor adjustor(counter++);
 	bool do_break = false;
 	try
 	  {
@@ -76,8 +79,22 @@ void test01()
     VERIFY( thrown_exceptions > 0 );
   }
 
+
+template<typename _Value, typename _Hash,
+	 typename _Pred, typename _Alloc>
+  using unordered_set_power2_rehash =
+  std::_Hashtable<_Value, _Value, _Alloc,
+		  std::__detail::_Identity,
+		  _Pred,
+		  _Hash,
+		  std::__detail::_Mask_range_hashing,
+		  std::__detail::_Default_ranged_hash,
+		  std::__detail::_Power2_rehash_policy,
+		  std::__detail::_Hashtable_traits<false, true, true>>;
+
 int main()
 {
-  test01();
+  test<std::unordered_set>();
+  test<unordered_set_power2_rehash>();
   return 0;
 }
diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc b/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc
index a8b2675..784ac71 100644
--- a/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc
+++ b/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc
@@ -127,8 +127,28 @@ template<bool cache>
   using __umset = std::__umset_hashtable<Foo, HashFunction,
 					 std::equal_to<Foo>,
 					 std::allocator<Foo>,
+					 std::__umset_traits<cache>>;
+
+template<bool cache>
+  using __uset2 =
+	      std::_Hashtable<Foo, Foo, std::allocator<Foo>,
+			      std::__detail::_Identity,
+			      std::equal_to<Foo>, HashFunction,
+			      std::__detail::_Mask_range_hashing,
+			      std::__detail::_Default_ranged_hash,
+			      std::__detail::_Power2_rehash_policy,
 			      std::__uset_traits<cache>>;
 
+template<bool cache>
+  using __umset2 =
+	      std::_Hashtable<Foo, Foo, std::allocator<Foo>,
+			      std::__detail::_Identity,
+			      std::equal_to<Foo>, HashFunction,
+			      std::__detail::_Mask_range_hashing,
+			      std::__detail::_Default_ranged_hash,
+			      std::__detail::_Power2_rehash_policy,
+			      std::__umset_traits<cache>>;
+
 int main()
 {
   using namespace __gnu_test;
@@ -181,6 +201,19 @@ int main()
   stop_counters(time, resource);
   report_performance(__FILE__, "std benches", time, resource);
 
+  start_counters(time, resource);
+  bench<__uset2<false>>(
+	"std::unordered_set2 without hash code cached ", foos);
+  bench<__uset2<true>>(
+	"std::unordered_set2 with hash code cached ", foos);
+  bench<__umset2<false>>(
+	"std::unordered_multiset2 without hash code cached ", foos);
+  bench<__umset2<true>>(
+	"std::unordered_multiset2 with hash code cached ", foos);
+
+  stop_counters(time, resource);
+  report_performance(__FILE__, "std2 benches", time, resource);
+
   bench<std::unordered_set<Foo, HashFunction>>(
 	"std::unordered_set default cache ", foos);
   bench<std::unordered_multiset<Foo, HashFunction>>(
diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc b/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc
index 4de6598..44781d2 100644
--- a/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc
+++ b/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc
@@ -177,6 +177,16 @@ template<bool cache>
 					cache>;
 
 template<bool cache>
+  using __uset2 =
+	      std::_Hashtable<int, int, std::allocator<int>,
+			      std::__detail::_Identity,
+			      std::equal_to<int>, std::hash<int>,
+			      std::__detail::_Mask_range_hashing,
+			      std::__detail::_Default_ranged_hash,
+			      std::__detail::_Power2_rehash_policy,
+			      std::__uset_traits<cache>>;
+
+template<bool cache>
   using __str_uset = 
 	      std::__uset_hashtable<std::string, std::hash<std::string>,
 				    std::equal_to<std::string>,
@@ -190,6 +200,16 @@ template<bool cache>
 					std::allocator<std::string>,
 					cache>;
 
+template<bool cache>
+  using __str_uset2 =
+	      std::_Hashtable<std::string, std::string, std::allocator<std::string>,
+			      std::__detail::_Identity,
+			      std::equal_to<std::string>, std::hash<std::string>,
+			      std::__detail::_Mask_range_hashing,
+			      std::__detail::_Default_ranged_hash,
+			      std::__detail::_Power2_rehash_policy,
+			      std::__uset_traits<cache>>;
+
 int main()
 {
   bench<__tr1_uset<false>>(
@@ -202,6 +222,10 @@ int main()
 	"std::unordered_set<int> with hash code cached");
   bench<std::unordered_set<int>>(
 	"std::unordered_set<int> default cache");
+  bench<__uset2<false>>(
+	"std::unordered_set2<int> without hash code cached");
+  bench<__uset2<true>>(
+	"std::unordered_set2<int> with hash code cached");
   bench_str<__tr1_str_uset<false>>(
 	"std::tr1::unordered_set<string> without hash code cached");
   bench_str<__tr1_str_uset<true>>(
@@ -212,5 +236,9 @@ int main()
 	"std::unordered_set<string> with hash code cached");
   bench_str<std::unordered_set<std::string>>(
 	"std::unordered_set<string> default cache");
+  bench_str<__str_uset2<false>>(
+	"std::unordered_set2<string> without hash code cached");
+  bench_str<__str_uset2<true>>(
+	"std::unordered_set2<string> with hash code cached");
   return 0;
 }