diff mbox

max_load_factor constant complexity

Message ID 5592FB22.6040407@gmail.com
State New
Headers show

Commit Message

François Dumont June 30, 2015, 8:25 p.m. UTC 
Hi

    During a recent discussion on Reflector about max_load_factor some
pointed that libstdc++ has not the constant complexity as imposed by the
Standard in Table 103 because we try to respect the new factor by
potentially rehashing the container. This patch fix this problem by
adopting VS Standard Library behavior of retaining the targeted
max_load_factor and comply to it as soon as possible on insertion.

    * include/bits/hashtable.h (_Hashtable<>::__rehash_policy): Remove
    container rehash.
    * testsuite/23_containers/unordered_set/max_load_factor/robustness.cc:
    Adapt.

Tested under linux x86_64.

Ok to commit ?

François

Comments

Jonathan Wakely June 30, 2015, 10:18 p.m. UTC | #1 
On 30/06/15 22:25 +0200, François Dumont wrote:
>Hi
>
>    During a recent discussion on Reflector about max_load_factor some
>pointed that libstdc++ has not the constant complexity as imposed by the
>Standard in Table 103 because we try to respect the new factor by
>potentially rehashing the container. This patch fix this problem by
>adopting VS Standard Library behavior of retaining the targeted
>max_load_factor and comply to it as soon as possible on insertion.
>
>    * include/bits/hashtable.h (_Hashtable<>::__rehash_policy): Remove
>    container rehash.
>    * testsuite/23_containers/unordered_set/max_load_factor/robustness.cc:
>    Adapt.
>
>Tested under linux x86_64.
>
>Ok to commit ?

OK, thanks.
diff mbox

Patch

diff --git libstdc++-v3/include/bits/hashtable.h libstdc++-v3/include/bits/hashtable.h
index 31d237e..19d7ee7 100644
--- libstdc++-v3/include/bits/hashtable.h
+++ libstdc++-v3/include/bits/hashtable.h
@@ -595,7 +595,8 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       { return _M_rehash_policy; }
 
       void
-      __rehash_policy(const _RehashPolicy&);
+      __rehash_policy(const _RehashPolicy& __pol)
+      { _M_rehash_policy = __pol; }
 
       // Lookup.
       iterator
@@ -1285,22 +1286,6 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
-    void
-    _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    __rehash_policy(const _RehashPolicy& __pol)
-    {
-      auto __do_rehash =
-	__pol._M_need_rehash(_M_bucket_count, _M_element_count, 0);
-      if (__do_rehash.first)
-	_M_rehash(__do_rehash.second, _M_rehash_policy._M_state());
-      _M_rehash_policy = __pol;
-    }
-
-  template<typename _Key, typename _Value,
-	   typename _Alloc, typename _ExtractKey, typename _Equal,
-	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
-	   typename _Traits>
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
diff --git libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc
index a72829e..5978228 100644
--- libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc
+++ libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc
@@ -32,41 +32,47 @@  void test01()
   int val = 0;
   for (; val != 100; ++val)
     {
-      VERIFY( us.insert(val).second) ;
+      VERIFY( us.insert(val).second );
       VERIFY( us.load_factor() <= us.max_load_factor() );
     }
 
   float cur_max_load_factor = us.max_load_factor();
   int counter = 0;
   std::size_t thrown_exceptions = 0;
+
+  // Reduce max load factor.
+  us.max_load_factor(us.max_load_factor() / 2);
+
+  // At this point load factor is higher than max_load_factor because we can't
+  // rehash in max_load_factor call.
+  VERIFY( us.load_factor() > us.max_load_factor() );
+
   while (true)
     {
       __gnu_cxx::limit_condition::set_limit(counter++);
       bool do_break = false;
       try
 	{
-	  us.max_load_factor(.5f);
+	  size_t nbkts = us.bucket_count();
+	  // Check that unordered_set will still be correctly resized when
+	  // needed.
+	  VERIFY( us.insert(val++).second );
+
+	  VERIFY( us.bucket_count() != nbkts );
+	  VERIFY( us.load_factor() <= us.max_load_factor() );
 	  do_break = true;
 	}
       catch (const __gnu_cxx::forced_error&)
 	{
-	  VERIFY( us.max_load_factor() == cur_max_load_factor );
+	  // max load factor doesn't change.
+	  VERIFY( us.max_load_factor() == .5f );
 	  ++thrown_exceptions;
 	}
-      // Lets check that unordered_set will still be correctly resized
-      // when needed
-      __gnu_cxx::limit_condition::set_limit(nl_size_t::max());
-      for (;;)
-	{
-	  VERIFY( us.load_factor() <= us.max_load_factor() );
-	  size_t nbkts = us.bucket_count();
-	  VERIFY( us.insert(val++).second );
-	  if (us.bucket_count() != nbkts)
-	    break;
-	}
+
       if (do_break)
 	break;
     }
+
   VERIFY( thrown_exceptions > 0 );
 }