On Mon, 10 Jul 2023 14:39:51 GMT, Raffaello Giulietti <[email protected]>
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
