RFR: 8188044: We need Math.unsignedMultiplyHigh
Please consider this proposal to add a method `unsignedMultiplyHigh(long,long)` to each of `java.lang.Math` and `java.lang.StrictMath`. ------------- Commit messages: - 8188044: We need Math.unsignedMultiplyHigh Changes: https://git.openjdk.java.net/jdk/pull/4644/files Webrev: https://webrevs.openjdk.java.net/?repo=jdk&pr=4644&range=00 Issue: https://bugs.openjdk.java.net/browse/JDK-8188044 Stats: 72 lines in 3 files changed: 62 ins; 0 del; 10 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
On Wed, 30 Jun 2021 23:13:06 GMT, Brian Burkhalter <bpb@openjdk.org> wrote:
Please consider this proposal to add a method `unsignedMultiplyHigh(long,long)` to each of `java.lang.Math` and `java.lang.StrictMath`.
This PR does not address intrinsics for the proposed method; that aspect can be handled subsequently. ------------- PR: https://git.openjdk.java.net/jdk/pull/4644
On Wed, 30 Jun 2021 23:13:06 GMT, Brian Burkhalter <bpb@openjdk.org> wrote:
Please consider this proposal to add a method `unsignedMultiplyHigh(long,long)` to each of `java.lang.Math` and `java.lang.StrictMath`.
Looks good. ------------- Marked as reviewed by rriggs (Reviewer). PR: https://git.openjdk.java.net/jdk/pull/4644
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&pr=4644&range=01 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=4644&range=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
On Thu, 1 Jul 2021 18:08:22 GMT, Brian Burkhalter <bpb@openjdk.org> 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
On Thu, 1 Jul 2021 18:08:22 GMT, Brian Burkhalter <bpb@openjdk.org> 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
On Thu, 1 Jul 2021 18:08:22 GMT, Brian Burkhalter <bpb@openjdk.org> 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
On Thu, 1 Jul 2021 18:08:22 GMT, Brian Burkhalter <bpb@openjdk.org> 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
On Fri, 2 Jul 2021 09:37:47 GMT, Andrew Haley <aph@openjdk.org> 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
On Fri, 2 Jul 2021 09:39:46 GMT, Andrew Haley <aph@openjdk.org> 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
... 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 <aph@openjdk.org> 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;
-------------
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! :-)
On Fri, 2 Jul 2021 11:06:06 GMT, Andrew Dinn <adinn@openjdk.org> 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 Score Error Units MulHiTest.mulHiTest1 (aph) avgt 3 1570.587 ± 16.602 ns/op MulHiTest.mulHiTest2 (adinn) avgt 3 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
On Fri, 2 Jul 2021 13:47:40 GMT, Andrew Haley <aph@openjdk.org> 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 Score Error Units MulHiTest.mulHiTest1 (aph) avgt 3 1570.587 ± 16.602 ns/op MulHiTest.mulHiTest2 (adinn) avgt 3 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 avgt 3 1492.108 ± 0.301 ns/op MulHiTest.mulHiTest2 avgt 3 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
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 <adinn@openjdk.org> 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 Score Error Units MulHiTest.mulHiTest1 (aph) avgt 3 1570.587 ± 16.602 ns/op MulHiTest.mulHiTest2 (adinn) avgt 3 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.
-------------
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
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://www.redhat.com> https://keybase.io/andrewhaley EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
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: Use multiplyHigh() to gleverage the inverage the intrinsic ------------- Changes: - all: https://git.openjdk.java.net/jdk/pull/4644/files - new: https://git.openjdk.java.net/jdk/pull/4644/files/0a8fec63..2ad5e395 Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk&pr=4644&range=02 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=4644&range=01-02 Stats: 20 lines in 2 files changed: 9 ins; 5 del; 6 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
Please consider this proposal to add a method `unsignedMultiplyHigh(long,long)` to each of `java.lang.Math` and `java.lang.StrictMath`.
Brian Burkhalter has refreshed the contents of this pull request, and previous commits have been removed. The incremental views will show differences compared to the previous content of the PR. The pull request contains one new commit since the last revision: 8188044: Use multiplyHigh() to leverage the intrinsic ------------- Changes: - all: https://git.openjdk.java.net/jdk/pull/4644/files - new: https://git.openjdk.java.net/jdk/pull/4644/files/2ad5e395..a499b2e5 Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk&pr=4644&range=03 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=4644&range=02-03 Stats: 0 lines in 0 files changed: 0 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
On Fri, 2 Jul 2021 16:37:21 GMT, Brian Burkhalter <bpb@openjdk.org> 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 refreshed the contents of this pull request, and previous commits have been removed. The incremental views will show differences compared to the previous content of the PR. The pull request contains one new commit since the last revision:
8188044: Use multiplyHigh() to leverage the intrinsic
Marked as reviewed by aph (Reviewer). ------------- PR: https://git.openjdk.java.net/jdk/pull/4644
On Fri, 2 Jul 2021 16:41:16 GMT, Brian Burkhalter <bpb@openjdk.org> 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 refreshed the contents of this pull request, and previous commits have been removed. The incremental views will show differences compared to the previous content of the PR.
Marked as reviewed by darcy (Reviewer). ------------- PR: https://git.openjdk.java.net/jdk/pull/4644
On Wed, 30 Jun 2021 23:13:06 GMT, Brian Burkhalter <bpb@openjdk.org> wrote:
Please consider this proposal to add a method `unsignedMultiplyHigh(long,long)` to each of `java.lang.Math` and `java.lang.StrictMath`.
This pull request has now been integrated. Changeset: ca4bea46 Author: Brian Burkhalter <bpb@openjdk.org> URL: https://git.openjdk.java.net/jdk/commit/ca4bea466581217cae2278c98c0fdc568c04... Stats: 81 lines in 3 files changed: 71 ins; 0 del; 10 mod 8188044: We need Math.unsignedMultiplyHigh Reviewed-by: rriggs, aph, darcy ------------- PR: https://git.openjdk.java.net/jdk/pull/4644
participants (9)
-
Andrew Dinn
-
Andrew Dinn
-
Andrew Haley
-
Andrew Haley
-
Brian Burkhalter
-
Eamonn McManus
-
Joe Darcy
-
Raffaello Giulietti
-
Roger Riggs