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

[Thomas Stüfe]

Hi Claes,

this looks all good to me. Thanks for your patience!

I won't be able to test the latest iteration on AIX (just started vacation)
but I am quite sure it will work since the delta to the last version is
minimal; should it not we will fix it.

Cheers, Thomas

On Thu, Dec 5, 2019 at 3:56 PM Claes Redestad <claes.redestad at oracle.com>
wrote:

> On 2019-12-05 11:26, Thomas Stüfe wrote:
> > Hi Claes,
> >
> > this looks nice, thank you for your work. Only minor stuff remains,
> > mostly matters of taste. Feel free to ignore them. The patch is already
> > fine as it is for me.
> >
> > With your latest patch, AIX still works.
>
> Great!
>
> >
> > ---
> >
> >
> http://cr.openjdk.java.net/~redestad/8234331/open.04/src/hotspot/share/utilities/count_leading_zeros.hpp.udiff.html
> >
> > Taste matter: I find the return type for count_leading_zeros as uint32_t
> > oddly specific. Instinctively I would have choosen int or unsigned. The
> > gcc buildins all return int.
>
> No particular reason.
>
> >
> > ---
> >
> > Question, why do we treat signed numbers of 8 and 16 bits different wrt
> > to values < 0?
> >
> > if you leave behavior as it is, could you please adjust the comment:
> >
> >   // Return the number of leading zeros in x, e.g. the zero-based index
> >   // of the most significant set bit in x.  Undefined for 0.
> > + // For signed numbers whose size is < 32bit, function will
> > + // return 0 for values < 0.
>
> Such a comment is a bit redundant since count_leading_zeros will return
> 0 for any negative input. Maybe we should spell that out more clearly,
> though.
>
> The special cases avoided issues with sign extension when upcasting,
> e.g, casting int8_t -1 to unsigned returns 0xFFFFFFFF, so
> __builtin_clz((int8_t)-1) returns 0, which then messes up the manual
> adjustment. But this can be further simplified by masking, avoiding
> an extra branch:
>
> template <typename T> struct CountLeadingZerosImpl<T, 1> {
>    static uint32_t doit(T v) {
>      return __builtin_clz((uint32_t)v & 0xFF) - 24u;
>    }
> };
>
> template <typename T> struct CountLeadingZerosImpl<T, 2> {
>    static uint32_t doit(T v) {
>      return __builtin_clz((uint32_t)v & 0xFFFF) - 16u;
>    }
> };
>
> >
> > ----
> >
> > Taste matter: Windows, 64bit version for x86: You could call your own
> > count_leading_zeros<uint32_t>, instead of calling _BitScanReverse.
>
> Sure.
>
> >
> > ----
> >
> >
> http://cr.openjdk.java.net/~redestad/8234331/open.04/test/hotspot/gtest/utilities/test_powerOfTwo.cpp.html
> >
> > In the test for next_up, can we have, for completeness sake, a test
> > which tests that with any valid input pow2 the result is the next pow2?
> >
> > --- a/test/hotspot/gtest/utilities/test_powerOfTwo.cpp  Thu Dec 05
> > 02:28:58 2019 +0100
> > +++ b/test/hotspot/gtest/utilities/test_powerOfTwo.cpp  Thu Dec 05
> > 11:08:47 2019 +0100
> > @@ -139,6 +139,11 @@
> >       EXPECT_EQ(pow2, next_power_of_2(pow2 - 1))
> >         << "value = " << pow2 - 1;
> >     }
> > +  // next(pow2) should return pow2 * 2
> > +  for (T pow2 = T(1); pow2 < t_max_pow2 / 2; pow2 = pow2 * 2) {
> > +    EXPECT_EQ(pow2 * 2, next_power_of_2(pow2))
> > +      << "value = " << pow2;
> > +  }
>
> Fixed.
>
> I also ran into an issue with use of std::numeric_limit<T>::max()
> causing obscure issues on some platforms at some call sites (*cough*
> Solaris), so I replaced those usages with a portable (but not very
> efficient) version of that in place for the few assert/test uses:
>
> http://cr.openjdk.java.net/~redestad/8234331/open.05
>
> Testing: tier1-3, some ongoing
>
> /Claes
>