PR 71181 Avoid rehash after reserve

[François Dumont]

On 14/06/2016 13:22, Jonathan Wakely wrote:
> On 13/06/16 21:49 +0200, François Dumont wrote:
>> Hi
>>
>>    I eventually would like to propose the attached patch.
>>
>>    In tr1 I made sure we use a special past-the-end iterator that 
>> makes usage of lower_bound result without check safe.
>
> I'm confused ... isn't that already done?

Indeed but my intention was to make sentinel values useless so that we 
can remove them one day.

I don't like current code because when you just look at lower_bound call 
you can wonder why returned value is not tested. You need to consider 
how __prime_list has been defined. When you add '- 1' in the call to 
lower_bound you don't need to look too far to understand it.

>
> _S_n_primes is defined as:
>
>    enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
>
> The table of primes is:
>
>  extern const unsigned long __prime_list[] = // 256 + 1 or 256 + 48 + 1
>
> Which means that _S_n_primes is already one less, so that the "end"
> returned by lower_bound is already dereferenceable. That's what the
> comment in the table suggests too:
>
>    // Sentinel, so we don't have to test the result of lower_bound,
>    // or, on 64-bit machines, rest of the table.
> #if __SIZEOF_LONG__ != 8
>    4294967291ul
>
> So ...
>
>> diff --git a/libstdc++-v3/include/tr1/hashtable_policy.h 
>> b/libstdc++-v3/include/tr1/hashtable_policy.h
>> index 4ee6d45..24d1a59 100644
>> --- a/libstdc++-v3/include/tr1/hashtable_policy.h
>> +++ b/libstdc++-v3/include/tr1/hashtable_policy.h
>> @@ -420,8 +420,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>   _Prime_rehash_policy::
>>   _M_next_bkt(std::size_t __n) const
>>   {
>> -    const unsigned long* __p = std::lower_bound(__prime_list, 
>> __prime_list
>> -                        + _S_n_primes, __n);
>> +    // Past-the-end iterator is made dereferenceable to avoid check on
>> +    // lower_bound result.
>> +    const unsigned long* __p
>> +      = std::lower_bound(__prime_list, __prime_list + _S_n_primes - 
>> 1, __n);
>
> Is this redundant? Unless I'm misunderstanding something, _S_n_primes
> already handles this.

Yes it does for now but not if __prime_list is a the pure list of prime 
numbers.
>
> The other changes in tr1/hashtable_policy.h are nice simplifications.
>
>> diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc 
>> b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
>> index a5e6520..7cbd364 100644
>> --- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc
>> +++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
>> @@ -46,22 +46,36 @@ 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);
>>     return __fast_bkt[__n];
>>       }
>>
>> +    // Number of primes without sentinel.
>>     constexpr auto __n_primes
>>       = sizeof(__prime_list) / sizeof(unsigned long) - 1;
>> +    // past-the-end iterator is made dereferenceable.
>> +    constexpr auto __prime_list_end = __prime_list + __n_primes - 1;
>
> I don't think this comment clarifies things very well.
>
> Because of the sentinel and because __n_primes doesn't include the
> sentinel, (__prime_list + __n_primes) is already dereferenceable
> anyway, so the comment doesn't explain why there's *another* -1 here.

The comment is doing as if there was no sentinel.

>
>
>>     const unsigned long* __next_bkt =
>> -      std::lower_bound(__prime_list + 5, __prime_list + __n_primes, 
>> __n);
>> +      std::lower_bound(__prime_list + 6, __prime_list_end, __n);
>> +
>> +    if (*__next_bkt == __n && __next_bkt != __prime_list_end)
>> +      ++__next_bkt;
>
> Can we avoid this check by searching for __n + 1 instead of __n with
> the lower_bound call?

Yes, that's another option, I will give it a try.
>
> If I understand the logic correctly we can do it like this:
>
>    // Number of primes without sentinel:
>    constexpr auto __n_primes
>      = sizeof(__prime_list) / sizeof(unsigned long) - 1;
>    // The greatest prime in the table:
>    constexpr auto __prime_list_end = __prime_list + __n_primes - 1;
>    const auto __next_bkt =
>      std::lower_bound(__prime_list + 6, __prime_list_end, __n + 1);
>    if (__next_bkt == __prime_list_end)
>      _M_next_resize = size_t(-1); // Reached maximum bucket count.
>    else
>      _M_next_resize =
>     __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
>    return *__next_bkt;
>
> i.e.
>
> - Ignore the sentinel (keeping it only for backward compatibility).
>
> - Search for __n + 1 so we find the *next* bucket count.
>
> - Don't include the largest prime in the search, because even if __n >
>  largest prime, we're going to use that largest value anyway, so:
>
> - if __n >= second largest prime then lower_bound will return the end
>  iterator, which points to the largest prime.
>
> Does this behave correctly?
Yes, it should, will run tests.
>
> I'd really like to see it tested for the boundary conditions, i.e.
> verify that _Prime_rehash_policy::_M_next_bkt behaves as expected when
> passed prime numbers, and when passed N-1, N and N+1 where N is the
> largest prime in the table.
>
>> +    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;
>>   }
>
>
> N.B. this chunk of the patch doesn't apply due to whitespace
> differences, what are you diffing against?

This patch is part of a list of patches I am managing thanks to the git 
mirror and I might also have generate it with 'git diff -w' so not 
showing all indentation fixes.

François