On 14/06/2016 13:22, Jonathan Wakely wrote:
On 13/06/16 21:49 +0200, François Dumont wrote:
Hi
I eventually would like to propose the attached patch.
In tr1 I made sure we use a special past-the-end iterator that
makes usage of lower_bound result without check safe.
I'm confused ... isn't that already done?
Indeed but my intention was to make sentinel values useless so that we
can remove them one day.
I don't like current code because when you just look at lower_bound call
you can wonder why returned value is not tested. You need to consider
how __prime_list has been defined. When you add '- 1' in the call to
lower_bound you don't need to look too far to understand it.
_S_n_primes is defined as:
enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
The table of primes is:
extern const unsigned long __prime_list[] = // 256 + 1 or 256 + 48 + 1
Which means that _S_n_primes is already one less, so that the "end"
returned by lower_bound is already dereferenceable. That's what the
comment in the table suggests too:
// Sentinel, so we don't have to test the result of lower_bound,
// or, on 64-bit machines, rest of the table.
#if __SIZEOF_LONG__ != 8
4294967291ul
So ...
diff --git a/libstdc++-v3/include/tr1/hashtable_policy.h
b/libstdc++-v3/include/tr1/hashtable_policy.h
index 4ee6d45..24d1a59 100644
--- a/libstdc++-v3/include/tr1/hashtable_policy.h
+++ b/libstdc++-v3/include/tr1/hashtable_policy.h
@@ -420,8 +420,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Prime_rehash_policy::
_M_next_bkt(std::size_t __n) const
{
- const unsigned long* __p = std::lower_bound(__prime_list,
__prime_list
- + _S_n_primes, __n);
+ // Past-the-end iterator is made dereferenceable to avoid check on
+ // lower_bound result.
+ const unsigned long* __p
+ = std::lower_bound(__prime_list, __prime_list + _S_n_primes -
1, __n);
Is this redundant? Unless I'm misunderstanding something, _S_n_primes
already handles this.
Yes it does for now but not if __prime_list is a the pure list of prime
numbers.
The other changes in tr1/hashtable_policy.h are nice simplifications.
diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc
b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
index a5e6520..7cbd364 100644
--- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc
+++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
@@ -46,22 +46,36 @@ namespace __detail
{
// Optimize lookups involving the first elements of __prime_list.
// (useful to speed-up, eg, constructors)
- static const unsigned char __fast_bkt[12]
- = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
+ static const unsigned char __fast_bkt[13]
+ = { 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 };
- if (__n <= 11)
+ if (__n <= 12)
{
_M_next_resize =
__builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor);
return __fast_bkt[__n];
}
+ // Number of primes without sentinel.
constexpr auto __n_primes
= sizeof(__prime_list) / sizeof(unsigned long) - 1;
+ // past-the-end iterator is made dereferenceable.
+ constexpr auto __prime_list_end = __prime_list + __n_primes - 1;
I don't think this comment clarifies things very well.
Because of the sentinel and because __n_primes doesn't include the
sentinel, (__prime_list + __n_primes) is already dereferenceable
anyway, so the comment doesn't explain why there's *another* -1 here.
The comment is doing as if there was no sentinel.
const unsigned long* __next_bkt =
- std::lower_bound(__prime_list + 5, __prime_list + __n_primes,
__n);
+ std::lower_bound(__prime_list + 6, __prime_list_end, __n);
+
+ if (*__next_bkt == __n && __next_bkt != __prime_list_end)
+ ++__next_bkt;
Can we avoid this check by searching for __n + 1 instead of __n with
the lower_bound call?
Yes, that's another option, I will give it a try.
If I understand the logic correctly we can do it like this:
// Number of primes without sentinel:
constexpr auto __n_primes
= sizeof(__prime_list) / sizeof(unsigned long) - 1;
// The greatest prime in the table:
constexpr auto __prime_list_end = __prime_list + __n_primes - 1;
const auto __next_bkt =
std::lower_bound(__prime_list + 6, __prime_list_end, __n + 1);
if (__next_bkt == __prime_list_end)
_M_next_resize = size_t(-1); // Reached maximum bucket count.
else
_M_next_resize =
__builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
return *__next_bkt;
i.e.
- Ignore the sentinel (keeping it only for backward compatibility).
- Search for __n + 1 so we find the *next* bucket count.
- Don't include the largest prime in the search, because even if __n >
largest prime, we're going to use that largest value anyway, so:
- if __n >= second largest prime then lower_bound will return the end
iterator, which points to the largest prime.
Does this behave correctly?
Yes, it should, will run tests.
I'd really like to see it tested for the boundary conditions, i.e.
verify that _Prime_rehash_policy::_M_next_bkt behaves as expected when
passed prime numbers, and when passed N-1, N and N+1 where N is the
largest prime in the table.
+ if (__next_bkt == __prime_list_end)
+ // Set next resize to the max value so that we never try to
rehash again
+ // as we already reach the biggest possible bucket number.
+ // Note that it might result in max_load_factor not being
respected.
+ _M_next_resize = std::size_t(-1);
+ else
_M_next_resize =
__builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
+
return *__next_bkt;
}
N.B. this chunk of the patch doesn't apply due to whitespace
differences, what are you diffing against?
This patch is part of a list of patches I am managing thanks to the git
mirror and I might also have generate it with 'git diff -w' so not
showing all indentation fixes.
François
