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!
