libstdc++/90277 Review rehash policy

[Jonathan Wakely]

On 03/05/19 06:21 +0200, François Dumont wrote:
>Hi
>
>Â Â Â  This is a patch I already proposed in another thread but I review 
>it and moreover there is now a PR associated so I am submitting it as 
>a brand new one.
>
>Â Â Â  So working on PR 68303 I noticed that one of the performance issue 
>of current implementation is that initial sizing of buckets is small. 
>In tr1 implementation we were starting at 11 but now we go through 2, 
>3, 5, 7 and eventually 11, a lot of intermediate reallocation/rehash. 
>It can be considered as a fix for PR 90277 cause when initial bucket 
>count is 11 there is no rehash anymore during those tests.
>
>Â Â Â  Compared to initial submission this version has the refinement 
>that if the user explicitly set initial bucket count we respect it and 
>do not jump to 11.
>
>Â Â Â  Additionally this patch extend the PR 87135 fix to the power of 2 
>rehash policy alternative and it adopts the long double versions of 
>builtin ceil/floor as advised in another message thread.
>
>Â Â Â  Last I realized that _Hashtable<>::reserve could leverage on 
>rehash policy _M_bkt_for_elements rather than trying to compute it 
>itself, it brings more consistency in the container behavior.
>
>Â Â Â  * include/bits/hashtable.h (_Hashtable<>::rehash): Review comment.
>Â Â Â  * include/bits/hashtable_policy.h
>Â Â Â  (_Prime_rehash_policy::_M_bkt_for_elements): Use __builtin_ceill.
>Â Â Â  (_Power2_rehash_policy::_M_bkt_for_elements): Likewise.
>Â Â Â  (_Power2_rehash_policy::_M_next_bkt): Enforce returning a result not
>Â Â Â  smaller than input value rather than always greater. Preserve
>Â Â Â  _M_next_resize if called with 0 input. Use __builtin_floorl.
>Â Â Â  (_Power2_rehash_policy::_M_need_rehash): Rehash only if number of
>Â Â Â  elements + number of insertions is greater than _M_next_resize. Start
>Â Â Â  with 11 buckets if not told otherwise. Use __builtin_floorl.
>Â Â Â  (_Rehash_base<>::reserve): Use rehash policy _M_bkt_for_elements.
>Â Â Â  * src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
>Â Â Â  Preserve _M_next_resize if called with 0 input. Use __builtin_floorl.
>Â Â Â  (_Prime_rehash_policy::_M_need_rehash): Start with 11 buckets if not
>Â Â Â  told otherwise. Use __builtin_floorl.
>Â Â Â  * testsuite/23_containers/unordered_set/hash_policy/71181.cc: 
>Adapt test
>Â Â Â  to also validate _Power2_rehash_policy.
>Â Â Â  * testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc:
>Â Â Â  Adapt.
>
>Tested under Linux x86_64 normal and debug modes.
>
>Ok to commit ?

Yes, looks good - thanks!