summaryrefslogtreecommitdiff
path: root/libstdc++-v3/include
diff options
context:
space:
mode:
authorfdumont <fdumont@138bc75d-0d04-0410-961f-82ee72b054a4>2012-11-16 21:28:44 +0000
committerfdumont <fdumont@138bc75d-0d04-0410-961f-82ee72b054a4>2012-11-16 21:28:44 +0000
commitc5981d0c3af4fa743c01fa2470f985ae53eb3238 (patch)
treeaf286ba5a2bef7d79795117e634ec60dc2a3c8df /libstdc++-v3/include
parent75e1829ff65760cfd66aa678dfc6fc0e42431958 (diff)
downloadgcc-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.h35
-rw-r--r--libstdc++-v3/include/bits/hashtable_policy.h43
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);
}