Re: PR 71181 Avoid rehash after reserve

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

On 25/05/2016 16:01, Jonathan Wakely wrote:
> On 22/05/16 17:16 +0200, François Dumont wrote:
> > Hi
> >
> >    To fix 71181 problem I propose to change how we deal with reserve 
> > called with pivot values that is to say prime numbers. Now 
> > _M_next_bkt always return a value higher than the input value. This 
> > way when reverse(97) is called we end up with 199 buckets and so 
> > enough space to store 97 values without rehashing.
> >
> >    I have integrated in this patch several other enhancements on the 
> > same subject. Improvement of _M_next_resize management when reaching 
> > highest bucket number. Remove sentinel value in __prime_list, just 
> > need to limit range when calling lower_bound.
>
> I don't think the change to __prime_list is safe. If you compile some
> code with GCC 5 and then used a libstdc++.so with this change the old
> code would still be looking for the sentinel in the array, and would
> not find it.
>
> I think it would be safe to leave the old __prime_list unchanged (and
> then not need to change anything in tr1/hashtable_policy.h?) and add a
> new array with a different name. Existing code compiled with older
> versions of GCC would still find __prime_list, but the new code would
> use a different array.

    What about this version ? tr1 mode still limit search range as it 
should to make sure it doesn't need to check lower_bound result. And 
sentinel is only kept for backward compatibility and commented to make 
that clear. Maybe there is a clearer way to express that sentinel can be 
removed on a future version breaking abi ?

François

diff --git a/libstdc++-v3/include/tr1/hashtable_policy.h b/libstdc++-v3/include/tr1/hashtable_policy.h
index 4ee6d45..2f70289 100644
--- a/libstdc++-v3/include/tr1/hashtable_policy.h
+++ b/libstdc++-v3/include/tr1/hashtable_policy.h
@@ -403,7 +403,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
 		   std::size_t __n_ins) const;
 
-    enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
+    // Number of primes minus 1 to avoid check on lower_bound result.
+    enum { _S_n_primes = (sizeof(unsigned long) != 8 ? 256 : 256 + 48) - 1 };
 
     float                _M_max_load_factor;
     float                _M_growth_factor;
diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
index a5e6520..dc0dab5 100644
--- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc
+++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
@@ -46,10 +46,10 @@ namespace __detail
   {
     // Optimize lookups involving the first elements of __prime_list.
     // (useful to speed-up, eg, constructors)
-    static const unsigned char __fast_bkt[12]
-      = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
+    static const unsigned char __fast_bkt[13]
+      = { 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 };
 
-    if (__n <= 11)
+    if (__n <= 12)
       {
 	_M_next_resize =
 	  __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor);
@@ -58,10 +58,22 @@ namespace __detail
 
     constexpr auto __n_primes
       = sizeof(__prime_list) / sizeof(unsigned long) - 1;
+    constexpr auto __prime_list_end = __prime_list + __n_primes;
     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);
+      std::lower_bound(__prime_list + 6, __prime_list_end, __n);
+
+    if (*__next_bkt == __n && __next_bkt != __prime_list_end)
+      ++__next_bkt;
+
+    if (__next_bkt == __prime_list_end)
+      // 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/src/shared/hashtable-aux.cc b/libstdc++-v3/src/shared/hashtable-aux.cc
index 081bb12..9cbca98 100644
--- a/libstdc++-v3/src/shared/hashtable-aux.cc
+++ b/libstdc++-v3/src/shared/hashtable-aux.cc
@@ -25,6 +25,7 @@
 namespace __detail
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
+  // The sentinel value is only kept for backward compatibility.
   extern const unsigned long __prime_list[] = // 256 + 1 or 256 + 48 + 1
   {
     2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,