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

[kabutz]

On Tue, 16 Nov 2021 12:48:03 GMT, kabutz <duke at openjdk.java.net> wrote:

>> BigInteger currently uses three different algorithms for multiply. The simple quadratic algorithm, then the slightly better Karatsuba if we exceed a bit count and then Toom Cook 3 once we go into the several thousands of bits. Since Toom Cook 3 is a recursive algorithm, it is trivial to parallelize it. I have demonstrated this several times in conference talks. In order to be consistent with other classes such as Arrays and Collection, I have added a parallelMultiply() method. Internally we have added a parameter to the private multiply method to indicate whether the calculation should be done in parallel.
>> 
>> The performance improvements are as should be expected. Fibonacci of 100 million (using a single-threaded Dijkstra's sum of squares version) completes in 9.2 seconds with the parallelMultiply() vs 25.3 seconds with the sequential multiply() method. This is on my 1-8-2 laptop. The final multiplications are with very large numbers, which then benefit from the parallelization of Toom-Cook 3.  Fibonacci 100 million is a 347084 bit number.
>> 
>> We have also parallelized the private square() method. Internally, the square() method defaults to be sequential.
>> 
>> 
>> Benchmark                                          (n)  Mode  Cnt      Score      Error  Units
>> BigIntegerParallelMultiply.multiply            1000000    ss    4     68,043 ±   25,317  ms/op
>> BigIntegerParallelMultiply.multiply           10000000    ss    4   1073,095 ±  125,296  ms/op
>> BigIntegerParallelMultiply.multiply          100000000    ss    4  25317,535 ± 5806,205  ms/op
>> BigIntegerParallelMultiply.parallelMultiply    1000000    ss    4     56,552 ±   22,368  ms/op
>> BigIntegerParallelMultiply.parallelMultiply   10000000    ss    4    536,193 ±   37,393  ms/op
>> BigIntegerParallelMultiply.parallelMultiply  100000000    ss    4   9274,657 ±  826,197  ms/op
>
> kabutz has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains four commits:
> 
>  - Update comments
>  - Added parallelMultiply() method to BigInteger to allow large multiplications to run in parallel
>  - 8176501: Method Shape.getBounds2D() incorrectly includes Bezier control points in bounding box
>    
>    Addressing some of Laurent's code review recommendations/comments:
>    
>    1. use the convention t for the parametric variable x(t),y(t)
>    2. solve the quadratic equation using QuadCurve2d.solveQuadratic() or like Helpers.quadraticRoots()
>    3. always use braces for x = (a < b) ? ...
>    4. always use double-precision constants in math or logical operations: (2 * x => 2.0 * x) and (coefficients[3] != 0) => (coefficients[3] != 0.0)
>    
>    (There are two additional recommendations not in this commit that I'll ask about shortly.)
>    
>    See https://github.com/openjdk/jdk/pull/6227#issuecomment-959757954
>  - 8176501: Method Shape.getBounds2D() incorrectly includes Bezier control points in bounding box
>    
>    The bug writeup indicated they wanted Path2D#getBounds2D() to be more accurate/concise. They didn't explicitly say they wanted CubicCurve2D and QuadCurve2D to become more accurate too. But a preexisting unit test failed when Path2D#getBounds2D() was updated and those other classes weren't. At this point I considered either:
>    A. Updating CubicCurve2D and QuadCurve2D to use the new more accurate getBounds2D() or
>    B. Updating the unit test to forgive the discrepancy.
>    
>    I chose A. Which might technically be seen as scope creep, but it feels like a more holistic/better approach.
>    
>    This also includes a new unit test (in Path2D/UnitTest.java) that fails without the changes in this commit.

Thanks Kevin, let me start again!

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

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