> 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 15 additional commits since the last revision: - 8277119: Add asserts in GenericTaskQueueSet methods Reviewed-by: tschatzl - 8274757: Cleanup unnecessary calls to Throwable.initCause() in java.management module Reviewed-by: dfuchs, sspitsyn - 8274662: Replace 'while' cycles with iterator with enhanced-for in jdk.hotspot.agent Reviewed-by: amenkov, cjplummer, sspitsyn - 8274163: Use String.equals instead of String.compareTo in jdk.jcmd Reviewed-by: cjplummer, amenkov, sspitsyn - 8274190: Use String.equals instead of String.compareTo in jdk.internal.jvmstat Reviewed-by: cjplummer, sspitsyn - 8274168: Avoid String.compareTo == 0 to check String equality in java.management Reviewed-by: sspitsyn, dfuchs, cjplummer, dholmes - 8274261: Use enhanced-for instead of plain 'for' in jdk.jcmd Reviewed-by: sspitsyn, cjplummer - Update comments - Added parallelMultiply() method to BigInteger to allow large multiplications to run in parallel - Merge branch 'openjdk:master' into master - ... and 5 more: https://git.openjdk.java.net/jdk/compare/744e9e8e...0075f04d ------------- Changes: - all: https://git.openjdk.java.net/jdk/pull/6391/files - new: https://git.openjdk.java.net/jdk/pull/6391/files/03be5518..0075f04d Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk&pr=6391&range=02 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=6391&range=01-02 Stats: 0 lines in 0 files changed: 0 ins; 0 del; 0 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
