This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: PR 51386
- From: François Dumont <frs dot dumont at gmail dot com>
- To: Paolo Carlini <paolo dot carlini at oracle dot com>
- Cc: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches at gcc dot gnu dot org
- Date: Wed, 07 Dec 2011 20:48:37 +0100
- Subject: Re: PR 51386
- References: <4EDB4F03.5050107@oracle.com> <4EDD2DAE.70507@gmail.com> <4EDD3413.9000602@oracle.com> <4EDDCCB8.6080601@gmail.com> <4EDF3E2F.8060201@oracle.com>
Attached patch applied:
2011-12-07 François Dumont <fdumont@gcc.gnu.org>
PR libstdc++/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.
François
On 12/07/2011 11:21 AM, Paolo Carlini wrote:
Hi,
Ok to commit ?
Yes, thanks a lot for handling this. Please remember to add a proper
header to the ChangeLog entry.
Thanks again,
Paolo.
Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h (revision 181975)
+++ include/bits/hashtable_policy.h (working copy)
@@ -300,23 +300,30 @@
{
// Optimize lookups involving the first elements of __prime_list.
// (useful to speed-up, eg, constructors)
- static const unsigned long __fast_bkt[12]
+ static const unsigned char __fast_bkt[12]
= { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
+ 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);
+
+ // Let's guaranty that a minimal grow step of 11 is used
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;
}