This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: hash policy patch


On 09/16/2011 03:00 AM, Paolo Carlini wrote:
Ok... but:

+      us.max_load_factor(.5f);
+      VERIFY( us.max_load_factor() == .5f );

as we discussed already (didn't we?), this kind of VERIFY is in general very brittle (even if on the widespread base-2 systems probably we are lucky in this *specific* case): please just remove it, I don't think we'll miss much anyway.
I also wondered if in __rehash_policy method we shouldn't rehash as soon as __n_bkt != _M_bucket_count rather than only when __n_bkt > _M_bucket_count. Users might change max load factor also to reduce the number of buckets...
I should find the time to check C++11 about this. I'll let you know my opinion ASAP.
Attached patch applied.

2011-09-17 François Dumont <fdumont@gcc.gnu.org>

* include/bits/hashtable.h (_Hashtable<>::__rehash_policy(const
_RehashPolicy&)): Commit the modification of the policy only if no
exception occured.
* testsuite/23_containers/unordered_set/max_load_factor/robustness.cc:
New.


Paolo, I know that using float equality comparison is not reliable in general and I have remove the suspicious line but in this case I can't imagine a system where it could fail. When I do

const float f = 0.5f;
float foo = f;
assert( foo == f );

I can't imagine a system where the assert would fail, no ? Even if the system is not able to represent 0.5f in an acurate way this inaccuracy will be taken into account in the equality comparison. Unless you mean that on a C++ Standard point of view users should not expect max_load_factor() to return a value equal the one passed through max_load_factor(float). The Standard indeed does not make it explicit.

François

Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h	(revision 178926)
+++ include/bits/hashtable.h	(working copy)
@@ -741,10 +741,10 @@
 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
     __rehash_policy(const _RehashPolicy& __pol)
     {
-      _M_rehash_policy = __pol;
       size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
       if (__n_bkt > _M_bucket_count)
-	_M_rehash(__n_bkt, __pol._M_next_resize);
+	_M_rehash(__n_bkt, _M_rehash_policy._M_next_resize);
+      _M_rehash_policy = __pol;
     }
 
   template<typename _Key, typename _Value,
Index: testsuite/23_containers/unordered_set/max_load_factor/robustness.cc
===================================================================
--- testsuite/23_containers/unordered_set/max_load_factor/robustness.cc	(revision 0)
+++ testsuite/23_containers/unordered_set/max_load_factor/robustness.cc	(revision 0)
@@ -0,0 +1,77 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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/>.
+
+#include <unordered_set>
+#include <limits>
+#include <ext/throw_allocator.h>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  typedef std::numeric_limits<std::size_t> nl_size_t;
+  std::unordered_set<int, std::hash<int>, std::equal_to<int>,
+		     __gnu_cxx::throw_allocator_limit<int> > us;
+  int val = 0;
+  for (; val != 100; ++val)
+    {
+      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;
+  while (true)
+    {
+      __gnu_cxx::limit_condition::set_limit(counter++);
+      bool do_break = false;
+      try
+	{
+	  us.max_load_factor(.5f);
+	  do_break = true;
+	}
+      catch (const __gnu_cxx::forced_error&)
+	{
+	  VERIFY( us.max_load_factor() == cur_max_load_factor );
+	  ++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 );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]