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

[Thomas Stüfe]

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
>