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

[Claes Redestad]

On 2019-12-04 03:28, John Rose wrote:
> On Dec 3, 2019, at 3:38 PM, Claes Redestad <claes.redestad at oracle.com 
> <mailto:claes.redestad at oracle.com>> wrote:
>>
>> http://cr.openjdk.java.net/~redestad/8234331/open.03
> 
> Nice work!

Thanks!

> 
> A few minor complaints follow:
> 
> I’m not totally comfortable with the proliferation of tiny header files.
> Are we crashing from one extreme (globalDefinitions.hpp) toward the
> other (usefulZeroConstant.hpp)?  So having count_leading_zeros.hpp
> is arguably a correction, but then adding powerOfTwo.hpp feels like
> an over-correction.  To be followed by more over-corrections:
> count_trailing_zeroes.hpp, populationCount.hpp, and so on.
> 
> You won’t be surprised to hear that I think this would be excessive
> splitting, and that a lumpier outcome would feel better to me, as a
> successor to the chaos globalDefinitions.hpp.  I propose putting
> anything involving integral bitmask operations into intBitmasks.hpp,
> including today’s count_trailing_zeroes.hpp and all the new stuff
> that will be like it.  Start by renaming count_trailing_zeroes.hpp and
> rolling the new stuff into it.  I can wait for this, but I’m going to 
> grumble
> some more if we keep going down this road to TinyHeaderVille.

I hear microservices is all the rage these days. :-)

I can agree that one-header-per-logical-function would become excessive,
but I think organizing functions into more logical units needs to be 
done iteratively as patterns emerge.

> 
> This particular code :
> +    if (high != 0) {
> +      _BitScanReverse(&index, x);
> +    } else {
> +      _BitScanReverse(&index, x);
> +      index += 32;
> +    }
> 
> is clearly untested, since it’s wrong. The `index+=32` belongs on the other
> branch.  (Or is it me?) 

You're both right and wrong: yes, this block is untested (we don't have
32-bit Windows builds in our test system). And the code is/was wrong,
since the statement in the first branch should read:

_BitScanReverse(&index, high); // high, not x

However, the += 32 is in the right place: when the upper 32-bit word of
a 64-bit is non-zero, the number of leading zeros is in the [0-31] 
range, but if it's in the lower 32-bit word the number of leading zeros 
is in the [32-63] range. _BitScanReverse only operates on a 32-bit int.

> The root cause of this is the needless obfuscation
> of the `index ^= 31` and `index ^= 63`.  Really??  Just say `31 - index` and
> `63 - index`, and the arithmetic reasoning will take care of itself.

I agree this is a bit obscure (a habit I probably picked up from 
Hacker's Delight and other sources), and will go with 31u|63u - index.

> 
> In the new code, `assert(lz > …)` and `assert(lz < …)` statements are in an
> unpredictable relative order, making it harder to compare and contrast the
> four versions.  Suggest putting the < before the > case more regularly.

Fixed.

> 
> To `next_power_of_2` I suggest adding an assert that the increment
> will not overflow.  The asserts won't catch `next_power_of_2(max_jint)`,
> not for sure.

Yes, adding a check for the max value should be sufficient, since other
overflows are asserted against in round_up:

assert(value != std::numeric_limits<T>::max(), "Overflow");

Updating in place and rerunning gtests on all platforms.

Thanks!

/Claes
> 
> — John B. Twiddler
>