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

[Pavel Rappo]

On Mon, 26 Jun 2023 14:42:11 GMT, Raffaello Giulietti <rgiulietti at openjdk.org> 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