PR 71181 Avoid rehash after reserve

[Jonathan Wakely]

On 16/06/16 21:29 +0200, François Dumont wrote:
>Here is a new version compiling all your feedbacks.
>
>    PR libstdc++/71181
>    * include/tr1/hashtable_policy.h
>    (_Prime_rehash_policy::_M_next_bkt): Make past-the-end iterator
>    dereferenceable to avoid check on lower_bound result.
>    (_Prime_rehash_policy::_M_bkt_for_elements): Call latter.
>    (_Prime_rehash_policy::_M_need_rehash): Likewise.
>    * src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
>    Always return a value greater than input value. Set _M_next_resize to
>    max value when reaching highest prime number.
>    * src/shared/hashtable-aux.cc (__prime_list): Add comment about 
>sentinel
>    being now useless.
>    * testsuite/23_containers/unordered_set/hash_policy/71181.cc: New.
>    * testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc
>    (test02): New.
>    * 
>testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc: 
>New.
>    * testsuite/23_containers/unordered_set/hash_policy/rehash.cc:
>    Fix indentation.

Great - OK for trunk, thanks.


>On 15/06/2016 10:29, Jonathan Wakely wrote:
>>On 14/06/16 22:34 +0200, François Dumont wrote:
>>>>>   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.
>>
>The only drawback is that calling _M_next_bkt(size_t(-1)) doesn't give 
>the right result. But reaching this kind of value is not likely to 
>happen in real use cases so it is acceptable.

Yes, good point. I don't think we can ever have that many buckets,
because each bucket requires more than one byte, so we can't fit that
many buckets in memory anyway.