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
