hashtable_policy.h (_Prime_rehash_policy): Remove automatic shrink.

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.

From-SVN: r193576

6 files changed, 204 insertions, 60 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 3744f94..9be305b 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,19 @@
+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.
+
 2012-11-16  Tom Tromey  <tromey@redhat.com>
 
 	* testsuite/libstdc++-prettyprinters/whatis.cc: New file.
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 9b2677b..0f15a46 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 259785d..ee289da 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);
   }
diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc b/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc
new file mode 100644
index 0000000..cb045ea
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc
@@ -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
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <testsuite_performance.h>
+#include <random>
+#include <sstream>
+#include <tr1/unordered_set>
+#include<unordered_set>
+
+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<typename T>
+    std::size_t operator()(const T& t) const noexcept
+    { return t.hash(); }
+};
+
+template<typename _ContType>
+  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<bool cache>
+  using __tr1_uset = std::tr1::__unordered_set<Foo, HashFunction,
+					       std::equal_to<Foo>,
+					       std::allocator<Foo>,
+					       cache>;
+template<bool cache>
+  using __tr1_umset = std::tr1::__unordered_multiset<Foo, HashFunction,
+						     std::equal_to<Foo>,
+						     std::allocator<Foo>,
+						     cache>;
+template<bool cache>
+  using __uset = std::__uset_hashtable<Foo, HashFunction,
+				       std::equal_to<Foo>,
+				       std::allocator<Foo>,
+				       std::__uset_traits<cache>>;
+template<bool cache>
+  using __umset = std::__umset_hashtable<Foo, HashFunction,
+					 std::equal_to<Foo>,
+					 std::allocator<Foo>,
+					 std::__uset_traits<cache>>;
+
+int main()
+{
+  bench<__tr1_uset<false>>("std::tr1::unordered_set without hash code cached ");
+  bench<__tr1_uset<true>>("std::tr1::unordered_set with hash code cached ");
+  bench<__tr1_umset<false>>("std::tr1::unordered_multiset without hash code cached ");
+  bench<__tr1_umset<true>>("std::tr1::unordered_multiset with hash code cached ");
+  bench<__uset<false>>("std::unordered_set without hash code cached ");
+  bench<__uset<true>>("std::unordered_set with hash code cached ");
+  bench<__umset<false>>("std::unordered_multiset without hash code cached ");
+  bench<__umset<true>>("std::unordered_multiset with hash code cached ");
+}
diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_set.cc b/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_set.cc
index 83d3935..a7fd4a0 100644
--- a/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_set.cc
+++ b/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_set.cc
@@ -17,8 +17,17 @@
 
 // { dg-options "-std=c++11" }
 
-#include <unordered_set>
 #include <testsuite_performance.h>
+#include <sstream>
+#ifdef _USE_TR1
+#  include <tr1/unordered_set>
+using namespace std::tr1;
+const char* ns = "std::tr1::";
+#else
+#  include<unordered_set>
+using namespace std;
+const char* ns = "std::";
+#endif
 
 int main()
 {
@@ -29,14 +38,16 @@ int main()
 
   const int sz = 10000000;
 
-  std::unordered_set<int> s;
+  unordered_set<int> 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;
 }
diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc b/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc
index 286a045..19226f6 100644
--- a/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc
+++ b/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc
@@ -18,7 +18,11 @@
 // <http://www.gnu.org/licenses/>.
 
 #include <sstream>
-#include <unordered_set>
+#ifdef _USE_TR1
+#  include <tr1/unordered_set>
+#else
+#  include <unordered_set>
+#endif
 #include <testsuite_performance.h>
 
 namespace
@@ -40,11 +44,17 @@ namespace
       const int nb = 200000;
       start_counters(time, resource);
 
+#ifdef _USE_TR1
+      std::tr1::__unordered_set<int, std::hash<int>, std::equal_to<int>,
+				std::allocator<int>,
+			       	use_cache> us;
+#else
       std::__uset_hashtable<int, std::hash<int>, std::equal_to<int>,
 			    std::allocator<int>,
 			    std::__uset_traits<use_cache>> 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 @@ namespace
 
       start_counters(time, resource);
 
+#ifdef _USE_TR1
+      std::tr1::__unordered_set<std::string, std::hash<std::string>,
+				std::equal_to<std::string>,
+				std::allocator<std::string>,
+				use_cache> us;
+#else
       std::__uset_hashtable<std::string, std::hash<std::string>,
 			    std::equal_to<std::string>,
 			    std::allocator<std::string>,
 			    std::__uset_traits<use_cache>> us;
+#endif
       for (int i = 0; i != nb; ++i)
 	us.insert(strs[i]);