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

[Raffaello Giulietti]

On Mon, 10 Jul 2023 13:48:34 GMT, Pavel Rappo <prappo at openjdk.org> wrote:

>> 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));
>     }

`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.)

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

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