From 95c0a8a714efb1be55f3bb2af190db003d6455dc Mon Sep 17 00:00:00 2001 From: =?utf8?q?Fran=C3=A7ois=20Dumont?= Date: Wed, 7 Dec 2011 19:47:03 +0000 Subject: [PATCH] re PR libstdc++/51386 (23_containers/unordered_set/hash_policy/load_factor.cc execution timeout) MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 2011-12-07 François Dumont PR libstdc++/51386 * include/bits/hashtable_policy.h (_Prime_rehash_policy::_M_next_bkt): Fix computation of _M_prev_resize so that hashtable do not keep on being rehashed when _M_max_load_factor is lower than 1. From-SVN: r182085 --- libstdc++-v3/ChangeLog | 7 +++++ libstdc++-v3/include/bits/hashtable_policy.h | 33 ++++++++++++-------- 2 files changed, 27 insertions(+), 13 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 065b6357e96..d8707d8d371 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,10 @@ +2011-12-07 François Dumont + + PR libstdc++/51386 + * include/bits/hashtable_policy.h (_Prime_rehash_policy::_M_next_bkt): + Fix computation of _M_prev_resize so that hashtable do not keep on + being rehashed when _M_max_load_factor is lower than 1. + 2011-12-06 Paolo Carlini PR libstdc++/51438 diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 44c749af515..e97685c6ae7 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -300,23 +300,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { // Optimize lookups involving the first elements of __prime_list. // (useful to speed-up, eg, constructors) - static const unsigned long __fast_bkt[12] + static const unsigned char __fast_bkt[12] = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 }; + if (__n <= 11) + { + _M_prev_resize = 0; + _M_next_resize + = __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor); + return __fast_bkt[__n]; + } + const unsigned long* __p - = __n <= 11 ? __fast_bkt + __n - : std::lower_bound(__prime_list + 5, - __prime_list + _S_n_primes, __n); - - _M_prev_resize = __builtin_floor(*__p * (long double)_M_max_load_factor); - if (__p != __fast_bkt) - _M_prev_resize = std::min(_M_prev_resize, - static_cast(*(__p - 1))); - // Lets guaranty a minimal grow step of 11: + = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, __n); + + // Shrink will take place only if the number of elements is small enough + // so that the prime number 2 steps before __p is large enough to still + // conform to the max load factor: + _M_prev_resize + = __builtin_floor(*(__p - 2) * (long double)_M_max_load_factor); + + // Let's guaranty that a minimal grow step of 11 is used if (*__p - __n < 11) - __p = std::lower_bound(__prime_list + 5, - __prime_list + _S_n_primes, __n + 11); - _M_next_resize = __builtin_floor(*__p * (long double)_M_max_load_factor); + __p = std::lower_bound(__p, __prime_list + _S_n_primes, __n + 11); + _M_next_resize = __builtin_ceil(*__p * (long double)_M_max_load_factor); return *__p; } -- 2.30.2