diff options
author | fdumont <fdumont@138bc75d-0d04-0410-961f-82ee72b054a4> | 2012-11-16 21:28:44 +0000 |
---|---|---|
committer | fdumont <fdumont@138bc75d-0d04-0410-961f-82ee72b054a4> | 2012-11-16 21:28:44 +0000 |
commit | c5981d0c3af4fa743c01fa2470f985ae53eb3238 (patch) | |
tree | af286ba5a2bef7d79795117e634ec60dc2a3c8df /libstdc++-v3/include | |
parent | 75e1829ff65760cfd66aa678dfc6fc0e42431958 (diff) | |
download | gcc-c5981d0c3af4fa743c01fa2470f985ae53eb3238.tar.gz |
2012-11-16 François Dumont <fdumont@gcc.gnu.org>
* include/bits/hashtable_policy.h (_Prime_rehash_policy): Remove
automatic shrink.
(_Prime_rehash_policy::_M_bkt_for_elements): Do not call
_M_next_bkt anymore.
(_Prime_rehash_policy::_M_next_bkt): Move usage of
_S_growth_factor ...
(_Prime_rehash_policy::_M_need_rehash): ... here.
* include/bits/hashtable.h (_Hashtable<>): Adapt.
* testsuite/performance/23_containers/insert_erase/41975.cc: Add
_USE_TR1 to force build using std::tr1 container.
* testsuite/performance/23_containers/insert/unordered_set.cc:
Likewise.
* testsuite/performance/23_containers/insert/54075.cc: New.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@193576 138bc75d-0d04-0410-961f-82ee72b054a4
Diffstat (limited to 'libstdc++-v3/include')
-rw-r--r-- | libstdc++-v3/include/bits/hashtable.h | 35 | ||||
-rw-r--r-- | libstdc++-v3/include/bits/hashtable_policy.h | 43 |
2 files changed, 23 insertions, 55 deletions
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 9b2677b098a..0f15a46e6db 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -806,11 +806,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_rehash_policy() { _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); - - // We don't want the rehash policy to ask for the hashtable to - // shrink on the first insertion so we need to reset its - // previous resize level. - _M_rehash_policy._M_prev_resize = 0; _M_buckets = _M_allocate_buckets(_M_bucket_count); } @@ -834,16 +829,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_element_count(0), _M_rehash_policy() { + auto __nb_elems = __detail::__distance_fw(__f, __l); _M_bucket_count = - _M_rehash_policy._M_bkt_for_elements(__detail::__distance_fw(__f, - __l)); - if (_M_bucket_count <= __bucket_hint) - _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); - - // We don't want the rehash policy to ask for the hashtable to - // shrink on the first insertion so we need to reset its - // previous resize level. - _M_rehash_policy._M_prev_resize = 0; + _M_rehash_policy._M_next_bkt( + std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems), + __bucket_hint)); + _M_buckets = _M_allocate_buckets(_M_bucket_count); __try { @@ -990,6 +981,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __rehash_policy(const _RehashPolicy& __pol) { size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count); + __n_bkt = __pol._M_next_bkt(__n_bkt); if (__n_bkt != _M_bucket_count) _M_rehash(__n_bkt, _M_rehash_policy._M_state()); _M_rehash_policy = __pol; @@ -1641,19 +1633,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { const __rehash_state& __saved_state = _M_rehash_policy._M_state(); std::size_t __buckets - = _M_rehash_policy._M_bkt_for_elements(_M_element_count + 1); - if (__buckets <= __n) - __buckets = _M_rehash_policy._M_next_bkt(__n); + = std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1), + __n); + __buckets = _M_rehash_policy._M_next_bkt(__buckets); if (__buckets != _M_bucket_count) - { - _M_rehash(__buckets, __saved_state); - - // We don't want the rehash policy to ask for the hashtable to shrink - // on the next insertion so we need to reset its previous resize - // level. - _M_rehash_policy._M_prev_resize = 0; - } + _M_rehash(__buckets, __saved_state); else // No rehash, restore previous state to keep a consistent 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 259785d6f54..ee289da6a48 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -358,7 +358,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION struct _Prime_rehash_policy { _Prime_rehash_policy(float __z = 1.0) - : _M_max_load_factor(__z), _M_prev_resize(0), _M_next_resize(0) { } + : _M_max_load_factor(__z), _M_next_resize(0) { } float max_load_factor() const noexcept @@ -380,25 +380,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, std::size_t __n_ins) const; - typedef std::pair<std::size_t, std::size_t> _State; + typedef std::size_t _State; _State _M_state() const - { return std::make_pair(_M_prev_resize, _M_next_resize); } + { return _M_next_resize; } void - _M_reset(const _State& __state) - { - _M_prev_resize = __state.first; - _M_next_resize = __state.second; - } + _M_reset(_State __state) + { _M_next_resize = __state; } enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 }; static const std::size_t _S_growth_factor = 2; float _M_max_load_factor; - mutable std::size_t _M_prev_resize; mutable std::size_t _M_next_resize; }; @@ -417,35 +413,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION static const unsigned char __fast_bkt[12] = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 }; - const std::size_t __grown_n = __n * _S_growth_factor; - if (__grown_n <= 11) + if (__n <= 11) { - _M_prev_resize = 0; _M_next_resize - = __builtin_ceil(__fast_bkt[__grown_n] + = __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor); - return __fast_bkt[__grown_n]; + return __fast_bkt[__n]; } const unsigned long* __next_bkt = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, - __grown_n); - const unsigned long* __prev_bkt - = std::lower_bound(__prime_list + 1, __next_bkt, __n / _S_growth_factor); - - _M_prev_resize - = __builtin_floor(*(__prev_bkt - 1) * (long double)_M_max_load_factor); + __n); _M_next_resize = __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor); return *__next_bkt; } - // Return the smallest prime p such that alpha p >= n, where alpha + // Return the smallest integer p such that alpha p >= n, where alpha // is the load factor. inline std::size_t _Prime_rehash_policy:: _M_bkt_for_elements(std::size_t __n) const - { return _M_next_bkt(__builtin_ceil(__n / (long double)_M_max_load_factor)); } + { return __builtin_ceil(__n / (long double)_M_max_load_factor); } // Finds the smallest prime p such that alpha p > __n_elt + __n_ins. // If p > __n_bkt, return make_pair(true, p); otherwise return @@ -467,7 +456,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION / (long double)_M_max_load_factor; if (__min_bkts >= __n_bkt) return std::make_pair(true, - _M_next_bkt(__builtin_floor(__min_bkts) + 1)); + _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1, + __n_bkt * _S_growth_factor))); else { _M_next_resize @@ -475,13 +465,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return std::make_pair(false, 0); } } - else if (__n_elt + __n_ins < _M_prev_resize) - { - long double __min_bkts = (__n_elt + __n_ins) - / (long double)_M_max_load_factor; - return std::make_pair(true, - _M_next_bkt(__builtin_floor(__min_bkts) + 1)); - } else return std::make_pair(false, 0); } |