RFR: 8257815: Replace global log2 functions with efficient implementations

[Claes Redestad]

Hi Kim,

On 2020-12-08 02:43, Kim Barrett wrote:
>> On Dec 7, 2020, at 8:18 PM, Kim Barrett <kbarrett at openjdk.java.net> wrote:
>>
>> On Mon, 7 Dec 2020 12:00:48 GMT, Claes Redestad <redestad at openjdk.org> wrote:
>>
>>> Naming is hard, but I think the following scheme is reasonable:
>>>
>>>     * log2i: any integral type. 0-hostile
>>
>> Not yet a review, but the "usual" name is "ilog2".  Do a web search for that and you'll find lots of relevant hits.  I like the short name having the non-zero precondition.  Whether the longer version that tests for zero carry's it's weight is a question.
> 
> I think the approach to dealing with negative values should be reconsidered.

I kind of agree, but...

> 
> ------------------------------------------------------------------------------
> src/hotspot/share/utilities/powerOfTwo.hpp
>   49 // Log2 of any integral value, i.e., largest i such that 2^i <= x
>   50 // Precondition: x != 0
>   51 // For negative values this will return 63 for 64-bit types, 31 for
>   52 // 32-bit types, and so on.
>   
> I think the behavior for negative values here is wrong. The precondition
> should be x > 0.  That flows through into the implementation.  This also
> affects the design around the proposed _allow_zero function.
> 
> ------------------------------------------------------------------------------
> src/hotspot/share/utilities/powerOfTwo.hpp
>   80 inline int exact_log2(intptr_t value) {
>   81   return exact_log2i(value);
>   82 }
> 
> This is widening the domain to include negative values, which were
> previously excluded since it had is_power_of_2 as a precondition, and that
> function is false for negative values.  I think the old behavior is correct
> and the change is not.
> 
> ------------------------------------------------------------------------------
> 

I think you misread slightly: the behavior of the pre-existing code *is*
to similarly treat signed values as unsigned wrt checking power_of_2:

inline int exact_log2(intptr_t x) {
   assert(is_power_of_2((uintptr_t)x), "x must be a power of 2: " 
INTPTR_FORMAT, x);
   ...

inline int exact_log2_long(jlong x) {
   assert(is_power_of_2((julong)x), "x must be a power of 2: " 
JLONG_FORMAT, x);

exact_log2i does an equivalent check. So unless I'm misreading the
context I'm _preserving_ this behavior.

I agree we could opt for a stricter precondition in the new method
(exact_ilog2?), while retrofitting exact_log/exact_log2_long to be
backwards compatible w.r.t. accepting signed values that turn into
0x8000... when cast to unsigned. I think we should then follow-up
and remove exact_log2/-_long.

WDYT?

/Claes