log2_up

[WhateverLiu]

This is not an issue but more of a remark.

The <bit> library in C++20 contains std::bit_width(), which by my testing is at least 1.6x faster than log2_up in utilities.h. I modified log2_up() as follows, passing all tests:

template <class T>
size_t log2_up(T i) {
  assert(i > 0);
#if defined(__cplusplus) && __cplusplus >= 202002L
#include <bit>
  return std::bit_width ( i - 1 ); 
#else
  size_t a = 0;
  T b = i - 1;
  while (b > 0) {
    b = b >> 1;
    a++;
  }
  return a;
#endif
}

Since log2_up() is key to the pool allocator, it shouldn't hurt to squeeze every bit of speed out of it :)

[DanielLiamAnderson]

Reasonable idea for sure, but here are some pedantic responses :P

1. We are planning at some point in the future to make Parlay require C++20 as a minimum, at which point we can have all the benefits of the latest features. In the meantime we could conditionally macro all of those nice things and have fallbacks, but that bloats the code a lot, so I'd rather just wait a little longer and make the switch all at once (we do admittedly already do this in some rare places, e.g., we currently do this is in the scheduler with atomic::wait but that is critical to the scheduler's behavior, while this is minor).
2. bit_width is only defined for unsigned integer types, but there is no (documented) restriction that log2_up only supports unsigned types, so this will probably fail if given a signed type.
3. I think your conditional macro is technically not the right one. bit_width is a standard library feature, not a language feature (and it is possible have a compiler that supports a higher language level but using old standard library), so you should use a feature test macro instead. I think the right one is __cpp_lib_int_pow2 according to CppReference.

[WhateverLiu]

@DanielLiamAnderson Thanks for the reply! The __cpp_lib_int_pow2 comment is particularly helpful. I checked all the parlay source files containing log2_up, and they all take in unsigned integers. But your caution is well-founded.