RFR: JDK-8277175 : Add a parallel multiply method to BigInteger [v9]

[Paul Sandoz]

On Fri, 28 Jan 2022 19:03:39 GMT, kabutz <duke at openjdk.java.net> wrote:

>> kabutz has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   Benchmark for testing the effectiveness of BigInteger.parallelMultiply()
>
> I have added a benchmark for checking performance difference between sequential and parallel multiply of very large Mersenne primes using BigInteger. We want to measure real time, user time, system time and the amount of memory allocated. To calculate this, we create our own thread factory for the common ForkJoinPool and then use that to measure user time, cpu time and bytes allocated.
> 
> We use reflection to discover all methods that match "*ultiply", and use them to multiply two very large Mersenne primes together.
> 
> ### Results on a 1-6-2 machine running Ubuntu linux
> 
> Memory allocation increased from 83.9GB to 84GB, for both the sequential and parallel versions. This is an increase of just 0.1%. On this machine, the parallel version was 3.8x faster in latency (real time), but it used 2.7x more CPU resources.
> 
> Testing multiplying Mersenne primes of 2^57885161-1 and 2^82589933-1
> 
> #### openjdk version "18-internal" 2022-03-15
> 
> BigInteger.parallelMultiply()
> real  0m6.288s
> user  1m3.010s
> sys   0m0.027s
> mem   84.0GB
> BigInteger.multiply()
> real  0m23.682s
> user  0m23.530s
> sys   0m0.004s
> mem   84.0GB
> 
> 
> #### openjdk version "1.8.0_302"
> 
> BigInteger.multiply()
> real  0m25.657s
> user  0m25.390s
> sys   0m0.001s
> mem   83.9GB
> 
> 
> #### openjdk version "9.0.7.1"
> 
> BigInteger.multiply()
> real  0m24.907s
> user  0m24.700s
> sys   0m0.001s
> mem   83.9GB
> 
> 
> #### openjdk version "10.0.2" 2018-07-17
> 
> BigInteger.multiply()
> real  0m24.632s
> user  0m24.380s
> sys   0m0.004s
> mem   83.9GB
> 
> 
> #### openjdk version "11.0.12" 2021-07-20 LTS
> 
> BigInteger.multiply()
> real  0m22.114s
> user  0m21.930s
> sys   0m0.001s
> mem   83.9GB
> 
> 
> #### openjdk version "12.0.2" 2019-07-16
> 
> BigInteger.multiply()
> real  0m23.015s
> user  0m22.830s
> sys   0m0.000s
> mem   83.9GB
> 
> 
> #### openjdk version "13.0.9" 2021-10-19
> 
> BigInteger.multiply()
> real  0m23.548s
> user  0m23.350s
> sys   0m0.005s
> mem   83.9GB
> 
> 
> #### openjdk version "14.0.2" 2020-07-14
> 
> BigInteger.multiply()
> real  0m22.918s
> user  0m22.530s
> sys   0m0.131s
> mem   83.9GB
> 
> 
> 
> #### openjdk version "15.0.5" 2021-10-19
> 
> BigInteger.multiply()
> real  0m22.038s
> user  0m21.750s
> sys   0m0.003s
> mem   83.9GB
> 
> 
> #### openjdk version "16.0.2" 2021-07-20
> 
> BigInteger.multiply()
> real  0m23.049s
> user  0m22.760s
> sys   0m0.006s
> mem   83.9GB
> 
> 
> #### openjdk version "17" 2021-09-14
> 
> BigInteger.multiply()
> real  0m22.580s
> user  0m22.310s
> sys   0m0.001s
> mem   83.9GB

@kabutz thanks for the additional testing, kind of what we intuitively expected.

Can you please update the specification in response to Joe's [comment](https://bugs.openjdk.java.net/browse/JDK-8278886?focusedCommentId=14470153&page=com.atlassian.jira.plugin.system.issuetabpanels%3Acomment-tabpanel#comment-14470153)?

Generally for parallel constructs we try to say as little as possible with regards to latency, CPU time, and memory. The first two are sort of obvious, the later less so for the developer.

>From your results I think can say a little more. Here a suggestive update addressing Joe's comments:


/**
 * Returns a BigInteger whose value is {@code (this * val)}.
 * When both {@code this} and {@code val} are large, typically
 * in the thousands of bits, parallel multiply might be used. 
 * This method returns the exact same mathematical result as {@link #multiply}. 
 *
 * @implNote This implementation may offer better algorithmic
 * performance when {@code val == this}.
 * 
 * @implNote Compared to {@link #multiply} this implementation's parallel multiplication algorithm 
 * will use more CPU resources to compute the result faster, with a relatively small increase memory
 * consumption.
 *
 * @param  val value to be multiplied by this BigInteger.
 * @return {@code this * val}
 * @see #multiply
 */

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

PR: https://git.openjdk.java.net/jdk/pull/6409