RFR: 8234331: Add robust and optimized utility for rounding up to next power of two+

[Claes Redestad]

Hi Thomas,

On 2019-12-04 17:32, Thomas Stüfe wrote:
> Hi Claes,
> 
> I think this is very good and useful.
> 
> General remarks:
> 
> - Pity that it only works for 32/64bit values. It would be neat to have 
> variants for 8 and 16 bit values too.

I don't think adding 8- and 16-bit variants would be too hard, but would
need specialized adjustment since most platforms only have 32- and 64-
bit intrinsics for clz. Do you know any code where we might need such
specializations...?

> 
> - +1 for a "lumpier" header.

o_O

> 
> - the round_down() variants: would it make sense to allow 0 as valid 
> input? I can imagine scenarios where 0 could be a valid input and result 
> for this operation.

I've been contemplating if there's room for variants that are less
strict, e.g., where you can define what values you should get on
0 or overflow. I think that's out of scope for this RFE.

> 
> - I tested on AIX, builds and gtests run through without errors.

Great, thanks!

> 
> ----
> 
> 
> http://cr.openjdk.java.net/~redestad/8234331/open.03/src/hotspot/share/runtime/threadSMR.cpp.udiff.html
> 
> +  int hash_table_size = 
> round_up_power_of_2(MIN2((int)get_java_thread_list()->length(), 32) << 1);
> 
> Style nit, I would have preferred this to be two operations for 
> readability.

Sure, will fix.

> 
> 
> http://cr.openjdk.java.net/~redestad/8234331/open.03/src/hotspot/share/utilities/powerOfTwo.hpp.html
> 
>    43 inline typename EnableIf<IsSigned<T>::value, T>::type 
> round_down_power_of_2(T value) {
> ...
> 
>    47   assert(lz < sizeof(T) * BitsPerByte, "Sanity");
> 
> Do we need this if we check the input value for >0 ? (Same question for 
> the signed version of round_up() below).

Technically we shouldn't need any of the "Sanity" asserts that check
that lz is in the expected range ([0-31]/[0-63]). I added them mostly as
scaffolding when writing these functions, but kept them since I think
they help reason about the code. I can remove them if you insist.

> 
>    48   assert(lz > 0, "Overflow to negative");
> 
> Same here?

Right, for round_down this one is pointless lz == 0 would only be
possible if value > 0. I'll remove this one.

For round_up we overflow when value > 2^30, so lz == 1, which is not
covered by value > 0. So that assert I think is needed.

> Also, small nit, the assert text is slightly off since no overflow 
> happened yet, but the input value is negative.

Maybe just:

   assert(lz > 1, "Will overflow");

> 
> (The asserts do not bother me much, I am just trying to understand why 
> we need them)

To catch obvious programming mistakes, catch more issues during testing,
and reason about the code.

> 
> -
> 
>   100 // Accepts 0 (returns 1); overflows if value is larger than or 
>   equal to 2^31
>   101 // or 2^63, for 32- and 64-bit integers, respectively
> 
> Comment is a bit off. True only for unsigned values. Also it should 
> mention that overflow results in assert to be in sync with the other 
> comments.

How about:

// Accepts 0 (returns 1), overflows with assert if value is larger than
// or equal to 2^31 (2^30 for signed) or 2^63 (2^62 if signed), for 32-
// and 64-bit integers, respectively

> 
> ----
> 
> http://cr.openjdk.java.net/~redestad/8234331/open.03/src/hotspot/share/utilities/count_leading_zeros.hpp.frames.html
> 
> template <typename T> inline uint32_t count_leading_zeros(T x) {
> 
> Instead of all the "if sizeof(T) == 4|8", could we specialize the 
> functions for different operand sizes? Example:
> 
> template <typename T, size_t n> struct Impl;
> template <typename T> struct Impl<T, 8> { static int doit(T v) { return 
> __builtin_clzll(v); } };
> template <typename T> struct Impl<T, 4> { static int doit(T v) { return 
> __builtin_clz(v); } };
> template <typename T> int count_leading_zero(T v) { return Impl<T, 
> sizeof(T)>::doit(v); }
> 
> Would make it easier later to plug in implementations for different 
> sizes, and we'd still get a compile time error for invalid input types.

I guess we could, but I'm not so sure it'd help readability.

> 
> -
> 
> I wondered why count_leading_zeros did not allow 0 as input until I saw 
> that __builtin_clz(ll) unfolds to bsr; and that does not work for 
> input=0. I still find it an artificial limitation but that was there 
> before your patch.

Yes, it's a bit unfortunate and artificial, and I think we'd regress
some actually performance-critical places by adding a special-case for
0. If we want graceful versions that give 0 and max on over- and
underflow we can add them in separately, I think.

> 
> ----
> 
> Thank you for the enhanced comment in the fallback implementation, thats 
> helpful.
> 
> ----
> 
> http://cr.openjdk.java.net/~redestad/8234331/open.03/test/hotspot/gtest/utilities/test_powerOfTwo.cpp.html
> 
> It bothers me a bit that we do not test invalid input and overflow. 
> There is a way, I believe, to have gtests expect an assert. We have 
> TEST_VM_ASSERT but I am not sure if that is a good idea since crashing 
> takes time. I also see that we only use it at a single place, so I guess 
> others share the same concern :)
> 
> Alternatively, one could have variants of round_up/down which return a 
> definite value on overflow. I wonder whether this may be useful 
> someplace outside the tests.

Yeah, a lighter mechanism for testing asserts would be great. I'd prefer
deferring negative tests to a follow-up, though, since I have a few
other things to attend to before 14 FC... :-)

> 
> -
> 
> Just a thought, but could you cut down the code for the many TEST 
> functions if you would use a templatized test function? Basically, 
> something like
> 
> template <class T> struct MyMaxImpl;
> template <int32_t> MyMaxImpl   { static int32 get() { return 
> int32_max_pow2; } };
> .. etc
> 
> template <typename T> void round_up_test() {
>    EXPECT_EQ(round_up_power_of_2((T)1), (T)1) << "value = " << 1;
> ...
>      const T max = MyMaxImpl<T>::get();
>    EXPECT_EQ(round_up_power_of_2(max - 1), max)
> ...
> }
> 
> TEST(power_of_2, round_up_power_of_2_signed_32) {
>    round_up_do_test<int32_t>();
> }
> 
> That way the test would also be easily extendable later if we decide to 
> add support for uint8_t or uint16_t.

We might save a few lines of code, yes, but my preference is keeping
tests explicit even if that makes them somewhat more repetitive - to a
point. I can see if we were to add int8/int16 variants that this might
move well beyond that point, though.

Thanks!

/Claes