Re: PR 51386

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

Hi

    The issue was on the hash policy, the result was that when max load 
factor was lower than 1 the hashtable keeps on being rehashed on each 
insertion, rather bad for performance. I took this opportunity to review 
a little bit the _M_next_bkt implementation and to add comments.

    Tested under linux x86_64, load_factor test is much faster now.

2011-12-05  François Dumont <fdumont@gcc.gnu.org>

        PR 51386
        * include/bits/hashtable_policy.h 
(_Prime_rehash_policy::_M_next_bkt):
        Fix computation of _M_prev_resize so that hashtable do not keep on
        being rehashed when _M_max_load_factor is lower than 1.

Ok to commit ?

François


On 12/04/2011 11:44 AM, Paolo Carlini wrote:
> Hi,
>
> just wanted to make sure you noticed the messages from Bugzilla about 
> this PR:
>
>     http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51386
>
> The issue seems rather urgent.
>
> Thanks,
> Paolo.

Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h	(revision 181975)
+++ include/bits/hashtable_policy.h	(working copy)
@@ -298,25 +298,34 @@
   _Prime_rehash_policy::
   _M_next_bkt(std::size_t __n) const
   {
-    // Optimize lookups involving the first elements of __prime_list.
-    // (useful to speed-up, eg, constructors)
-    static const unsigned long __fast_bkt[12]
-      = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
+    // Optimize lookups involving the first elements of __prime_list (useful to
+    // speed-up, eg, constructors). The contained values are already containing
+    // a minimal grow step.
+    static const unsigned char __fast_bkt[12]
+      = { 2, 3, 5, 7, 7, 11, 11, 11, 13, 13, 17, 17 };
 
+    if (__n <= 11)
+      {
+	_M_prev_resize = 0;
+	_M_next_resize
+	  = __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor);
+	return __fast_bkt[__n];
+      }
+
     const unsigned long* __p
-      = __n <= 11 ? __fast_bkt + __n
-		  : std::lower_bound(__prime_list + 5,
-				     __prime_list + _S_n_primes, __n);
+      = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, __n);
 
-    _M_prev_resize = __builtin_floor(*__p * (long double)_M_max_load_factor);
-    if (__p != __fast_bkt)
-      _M_prev_resize = std::min(_M_prev_resize,
-				static_cast<std::size_t>(*(__p - 1)));
-    // Lets guaranty a minimal grow step of 11:
+    // Shrink will take place only if the number of elements is small enough
+    // so that the prime number 2 steps before __p is large enough to still
+    // conform to the max load factor:
+    _M_prev_resize
+      = __builtin_floor(*(__p - 2) * (long double)_M_max_load_factor);
+
+    // Lets guaranty a minimal grow step of 11 used only when working in the
+    // range of small prime numbers
     if (*__p - __n < 11)
-      __p = std::lower_bound(__prime_list + 5,
-			     __prime_list + _S_n_primes, __n + 11);
-    _M_next_resize = __builtin_floor(*__p * (long double)_M_max_load_factor);
+      __p = std::lower_bound(__p, __prime_list + _S_n_primes, __n + 11);
+    _M_next_resize = __builtin_ceil(*__p * (long double)_M_max_load_factor);
     return *__p;
   }