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

[Thomas Stüfe]

p.s. I think it would be good to have some gtests for these functions,
especially to test corner cases.

Cheers, Thomas

On Thu, Nov 28, 2019 at 8:34 AM Thomas Stüfe <thomas.stuefe at gmail.com>
wrote:

> Hi Claes,
>
> I think this is useful. Why not a 64bit variant too? If you do not want to
> go through the hassle of providing a count_leading_zeros(uint64_t), you
> could call the 32bit variant twice and take care of endianness for the
> caller.
>
> --
>
> In inline int32_t next_power_of_two(int32_t value) , should we weed out
> negative input values right away instead of asserting at the end of the
> function?
>
> --
>
> The functions will always return the next power of two, even if the input
> is a power of two - e.g. "2" for "1". Is that intended? It would be nice to
> have an API comment in the header describing these corner cases (what
> happens for negative input, what happens if input is power 2).
>
> --
>
> The patch can cause subtle differences in some caller code, I think, if
> input value is a power of 2 already. See e.g:
>
>
> http://cr.openjdk.java.net/~redestad/8234331/open.01/src/hotspot/share/libadt/dict.cpp.udiff.html
>
> -  i=16;
> -  while( i < size ) i <<= 1;
> +  i = MAX2(16, (int)next_power_of_two(size));
>
> If i == size == 16, old code would keep i==16, new code would come to
> i==32, I think.
>
>
> http://cr.openjdk.java.net/~redestad/8234331/open.01/src/hotspot/share/opto/phaseX.cpp.udiff.html
>
>
>  //------------------------------round_up---------------------------------------
>  // Round up to nearest power of 2
> -uint NodeHash::round_up( uint x ) {
> -  x += (x>>2);                  // Add 25% slop
> -  if( x <16 ) return 16;        // Small stuff
> -  uint i=16;
> -  while( i < x ) i <<= 1;       // Double to fit
> -  return i;                     // Return hash table size
> +uint NodeHash::round_up(uint x) {
> +  x += (x >> 2);                  // Add 25% slop
> +  return MAX2(16U, next_power_of_two(x));
>  }
>
> same here. If x == 16, before we'd return 16, now 32.
>
> ---
>
>
> http://cr.openjdk.java.net/~redestad/8234331/open.01/src/hotspot/share/runtime/threadSMR.cpp.udiff.html
>
> I admit I do not understand the current coding :) I do not believe it
> works for all input values, e.g. were
> get_java_thread_list()->length()==1025, we'd get 1861 - if I am not
> mistaken. Your code is definitely clearer but not equivalent to the old one.
>
> ---
>
> In the end, I wonder whether we should have two kind of APIs, or a
> parameter, distinguishing between "next power of 2" and "next power of 2
> unless input value is already power of 2".
>
> Cheers, Thomas
>
>
>
>
>
> On Tue, Nov 26, 2019 at 10:42 AM Claes Redestad <claes.redestad at oracle.com>
> wrote:
>
>> Hi,
>>
>> in various places in the hotspot we have custom code to calculate the
>> next power of two, some of which have potential to go into an infinite
>> loop in case of an overflow.
>>
>> This patch proposes adding next_power_of_two utility methods which
>> avoid infinite loops on overflow, while providing slightly more
>> efficient code in most cases.
>>
>> Bug:    https://bugs.openjdk.java.net/browse/JDK-8234331
>> Webrev: http://cr.openjdk.java.net/~redestad/8234331/open.01/
>>
>> Testing: tier1-3
>>
>> Thanks!
>>
>> /Claes
>>
>