max_load_factor constant complexity

max_load_factor constant complexity

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 653 bytes --]

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




[-- Attachment #2: constant_max_load_factor.patch --]
[-- Type: text/x-patch, Size: 3490 bytes --]

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 );
 }
 

Re: max_load_factor constant complexity

[Jonathan Wakely]

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.