On Mon, 10 Jul 2023 13:48:34 GMT, Pavel Rappo <pra...@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
