Re: PR 71181 Avoid rehash after reserve

[Jonathan Wakely <jwakely at redhat dot com>]

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?

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

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.


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

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?

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?

In your patch these two lines are already indented:

>       _M_next_resize =
> 	__builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);

But in the current code on trunk they are not.


> diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc
> index 2dac583..9658131 100644
> --- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc
> +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc
> @@ -34,8 +34,8 @@ void test()
> 	us.insert(i);
> 	if (bkt_count != us.bucket_count())
> 	  {
> -	// Container has been rehashed, lets check that it won't be rehash again
> -	// if we remove and restore the last 2 inserted elements:
> +	    // Container has been rehashed, lets check that it won't be rehash
> +	    // again if we remove and restore the last 2 inserted elements:
> 	    rehashed = true;
> 	    bkt_count = us.bucket_count();
> 	    VERIFY( us.erase(i) == 1 );


This chunk of the patch doesn't apply either. The indentation already
looks correct on trunk.