From de6f5f57650500a447a389252bc215384db2bd80 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Fran=C3=A7ois=20Dumont?= Date: Sat, 4 May 2019 07:38:46 +0000 Subject: [PATCH] hashtable.h (_Hashtable<>::rehash): Review comment. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 2019-05-04 François Dumont * 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. From-SVN: r270868 --- libstdc++-v3/ChangeLog | 22 +++++++++ libstdc++-v3/include/bits/hashtable.h | 3 +- libstdc++-v3/include/bits/hashtable_policy.h | 46 ++++++++++++------- libstdc++-v3/src/c++11/hashtable_c++0x.cc | 32 ++++++++----- .../unordered_set/hash_policy/71181.cc | 27 ++++++++--- .../hash_policy/power2_rehash.cc | 13 +++--- 6 files changed, 101 insertions(+), 42 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 40396312a0c..995ae0f6bb0 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,25 @@ +2019-05-04 François Dumont + + * 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. + 2019-05-03 Jonathan Wakely PR libstdc++/61761 diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index da78c68434f..2e8aeb7e4d4 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -2055,7 +2055,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__buckets != _M_bucket_count) _M_rehash(__buckets, __saved_state); else - // No rehash, restore previous state to keep a consistent state. + // No rehash, restore previous state to keep it consistent with + // container state. _M_rehash_policy._M_reset(__saved_state); } diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index b38e8e0ecef..c7f466cd686 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -460,7 +460,7 @@ namespace __detail // Return a bucket count appropriate for n elements std::size_t _M_bkt_for_elements(std::size_t __n) const - { return __builtin_ceil(__n / (long double)_M_max_load_factor); } + { return __builtin_ceill(__n / (long double)_M_max_load_factor); } // __n_bkt is current bucket count, __n_elt is current element count, // and __n_ins is number of elements to be inserted. Do we need to @@ -535,24 +535,32 @@ namespace __detail std::size_t _M_next_bkt(std::size_t __n) noexcept { + if (__n == 0) + // Special case on container 1st initialization with 0 bucket count + // hint. We keep _M_next_resize to 0 to make sure that next time we + // want to add an element allocation will take place. + return 1; + const auto __max_width = std::min(sizeof(size_t), 8); const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1); std::size_t __res = __clp2(__n); - if (__res == __n) - __res <<= 1; - if (__res == 0) __res = __max_bkt; + else if (__res == 1) + // If __res is 1 we force it to 2 to make sure there will be an + // allocation so that nothing need to be stored in the initial + // single bucket + __res = 2; if (__res == __max_bkt) // Set next resize to the max value so that we never try to rehash again // as we already reach the biggest possible bucket number. // Note that it might result in max_load_factor not being respected. - _M_next_resize = std::size_t(-1); + _M_next_resize = numeric_limits::max(); else _M_next_resize - = __builtin_ceil(__res * (long double)_M_max_load_factor); + = __builtin_floorl(__res * (long double)_M_max_load_factor); return __res; } @@ -560,7 +568,7 @@ namespace __detail // Return a bucket count appropriate for n elements std::size_t _M_bkt_for_elements(std::size_t __n) const noexcept - { return __builtin_ceil(__n / (long double)_M_max_load_factor); } + { return __builtin_ceill(__n / (long double)_M_max_load_factor); } // __n_bkt is current bucket count, __n_elt is current element count, // and __n_ins is number of elements to be inserted. Do we need to @@ -570,21 +578,25 @@ namespace __detail _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, std::size_t __n_ins) noexcept { - if (__n_elt + __n_ins >= _M_next_resize) + if (__n_elt + __n_ins > _M_next_resize) { - long double __min_bkts = (__n_elt + __n_ins) - / (long double)_M_max_load_factor; + // If _M_next_resize is 0 it means that we have nothing allocated so + // far and that we start inserting elements. In this case we start + // with an initial bucket size of 11. + long double __min_bkts + = std::max(__n_elt + __n_ins, _M_next_resize ? 0 : 11) + / (long double)_M_max_load_factor; if (__min_bkts >= __n_bkt) - return std::make_pair(true, - _M_next_bkt(std::max(__builtin_floor(__min_bkts) + 1, - __n_bkt * _S_growth_factor))); + return { true, + _M_next_bkt(std::max(__builtin_floorl(__min_bkts) + 1, + __n_bkt * _S_growth_factor)) }; _M_next_resize - = __builtin_floor(__n_bkt * (long double)_M_max_load_factor); - return std::make_pair(false, 0); + = __builtin_floorl(__n_bkt * (long double)_M_max_load_factor); + return { false, 0 }; } else - return std::make_pair(false, 0); + return { false, 0 }; } typedef std::size_t _State; @@ -1074,7 +1086,7 @@ namespace __detail reserve(std::size_t __n) { __hashtable* __this = static_cast<__hashtable*>(this); - __this->rehash(__builtin_ceil(__n / max_load_factor())); + __this->rehash(__this->__rehash_policy()._M_bkt_for_elements(__n)); } }; diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc index 47c609d1800..de437d00b56 100644 --- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc +++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc @@ -51,8 +51,14 @@ namespace __detail if (__n < sizeof(__fast_bkt)) { + if (__n == 0) + // Special case on container 1st initialization with 0 bucket count + // hint. We keep _M_next_resize to 0 to make sure that next time we + // want to add an element allocation will take place. + return 1; + _M_next_resize = - __builtin_floor(__fast_bkt[__n] * (long double)_M_max_load_factor); + __builtin_floorl(__fast_bkt[__n] * (long double)_M_max_load_factor); return __fast_bkt[__n]; } @@ -72,10 +78,10 @@ namespace __detail // Set next resize to the max value so that we never try to rehash again // as we already reach the biggest possible bucket number. // Note that it might result in max_load_factor not being respected. - _M_next_resize = std::size_t(-1); + _M_next_resize = numeric_limits::max(); else _M_next_resize = - __builtin_floor(*__next_bkt * (long double)_M_max_load_factor); + __builtin_floorl(*__next_bkt * (long double)_M_max_load_factor); return *__next_bkt; } @@ -96,19 +102,23 @@ namespace __detail { if (__n_elt + __n_ins > _M_next_resize) { - long double __min_bkts = (__n_elt + __n_ins) - / (long double)_M_max_load_factor; + // If _M_next_resize is 0 it means that we have nothing allocated so + // far and that we start inserting elements. In this case we start + // with an initial bucket size of 11. + long double __min_bkts + = std::max(__n_elt + __n_ins, _M_next_resize ? 0 : 11) + / (long double)_M_max_load_factor; if (__min_bkts >= __n_bkt) - return std::make_pair(true, - _M_next_bkt(std::max(__builtin_floor(__min_bkts) + 1, - __n_bkt * _S_growth_factor))); + return { true, + _M_next_bkt(std::max(__builtin_floorl(__min_bkts) + 1, + __n_bkt * _S_growth_factor)) }; _M_next_resize - = __builtin_floor(__n_bkt * (long double)_M_max_load_factor); - return std::make_pair(false, 0); + = __builtin_floorl(__n_bkt * (long double)_M_max_load_factor); + return { false, 0 }; } else - return std::make_pair(false, 0); + return { false, 0 }; } } // namespace __detail diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc index 6e38eba2c2c..7bbf4fd73db 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc @@ -22,22 +22,22 @@ #include template - void test(int threshold) + void + test(_USet& us, int threshold) { - _USet us; auto nb_reserved = us.bucket_count(); us.reserve(nb_reserved); auto bkts = us.bucket_count(); - for (int i = 0; i != threshold; ++i) + for (int nb_insert = 1; nb_insert <= threshold; ++nb_insert) { - if (i >= nb_reserved) + if (nb_insert > nb_reserved) { nb_reserved = bkts; us.reserve(nb_reserved); bkts = us.bucket_count(); } - us.insert(i); + us.insert(nb_insert); VERIFY( us.bucket_count() == bkts ); } @@ -54,9 +54,22 @@ template std::__detail::_Power2_rehash_policy, std::__detail::_Hashtable_traits>; +template + void + test_cont() + { + _USet us; + test(us, 150); + + us.clear(); + us.rehash(0); + + test(us, 150); + } + int main() { - test>(150); - test>(150); + test_cont>(); + test_cont>(); return 0; } diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc index 58ed268ee4c..5e42485b977 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc @@ -26,9 +26,10 @@ void test01() { std::__detail::_Power2_rehash_policy policy; VERIFY( policy._M_next_bkt(1) == 2 ); - VERIFY( policy._M_next_bkt(2) == 4 ); + VERIFY( policy._M_next_bkt(2) == 2 ); VERIFY( policy._M_next_bkt(3) == 4 ); VERIFY( policy._M_next_bkt(5) == 8 ); + VERIFY( policy._M_next_bkt(16) == 16 ); VERIFY( policy._M_next_bkt(33) == 64 ); VERIFY( policy._M_next_bkt((std::size_t(1) << (sizeof(std::size_t) * 8 - 2)) + 1) == (std::size_t(1) << (sizeof(std::size_t) * 8 - 1)) ); @@ -38,20 +39,20 @@ void test02() { std::__detail::_Power2_rehash_policy policy; - for (std::size_t i = 1;;) + for (std::size_t i = 3;;) { auto nxt = policy._M_next_bkt(i); - if (nxt == i) + if (nxt <= i) { - // Equals only when reaching max. + // Lower or equal only when reaching max. constexpr auto mx = std::numeric_limits::max(); VERIFY( nxt == policy._M_next_bkt(mx) ); break; } - VERIFY( nxt > i ); - i = nxt; + VERIFY( nxt >= i ); + i = nxt + 1; } } -- 2.30.2