PR 51386

[François Dumont]

On 12/05/2011 10:13 PM, Paolo Carlini wrote:
> Hi,
>
> >     Tested under linux x86_64, load_factor test is much faster now.
>
> How much, exactly?

About 2000 times faster. I have temporarily added the slow part of 
load_factor test in a performance test to measure it, do you want to 
keep this ? I hadn't proposed it before because a max load factor of 0.3 
is quite unusual. load_factor test simply challenge a possible use case 
that has little chances to be experimented in a production environment.

>
> >
> > 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.
I finally restore the original values, the small containers will simply 
grow slower at the beginning, not a big deal.

Ok to commit ?

François

-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashtable_policy.patch
Type: text/x-patch
Size: 1896 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20111206/77aa4ce0/attachment.bin>