diff mbox

hash policy patch

Message ID 4E7467FA.4090003@gmail.com
State New
Headers show

Commit Message

François Dumont Sept. 17, 2011, 9:27 a.m. UTC 
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

Comments

Paolo Carlini Sept. 17, 2011, 9:38 a.m. UTC | #1 
On 09/17/2011 11:27 AM, François Dumont wrote:
> 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.
As a general policy, in the testsuite we should never assert equality of 
floating point quantities, sooner or later that would byte us, and very 
badly (just search our Bugzilla or the web if you are not convinced). 
And, given that, I don't think we should waste time figuring out whether 
in specific cases, for specific machines, actually it would be safe to 
do it.

Paolo.
Robert Dewar Sept. 17, 2011, 1:41 p.m. UTC | #2 
On 9/17/2011 5:38 AM, Paolo Carlini wrote:
> On 09/17/2011 11:27 AM, François Dumont wrote:
>> 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.
> As a general policy, in the testsuite we should never assert equality of
> floating point quantities, sooner or later that would byte us, and very
> badly (just search our Bugzilla or the web if you are not convinced).
> And, given that, I don't think we should waste time figuring out whether
> in specific cases, for specific machines, actually it would be safe to
> do it.

An absolute rule of this kind makes me a bit nervous. There are
perfectly legitimate algorithms that assume IEEE arithmetic and
expect and should get absolute equality, and as long as the test
is restricted to IEEE, it seems quite reasonable to have equality
checks.

If you are creating a set of records where a unique floating-point
value is the key, that's another case where equality comparison
is reasonable.

Finally

    if x = x

is a reasonable test for not being a NaN
diff mbox

Patch

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