Re: hash policy patch
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
Re: hash policy patch
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.
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
* 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;
}
templatehttp://www.gnu.org/licenses/>.
+
+#include
+#include
+#include
+#include
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ typedef std::numeric_limits nl_size_t;
+ std::unordered_set, std::equal_to,
+ __gnu_cxx::throw_allocator_limit > 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;
+}
Re: hash policy patch
... Francois, your patch, as applied had nasty typos, which probably
broke the build (or we lacking tons of testcases ;) I committed the below.
Paolo.
PS: I think the fix could be suited also for the branch, maybe after a
couple of weeks of testing...
///
2011-07-24 Paolo Carlini
* include/bits/hashtable_policy.h (_Prime_rehash_policy::_M_next_bkt,
_M_bkt_for_elements, _M_need_rehash): Fix typos in the last commit.
Index: include/bits/hashtable_policy.h
===
--- include/bits/hashtable_policy.h (revision 176717)
+++ include/bits/hashtable_policy.h (working copy)
@@ -431,7 +431,7 @@
+ _S_n_primes, __n);
_M_next_resize =
static_cast(__builtin_floor(__p * _M_max_load_factor));
-return *__p;
+return __p;
}
// Return the smallest prime p such that alpha p >= n, where alpha
@@ -445,7 +445,7 @@
+ _S_n_primes, __min_bkts);
_M_next_resize =
static_cast(__builtin_floor(__p * _M_max_load_factor));
-return *__p;
+return __p;
}
// Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
@@ -474,7 +474,7 @@
__min_bkts);
_M_next_resize = static_cast
(__builtin_floor(__p * _M_max_load_factor));
- return std::make_pair(true, *__p);
+ return std::make_pair(true, __p);
}
else
{
Re: hash policy patch
On 07/24/2011 09:24 PM, François Dumont wrote: For info, I will submit a proposal for DR 41975 tomorrow or the day after. Oh, excellent, and good idea saying it in advance. Paolo.
Re: hash policy patch
On 07/24/2011 01:31 AM, Paolo Carlini wrote:
On 07/23/2011 10:31 PM, François Dumont wrote:
Hi
While working on DR 41975 I realized a small issue in current
rehash implementation that sometimes lead to load_factor being
greater than max_load_factor. Here is a patch to fix that:
Ok, good.
I think we could as well have everywhere:
const unsigned long __p = *std::lower_bound...
and then change the following *__p to __p. Isn't a tad cleaner?
Thanks,
Paolo.
Attached patch applied, I have integrated your remark Paolo.
2011-07-24 François Dumont
* include/bits/hashtable_policy.h (_Prime_rehash_policy): Use
__builtin_floor rather than __builtin_ceil to compute next resize
value.
* testsuite/23_containers/unordered_set/hash_policy/load_factor.cc:
New.
For info, I will submit a proposal for DR 41975 tomorrow or the day after.
Regards
Index: include/bits/hashtable_policy.h
===
--- include/bits/hashtable_policy.h (revision 176581)
+++ include/bits/hashtable_policy.h (working copy)
@@ -427,10 +427,10 @@
_Prime_rehash_policy::
_M_next_bkt(std::size_t __n) const
{
-const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
+const unsigned long __p = *std::lower_bound(__prime_list, __prime_list
+ _S_n_primes, __n);
_M_next_resize =
- static_cast(__builtin_ceil(*__p * _M_max_load_factor));
+ static_cast(__builtin_floor(__p * _M_max_load_factor));
return *__p;
}
@@ -441,10 +441,10 @@
_M_bkt_for_elements(std::size_t __n) const
{
const float __min_bkts = __n / _M_max_load_factor;
-const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
+const unsigned long __p = *std::lower_bound(__prime_list, __prime_list
+ _S_n_primes, __min_bkts);
_M_next_resize =
- static_cast(__builtin_ceil(*__p * _M_max_load_factor));
+ static_cast(__builtin_floor(__p * _M_max_load_factor));
return *__p;
}
@@ -469,17 +469,17 @@
if (__min_bkts > __n_bkt)
{
__min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
- const unsigned long* __p =
- std::lower_bound(__prime_list, __prime_list + _S_n_primes,
- __min_bkts);
+ const unsigned long __p =
+ *std::lower_bound(__prime_list, __prime_list + _S_n_primes,
+__min_bkts);
_M_next_resize = static_cast
- (__builtin_ceil(*__p * _M_max_load_factor));
+ (__builtin_floor(__p * _M_max_load_factor));
return std::make_pair(true, *__p);
}
else
{
_M_next_resize = static_cast
- (__builtin_ceil(__n_bkt * _M_max_load_factor));
+ (__builtin_floor(__n_bkt * _M_max_load_factor));
return std::make_pair(false, 0);
}
}
Index: testsuite/23_containers/unordered_set/hash_policy/load_factor.cc
===
--- testsuite/23_containers/unordered_set/hash_policy/load_factor.cc (revision 0)
+++ testsuite/23_containers/unordered_set/hash_policy/load_factor.cc (revision 0)
@@ -0,0 +1,58 @@
+// 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
+//
