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: PR 71181 Avoid rehash after reserve


On 16/06/16 21:29 +0200, François Dumont wrote:
Here is a new version compiling all your feedbacks.

   PR libstdc++/71181
   * include/tr1/hashtable_policy.h
   (_Prime_rehash_policy::_M_next_bkt): Make past-the-end iterator
   dereferenceable to avoid check on lower_bound result.
   (_Prime_rehash_policy::_M_bkt_for_elements): Call latter.
   (_Prime_rehash_policy::_M_need_rehash): Likewise.
   * src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
   Always return a value greater than input value. Set _M_next_resize to
   max value when reaching highest prime number.
* src/shared/hashtable-aux.cc (__prime_list): Add comment about sentinel
   being now useless.
   * testsuite/23_containers/unordered_set/hash_policy/71181.cc: New.
   * testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc
   (test02): New.
* testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc: New.
   * testsuite/23_containers/unordered_set/hash_policy/rehash.cc:
   Fix indentation.

Great - OK for trunk, thanks.


On 15/06/2016 10:29, Jonathan Wakely wrote:
On 14/06/16 22:34 +0200, François Dumont wrote:
  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.

The only drawback is that calling _M_next_bkt(size_t(-1)) doesn't give the right result. But reaching this kind of value is not likely to happen in real use cases so it is acceptable.

Yes, good point. I don't think we can ever have that many buckets,
because each bucket requires more than one byte, so we can't fit that
many buckets in memory anyway.


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