Re: RFR: 8188044: We need Math.unsignedMultiplyHigh [v2]

[Andrew Haley]

On 7/2/21 4:30 PM, Raffaello Giulietti wrote:
> FWIW, adinn's branchless code together with
> PR https://git.openjdk.java.net/jdk/pull/4660
> make both methods less vulnerable to timing attacks.

I doubt it, because HotSpot generates conditional select instructions for
the popular systems, at least for C2.

I guess it might on a C1-only or pure interpreter system. That certainly
might be an argument for using the shift-and-add magic. With a comment
that would be fine, as the difference in performance doesn't seem to be
worth worrying about. We're looking at sub-nanosecond throughput.

-- 
Andrew Haley  (he/him)
Java Platform Lead Engineer
Red Hat UK Ltd. 
https://keybase.io/andrewhaley
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671

Re: RFR: 8188044: We need Math.unsignedMultiplyHigh [v2]

[Andrew Dinn]

On 02/07/2021 16:30, Raffaello Giulietti wrote:

FWIW, adinn's branchless code together with
PR https://git.openjdk.java.net/jdk/pull/4660
make both methods less vulnerable to timing attacks.
That was indeed the point of the change. However, I doubt the difference 
in timing is going to be significant given Andrew's micro-benchmark results.


regards,


Andrew Dinn
---
Red Hat Distinguished Engineer
Red Hat UK Ltd
Registered in England and Wales under Company Registration No. 03798903
Directors: Michael Cunningham, Michael ("Mike") O'Neill

Re: RFR: 8188044: We need Math.unsignedMultiplyHigh [v2]

[Raffaello Giulietti]

FWIW, adinn's branchless code together with
PR https://git.openjdk.java.net/jdk/pull/4660
make both methods less vulnerable to timing attacks.


Greetings
Raffaello


On 2021-07-02 15:50, Andrew Haley wrote:

On Fri, 2 Jul 2021 11:06:06 GMT, Andrew Dinn  wrote:


You can also do that branchlessly which might prove better

```
  long result = Math.multiplyHigh(x, y);
  result += (y & (x >> 63));
  result += (x & (y >> 63));
  return result;
```

I doubt very much that it would be better, because these days branch prediction 
is excellent, and we also have conditional select instructions. Exposing the 
condition helps C2 to eliminate it if the range of args is known. The `if` code 
is easier to understand.

Benchmark results, with one of the operands changing signs every iteration, 
1000 iterations:


Benchmark  Mode  Cnt ScoreError  Units
MulHiTest.mulHiTest1   (aph) avgt3  1570.587 ± 16.602  ns/op
MulHiTest.mulHiTest2   (adinn)   avgt3  2237.637 ±  4.740  ns/op

In any case, note that with this optimization the unsigned mulHi is in the 
nanosecond range, so Good Enough. IMO.

-

PR: https://git.openjdk.java.net/jdk/pull/4644

Re: RFR: 8188044: We need Math.unsignedMultiplyHigh [v2]

[Andrew Haley]

On 7/2/21 12:26 PM, Raffaello Giulietti wrote:
> ... or even as a one liner, like in the test
> 
>   return Math.multiplyHigh(x, y) + ((x >> (Long.SIZE - 1)) & y) + ((y >> 
> (Long.SIZE - 1)) & x);

It was hard to write, so it should be hard to read too! :-)

Re: RFR: 8188044: We need Math.unsignedMultiplyHigh [v2]

[Andrew Haley]

On Fri, 2 Jul 2021 13:47:40 GMT, Andrew Haley  wrote:

>> You can also do that branchlessly which might prove better
>> 
>>  long result = Math.multiplyHigh(x, y);
>>  result += (y & (x >> 63));
>>  result += (x & (y >> 63));
>>  return result;
>
>> You can also do that branchlessly which might prove better
>> 
>> ```
>>  long result = Math.multiplyHigh(x, y);
>>  result += (y & (x >> 63));
>>  result += (x & (y >> 63));
>>  return result;
>> ```
> I doubt very much that it would be better, because these days branch 
> prediction is excellent, and we also have conditional select instructions. 
> Exposing the condition helps C2 to eliminate it if the range of args is 
> known. The `if` code is easier to understand.
> 
> Benchmark results, with one of the operands changing signs every iteration, 
> 1000 iterations:
> 
> 
> Benchmark  Mode  Cnt ScoreError  Units
> MulHiTest.mulHiTest1   (aph) avgt3  1570.587 ± 16.602  ns/op
> MulHiTest.mulHiTest2   (adinn)   avgt3  2237.637 ±  4.740  ns/op
> 
> In any case, note that with this optimization the unsigned mulHi is in the 
> nanosecond range, so Good Enough. IMO.

But weirdly, it's the other way around on AArch64, but there's little in it:


Benchmark Mode  Cnt Score   Error  Units
MulHiTest.mulHiTest1  avgt3  1492.108 ± 0.301  ns/op
MulHiTest.mulHiTest2  avgt3  1219.521 ± 1.516  ns/op


but this is only in the case where we have unpredictable branches. Go with 
simple and easy to understand; it doesn't much matter.

-

PR: https://git.openjdk.java.net/jdk/pull/4644

Re: RFR: 8188044: We need Math.unsignedMultiplyHigh [v2]

[Andrew Haley]

On Fri, 2 Jul 2021 11:06:06 GMT, Andrew Dinn  wrote:

> You can also do that branchlessly which might prove better
> 
> ```
>  long result = Math.multiplyHigh(x, y);
>  result += (y & (x >> 63));
>  result += (x & (y >> 63));
>  return result;
> ```
I doubt very much that it would be better, because these days branch prediction 
is excellent, and we also have conditional select instructions. Exposing the 
condition helps C2 to eliminate it if the range of args is known. The `if` code 
is easier to understand.

Benchmark results, with one of the operands changing signs every iteration, 
1000 iterations:


Benchmark  Mode  Cnt ScoreError  Units
MulHiTest.mulHiTest1   (aph) avgt3  1570.587 ± 16.602  ns/op
MulHiTest.mulHiTest2   (adinn)   avgt3  2237.637 ±  4.740  ns/op

In any case, note that with this optimization the unsigned mulHi is in the 
nanosecond range, so Good Enough. IMO.

-

PR: https://git.openjdk.java.net/jdk/pull/4644

Re: RFR: 8188044: We need Math.unsignedMultiplyHigh [v2]

[Raffaello Giulietti]

... or even as a one liner, like in the test

	return Math.multiplyHigh(x, y) + ((x >> (Long.SIZE - 1)) & y) + ((y >> 
(Long.SIZE - 1)) & x);




On 2021-07-02 13:08, Andrew Dinn wrote:

On Fri, 2 Jul 2021 09:39:46 GMT, Andrew Haley  wrote:


src/java.base/share/classes/java/lang/Math.java line 1211:


1209: long z1 = t >>> 32;
1210:
1211: return x1 * y1 + z1 + (z0 >>> 32);


Suggestion:

 long result = Math.multiplyHigh(x, y);
 if (x < 0) result += y;
 if (y < 0) result += x;
 return result;


This is just subtracting the 2's-complement offset. I guess the idea, longer 
term, is that this be an intrinsic anyway, but if you do `unsignedMultiplyHigh` 
this way you'll utilize the existing `multiplyHigh` intrinsic on all platforms 
that have it.


You can also do that branchlessly which might prove better

  long result = Math.multiplyHigh(x, y);
  result += (y & (x >> 63));
  result += (x & (y >> 63));
  return result;

-

PR: https://git.openjdk.java.net/jdk/pull/4644

Re: RFR: 8188044: We need Math.unsignedMultiplyHigh [v2]

[Andrew Dinn]

On Fri, 2 Jul 2021 09:39:46 GMT, Andrew Haley  wrote:

>> src/java.base/share/classes/java/lang/Math.java line 1211:
>> 
>>> 1209: long z1 = t >>> 32;
>>> 1210: 
>>> 1211: return x1 * y1 + z1 + (z0 >>> 32);
>> 
>> Suggestion:
>> 
>> long result = Math.multiplyHigh(x, y);
>> if (x < 0) result += y;
>> if (y < 0) result += x;
>> return result;
>
> This is just subtracting the 2's-complement offset. I guess the idea, longer 
> term, is that this be an intrinsic anyway, but if you do 
> `unsignedMultiplyHigh` this way you'll utilize the existing `multiplyHigh` 
> intrinsic on all platforms that have it.

You can also do that branchlessly which might prove better

 long result = Math.multiplyHigh(x, y);
 result += (y & (x >> 63));
 result += (x & (y >> 63));
 return result;

-

PR: https://git.openjdk.java.net/jdk/pull/4644

Re: RFR: 8188044: We need Math.unsignedMultiplyHigh [v2]

[Andrew Haley]

On Fri, 2 Jul 2021 09:37:47 GMT, Andrew Haley  wrote:

>> Brian Burkhalter has updated the pull request incrementally with one 
>> additional commit since the last revision:
>> 
>>   8188044: Add @see links between multiplyHigh() and unsignedMultiplyHigh().
>
> src/java.base/share/classes/java/lang/Math.java line 1211:
> 
>> 1209: long z1 = t >>> 32;
>> 1210: 
>> 1211: return x1 * y1 + z1 + (z0 >>> 32);
> 
> Suggestion:
> 
> long result = Math.multiplyHigh(x, y);
> if (x < 0) result += y;
> if (y < 0) result += x;
> return result;

This is just subtracting the 2's-complement offset. I guess the idea, longer 
term, is that this be an intrinsic anyway, but if you do `unsignedMultiplyHigh` 
this way you'll utilize the existing `multiplyHigh` intrinsic on all platforms 
that have it.

-

PR: https://git.openjdk.java.net/jdk/pull/4644

Re: RFR: 8188044: We need Math.unsignedMultiplyHigh [v2]

[Andrew Haley]

On Thu, 1 Jul 2021 18:08:22 GMT, Brian Burkhalter  wrote:

>> Please consider this proposal to add a method 
>> `unsignedMultiplyHigh(long,long)` to each of `java.lang.Math` and 
>> `java.lang.StrictMath`.
>
> Brian Burkhalter has updated the pull request incrementally with one 
> additional commit since the last revision:
> 
>   8188044: Add @see links between multiplyHigh() and unsignedMultiplyHigh().

src/java.base/share/classes/java/lang/Math.java line 1211:

> 1209: long z1 = t >>> 32;
> 1210: 
> 1211: return x1 * y1 + z1 + (z0 >>> 32);

Suggestion:

long result = Math.multiplyHigh(x, y);
if (x < 0) result += y;
if (y < 0) result += x;
return result;

-

PR: https://git.openjdk.java.net/jdk/pull/4644

Re: RFR: 8188044: We need Math.unsignedMultiplyHigh [v2]

[Eamonn McManus]

On Thu, 1 Jul 2021 18:08:22 GMT, Brian Burkhalter  wrote:

>> Please consider this proposal to add a method 
>> `unsignedMultiplyHigh(long,long)` to each of `java.lang.Math` and 
>> `java.lang.StrictMath`.
>
> Brian Burkhalter has updated the pull request incrementally with one 
> additional commit since the last revision:
> 
>   8188044: Add @see links between multiplyHigh() and unsignedMultiplyHigh().

Oh right. Then obviously this is the right place for the new method. Sorry for 
the noise.

-

PR: https://git.openjdk.java.net/jdk/pull/4644

Re: RFR: 8188044: We need Math.unsignedMultiplyHigh [v2]

[Brian Burkhalter]

On Thu, 1 Jul 2021 18:08:22 GMT, Brian Burkhalter  wrote:

>> Please consider this proposal to add a method 
>> `unsignedMultiplyHigh(long,long)` to each of `java.lang.Math` and 
>> `java.lang.StrictMath`.
>
> Brian Burkhalter has updated the pull request incrementally with one 
> additional commit since the last revision:
> 
>   8188044: Add @see links between multiplyHigh() and unsignedMultiplyHigh().

Yes, I am aware of those methods on `Long`. We do however already have 
`Math.multiplyHigh()` so adding the new method to `Math` would be consistent.

-

PR: https://git.openjdk.java.net/jdk/pull/4644

Re: RFR: 8188044: We need Math.unsignedMultiplyHigh [v2]

[Eamonn McManus]

On Thu, 1 Jul 2021 18:08:22 GMT, Brian Burkhalter  wrote:

>> Please consider this proposal to add a method 
>> `unsignedMultiplyHigh(long,long)` to each of `java.lang.Math` and 
>> `java.lang.StrictMath`.
>
> Brian Burkhalter has updated the pull request incrementally with one 
> additional commit since the last revision:
> 
>   8188044: Add @see links between multiplyHigh() and unsignedMultiplyHigh().

`Long` already has some unsigned arithmetic methods: `divideUnsigned`, 
`compareUnsigned`, `toUnsignedString`. `Math` doesn't. Would it make more sense 
to add the new method to `Long`? That would also avoid the quirk of having 
distinct methods in `Math` and `StringMath` when the numbers in involved are 
integers.

-

PR: https://git.openjdk.java.net/jdk/pull/4644

Re: RFR: 8188044: We need Math.unsignedMultiplyHigh [v2]

[Brian Burkhalter]

> Please consider this proposal to add a method 
> `unsignedMultiplyHigh(long,long)` to each of `java.lang.Math` and 
> `java.lang.StrictMath`.

Brian Burkhalter has updated the pull request incrementally with one additional 
commit since the last revision:

  8188044: Add @see links between multiplyHigh() and unsignedMultiplyHigh().

-

Changes:
  - all: https://git.openjdk.java.net/jdk/pull/4644/files
  - new: https://git.openjdk.java.net/jdk/pull/4644/files/df884569..0a8fec63

Webrevs:
 - full: https://webrevs.openjdk.java.net/?repo=jdk=4644=01
 - incr: https://webrevs.openjdk.java.net/?repo=jdk=4644=00-01

  Stats: 5 lines in 2 files changed: 5 ins; 0 del; 0 mod
  Patch: https://git.openjdk.java.net/jdk/pull/4644.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/4644/head:pull/4644

PR: https://git.openjdk.java.net/jdk/pull/4644