New hashtable power 2 rehash policy

New hashtable power 2 rehash policy

[François Dumont]

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

Hi

     Here is a patch to introduce a new power of 2 based rehash policy. 
It enhances performance as it avoids modulo float operations. I have 
updated performance benches and here is the result:

54075.cc                        tr1 benches 455r  446u    8s        
0mem    0pf
54075.cc                        std benches 466r  460u    6s        
0mem    0pf
54075.cc                        std2 benches 375r  369u    6s        
0mem    0pf

std2 benches is the one using power of 2 bucket count.

     Note that I made use of __detected_or_t to avoid duplicating all 
the code of _Rehash_base<>.

     It brings a simplification of _Insert<>, it doesn't take a 
_Unique_keys template parameter anymore. It allowed to remove a 
specialization.

     It also improve behavior when we reach maximum number of buckets, 
we won't keep on trying to increase the number as it is impossible.

     Last it fixes a small problem in 54075.cc bench. We were using 
__uset_traits rather than __umset_traits in definition of __umset. 
Results were not the expected ones.

2016-04-22  François Dumont <fdumont@gcc.gnu.org>

     * include/bits/hashtable_policy.h
     (_Prime_rehash_policy::__has_load_factor): New. Mark rehash policy
     having load factor management.
     (_Mask_range_hashing): New.
     (_NextPower2<size_t>): New.
     (_Power2_rehash_policy): New.
     (_Inserts<>): Remove last template parameter _Unique_keys. Use the same
     implementation when keys are unique no matter if iterators are constant
     or not.
     * src/c++11/hashable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
     Consider when last prime number has been reach.
     * testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc:
     New.
     * testsuite/performance/23_containers/insert/54075.cc: Add bench using
     the new hash policy.
     * testsuite/performance/23_containers/insert_erase/41975.cc: Likewise.

Tested under linux x64_86, ok to commit ?

François



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch; name="hashtable.patch", Size: 17473 bytes --]

Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h	(révision 235348)
+++ include/bits/hashtable_policy.h	(copie de travail)
@@ -457,6 +457,8 @@
   /// 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 +503,136 @@
     mutable std::size_t	_M_next_resize;
   };
 
+  /// Range hashing function assuming that second args 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); }
+  };
+
+
+  /// Helper type to compute next power of 2.
+  template<typename _SizeT,
+	   std::size_t _N = sizeof(_SizeT) << 2, bool _Increment = true>
+    struct _NextPower2
+    {
+      static _SizeT
+      _Get(_SizeT __n)
+      {
+	_SizeT __next = _NextPower2<_SizeT, (_N >> 1), false>::_Get(__n);
+	__next |= __next >> _N;
+	if (_Increment)
+	  ++__next;
+
+	return __next;
+      }
+    };
+
+  template<typename _SizeT>
+    struct _NextPower2<_SizeT, 1, false>
+    {
+      static _SizeT
+      _Get(_SizeT __n)
+      {
+	--__n;
+	return __n |= __n >> 1;
+      }
+    };
+
+  /// Rehash policy providing power of 2 bucket numbers. Ease 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
+    {
+      constexpr auto __max_bkt
+	= std::size_t(1) << ((sizeof(std::size_t) << 3) - 1);
+
+      std::size_t __res = _NextPower2<std::size_t>::_Get(__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(0) - 1;
+      else
+	_M_next_resize
+	  = __builtin_floor(__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
+    { 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
+    {
+      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
+    { return _M_next_resize; }
+
+    void
+    _M_reset() noexcept
+    { _M_next_resize = 0; }
+
+    void
+    _M_reset(_State __state)
+    { _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
@@ -775,8 +907,7 @@
 	   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.
@@ -785,7 +916,7 @@
 	   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>
     {
@@ -792,58 +923,23 @@
       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 __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
+					       _Equal, _H1, _H2, _Hash,
+					       _Traits>;
 
-      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,
-					_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 __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();
@@ -865,9 +961,9 @@
   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>
     {
@@ -911,28 +1007,46 @@
 	}
    };
 
+  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
@@ -945,7 +1059,7 @@
       max_load_factor(float __z)
       {
 	__hashtable* __this = static_cast<__hashtable*>(this);
-	__this->__rehash_policy(_Prime_rehash_policy(__z));
+	__this->__rehash_policy(_RehashPolicy(__z));
       }
 
       void
Index: src/c++11/hashtable_c++0x.cc
===================================================================
--- src/c++11/hashtable_c++0x.cc	(révision 235348)
+++ src/c++11/hashtable_c++0x.cc	(copie de travail)
@@ -60,8 +60,16 @@
       = sizeof(__prime_list) / sizeof(unsigned long) - 1;
     const unsigned long* __next_bkt =
       std::lower_bound(__prime_list + 5, __prime_list + __n_primes, __n);
-    _M_next_resize =
-      __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
+
+    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(0) - 1;
+    else
+      _M_next_resize =
+	__builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
+
     return *__next_bkt;
   }
 
Index: testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc
===================================================================
--- testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc	(nonexistent)
+++ testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc	(copie de travail)
@@ -0,0 +1,43 @@
+// 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;
+}
Index: testsuite/performance/23_containers/insert/54075.cc
===================================================================
--- testsuite/performance/23_containers/insert/54075.cc	(révision 235348)
+++ testsuite/performance/23_containers/insert/54075.cc	(copie de travail)
@@ -127,8 +127,28 @@
   using __umset = std::__umset_hashtable<Foo, HashFunction,
 					 std::equal_to<Foo>,
 					 std::allocator<Foo>,
-					 std::__uset_traits<cache>>;
+					 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 @@
   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>>(
Index: testsuite/performance/23_containers/insert_erase/41975.cc
===================================================================
--- testsuite/performance/23_containers/insert_erase/41975.cc	(révision 235348)
+++ testsuite/performance/23_containers/insert_erase/41975.cc	(copie de travail)
@@ -177,6 +177,16 @@
 					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,18 @@
 					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 +224,10 @@
 	"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>>(
@@ -210,7 +236,11 @@
 	"std::unordered_set<string> without hash code cached");
   bench_str<__str_uset<true>>(
 	"std::unordered_set<string> with hash code cached");
-    bench_str<std::unordered_set<std::string>>(
+  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;
 }

Re: New hashtable power 2 rehash policy

[Jonathan Wakely]

On 23/04/16 10:27 +0200, François Dumont wrote:
>Hi
>
>    Here is a patch to introduce a new power of 2 based rehash policy. 
>It enhances performance as it avoids modulo float operations. I have 
>updated performance benches and here is the result:
>
>54075.cc                        tr1 benches 455r  446u    8s        
>0mem    0pf
>54075.cc                        std benches 466r  460u    6s        
>0mem    0pf
>54075.cc                        std2 benches 375r  369u    6s        
>0mem    0pf
>
>std2 benches is the one using power of 2 bucket count.
>
>    Note that I made use of __detected_or_t to avoid duplicating all 
>the code of _Rehash_base<>.
>
>    It brings a simplification of _Insert<>, it doesn't take a 
>_Unique_keys template parameter anymore. It allowed to remove a 
>specialization.
>
>    It also improve behavior when we reach maximum number of buckets, 
>we won't keep on trying to increase the number as it is impossible.
>
>    Last it fixes a small problem in 54075.cc bench. We were using 
>__uset_traits rather than __umset_traits in definition of __umset. 
>Results were not the expected ones.

Thanks, now that we're back in stage 1 we can make this change.


>
>2016-04-22  François Dumont <fdumont@gcc.gnu.org>
>
>    * include/bits/hashtable_policy.h
>    (_Prime_rehash_policy::__has_load_factor): New. Mark rehash policy
>    having load factor management.
>    (_Mask_range_hashing): New.
>    (_NextPower2<size_t>): New.
>    (_Power2_rehash_policy): New.
>    (_Inserts<>): Remove last template parameter _Unique_keys. Use the same
>    implementation when keys are unique no matter if iterators are constant
>    or not.

I found this change description confusing, because it's really using
the same implementation whether keys are unique or not, but this says
"Use the same implementation whether iterators are constant or not".

Shouldn't it be "Use the same implementation when iterators are
constant, no matter if keys are unique or not" ?

Maybe this would be clearer:

    (_Inserts<>): Remove last template parameter, _Unique_keys, so
    that partial specializations only depend on whether iterators are
    constant or not.


>    * src/c++11/hashable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
>    Consider when last prime number has been reach.

s/reach/reached/

>    * testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc:
>    New.
>    * testsuite/performance/23_containers/insert/54075.cc: Add bench using

s/bench/benchmark/

>    the new hash policy.
>    * testsuite/performance/23_containers/insert_erase/41975.cc: Likewise.
>
>Tested under linux x64_86, ok to commit ?
>
>François
>
>

>Index: include/bits/hashtable_policy.h
>===================================================================
>--- include/bits/hashtable_policy.h	(r??vision 235348)
>+++ include/bits/hashtable_policy.h	(copie de travail)
>@@ -457,6 +457,8 @@
>   /// 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 +503,136 @@
>     mutable std::size_t	_M_next_resize;
>   };
> 
>+  /// Range hashing function assuming that second args is a power of 2.

s/args/arg/

>+  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); }
>+  };
>+
>+
>+  /// Helper type to compute next power of 2.
>+  template<typename _SizeT,
>+	   std::size_t _N = sizeof(_SizeT) << 2, bool _Increment = true>
>+    struct _NextPower2
>+    {
>+      static _SizeT
>+      _Get(_SizeT __n)
>+      {
>+	_SizeT __next = _NextPower2<_SizeT, (_N >> 1), false>::_Get(__n);
>+	__next |= __next >> _N;
>+	if (_Increment)
>+	  ++__next;
>+
>+	return __next;
>+      }
>+    };
>+
>+  template<typename _SizeT>
>+    struct _NextPower2<_SizeT, 1, false>
>+    {
>+      static _SizeT
>+      _Get(_SizeT __n)
>+      {
>+	--__n;
>+	return __n |= __n >> 1;
>+      }
>+    };

What's the reason to keep this recursive template instead of using a
simple function like the clp2() we discussed? A simple function (which
could be _GLIBCXX14_CONSTEXPR) compiles faster, and produces similar
object code for the default -std=gnu++14 mode. And it doesn't require
six calls to _NextPower2::_Get to calculate the result.

If you're worried about the final shift being unnecessary on 32-bit
you can use the preprocessor, something like:

  _GLIBCXX14_CONSTEXPR
  std::size_t
  __clp2(std::size_t n)
  {
#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;
  }

I don't think we need to worry about 128-bit integers, because that
would be a ridiculous number of buckets anyway. We can just limit
__max_bkt so we don't have to deal with more than 2^63 buckets.

>+  /// Rehash policy providing power of 2 bucket numbers. Ease modulo

s/Ease/Avoids/

>+  /// 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
>+    {
>+      constexpr auto __max_bkt
>+	= std::size_t(1) << ((sizeof(std::size_t) << 3) - 1);

Should this be sizeof(size_t) * __CHAR_BITS__ instead of << 3 ?
Otherwise targets with char wider than 8 bits would get a smaller
maximum number of buckets, even if they have 64-bit size_t.

So, including the suggestion above to limit it to 2^63, it would be:

     constexpr size_t __max_width = std::min(sizeof(size_t), 8);
     constexpr auto __max_bkt
      = std::size_t(1) << (__max_width * __CHAR_BITS__ - 1);

>+
>+      std::size_t __res = _NextPower2<std::size_t>::_Get(__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(0) - 1;

This can be simplified to size_t(-1), there's no need for arithmetic.

>+      else
>+	_M_next_resize
>+	  = __builtin_floor(__res * (long double)_M_max_load_factor);

Isn't floor() on a positive value identical to the truncation we'd get
by converting to an integer anyway? I suppose it makes it explicit,
and is symmetrical with the ceil() calls, so is OK.


>@@ -775,8 +907,7 @@
> 	   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.

(I'm sure I've said it before, but having 10+ template parameters here
makes me sad).




>Index: src/c++11/hashtable_c++0x.cc
>===================================================================
>--- src/c++11/hashtable_c++0x.cc	(r??vision 235348)
>+++ src/c++11/hashtable_c++0x.cc	(copie de travail)
>@@ -60,8 +60,16 @@
>       = sizeof(__prime_list) / sizeof(unsigned long) - 1;
>     const unsigned long* __next_bkt =
>       std::lower_bound(__prime_list + 5, __prime_list + __n_primes, __n);
>-    _M_next_resize =
>-      __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
>+
>+    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(0) - 1;

This can be simplified as above:

      _M_next_resize = size_t(-1);

>+    else
>+      _M_next_resize =
>+	__builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
>+
>     return *__next_bkt;
>   }
> 

Re: New hashtable power 2 rehash policy

[Jonathan Wakely]

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

I'm making this small change to some comments in hashtable_policy.h

Tested x86_64-linux, committing to trunk.



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

commit c387345f7c68df8812c7909f9187445a79bd5dcb
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Apr 28 11:25:29 2016 +0100

    	* include/bits/hashtable_policy.h (__detail::_Insert_base,
    	__detail::_Insert): Improve comments.

diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 7a2ac92..2c24c19 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -667,7 +667,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   /**
    *  Primary class template _Insert_base.
    *
-   *  insert member functions appropriate to all _Hashtables.
+   *  Defines @c insert member functions appropriate to all _Hashtables.
    */
   template<typename _Key, typename _Value, typename _Alloc,
 	   typename _ExtractKey, typename _Equal,
@@ -769,7 +769,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   /**
    *  Primary class template _Insert.
    *
-   *  Select insert member functions appropriate to _Hashtable policy choices.
+   *  Defines @c insert member functions that depend on _Hashtable policies,
+   *  via partial specializations.
    */
   template<typename _Key, typename _Value, typename _Alloc,
 	   typename _ExtractKey, typename _Equal,

Re: New hashtable power 2 rehash policy

[François Dumont]

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

Le 28/04/2016 12:22, Jonathan Wakely a écrit :
> On 23/04/16 10:27 +0200, François Dumont wrote:
>> Hi
>>
>>    Here is a patch to introduce a new power of 2 based rehash policy. 
>> It enhances performance as it avoids modulo float operations. I have 
>> updated performance benches and here is the result:
>>
> Thanks, now that we're back in stage 1 we can make this change.
>
>
>>
>> 2016-04-22  François Dumont <fdumont@gcc.gnu.org>
>>
>>    * include/bits/hashtable_policy.h
>>    (_Prime_rehash_policy::__has_load_factor): New. Mark rehash policy
>>    having load factor management.
>>    (_Mask_range_hashing): New.
>>    (_NextPower2<size_t>): New.
>>    (_Power2_rehash_policy): New.
>>    (_Inserts<>): Remove last template parameter _Unique_keys. Use the 
>> same
>>    implementation when keys are unique no matter if iterators are 
>> constant
>>    or not.
>
> I found this change description confusing, because it's really using
> the same implementation whether keys are unique or not, but this says
> "Use the same implementation whether iterators are constant or not".
>
> Shouldn't it be "Use the same implementation when iterators are
> constant, no matter if keys are unique or not" ?
>
> Maybe this would be clearer:
>
>    (_Inserts<>): Remove last template parameter, _Unique_keys, so
>    that partial specializations only depend on whether iterators are
>    constant or not.

Yes, sorry, I prepared this patch a long time ago and didn't reconsider 
it in enough details.

>
>> +  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); }
>> +  };
>> +
>> +
>> +  /// Helper type to compute next power of 2.
>> +  template<typename _SizeT,
>> +       std::size_t _N = sizeof(_SizeT) << 2, bool _Increment = true>
>> +    struct _NextPower2
>> +    {
>> +      static _SizeT
>> +      _Get(_SizeT __n)
>> +      {
>> +    _SizeT __next = _NextPower2<_SizeT, (_N >> 1), false>::_Get(__n);
>> +    __next |= __next >> _N;
>> +    if (_Increment)
>> +      ++__next;
>> +
>> +    return __next;
>> +      }
>> +    };
>> +
>> +  template<typename _SizeT>
>> +    struct _NextPower2<_SizeT, 1, false>
>> +    {
>> +      static _SizeT
>> +      _Get(_SizeT __n)
>> +      {
>> +    --__n;
>> +    return __n |= __n >> 1;
>> +      }
>> +    };
>
> What's the reason to keep this recursive template instead of using a
> simple function like the clp2() we discussed? A simple function (which
> could be _GLIBCXX14_CONSTEXPR) compiles faster, and produces similar
> object code for the default -std=gnu++14 mode. And it doesn't require
> six calls to _NextPower2::_Get to calculate the result.

I though we could have a wide variety of std::size_t definition on 
different platforms. If we just need to consider 32/64 bits then it is 
fine. Note that I thought that gcc would optimize away the calls to 
_NextPower2::_Get.

>
> If you're worried about the final shift being unnecessary on 32-bit
> you can use the preprocessor, something like:
>
>  _GLIBCXX14_CONSTEXPR
>  std::size_t
>  __clp2(std::size_t n)
>  {
> #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;
>  }
>
> I don't think we need to worry about 128-bit integers, because that
> would be a ridiculous number of buckets anyway. We can just limit
> __max_bkt so we don't have to deal with more than 2^63 buckets.

Adopted.

>> +  /// 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
>> +    {
>> +      constexpr auto __max_bkt
>> +    = std::size_t(1) << ((sizeof(std::size_t) << 3) - 1);
>
> Should this be sizeof(size_t) * __CHAR_BITS__ instead of << 3 ?
> Otherwise targets with char wider than 8 bits would get a smaller
> maximum number of buckets, even if they have 64-bit size_t.

sizeof() returns number of char elements in the given type ? I thought 
it was the number of bytes and that a byte was always 8 bits. But I know 
that you know your stuff so fixed in the new patch.

>
> So, including the suggestion above to limit it to 2^63, it would be:
>
>     constexpr size_t __max_width = std::min(sizeof(size_t), 8);
>     constexpr auto __max_bkt
>      = std::size_t(1) << (__max_width * __CHAR_BITS__ - 1);

Ok,I just had to introduce a _GLIBCXX14_USE_CONSTEXPR to be able to 
define this expression as constexpr.
>
>> +
>> +      std::size_t __res = _NextPower2<std::size_t>::_Get(__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(0) - 1;
>
> This can be simplified to size_t(-1), there's no need for arithmetic.

This was my mental representation of it, size_t(-1) adopted.

>
>
>> @@ -775,8 +907,7 @@
>>        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.
>
> (I'm sure I've said it before, but having 10+ template parameters here
> makes me sad).

Me too but there are quite some work to reduce it. It would sure be a 
very interesting design change to work on.

I took the time to adapt a number of test case to also cover this new 
hash policy.

New patch attached, tested under linux x86_64.

François


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

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..c030eab 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
+  std::size_t
+  __clp2(std::size_t n)
+  {
+#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
+    {
+      _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
+    { 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
+    {
+      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
+    { return _M_next_resize; }
+
+    void
+    _M_reset() noexcept
+    { _M_next_resize = 0; }
+
+    void
+    _M_reset(_State __state)
+    { _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, _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, _Prime_rehash_policy, _Traits>
+			_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;
 }

Re: New hashtable power 2 rehash policy

[Daniel Krügler]

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.

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

- Daniel

Re: New hashtable power 2 rehash policy

[Jonathan Wakely]

On 14/05/16 18:13 +0200, François Dumont wrote:
>sizeof() returns number of char elements in the given type ? I thought 
>it was the number of bytes and that a byte was always 8 bits. But I 
>know that you know your stuff so fixed in the new patch.

A char is a byte, by definition, so sizeof returns the number of
bytes, which is also the number of chars.

But a byte can have more than 8 bits. The number of bits is given by
the standard macro CHAR_BITS, and the non-standard (but always defined
by GCC) macro __CHAR_BITS__.

Re: New hashtable power 2 rehash policy

[François Dumont]

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

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


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

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;
 }

Re: New hashtable power 2 rehash policy

[Jonathan Wakely]

On 17/05/16 22:28 +0200, François Dumont wrote:
>On 14/05/2016 19:06, Daniel Krügler wrote:
>>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.

That's probably a good idea.

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

OK, thanks.

>>
>>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.

I'm in favour of adding it anywhere that that definitely can't throw.
We don't *need* to do that everywhere, but it doesn't hurt.

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

Great.

>Thanks for feedback, updated and tested patch attached.

OK for trunk - thanks!

Re: New hashtable power 2 rehash policy

[François Dumont]

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

Attached patch applied then.

I had to regorganize things a little now that some pieces have been 
integrated in 71181 patch.

2016-05-24  François Dumont  <fdumont@gcc.gnu.org>

     * include/bits/c++config (_GLIBCXX14_USE_CONSTEXPR): New.
     * include/bits/hashtable_policy.h
     (_Prime_rehash_policy::__has_load_factor): New. Mark rehash policy
     having load factor management.
     (_Mask_range_hashing): New.
     (__clp2): New.
     (_Power2_rehash_policy): New.
     (_Inserts<>): Remove last template parameter, _Unique_keys, so that
     partial specializations only depend on whether iterators are constant
     or not.
     * testsuite/23_containers/unordered_set/hash_policy/26132.cc: Adapt to
     test new hash policy.
     * testsuite/23_containers/unordered_set/hash_policy/load_factor.cc:
     Likewise.
     * testsuite/23_containers/unordered_set/hash_policy/rehash.cc:
     Likewise.
     * testsuite/23_containers/unordered_set/insert/hash_policy.cc:
     Likewise.
     * testsuite/23_containers/unordered_set/max_load_factor/robustness.cc:
     Likewise.
     * testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc:
     New.
     * testsuite/performance/23_containers/insert/54075.cc: Add benchmark
     using the new hash policy.
     * testsuite/performance/23_containers/insert_erase/41975.cc: Likewise.

François

On 23/05/2016 13:31, Jonathan Wakely wrote:
> On 17/05/16 22:28 +0200, François Dumont wrote:
>> On 14/05/2016 19:06, Daniel Krügler wrote:
>>> 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.
>
> That's probably a good idea.
>
>> For the moment I simply added the inline as done in other situations.
>
> OK, thanks.
>
>>>
>>> 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.
>
> I'm in favour of adding it anywhere that that definitely can't throw.
> We don't *need* to do that everywhere, but it doesn't hurt.
>
>> For the moment I have added it on all those methods.
>
> Great.
>
>> Thanks for feedback, updated and tested patch attached.
>
> OK for trunk - thanks!
>
>


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

Index: include/bits/c++config
===================================================================
--- include/bits/c++config	(revision 236662)
+++ include/bits/c++config	(working copy)
@@ -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
 
Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h	(revision 236662)
+++ include/bits/hashtable_policy.h	(working copy)
@@ -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 @@
   /// 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,135 @@
     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 == __n)
+	__res <<= 1;
+
+      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 +909,7 @@
 	   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,7 +918,7 @@
 	   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>
     {
@@ -793,58 +925,23 @@
       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 __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
+					       _Equal, _H1, _H2, _Hash,
+					       _Traits>;
 
-      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,
-					_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 __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 +963,9 @@
   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 +1009,46 @@
 	}
    };
 
+  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 +1061,7 @@
       max_load_factor(float __z)
       {
 	__hashtable* __this = static_cast<__hashtable*>(this);
-	__this->__rehash_policy(_Prime_rehash_policy(__z));
+	__this->__rehash_policy(_RehashPolicy(__z));
       }
 
       void
Index: testsuite/23_containers/unordered_set/hash_policy/26132.cc
===================================================================
--- testsuite/23_containers/unordered_set/hash_policy/26132.cc	(revision 236662)
+++ testsuite/23_containers/unordered_set/hash_policy/26132.cc	(working copy)
@@ -23,35 +23,48 @@
 #include <testsuite_hooks.h>
 
 // libstdc++/26132
-void test01()
-{
-  bool test __attribute__((unused)) = true;
+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;
-	
-	us1.max_load_factor(10.0);
+    for (float lf = 1.0; lf < 101.0; lf *= 10.0)
+      for (int size = 1; size <= 6561; size *= 3)
+	{
+	  _USet us1;
+	  typedef typename _USet::size_type size_type;
 
-	for (int i = 0; i < size; ++i)
-	  us1.insert(i);
+	  us1.max_load_factor(10.0);
 
-	us1.max_load_factor(lf);
+	  for (int i = 0; i < size; ++i)
+	    us1.insert(i);
 
-	for (int i = 1; i <= 6561; i *= 81)
-	  {
-	    const size_type n = size * 81 / i;
-	    us1.rehash(n);
-	    VERIFY( us1.bucket_count() > us1.size() / us1.max_load_factor() );
-	    VERIFY( us1.bucket_count() >= n );
-	  }
-      }
-}
+	  us1.max_load_factor(lf);
 
+	  for (int i = 1; i <= 6561; i *= 81)
+	    {
+	      const size_type n = size * 81 / i;
+	      us1.rehash(n);
+	      VERIFY( us1.bucket_count() > us1.size() / us1.max_load_factor() );
+	      VERIFY( us1.bucket_count() >= n );
+	    }
+	}
+  }
+
+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;
 }
Index: testsuite/23_containers/unordered_set/hash_policy/load_factor.cc
===================================================================
--- testsuite/23_containers/unordered_set/hash_policy/load_factor.cc	(revision 236662)
+++ testsuite/23_containers/unordered_set/hash_policy/load_factor.cc	(working copy)
@@ -18,41 +18,55 @@
 // { dg-options "-std=gnu++11" }
 
 #include <unordered_set>
+
 #include <testsuite_hooks.h>
 
-void test01()
-{
-  bool test __attribute__((unused)) = true;
+template<typename _USet>
+  void test()
   {
-    std::unordered_set<int> us;
-    for (int i = 0; i != 100000; ++i)
+    bool test __attribute__((unused)) = true;
     {
-      us.insert(i);
-      VERIFY( us.load_factor() <= us.max_load_factor() );
+      _USet us;
+      for (int i = 0; i != 100000; ++i)
+	{
+	  us.insert(i);
+	  VERIFY( us.load_factor() <= us.max_load_factor() );
+	}
     }
-  }
-  {
-    std::unordered_set<int> us;
-    us.max_load_factor(3.f);
-    for (int i = 0; i != 100000; ++i)
     {
-      us.insert(i);
-      VERIFY( us.load_factor() <= us.max_load_factor() );
+      _USet us;
+      us.max_load_factor(3.f);
+      for (int i = 0; i != 100000; ++i)
+	{
+	  us.insert(i);
+	  VERIFY( us.load_factor() <= us.max_load_factor() );
+	}
     }
-  }
-  {
-    std::unordered_set<int> us;
-    us.max_load_factor(.3f);
-    for (int i = 0; i != 100000; ++i)
     {
-      us.insert(i);
-      VERIFY( us.load_factor() <= us.max_load_factor() );
+      _USet us;
+      us.max_load_factor(.3f);
+      for (int i = 0; i != 100000; ++i)
+	{
+	  us.insert(i);
+	  VERIFY( us.load_factor() <= us.max_load_factor() );
+	}
     }
   }
-}
 
+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;
 }
Index: testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc
===================================================================
--- testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc	(nonexistent)
+++ testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc	(working copy)
@@ -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) == 2 );
+  VERIFY( policy._M_next_bkt(2) == 4 );
+  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;
+}
Index: testsuite/23_containers/unordered_set/hash_policy/rehash.cc
===================================================================
--- testsuite/23_containers/unordered_set/hash_policy/rehash.cc	(revision 236662)
+++ testsuite/23_containers/unordered_set/hash_policy/rehash.cc	(working copy)
@@ -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 @@
   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;
 }
Index: testsuite/23_containers/unordered_set/insert/hash_policy.cc
===================================================================
--- testsuite/23_containers/unordered_set/insert/hash_policy.cc	(revision 236662)
+++ testsuite/23_containers/unordered_set/insert/hash_policy.cc	(working copy)
@@ -20,94 +20,122 @@
 #include <unordered_set>
 #include <vector>
 #include <limits>
+
 #include <ext/throw_allocator.h>
+
 #include <testsuite_hooks.h>
 
-void test01()
-{
-  bool test __attribute__((unused)) = true;
+template<template<typename _Value, typename _Hash,
+		  typename _Pred, typename _Alloc>
+	   typename _USet>
+  void test01()
+  {
+    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>,
-		     __gnu_cxx::throw_allocator_limit<int> > us;
-  const int nb = 100;
-  int scheduled_throw_counter = 0;
-  std::size_t thrown_exceptions = 0;
-  for (int i = 0; i != nb; ++i)
-    {
-      if ((float)(us.size() + 1)
-	  / (float)us.bucket_count() >= us.max_load_factor())
-	{
-	  // We are going to need a rehash, lets introduce allocation issues:
-	  __gnu_cxx::limit_condition::set_limit(scheduled_throw_counter++);
-	}
-      try
-	{
-	  VERIFY(us.insert(i).second);
-	  scheduled_throw_counter = 0;
-	}
-      catch (const __gnu_cxx::forced_error&)
-	{
-	  ++thrown_exceptions;
-	  --i;
-	}
-      VERIFY( us.load_factor() <= us.max_load_factor() );
-      __gnu_cxx::limit_condition::set_limit(nl_size_t::max());
-    }
+    // Make sure whatever happen we restore throw allocator limit at exit.
+    __gnu_cxx::limit_condition::adjustor_base adj;
 
-  VERIFY( thrown_exceptions != 0 );
-  // Check that all values have been inserted:
-  for (int i = 0; i != nb; ++i)
-    {
-      VERIFY( us.count(i) == 1 );
-    }
-}
+    typedef std::numeric_limits<std::size_t> nl_size_t;
+    _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;
+    std::size_t thrown_exceptions = 0;
+    for (int i = 0; i != nb; ++i)
+      {
+	if ((float)(us.size() + 1)
+	    / (float)us.bucket_count() >= us.max_load_factor())
+	  {
+	    // We are going to need a rehash, lets introduce allocation issues:
+	    __gnu_cxx::limit_condition::set_limit(scheduled_throw_counter++);
+	  }
+	try
+	  {
+	    VERIFY(us.insert(i).second);
+	    scheduled_throw_counter = 0;
+	  }
+	catch (const __gnu_cxx::forced_error&)
+	  {
+	    ++thrown_exceptions;
+	    --i;
+	  }
+	VERIFY( us.load_factor() <= us.max_load_factor() );
+	__gnu_cxx::limit_condition::set_limit(nl_size_t::max());
+      }
 
-void test02()
-{
-  bool test __attribute__((unused)) = true;
+    VERIFY( thrown_exceptions != 0 );
+    // Check that all values have been inserted:
+    for (int i = 0; i != nb; ++i)
+      {
+	VERIFY( us.count(i) == 1 );
+      }
+  }
 
-  typedef std::numeric_limits<std::size_t> nl_size_t;
-  std::unordered_set<int, std::hash<int>, std::equal_to<int>,
-		     __gnu_cxx::throw_allocator_limit<int> > us;
-  const int nb = 100;
-  int scheduled_throw_counter = 0;
-  std::size_t thrown_exceptions = 0;
-  for (int i = 0; i != nb; ++i)
-    {
-      if ((float)(us.size() + 2)
-	  / (float)us.bucket_count() >= us.max_load_factor())
-	{
-	  // We are going to need a rehash, lets introduce allocation issues:
-	  __gnu_cxx::limit_condition::set_limit(scheduled_throw_counter++);
-	}
-      try
-	{
-	  std::vector<int> v = { i, i };
-	  // Check the insert range robustness
-	  us.insert(v.begin(), v.end());
-	  scheduled_throw_counter = 0;
-	}
-      catch (const __gnu_cxx::forced_error&)
-	{
-	  ++thrown_exceptions;
-	  --i;
-	}
-      VERIFY( us.load_factor() <= us.max_load_factor() );
-      __gnu_cxx::limit_condition::set_limit(nl_size_t::max());
-    }
+template<template<typename _Value, typename _Hash,
+		  typename _Pred, typename _Alloc>
+	   typename _USet>
+  void test02()
+  {
+    bool test __attribute__((unused)) = true;
 
-  VERIFY( thrown_exceptions != 0 );
-  // Check that all values have been inserted:
-  for (int i = 0; i != nb; ++i)
-    {
-      VERIFY( us.count(i) == 1 );
-    }
-}
+    // 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;
+    _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;
+    std::size_t thrown_exceptions = 0;
+    for (int i = 0; i != nb; ++i)
+      {
+	if ((float)(us.size() + 2)
+	    / (float)us.bucket_count() >= us.max_load_factor())
+	  {
+	    // We are going to need a rehash, lets introduce allocation issues:
+	    __gnu_cxx::limit_condition::set_limit(scheduled_throw_counter++);
+	  }
+	try
+	  {
+	    std::vector<int> v = { i, i };
+	    // Check the insert range robustness
+	    us.insert(v.begin(), v.end());
+	    scheduled_throw_counter = 0;
+	  }
+	catch (const __gnu_cxx::forced_error&)
+	  {
+	    ++thrown_exceptions;
+	    --i;
+	  }
+	VERIFY( us.load_factor() <= us.max_load_factor() );
+	__gnu_cxx::limit_condition::set_limit(nl_size_t::max());
+      }
+
+    VERIFY( thrown_exceptions != 0 );
+    // Check that all values have been inserted:
+    for (int i = 0; i != nb; ++i)
+      {
+	VERIFY( us.count(i) == 1 );
+      }
+  }
+
+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;
 }
Index: testsuite/23_containers/unordered_set/max_load_factor/robustness.cc
===================================================================
--- testsuite/23_containers/unordered_set/max_load_factor/robustness.cc	(revision 236662)
+++ testsuite/23_containers/unordered_set/max_load_factor/robustness.cc	(working copy)
@@ -22,62 +22,78 @@
 #include <ext/throw_allocator.h>
 #include <testsuite_hooks.h>
 
-void test01()
-{
-  bool test __attribute__((unused)) = true;
+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>,
-		     __gnu_cxx::throw_allocator_limit<int> > us;
-  int val = 0;
-  for (; val != 100; ++val)
-    {
-      VERIFY( us.insert(val).second );
-      VERIFY( us.load_factor() <= us.max_load_factor() );
-    }
+    typedef std::numeric_limits<std::size_t> nl_size_t;
+    _USet<int, std::hash<int>, std::equal_to<int>,
+	  __gnu_cxx::throw_allocator_limit<int> > us;
+    int val = 0;
+    for (; val != 100; ++val)
+      {
+	VERIFY( us.insert(val).second );
+	VERIFY( us.load_factor() <= us.max_load_factor() );
+      }
 
-  float cur_max_load_factor = us.max_load_factor();
-  int counter = 0;
-  std::size_t thrown_exceptions = 0;
+    float cur_max_load_factor = us.max_load_factor();
+    int counter = 0;
+    std::size_t thrown_exceptions = 0;
 
-  // Reduce max load factor.
-  us.max_load_factor(us.max_load_factor() / 2);
+    // Reduce max load factor.
+    us.max_load_factor(us.max_load_factor() / 4);
 
-  // At this point load factor is higher than max_load_factor because we can't
-  // rehash in max_load_factor call.
-  VERIFY( us.load_factor() > us.max_load_factor() );
+    // At this point load factor is higher than max_load_factor because we can't
+    // rehash in max_load_factor call.
+    VERIFY( us.load_factor() > us.max_load_factor() );
 
-  while (true)
-    {
-      __gnu_cxx::limit_condition::set_limit(counter++);
-      bool do_break = false;
-      try
-	{
-	  size_t nbkts = us.bucket_count();
-	  // Check that unordered_set will still be correctly resized when
-	  // needed.
-	  VERIFY( us.insert(val++).second );
+    while (true)
+      {
+	__gnu_cxx::limit_condition::limit_adjustor adjustor(counter++);
+	bool do_break = false;
+	try
+	  {
+	    size_t nbkts = us.bucket_count();
+	    // Check that unordered_set will still be correctly resized when
+	    // needed.
+	    VERIFY( us.insert(val++).second );
+	    VERIFY( us.bucket_count() != nbkts );
+	    VERIFY( us.load_factor() <= us.max_load_factor() );
+	    do_break = true;
+	  }
+	catch (const __gnu_cxx::forced_error&)
+	  {
+	    // max load factor doesn't change.
+	    VERIFY( us.max_load_factor() == .25f );
+	    ++thrown_exceptions;
+	  }
 
-	  VERIFY( us.bucket_count() != nbkts );
-	  VERIFY( us.load_factor() <= us.max_load_factor() );
-	  do_break = true;
-	}
-      catch (const __gnu_cxx::forced_error&)
-	{
-	  // max load factor doesn't change.
-	  VERIFY( us.max_load_factor() == .5f );
-	  ++thrown_exceptions;
-	}
+	if (do_break)
+	  break;
+      }
 
-      if (do_break)
-	break;
-    }
+    VERIFY( thrown_exceptions > 0 );
+  }
 
-  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;
 }
Index: testsuite/performance/23_containers/insert/54075.cc
===================================================================
--- testsuite/performance/23_containers/insert/54075.cc	(revision 236662)
+++ testsuite/performance/23_containers/insert/54075.cc	(working copy)
@@ -127,8 +127,28 @@
   using __umset = std::__umset_hashtable<Foo, HashFunction,
 					 std::equal_to<Foo>,
 					 std::allocator<Foo>,
-					 std::__uset_traits<cache>>;
+					 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 @@
   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>>(
Index: testsuite/performance/23_containers/insert_erase/41975.cc
===================================================================
--- testsuite/performance/23_containers/insert_erase/41975.cc	(revision 236662)
+++ testsuite/performance/23_containers/insert_erase/41975.cc	(working copy)
@@ -177,6 +177,16 @@
 					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 @@
 					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 @@
 	"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>>(
@@ -210,7 +234,11 @@
 	"std::unordered_set<string> without hash code cached");
   bench_str<__str_uset<true>>(
 	"std::unordered_set<string> with hash code cached");
-    bench_str<std::unordered_set<std::string>>(
+  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;
 }

Re: New hashtable power 2 rehash policy

[Andreas Schwab]

François Dumont <frs.dumont@gmail.com> writes:

>     * include/bits/c++config (_GLIBCXX14_USE_CONSTEXPR): New.

FAIL: ext/profile/mutex_extensions_neg.cc  (test for errors, line 324)
FAIL: ext/profile/mutex_extensions_neg.cc (test for excess errors)
Excess errors:
/usr/local/gcc/gcc-20160525/Build/ia64-suse-linux/libstdc++-v3/include/ia64-suse-linux/bits/c++config.h:326:4: error: #error illegal use of multiple inlined namespaces

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: New hashtable power 2 rehash policy

[Jonathan Wakely]

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

On 25/05/16 10:15 +0200, Andreas Schwab wrote:
>François Dumont <frs.dumont@gmail.com> writes:
>
>>     * include/bits/c++config (_GLIBCXX14_USE_CONSTEXPR): New.
>
>FAIL: ext/profile/mutex_extensions_neg.cc  (test for errors, line 324)
>FAIL: ext/profile/mutex_extensions_neg.cc (test for excess errors)
>Excess errors:
>/usr/local/gcc/gcc-20160525/Build/ia64-suse-linux/libstdc++-v3/include/ia64-suse-linux/bits/c++config.h:326:4: error: #error illegal use of multiple inlined namespaces

Fixed with this patch (we don't need the new macro anyway, so it can
be simply removed).

The mutable specifier on _Power2_rehash_policy::_M_next_bkt is also
unnecessary, because the member functions that change it don't need to
be const. It's best to avoid mutable wherever possible, since in
general modifying member data in const functions leads to data races.
In this case it doesn't, because the const member functions are only
called on non-const objects, so the functions don't need to be const.

I'll commit to trunk when testing finishes.



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

commit 327e9529040b5c044339e168e5577e1c3d3d4934
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Wed May 25 09:43:00 2016 +0100

    Remove _GLIBCXX14_USE_CONSTEXPR
    
    	* include/bits/c++config (_GLIBCXX14_USE_CONSTEXPR): Remove it.
    	* include/bits/hashtable_policy.h (_Power2_rehash_policy::_M_next_bkt):
    	Remove const qualification on function. Replace
    	_GLIBCXX14_USE_CONSTEXPR on automatic variables with const.
    	(_Power2_rehash_policy::_M_need_rehash): Remove const qualification.
    	(_Power2_rehash_policy::_M_next_bkt): Remove mutable specifier.

diff --git a/libstdc++-v3/include/bits/c++config b/libstdc++-v3/include/bits/c++config
index 78353ae..57024e4 100644
--- a/libstdc++-v3/include/bits/c++config
+++ b/libstdc++-v3/include/bits/c++config
@@ -106,10 +106,8 @@
 #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 0b317c3..759d0ca 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -557,13 +557,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     // 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
+    _M_next_bkt(std::size_t __n) 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);
-
+      const auto __max_width = std::min<size_t>(sizeof(size_t), 8);
+      const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1);
       std::size_t __res = __clp2(__n);
 
       if (__res == __n)
@@ -595,7 +592,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     // 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
+		   std::size_t __n_ins) noexcept
     {
       if (__n_elt + __n_ins >= _M_next_resize)
 	{
@@ -630,8 +627,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
     static const std::size_t _S_growth_factor = 2;
 
-    float		_M_max_load_factor;
-    mutable std::size_t	_M_next_resize;
+    float	_M_max_load_factor;
+    std::size_t	_M_next_resize;
   };
 
   // Base classes for std::_Hashtable.  We define these base classes