RFR: 8355719: Reduce memory consumption of BigInteger.pow() [v46]
Raffaello Giulietti
rgiulietti at openjdk.org
Tue Apr 29 17:02:49 UTC 2025
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 must have screwed up something in my previous benchmarks, probably when copying the master branch (current) `BigInteger` into the PR branch for the "before" figures.
Here's indeed a more favorable picture (but certainly not a 50% enhancement in allocation rate).
I obtain comparable results with more iterations (`make test TEST="micro:java.math.BigIntegerPow" MICRO="WARMUP_ITER=3;ITER=3;OPTIONS=-prof gc"`).
I'll delete my previous misleading results.
Sorry for the noise.
macOS 15.4.1 / M1 Pro / 32 GiB / java 25-internal
_before_
Benchmark Mode Cnt Score Error Units
BigIntegerPow.testPowL avgt 3 7828857180.333 ± 723831405.464 ns/op
BigIntegerPow.testPowL:gc.alloc.rate avgt 3 4766.633 ± 440.607 MB/sec
BigIntegerPow.testPowL:gc.alloc.rate.norm avgt 3 39130646080.000 ± 0.001 B/op
BigIntegerPow.testPowL:gc.count avgt 3 260.000 counts
BigIntegerPow.testPowL:gc.time avgt 3 190.000 ms
BigIntegerPow.testPowM avgt 3 7784905013.667 ± 751070238.685 ns/op
BigIntegerPow.testPowM:gc.alloc.rate avgt 3 4737.671 ± 455.843 MB/sec
BigIntegerPow.testPowM:gc.alloc.rate.norm avgt 3 38674111834.667 ± 337.057 B/op
BigIntegerPow.testPowM:gc.count avgt 3 257.000 counts
BigIntegerPow.testPowM:gc.time avgt 3 192.000 ms
BigIntegerPow.testPowS avgt 3 7615946041.333 ± 505408224.968 ns/op
BigIntegerPow.testPowS:gc.alloc.rate avgt 3 4622.726 ± 306.660 MB/sec
BigIntegerPow.testPowS:gc.alloc.rate.norm avgt 3 36917399656.000 ± 0.001 B/op
BigIntegerPow.testPowS:gc.count avgt 3 246.000 counts
BigIntegerPow.testPowS:gc.time avgt 3 184.000 ms
BigIntegerPow.testPowXL avgt 3 7806063305.667 ± 841981680.300 ns/op
BigIntegerPow.testPowXL:gc.alloc.rate avgt 3 4795.153 ± 515.480 MB/sec
BigIntegerPow.testPowXL:gc.alloc.rate.norm avgt 3 39249581269.333 ± 337.057 B/op
BigIntegerPow.testPowXL:gc.count avgt 3 261.000 counts
BigIntegerPow.testPowXL:gc.time avgt 3 194.000 ms
BigIntegerPow.testPowXS avgt 3 6613315027.667 ± 330610647.532 ns/op
BigIntegerPow.testPowXS:gc.alloc.rate avgt 3 4254.182 ± 212.492 MB/sec
BigIntegerPow.testPowXS:gc.alloc.rate.norm avgt 3 29501518834.667 ± 337.057 B/op
BigIntegerPow.testPowXS:gc.count avgt 3 197.000 counts
BigIntegerPow.testPowXS:gc.time avgt 3 147.000 ms
_after_
Benchmark Mode Cnt Score Error Units
BigIntegerPow.testPowL avgt 3 7366544708.333 ± 829671998.680 ns/op
BigIntegerPow.testPowL:gc.alloc.rate avgt 3 4018.527 ± 452.726 MB/sec
BigIntegerPow.testPowL:gc.alloc.rate.norm avgt 3 31040625690.667 ± 337.057 B/op
BigIntegerPow.testPowL:gc.count avgt 3 201.000 counts
BigIntegerPow.testPowL:gc.time avgt 3 138.000 ms
BigIntegerPow.testPowM avgt 3 5185182639.000 ± 115159325.868 ns/op
BigIntegerPow.testPowM:gc.alloc.rate avgt 3 3784.654 ± 158.695 MB/sec
BigIntegerPow.testPowM:gc.alloc.rate.norm avgt 3 20578167389.333 ± 439891534.193 B/op
BigIntegerPow.testPowM:gc.count avgt 3 135.000 counts
BigIntegerPow.testPowM:gc.time avgt 3 89.000 ms
BigIntegerPow.testPowS avgt 3 5129524208.333 ± 622597661.429 ns/op
BigIntegerPow.testPowS:gc.alloc.rate avgt 3 3807.115 ± 460.287 MB/sec
BigIntegerPow.testPowS:gc.alloc.rate.norm avgt 3 20477396202.667 ± 337.057 B/op
BigIntegerPow.testPowS:gc.count avgt 3 135.000 counts
BigIntegerPow.testPowS:gc.time avgt 3 90.000 ms
BigIntegerPow.testPowXL avgt 3 8098242069.667 ± 905979832.443 ns/op
BigIntegerPow.testPowXL:gc.alloc.rate avgt 3 4134.655 ± 462.498 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 159.000 ms
BigIntegerPow.testPowXS avgt 3 4587145069.333 ± 537879394.284 ns/op
BigIntegerPow.testPowXS:gc.alloc.rate avgt 3 3916.668 ± 458.061 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 82.000 ms
-------------
PR Comment: https://git.openjdk.org/jdk/pull/24690#issuecomment-2839600648
More information about the core-libs-dev
mailing list