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] |

*From*: Jonathan Wakely <jwakely at redhat dot com>*To*: François Dumont <frs dot dumont at gmail dot com>*Cc*: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>*Date*: Wed, 15 Jun 2016 09:29:32 +0100*Subject*: Re: PR 71181 Avoid rehash after reserve*Authentication-results*: sourceware.org; auth=none*References*: <5741CD4E dot 4050104 at gmail dot com> <20160525140157 dot GK14158 at redhat dot com> <57460F81 dot 8050903 at gmail dot com> <575F0E40 dot 7050004 at gmail dot com> <20160614112253 dot GD11538 at redhat dot com> <57606A48 dot 6020904 at gmail dot com>

On 14/06/16 22:34 +0200, François Dumont wrote:

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 thatmakes 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 wecan remove them one day.I don't like current code because when you just look at lower_boundcall you can wonder why returned value is not tested. You need toconsider how __prime_list has been defined. When you add '- 1' in thecall 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.hb/libstdc++-v3/include/tr1/hashtable_policy.hindex 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 ofprime numbers.

OK. And as I said below, lower_bound(primes, primes + nprimes - 1, n) still works because anything greater than the second-to-last prime should be treated as the last one anyway. Would this comment make it clearer? // Don't include the last prime in the search, so that anything // higher than the second-to-last prime returns a past-the-end // iterator that can be dereferenced to get the last prime. const unsigned long* __p = std::lower_bound(__prime_list, __prime_list + _S_n_primes - 1, __n)

The other changes in tr1/hashtable_policy.h are nice simplifications.diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.ccb/libstdc++-v3/src/c++11/hashtable_c++0x.ccindex 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.

OK. I think a similar comment as suggested above could help, by being more verbose about what's happening. // Don't include the last prime in the search, so that anything // higher than the second-to-last prime returns a past-the-end // iterator that can be dereferenced to get the last prime.

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.

I did some comparisons and this version seems to execute fewer instructions in some simple tests, according to cachegrind.

**Follow-Ups**:**Re: PR 71181 Avoid rehash after reserve***From:*FranÃois Dumont

**References**:**Re: PR 71181 Avoid rehash after reserve***From:*FranÃois Dumont

**Re: PR 71181 Avoid rehash after reserve***From:*Jonathan Wakely

**Re: PR 71181 Avoid rehash after reserve***From:*FranÃois Dumont

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |