On Mon, 19 Oct 2026 05:46:00 GMT, Volodymyr Paprotski <[email protected]>
wrote:
>> Shawn Emery has updated the pull request incrementally with one additional
>> commit since the last revision:
>>
>> Improve x86_64 performance by 13%
>
> 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)
Projective point addition can increase `numAdds` up to 4 before multiplication,
however, there is no performance gains when setting MAX_ADDS > 2 when
performing P-384 key generation and key agreement.
> 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?)
`finalCarryReduceLast` folds back into the low-order limbs [0..3] from 2^384,
whereas the other high-order reductions start from limb 7, at 2^385, which is
why you see a one bit difference in shifts.
> 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
No intermediate carries are required when folding the upper 7 limbs as the
associated operations are performing left shifts while masking 55 bits and the
others are right shifts. In addition (no pun intended), MAX_ADDS is set to 2,
so there would be at most two pending additions before performing
multiplication and squaring operations.
> 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)
I don't have the numbers for performance gains when unrolling here, but I can
run them unless you already have.
> 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?
You are correct, there could still be excessive bits in limb 6 caused by a limb
5 carry. However, for P-384 EC call sequences, |limb 6| value would still be
less than 2^55 after `carryReduce`. After projective point addition,
`numAdds` could reach 4, where the |limb 6| value would be bounded to less than
2^59. Multiplication and squaring reduce their inputs when `numAdds` exceeds
2. In addition, during canonicalization, `finalReduce` is called to remove
excessive bits from the high-order limb. Arbitrary `setSum()` invocations
could overflow longs, but the scope of call paths here are for P-384 EC
operations as opposed to a general API.
> 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.
Haha, thank you for noticing!
> 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
Yes, this technique gained about 16% performance improvements for high-level
operations.
-------------
PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4323098997
PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4323092666
PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4323098136
PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4323094281
PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4323094915
PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4323096314
PR Review Comment: https://git.openjdk.org/jdk/pull/33193#discussion_r4323097066
