PR 71181 Avoid rehash after reserve

[François Dumont]

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.

     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 that sentinel
     is useless.
     * testsuite/23_containers/unordered_set/hash_policy/71181.cc: New.
     * 
testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc: New.
     * testsuite/23_containers/unordered_set/hash_policy/rehash.cc:
     Fix indentation.

Tested under Linux x86_64.

François


On 25/05/2016 22:48, François Dumont wrote:
> On 25/05/2016 16:01, Jonathan Wakely wrote:
>> On 22/05/16 17:16 +0200, François Dumont wrote:
>>> Hi
>>>
>>>    To fix 71181 problem I propose to change how we deal with reserve 
>>> called with pivot values that is to say prime numbers. Now 
>>> _M_next_bkt always return a value higher than the input value. This 
>>> way when reverse(97) is called we end up with 199 buckets and so 
>>> enough space to store 97 values without rehashing.
>>>
>>>    I have integrated in this patch several other enhancements on the 
>>> same subject. Improvement of _M_next_resize management when reaching 
>>> highest bucket number. Remove sentinel value in __prime_list, just 
>>> need to limit range when calling lower_bound.
>>
>> I don't think the change to __prime_list is safe. If you compile some
>> code with GCC 5 and then used a libstdc++.so with this change the old
>> code would still be looking for the sentinel in the array, and would
>> not find it.
>>
>> I think it would be safe to leave the old __prime_list unchanged (and
>> then not need to change anything in tr1/hashtable_policy.h?) and add a
>> new array with a different name. Existing code compiled with older
>> versions of GCC would still find __prime_list, but the new code would
>> use a different array.
>>
>>
>
>     What about this version ? tr1 mode still limit search range as it 
> should to make sure it doesn't need to check lower_bound result. And 
> sentinel is only kept for backward compatibility and commented to make 
> that clear. Maybe there is a clearer way to express that sentinel can 
> be removed on a future version breaking abi ?
>
> François

-------------- next part --------------
A non-text attachment was scrubbed...
Name: 71181.patch
Type: text/x-patch
Size: 9883 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20160613/2e2ede74/attachment.bin>