RFR: 8203352: Improve java implementation of Integer/Long.numberOfLeadingZeros

[Ivan Gerasimov]

On 5/18/18 10:47 AM, Ivan Gerasimov wrote:
> Hi Claes!
>
>
> On 5/18/18 3:51 AM, Claes Redestad wrote:
>> Hi,
>>
>> while there are C2 intrinsics on most platforms providing access to 
>> specialized hardware instructions, e.g., lzcnt on Intel, optimizing 
>> the java implementations of Integer/Long.numberOfLeadingZeros can 
>> still be worthwhile, especially if it also helps C1 and implicitly 
>> startup/warmup. This implementation wins slightly (5-25%) over the 
>> baseline in all tested optimization modes (-Xint, 
>> -XX:TieredStopAtLevel=1-3), as well as on C2 if the intrinsics are 
>> disabled.
>>
>> Webrev: http://cr.openjdk.java.net/~redestad/8203352/open.00/
>>
>> Bug: https://bugs.openjdk.java.net/browse/JDK-8203352
>>
>> Correctness is checked by existing tests, mainly 
>> test/jdk/java/lang/Integer|Long/BitTwiddle.java
>>
> I think the Long version needs some adjustment.
> The old code correctly handled the case when 32nd bit is the highest 
> bit set.
> However, the in the new code such a value will be cast to a negative 
> int, and all the checks at lines 1774-1777 will fail.
>
> We may want to add such test case to the existing tests.
>
One possible implementation may be as following:

     public static int numberOfLeadingZeros(long i) {
         // HD, Count leading 0's
         int n = 63;
         int x = (int)(i >>> 32);
         if (x == 0) {
             x = (int)i;
         } else {
             n -= 32;
         }
         if (x <= 0)
             return x == 0 ? 64 : n - 31;
         if (x >= 1 << 16) { n -= 16; x >>>= 16; }
         if (x >= 1 <<  8) { n -=  8; x >>>=  8; }
         if (x >= 1 <<  4) { n -=  4; x >>>=  4; }
         if (x >= 1 <<  2) { n -=  2; x >>>=  2; }
         return n - (x >>> 1);
     }

Comparing to the base line, it is expected to be slightly slower for 
non-positive longs.
However for positive numbers it may be a tiny-bit faster because we 
replace long-comparison with int-comparison :)

Another approach may be to just delegate to 
Integer.numberOfLeadingZeros() like this:

     public static int numberOfLeadingZeros(long i) {
         int x = (int)(i >>> 32);
         return x == 0 ? 32 + Integer.numberOfLeadingZeros((int)i)
                 : Integer.numberOfLeadingZeros(x);
     }

By the way, is it possible that we have an intrinsic for 
Integer.numberOfLeadingZeros, but not for Long.numberOfLeadingZeros on 
some platform?
If yes, then the later variant may be preferable.

With kind regards,
Ivan

> With kind regards,
> Ivan
>
>> /Claes
>>
>>
>

-- 
With kind regards,
Ivan Gerasimov