libstdc++/90277 Review rehash policy

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

Hi

    This is a patch I already proposed in another thread but I review 
it and moreover there is now a PR associated so I am submitting it as a 
brand new one.

    So working on PR 68303 I noticed that one of the performance issue 
of current implementation is that initial sizing of buckets is small. In 
tr1 implementation we were starting at 11 but now we go through 2, 3, 5, 
7 and eventually 11, a lot of intermediate reallocation/rehash. It can 
be considered as a fix for PR 90277 cause when initial bucket count is 
11 there is no rehash anymore during those tests.

    Compared to initial submission this version has the refinement that 
if the user explicitly set initial bucket count we respect it and do not 
jump to 11.

    Additionally this patch extend the PR 87135 fix to the power of 2 
rehash policy alternative and it adopts the long double versions of 
builtin ceil/floor as advised in another message thread.

    Last I realized that _Hashtable<>::reserve could leverage on rehash 
policy _M_bkt_for_elements rather than trying to compute it itself, it 
brings more consistency in the container behavior.

    * include/bits/hashtable.h (_Hashtable<>::rehash): Review comment.
    * include/bits/hashtable_policy.h
    (_Prime_rehash_policy::_M_bkt_for_elements): Use __builtin_ceill.
    (_Power2_rehash_policy::_M_bkt_for_elements): Likewise.
    (_Power2_rehash_policy::_M_next_bkt): Enforce returning a result not
    smaller than input value rather than always greater. Preserve
    _M_next_resize if called with 0 input. Use __builtin_floorl.
    (_Power2_rehash_policy::_M_need_rehash): Rehash only if number of
    elements + number of insertions is greater than _M_next_resize. Start
    with 11 buckets if not told otherwise. Use __builtin_floorl.
    (_Rehash_base<>::reserve): Use rehash policy _M_bkt_for_elements.
    * src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
    Preserve _M_next_resize if called with 0 input. Use __builtin_floorl.
    (_Prime_rehash_policy::_M_need_rehash): Start with 11 buckets if not
    told otherwise. Use __builtin_floorl.
    * testsuite/23_containers/unordered_set/hash_policy/71181.cc: Adapt 
test
    to also validate _Power2_rehash_policy.
    * testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc:
    Adapt.

Tested under Linux x86_64 normal and debug modes.

Ok to commit ?

François


diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index da78c68434f..2e8aeb7e4d4 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -2055,7 +2055,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (__buckets != _M_bucket_count)
 	_M_rehash(__buckets, __saved_state);
       else
-	// No rehash, restore previous state to keep a consistent state.
+	// No rehash, restore previous state to keep it consistent with
+	// container state.
 	_M_rehash_policy._M_reset(__saved_state);
     }
 
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index b38e8e0ecef..c7f466cd686 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -460,7 +460,7 @@ namespace __detail
     // 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); }
+    { return __builtin_ceill(__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
@@ -535,24 +535,32 @@ namespace __detail
     std::size_t
     _M_next_bkt(std::size_t __n) noexcept
     {
+      if (__n == 0)
+	// Special case on container 1st initialization with 0 bucket count
+	// hint. We keep _M_next_resize to 0 to make sure that next time we
+	// want to add an element allocation will take place.
+	return 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)
-	__res <<= 1;
-
       if (__res == 0)
 	__res = __max_bkt;
+      else if (__res == 1)
+	// If __res is 1 we force it to 2 to make sure there will be an
+	// allocation so that nothing need to be stored in the initial
+	// single bucket
+	__res = 2;
 
       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);
+	_M_next_resize = numeric_limits<size_t>::max();
       else
 	_M_next_resize
-	  = __builtin_ceil(__res * (long double)_M_max_load_factor);
+	  = __builtin_floorl(__res * (long double)_M_max_load_factor);
 
       return __res;
     }
@@ -560,7 +568,7 @@ namespace __detail
     // 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); }
+    { return __builtin_ceill(__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
@@ -570,21 +578,25 @@ namespace __detail
     _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
 		   std::size_t __n_ins) noexcept
     {
-      if (__n_elt + __n_ins >= _M_next_resize)
+      if (__n_elt + __n_ins > _M_next_resize)
 	{
-	  long double __min_bkts = (__n_elt + __n_ins)
-					/ (long double)_M_max_load_factor;
+	  // If _M_next_resize is 0 it means that we have nothing allocated so
+	  // far and that we start inserting elements. In this case we start
+	  // with an initial bucket size of 11.
+	  long double __min_bkts
+	    = std::max<std::size_t>(__n_elt + __n_ins, _M_next_resize ? 0 : 11)
+	      / (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)));
+	    return { true,
+	      _M_next_bkt(std::max<std::size_t>(__builtin_floorl(__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);
+	    = __builtin_floorl(__n_bkt * (long double)_M_max_load_factor);
+	  return { false, 0 };
 	}
       else
-	return std::make_pair(false, 0);
+	return { false, 0 };
     }
 
     typedef std::size_t _State;
@@ -1074,7 +1086,7 @@ namespace __detail
       reserve(std::size_t __n)
       {
 	__hashtable* __this = static_cast<__hashtable*>(this);
-	__this->rehash(__builtin_ceil(__n / max_load_factor()));
+	__this->rehash(__this->__rehash_policy()._M_bkt_for_elements(__n));
       }
     };
 
diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
index 47c609d1800..de437d00b56 100644
--- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc
+++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
@@ -51,8 +51,14 @@ namespace __detail
 
     if (__n < sizeof(__fast_bkt))
       {
+	if (__n == 0)
+	  // Special case on container 1st initialization with 0 bucket count
+	  // hint. We keep _M_next_resize to 0 to make sure that next time we
+	  // want to add an element allocation will take place.
+	  return 1;
+
 	_M_next_resize =
-	  __builtin_floor(__fast_bkt[__n] * (long double)_M_max_load_factor);
+	  __builtin_floorl(__fast_bkt[__n] * (long double)_M_max_load_factor);
 	return __fast_bkt[__n];
       }
 
@@ -72,10 +78,10 @@ namespace __detail
       // 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);
+      _M_next_resize = numeric_limits<size_t>::max();
     else
       _M_next_resize =
-	__builtin_floor(*__next_bkt * (long double)_M_max_load_factor);
+	__builtin_floorl(*__next_bkt * (long double)_M_max_load_factor);
 
     return *__next_bkt;
   }
@@ -96,19 +102,23 @@ namespace __detail
   {
     if (__n_elt + __n_ins > _M_next_resize)
       {
-	long double __min_bkts = (__n_elt + __n_ins)
-				   / (long double)_M_max_load_factor;
+	// If _M_next_resize is 0 it means that we have nothing allocated so
+	// far and that we start inserting elements. In this case we start
+	// with an initial bucket size of 11.
+	long double __min_bkts
+	  = std::max<std::size_t>(__n_elt + __n_ins, _M_next_resize ? 0 : 11)
+	  / (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)));
+	  return { true,
+	    _M_next_bkt(std::max<std::size_t>(__builtin_floorl(__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);
+	  = __builtin_floorl(__n_bkt * (long double)_M_max_load_factor);
+	return { false, 0 };
       }
     else
-      return std::make_pair(false, 0);
+      return { false, 0 };
   }
 } // namespace __detail
 
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc
index 6e38eba2c2c..7bbf4fd73db 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc
@@ -22,22 +22,22 @@
 #include <testsuite_hooks.h>
 
 template<typename _USet>
-  void test(int threshold)
+  void
+  test(_USet& us, int threshold)
   {
-    _USet us;
     auto nb_reserved = us.bucket_count();
     us.reserve(nb_reserved);
     auto bkts = us.bucket_count();
-    for (int i = 0; i != threshold; ++i)
+    for (int nb_insert = 1; nb_insert <= threshold; ++nb_insert)
       {
-	if (i >= nb_reserved)
+	if (nb_insert > nb_reserved)
 	  {
 	    nb_reserved = bkts;
 	    us.reserve(nb_reserved);
 	    bkts = us.bucket_count();
 	  }
 
-	us.insert(i);
+	us.insert(nb_insert);
 
 	VERIFY( us.bucket_count() == bkts );
       }
@@ -54,9 +54,22 @@ template<typename _Value>
 		  std::__detail::_Power2_rehash_policy,
 		  std::__detail::_Hashtable_traits<false, true, true>>;
 
+template<typename _USet>
+  void
+  test_cont()
+  {
+    _USet us;
+    test(us, 150);
+
+    us.clear();
+    us.rehash(0);
+
+    test(us, 150);
+  }
+
 int main()
 {
-  test<std::unordered_set<int>>(150);
-  test<unordered_set_power2_rehash<int>>(150);
+  test_cont<std::unordered_set<int>>();
+  test_cont<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
index 58ed268ee4c..5e42485b977 100644
--- 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
@@ -26,9 +26,10 @@ void test01()
 {
   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(2) == 2 );
   VERIFY( policy._M_next_bkt(3) == 4 );
   VERIFY( policy._M_next_bkt(5) == 8 );
+  VERIFY( policy._M_next_bkt(16) == 16 );
   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)) );
@@ -38,20 +39,20 @@ void test02()
 {
   std::__detail::_Power2_rehash_policy policy;
 
-  for (std::size_t i = 1;;)
+  for (std::size_t i = 3;;)
     {
       auto nxt = policy._M_next_bkt(i);
 
-      if (nxt == i)
+      if (nxt <= i)
 	{
-	  // Equals only when reaching max.
+	  // Lower or equal only when reaching max.
 	  constexpr auto mx = std::numeric_limits<std::size_t>::max();
 	  VERIFY( nxt == policy._M_next_bkt(mx) );
 	  break;
 	}
 
-      VERIFY( nxt > i );
-      i = nxt;
+      VERIFY( nxt >= i );
+      i = nxt + 1;
     }
 }