Re: PR 51386

[Paolo Carlini <paolo dot carlini at oracle dot com>]

Hi,

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

How much, exactly?

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

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.
>
> Ok to commit ?

The whole patch doesn't really look self-explaining, but I'm willing to 
largely trust you ;) Please improve a bit the English in the comments:

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

I would say "The values already include a minimal grow step" and avoid 
the repetition. But to be honest, I don't like much that the numbers are 
not the same numbers as in __prime_list. This should be *purely* a trick 
to improve the speed of the search, should not serve other purposes. Can 
we decouple the two things? Sooner or later the inconsistency would byte 
us, I'm sure. Please reason this way: imagine the trick was not there, 
re-do the patch, and, at the *very* end, put the trick back *only* to 
avoid calling lower_bound.

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

"Let's guarantee that a minimal grow step of 11 is used". Full stop at 
the end.

Paolo.