PR 71181 Avoid rehash after reserve

[Jonathan Wakely]

On 14/06/16 22:34 +0200, François Dumont wrote:
>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.

OK. And as I said below, lower_bound(primes, primes + nprimes - 1, n)
still works because anything greater than the second-to-last prime
should be treated as the last one anyway.

Would this comment make it clearer?

  // Don't include the last prime in the search, so that anything
  // higher than the second-to-last prime returns a past-the-end
  // iterator that can be dereferenced to get the last prime.
  const unsigned long* __p
    = std::lower_bound(__prime_list, __prime_list + _S_n_primes - 1, __n)


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

OK. I think a similar comment as suggested above could help, by being
more verbose about what's happening.

  // Don't include the last prime in the search, so that anything
  // higher than the second-to-last prime returns a past-the-end
  // iterator that can be dereferenced to get the last prime.

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

I did some comparisons and this version seems to execute fewer
instructions in some simple tests, according to cachegrind.