On Sun, 11 Oct 2026 07:03:57 GMT, Shawn Emery <[email protected]> wrote:
>> Currently, P-384 field operations use 14x28-bit limbs. The efficiency of >> these operations vastly improve by using a 7x55-bit limb configuration. >> Performance gains yield 32% to 52% for Java alone: >> >> AArch64: >> Key pair generation - P-384: +51% >> Key agreement - P-384: +51% >> >> Key pair generation - secP384r1MLKEM1024: +50% >> KEM decapsulation - secP384r1MLKEM1024: +49% >> KEM encapsulation - secP384r1MLKEM1024: +52% >> >> x86_64: >> Key pair generation - P-384: +35% >> Key agreement - P-384: +35% >> >> Key pair generation - secP384r1MLKEM1024: +32% >> KEM decapsulation - secP384r1MLKEM1024: +32% >> KEM encapsulation - secP384r1MLKEM1024: +33% >> >> --------- >> - [X] I confirm that I make this contribution in accordance with the >> [OpenJDK Interim AI Policy](https://openjdk.org/legal/ai). > > Shawn Emery has updated the pull request incrementally with one additional > commit since the last revision: > > Improve x86_64 performance by 13% There are a couple of 'math' places I am still unsure, getting there, but if you got comments to help me along.. Also want to do a bit more targeted fuzzing with 'numbers designed with malice of forethought' (mostly to cause carries :) ) src/java.base/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP384.java line 32: > 30: private static final int BITS_PER_LIMB = 55; > 31: private static final int NUM_LIMBS = 7; > 32: private static final int MAX_ADDS = 2; I think MAX_ADDS should be 9, but I cant seem to prove it with fuzzing at least.. (I think you should be able to do more then 2 Additions/Subtractions before a multiply, you have 9 bits for overflow with a 64-bit multiplier. But need to think how that flows through, unless you already did) src/java.base/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP384.java line 43: > 41: } > 42: > 43: private static BigInteger evaluateModulus() { checked src/java.base/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP384.java line 63: > 61: */ > 62: @Override > 63: protected void carry(long[] limbs, int start, int end) { checked src/java.base/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP384.java line 80: > 78: */ > 79: @Override > 80: protected void carry(long[] limbs) { checked src/java.base/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP384.java line 114: > 112: * @param i [in] the limbs to reduce from. > 113: */ > 114: protected void reduceIn(long[] limbs, long v, int i) { good. (128, 96, -32, 1; across digits to line up to 55) src/java.base/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP384.java line 131: > 129: * @param limbs [in|out] the limbs to fully carry and reduce. > 130: */ > 131: protected void finalCarryReduceLast(long[] limbs) { similar to reduceIn, except i position hardcoded. (though.. why off by one bit?) src/java.base/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP384.java line 150: > 148: * @param c0..c13 [in] the limbs to be reduced > 149: */ > 150: private void carryReduceUpper(long[] r, long c0, long c1, long c2, > long c3, the shape of this looks correct. (this is essentially reduceIn as called by IntegerPolynomial.reduceHigh: for (int i = limbs.length - 1; i >= numLimbs; i--) { reduceIn(limbs, limbs[i], i); Though. Another interesting puzzle.. 55->64 bits.. you can do ~9 adds before needing carry propagation.. that seems a lot.. but with reduceIn you have i-6 x3 per each digit, so does it mean you need to do a carry propagation part-way through? (-7 and -5 twice, but seems like -6 is more likely to show up..) This might not be the case that my current fuzzing caught, need to do some targeted testing src/java.base/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP384.java line 230: > 228: * @param r [out] the product of the limbs operands that is fully > reduced. > 229: */ > 230: protected void mult(long[] a, long[] b, long[] r) { checked. (on a sidenote: I was disappointed at our loop optimizer.. this is exactly the sort of thing it should had detected? Perhaps there is a good reason why we need to bother unrolling this manually, because it does nothing for readability. But perf gain is surprisingly big for doing something the compiler should know how to do) src/java.base/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP384.java line 587: > 585: carry = (c5 + CARRY_ADD) >> BITS_PER_LIMB; > 586: c5 -= carry << BITS_PER_LIMB; > 587: c6 += carry; This is another Math question really.. (and a bit circular, but) wont c6 += carry; potentially produce a carry into c7 again? I often concluded my functions with {underflow, R2} = R - P.. and if there is an underflow, return R.. return R2 otherwise (no conditional but underflow is an easy mask). But that only works when you are not sure about 1 bit overflow But it has been a few years since I reasoned that out. And I notice carryReduce0 also starts from 'last two columns, then reduceIn carry, then propagate the rest.. Maybe its a matter of writing it out with ranges to prove that with max range wont happen? src/java.base/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP384.java line 677: > 675: > 676: // Reduce single high-order limb before reduce/carry the rest > 677: reduceIn(a, dd0, 7); nice! much smaller reduction. src/java.base/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP384.java line 736: > 734: > 735: c0 = d0; > 736: c1 = (d1 << 1) + dd0; good. easy to verify, looks like multiply except with this extra shift/double ------------- PR Review: https://git.openjdk.org/jdk/pull/33193#pullrequestreview-5566365475 PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4310687166 PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4309884257 PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4309886807 PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4309892726 PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4310386798 PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4310398104 PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4310684224 PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4310448404 PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4310557706 PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4310656161 PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4310682043
