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

[Raffaello Giulietti]

On Tue, 29 Apr 2025 15:10:10 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 two additional commits since the last revision:
> 
>  - Adjust the type of operand
>  - Use a more loose formula to do range check
>    
>    Use a more loose formula to do range check, in order not to exclude a priori values that may be inside the supported range

I don't observe any significant difference on my environment

macOS 15.4.1 / M1 Pro / 32 GiB / java 25-internal

before
----

Benchmark                                   Mode  Cnt            Score            Error   Units
BigIntegerPow.testPowL                      avgt    3   7466740027.667 ± 1815231444.569   ns/op
BigIntegerPow.testPowL:gc.alloc.rate        avgt    3         3964.967 ±        970.175  MB/sec
BigIntegerPow.testPowL:gc.alloc.rate.norm   avgt    3  31040625701.333 ±        337.057    B/op
BigIntegerPow.testPowL:gc.count             avgt    3          201.000                   counts
BigIntegerPow.testPowL:gc.time              avgt    3          145.000                       ms
BigIntegerPow.testPowM                      avgt    3   5281109916.667 ± 1387864024.559   ns/op
BigIntegerPow.testPowM:gc.alloc.rate        avgt    3         3718.944 ±        968.869  MB/sec
BigIntegerPow.testPowM:gc.alloc.rate.norm   avgt    3  20592088429.333 ±        337.057    B/op
BigIntegerPow.testPowM:gc.count             avgt    3          135.000                   counts
BigIntegerPow.testPowM:gc.time              avgt    3           98.000                       ms
BigIntegerPow.testPowS                      avgt    3   5195628500.333 ±  738936923.575   ns/op
BigIntegerPow.testPowS:gc.alloc.rate        avgt    3         3758.710 ±        534.778  MB/sec
BigIntegerPow.testPowS:gc.alloc.rate.norm   avgt    3  20477396224.000 ±          0.001    B/op
BigIntegerPow.testPowS:gc.count             avgt    3          135.000                   counts
BigIntegerPow.testPowS:gc.time              avgt    3           94.000                       ms
BigIntegerPow.testPowXL                     avgt    3   8125774666.667 ± 1137294539.763   ns/op
BigIntegerPow.testPowXL:gc.alloc.rate       avgt    3         4120.707 ±        577.639  MB/sec
BigIntegerPow.testPowXL:gc.alloc.rate.norm  avgt    3  35109921325.333 ±        337.057    B/op
BigIntegerPow.testPowXL:gc.count            avgt    3          231.000                   counts
BigIntegerPow.testPowXL:gc.time             avgt    3          161.000                       ms
BigIntegerPow.testPowXS                     avgt    3   4631164917.000 ±  354282119.389   ns/op
BigIntegerPow.testPowXS:gc.alloc.rate       avgt    3         3879.394 ±        297.057  MB/sec
BigIntegerPow.testPowXS:gc.alloc.rate.norm  avgt    3  18839312808.000 ±          0.001    B/op
BigIntegerPow.testPowXS:gc.count            avgt    3          124.000                   counts
BigIntegerPow.testPowXS:gc.time             avgt    3           85.000                       ms


after
----

Benchmark                                   Mode  Cnt            Score            Error   Units
BigIntegerPow.testPowL                      avgt    3   7502352027.667 ± 1599949168.779   ns/op
BigIntegerPow.testPowL:gc.alloc.rate        avgt    3         3946.047 ±        845.736  MB/sec
BigIntegerPow.testPowL:gc.alloc.rate.norm   avgt    3  31040625690.667 ±        337.057    B/op
BigIntegerPow.testPowL:gc.count             avgt    3          202.000                   counts
BigIntegerPow.testPowL:gc.time              avgt    3          143.000                       ms
BigIntegerPow.testPowM                      avgt    3   5269442569.333 ±  869646901.137   ns/op
BigIntegerPow.testPowM:gc.alloc.rate        avgt    3         3724.365 ±        638.773  MB/sec
BigIntegerPow.testPowM:gc.alloc.rate.norm   avgt    3  20578167389.333 ±  439892039.777    B/op
BigIntegerPow.testPowM:gc.count             avgt    3          135.000                   counts
BigIntegerPow.testPowM:gc.time              avgt    3           93.000                       ms
BigIntegerPow.testPowS                      avgt    3   5186210888.667 ±  723686794.493   ns/op
BigIntegerPow.testPowS:gc.alloc.rate        avgt    3         3765.528 ±        523.216  MB/sec
BigIntegerPow.testPowS:gc.alloc.rate.norm   avgt    3  20477396224.000 ±          0.001    B/op
BigIntegerPow.testPowS:gc.count             avgt    3          134.000                   counts
BigIntegerPow.testPowS:gc.time              avgt    3           94.000                       ms
BigIntegerPow.testPowXL                     avgt    3   8153839055.667 ± 1004638585.690   ns/op
BigIntegerPow.testPowXL:gc.alloc.rate       avgt    3         4106.489 ±        506.894  MB/sec
BigIntegerPow.testPowXL:gc.alloc.rate.norm  avgt    3  35109921325.333 ±        337.057    B/op
BigIntegerPow.testPowXL:gc.count            avgt    3          230.000                   counts
BigIntegerPow.testPowXL:gc.time             avgt    3          158.000                       ms
BigIntegerPow.testPowXS                     avgt    3   4588205708.333 ±  312969172.545   ns/op
BigIntegerPow.testPowXS:gc.alloc.rate       avgt    3         3915.690 ±        266.340  MB/sec
BigIntegerPow.testPowXS:gc.alloc.rate.norm  avgt    3  18839312829.333 ±        337.057    B/op
BigIntegerPow.testPowXS:gc.count            avgt    3          123.000                   counts
BigIntegerPow.testPowXS:gc.time             avgt    3           83.000                       ms

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

PR Comment: https://git.openjdk.org/jdk/pull/24690#issuecomment-2839390637