> 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 incremental webrev excludes the unrelated changes brought in by the 
merge/rebase. The pull request contains eight additional commits since the last 
revision:

 - Merge branch 'openjdk:master' into parallel-bigInteger
 - Update comments
 - Added parallelMultiply() method to BigInteger to allow large multiplications 
to run in parallel
 - Merge remote-tracking branch 'upstream/master'
 - Merge remote-tracking branch 'upstream/master'
 - Merge remote-tracking branch 'origin/master'
 - 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.

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

Changes:
  - all: https://git.openjdk.java.net/jdk/pull/6391/files
  - new: https://git.openjdk.java.net/jdk/pull/6391/files/eac09f15..03be5518

Webrevs:
 - full: https://webrevs.openjdk.java.net/?repo=jdk&pr=6391&range=01
 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=6391&range=00-01

  Stats: 24162 lines in 218 files changed: 17701 ins; 2440 del; 4021 mod
  Patch: https://git.openjdk.java.net/jdk/pull/6391.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/6391/head:pull/6391

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

Reply via email to