On Mon, 26 Jun 2023 14:42:11 GMT, Raffaello Giulietti <[email protected]>
wrote:
>> Thanks for looking at this. My reply to both of your comments, is that there
>> are further improvements possible, and I'd be happy to explore such
>> possibilities later. Right now I'm more concerned with `hashCode` and
>> possible performance degradation, which my local benchmarks on arm64 showed
>> approx. 10%.
>>
>> On your signum suggestion: signum of 0 is what makes that suggestion
>> inapplicable.
>
> Yep, you're right.
Back to your two suggestions, Raffaello. On the one hand, I think it's hard to
beat the readability of `?:`. On the other hand, such comparison is
performance-sensitive and is a pattern in BigInteger. So we might as well
extract it into a private utility method whose initial version could look like
this:
static int compareUnequal(int x, int y) {
return x > y ? 1 : -1;
}
That method has a clear name and returns only guaranteed values. (You were
right about being on the safe side with `Integer.compareUnsigned(x, y)`. Look
at its `Byte` cousin, who was a similarly-worded spec but does not only return
-1, 0, 1:
public static int compareUnsigned(byte x, byte y) {
return Byte.toUnsignedInt(x) - Byte.toUnsignedInt(y);
}
.)
Then someone experienced in bit-twiddling could probably take it from there and
produce a branchless comparison, which will be fast, but likely far from
readable or obvious.
I'm not experienced in bit-twiddling, but probably there are some
simplifications to that naive solution one could come up from quickly glancing
into "Hacker's Delight":
private final static int[] TAB = new int[]{-1, 1};
public static int compareUnequal(int x, int y) {
// In HD, 3-valued compare function:
// * outputs 0 and 1, but we need -1 and 1
// * might not be taking advantage of the fact that x != y
int idx = (c(y, x) - c(x, y)) >>> 31;
return TAB[idx];
}
private static int c(int x, int y) {
return (x - y) ^ ((x ^ y) & ((x - y) ^ x));
}
-------------
PR Review Comment: https://git.openjdk.org/jdk/pull/14630#discussion_r1258298626
