libstdc++/90277 Review rehash policy

[François Dumont]

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 ?

François


-------------- next part --------------
A non-text attachment was scrubbed...
Name: hash_policy.patch
Type: text/x-patch
Size: 10078 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20190503/cb5ebdcf/attachment.bin>