diff options
| author | François Dumont <fdumont@gcc.gnu.org> | 2011-12-07 19:47:03 +0000 |
|---|---|---|
| committer | François Dumont <fdumont@gcc.gnu.org> | 2011-12-07 19:47:03 +0000 |
| commit | 95c0a8a714efb1be55f3bb2af190db003d6455dc (patch) | |
| tree | c55917c60479c8571ba34ecd6313ba38a6d70232 | |
| parent | 3c411f3f2c4ed6dbc3a2c0996533dcb9d0365a8d (diff) | |
| download | gcc-95c0a8a714efb1be55f3bb2af190db003d6455dc.zip gcc-95c0a8a714efb1be55f3bb2af190db003d6455dc.tar.gz gcc-95c0a8a714efb1be55f3bb2af190db003d6455dc.tar.bz2 | |
re PR libstdc++/51386 (23_containers/unordered_set/hash_policy/load_factor.cc execution timeout)
2011-12-07 François Dumont <fdumont@gcc.gnu.org>
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
| -rw-r--r-- | libstdc++-v3/ChangeLog | 7 | ||||
| -rw-r--r-- | 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 065b635..d8707d8 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,10 @@ +2011-12-07 François Dumont <fdumont@gcc.gnu.org> + + 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 <paolo.carlini@oracle.com> PR libstdc++/51438 diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 44c749a..e97685c 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<std::size_t>(*(__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; } |