[libcxx] Fix __is_power2 and __next_power2. Change hashmap to handle new behavior.

[EricWF]

Summary

• Fix that __is_power2 returns false on 1 and 2.
• Change all uses of __is_power2 in hashtable to __is_rehash_power2 which retains the old behavior.
• Handle 0 and 1 as special cases in __next_pow2. Prevents calling __clz(0) which is undefined behavior.

I use these functions in the polymorphic allocator implementation I'm working on. For that reason I think we should fix this.

[gribozavr]

Instead of duplicating the `__bc <= 2 || !__is_power2(__bc)` check, can it be abstracted into another predicate?

Also, I don't know what is the policy of libc++ about testing internal APIs, but is_power2 and next_pow2 seem to be clearly testable.

[EricWF]

I've abstracted the changes to __hash_table to call __is_rehash_power2. As for internal API testing, there currently is none. there has been some offline discussion about changing that and (this being a motivating case). I'll bring it up with Marshall again when he gets back.

[EricWF]

Woops. That last patch was wrong. I forgot to negate __is_rehash_power2.
I also incorrectly rounded 1 -> 2 in __next_power2. Both of these errors have been fixed.

[mclow.lists]

If this isn't/wasn't going to help out the PMF stuff in std::experimental, then I don't think that this is worth doing.

that being said, other than the inline comments, I think this looks fine.

include/__hash_table

86

Looks to me that this produces:
0 --> 1
1 --> 1
2 --> 4
4 --> 8

Is that the intended behavior? (especially the second one)

1959

This expression seems (to me) to be crying out for a small inline function, like: (untested code!)

size_t XXX ( size_t sz, float max_load )
{ return size_t( ciel (float(sz) / max_load )); }

and then the expression could be:

(__is_rehash_power2(__bc))
    ? __next_pow2  ( XXX ( size(), max_load_factor()))
    : __next_prime ( XXX ( size(), max_load_factor()))

or even have XXX call size() and max_load_factor() itself.

[EricWF]

If this isn't/wasn't going to help out the PMF stuff in std::experimental, then I don't think that this is worth doing.

I agree, I think the best thing to do would be to simply rename the functions to avoid name collisions and then implement them separately for the PMR stuff. That way we don't have to worry about changing the performance of the hash containers.

include/__hash_table

86

Oops, I don't think so.

return n < 2 ? __n + 1

Should fix that.

But IDK if the change is needed. However I am still concerned that the current version exhibits undefined behaviour for __n = 1.

[howard.hinnant]

Only tangentially related, here is some documentation on __next_prime:

http://stackoverflow.com/a/5694432/576911

Howard

[EricWF]

Ok, I'm abandoning this revision. I'm going to rename the functions so the names better suit the specialized functionality and implement different versions for PMR.
There is clearly a lot of interest in changes to the power of 2 / prime resizing of __hash_table but I think a better time to handle this all will be when I'm writing libc++ performance tests.
As Howard mentioned the performance of this code is critical and I don't want to make any changes without doing the proper performance testing legwork.

Thank's for all the input it has been invaluable.

include/__hash_table

 bool
 __is_power2(size_t __bc)
 {
-    return __bc > 2 && !(__bc & (__bc - 1));
+    return __bc && !(__bc & (__bc - 1));
 }
 
 inline _LIBCPP_INLINE_VISIBILITY

 }
 
 inline _LIBCPP_INLINE_VISIBILITY
+bool __is_rehash_power2(size_t __bc)
+{
+    return __bc > 2 && __is_power2(__bc);
+}
+
+inline _LIBCPP_INLINE_VISIBILITY
 size_t
 __next_pow2(size_t __n)
 {
-    return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1));
+    return __n < 2 ? __n + (__n == 0)
+        : size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1));
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table;

     {
         if (size()+1 > __bc * max_load_factor() || __bc == 0)
         {
-            rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc),
+            rehash(_VSTD::max<size_type>(2 * __bc + !__is_rehash_power2(__bc),
                            size_type(ceil(float(size() + 1) / max_load_factor()))));
             __bc = bucket_count();
             __chash = __constrain_hash(__nd->__hash_, __bc);

     size_type __bc = bucket_count();
     if (size()+1 > __bc * max_load_factor() || __bc == 0)
     {
-        rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc),
+        rehash(_VSTD::max<size_type>(2 * __bc + !__is_rehash_power2(__bc),
                        size_type(ceil(float(size() + 1) / max_load_factor()))));
         __bc = bucket_count();
     }

         size_type __bc = bucket_count();
         if (size()+1 > __bc * max_load_factor() || __bc == 0)
         {
-            rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc),
+            rehash(_VSTD::max<size_type>(2 * __bc + !__is_rehash_power2(__bc),
                            size_type(ceil(float(size() + 1) / max_load_factor()))));
             __bc = bucket_count();
         }

         __node_holder __h = __construct_node(__x, __hash);
         if (size()+1 > __bc * max_load_factor() || __bc == 0)
         {
-            rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc),
+            rehash(_VSTD::max<size_type>(2 * __bc + !__is_rehash_power2(__bc),
                            size_type(ceil(float(size() + 1) / max_load_factor()))));
             __bc = bucket_count();
             __chash = __constrain_hash(__hash, __bc);

         __n = _VSTD::max<size_type>
               (
                   __n,
-                  __is_power2(__bc) ? __next_pow2(size_t(ceil(float(size()) / max_load_factor()))) :
-                                      __next_prime(size_t(ceil(float(size()) / max_load_factor())))
+                  (__is_rehash_power2(__bc))
+                    ? __next_pow2(size_t(ceil(float(size()) / max_load_factor())))
+                    : __next_prime(size_t(ceil(float(size()) / max_load_factor())))
               );
         if (__n < __bc)
             __rehash(__n);