RFR: 8355719: Reduce memory consumption of BigInteger.pow() [v51]

[Raffaello Giulietti]

On Wed, 7 May 2025 15:03:36 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> This PR optimizes `BigInteger.pow(int)` method. The primary enhancement in `pow()` is not concerned most on execution time, but rather in memory optimization, because the PR implementation does the "shift of the exponent" squaring the result rather than the base, so the base is not squared like in the current implementation, and this permits to save about half of the memory.
>
> fabioromano1 has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Removed needless brackets

src/java.base/share/classes/java/math/BigInteger.java line 2607:

> 2605: 
> 2606:         BigInteger base = this.abs();
> 2607:         final boolean negative = signum < 0 && (exponent & 1) == 1;

Some effectively final locals are declared `final`, while others are not.

src/java.base/share/classes/java/math/BigInteger.java line 2643:

> 2641:                     : new BigInteger(result, newSign).shiftLeft(bitsToShift);
> 2642:         } else {
> 2643:             if ((bitLength() - 1L) * exponent >= (long) MAX_MAG_LENGTH << 5) {

Suggestion:

            if ((bitLength() - 1L) * exponent >= 32L * MAX_MAG_LENGTH) {

or
Suggestion:

            if ((bitLength() - 1L) * exponent >= (long) Integer.SIZE * MAX_MAG_LENGTH) {


Both variant are easier to read, more honest, and exactly as efficient as with the shift. The right-hand sides are compile-time constants, so they have no impact on runtime performance.

More generally, the runtime compilers are perfectly capable to optimize multiplications by constant powers of 2 and replace them with shifts, even if the other operand is not a constant.

test/micro/org/openjdk/bench/java/math/BigIntegerPow.java line 74:

> 72:          * Each array entry is atmost 64 bits
> 73:          * in size
> 74:          */

These should probably be part of the declarations:

private int xsExp = (1 << 20) - 1;
private BigInteger[] xsArray = new BigInteger[TESTSIZE];  // Each array entry is atmost 64 bits in size


Similarly for the other fields.

-------------

PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2077924006
PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2077942835
PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2077949298