Index: include/bits/hashtable.h =================================================================== --- include/bits/hashtable.h (revision 193575) +++ include/bits/hashtable.h (working copy) @@ -806,11 +806,6 @@ _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 @@ _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); + _M_rehash_policy._M_next_bkt( + std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems), + __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); __try { @@ -990,6 +981,7 @@ __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 @@ { 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); Index: include/bits/hashtable_policy.h =================================================================== --- include/bits/hashtable_policy.h (revision 193575) +++ include/bits/hashtable_policy.h (working copy) @@ -358,7 +358,7 @@ 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 @@ _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, std::size_t __n_ins) const; - typedef std::pair _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 @@ 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 @@ / (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(__builtin_floor(__min_bkts) + 1, + __n_bkt * _S_growth_factor))); else { _M_next_resize @@ -475,13 +465,6 @@ 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); } Index: testsuite/performance/23_containers/insert_erase/41975.cc =================================================================== --- testsuite/performance/23_containers/insert_erase/41975.cc (revision 193575) +++ testsuite/performance/23_containers/insert_erase/41975.cc (working copy) @@ -18,7 +18,11 @@ // . #include -#include +#ifdef _USE_TR1 +# include +#else +# include +#endif #include namespace @@ -40,11 +44,17 @@ const int nb = 200000; start_counters(time, resource); +#ifdef _USE_TR1 + std::tr1::__unordered_set, std::equal_to, + std::allocator, + use_cache> us; +#else std::__uset_hashtable, std::equal_to, std::allocator, std::__uset_traits> us; +#endif for (int i = 0; i != nb; ++i) - us.insert(i); + us.insert(i); stop_counters(time, resource); ostr.str(""); @@ -126,10 +136,17 @@ start_counters(time, resource); +#ifdef _USE_TR1 + std::tr1::__unordered_set, + std::equal_to, + std::allocator, + use_cache> us; +#else std::__uset_hashtable, std::equal_to, std::allocator, std::__uset_traits> us; +#endif for (int i = 0; i != nb; ++i) us.insert(strs[i]); Index: testsuite/performance/23_containers/insert/unordered_set.cc =================================================================== --- testsuite/performance/23_containers/insert/unordered_set.cc (revision 193575) +++ testsuite/performance/23_containers/insert/unordered_set.cc (working copy) @@ -17,8 +17,17 @@ // { dg-options "-std=c++11" } -#include #include +#include +#ifdef _USE_TR1 +# include +using namespace std::tr1; +const char* ns = "std::tr1::"; +#else +# include +using namespace std; +const char* ns = "std::"; +#endif int main() { @@ -29,14 +38,16 @@ const int sz = 10000000; - std::unordered_set s; + unordered_set s; start_counters(time, resource); for (int i = 0; i != sz ; ++i) s.insert(i); stop_counters(time, resource); - report_performance(__FILE__, "unordered_set 10000000 insertions", + std::ostringstream ostr; + ostr << ns << "unordered_set " << sz << " insertions"; + report_performance(__FILE__, ostr.str().c_str(), time, resource); return 0; } Index: testsuite/performance/23_containers/insert/54075.cc =================================================================== --- testsuite/performance/23_containers/insert/54075.cc (revision 0) +++ testsuite/performance/23_containers/insert/54075.cc (revision 0) @@ -0,0 +1,132 @@ +// Copyright (C) 2012 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=c++11" } + +#include +#include +#include +#include +#include + +struct Foo +{ + typedef std::random_device::result_type _Type; + _Type bar; + _Type baz; + _Type meh; + + void + init(std::random_device& randev) + { + bar = randev(); + baz = randev(); + meh = randev(); + } + + std::size_t + hash() const noexcept + { return std::size_t(bar ^ baz ^ meh); } + + inline bool + operator==(const Foo& other) const + { return other.bar == bar && other.baz == baz && other.meh == meh; } +}; + +struct HashFunction +{ + template + std::size_t operator()(const T& t) const noexcept + { return t.hash(); } +}; + +template + void bench(const char* container_desc) + { + using namespace __gnu_test; + + time_counter time; + resource_counter resource; + + const int sz = 300000; + + Foo foos[sz]; + { + std::random_device randev; + for (int i = 0; i != sz; ++i) + foos[i].init(randev); + } + + _ContType s; + start_counters(time, resource); + + for (int i = 0; i != sz ; ++i) + s.insert(foos[i]); + + stop_counters(time, resource); + std::ostringstream ostr; + ostr << container_desc << sz << " Foo insertions"; + report_performance(__FILE__, ostr.str().c_str(), time, resource); + + // Try to insert again to check performance of collision detection + + const int nb_loop = 10; + start_counters(time, resource); + + for (int j = 0; j != nb_loop; ++j) + for (int i = 0; i != sz; ++i) + s.insert(foos[i]); + + stop_counters(time, resource); + ostr.str(""); + ostr << container_desc << nb_loop << " times insertion of " + << sz << " Foo"; + report_performance(__FILE__, ostr.str().c_str(), time, resource); + } + +template + using __tr1_uset = std::tr1::__unordered_set, + std::allocator, + cache>; +template + using __tr1_umset = std::tr1::__unordered_multiset, + std::allocator, + cache>; +template + using __uset = std::__uset_hashtable, + std::allocator, + std::__uset_traits>; +template + using __umset = std::__umset_hashtable, + std::allocator, + std::__uset_traits>; + +int main() +{ + bench<__tr1_uset>("std::tr1::unordered_set without hash code cached "); + bench<__tr1_uset>("std::tr1::unordered_set with hash code cached "); + bench<__tr1_umset>("std::tr1::unordered_multiset without hash code cached "); + bench<__tr1_umset>("std::tr1::unordered_multiset with hash code cached "); + bench<__uset>("std::unordered_set without hash code cached "); + bench<__uset>("std::unordered_set with hash code cached "); + bench<__umset>("std::unordered_multiset without hash code cached "); + bench<__umset>("std::unordered_multiset with hash code cached "); +}