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

[Thomas Stüfe]

Hi Claes,

answers to your remarks inline. I will post the review for v0.4 separately.

On Wed, Dec 4, 2019 at 6:36 PM Claes Redestad <claes.redestad at oracle.com>
wrote:

> 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...?
>
>
Not offhand, no. Just an urge to completeness.


> >
> > - +1 for a "lumpier" header.
>
> o_O
>
>
Referring to Johns earlier mail about lumping the utility functions
together in a single header instead of having micro headers for every
function.

>
> > - 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.
>
>
No, not necessary. Just wondered if I missed something.


> >
> >    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.
>
>
Oh, right.


> > 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");
>

Thanks.


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

Sounds good thank you.


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

Cheers, Thomas