RFR: 8310813: Simplify and modernize equals, hashCode, and compareTo for BigInteger [v2]

[Raffaello Giulietti]

On Mon, 10 Jul 2023 14:39:51 GMT, Raffaello Giulietti <rgiulietti at openjdk.org> wrote:

>> 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));
>>     }
>
> `Comparable.compareTo()` is defined to return a negative, zero, or positive integer, not necessarily -1, 0, 1. Code that depends on specific values like the latter is not robust. That said, I have no clue why `BigInteger.compareTo()`'s spec mentions these specific values.
> 
> As for bit twiddling, I would not make the code less readable, except in highly performance sensitive code.
> 
> (BTW, rather than the `TAB `array above, I would compute the result as: `2 * idx - 1`, or `(idx << 1) - 1` if you don't trust you compiler. But in the end I think branches in modern CPUs are faster than all that twiddling.)

A branchless way to clamp an `int v` to {-1, 0, 1} depending on whether `v < 0`, `v == 0`, or `v > 0` is

(v >> 31) | ((v | -v) >>> 31);

This extends to `long` as well: replace `31` by `63`.

If left uncommented, this is less readable than branches.
In addition, you'd need to measure whether 5 ops are better than 2 branches: you might be surprised ;-)

-------------

PR Review Comment: https://git.openjdk.org/jdk/pull/14630#discussion_r1258420065