JDK 8 RFR 4891331: BigInteger a.multiply(a) should use squaring code

[Joe Darcy]

Hi Brian,

I approve the code implementation changes going back contingent on the 
Windows i7 performance results being similar.

I would change the @implNote to something less specific:

"An implementation may offer better algorithmic performance when {@code 
val == this}."

Thanks for running the additional performance numbers; cheers,

-Joe

On 10/23/2013 05:37 PM, Brian Burkhalter wrote:
> Please review this patch at your convenience:
>
> Issue:	https://bugs.openjdk.java.net/browse/JDK-4891331
> Webrev:	http://cr.openjdk.java.net/~bpb/4891331/webrev/
>
> This review request follows from this RFC thread:
>
> http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-October/022266.html
>
> More extensive micro-benchmark testing was performed using JMH [1] for the following cases:
>
> 1) multiply: current version of multiply()
> 2) multiplyNonSquare: proposed version of multiply() with parameter val such that (val != this && val.equals(this)) == true
> 3) multiplyPowTwo: multiply by val == this with squaring performed via pow(2)
> 4) multiplySquare: proposed version of multiply() with parameter val such that val == this
> 5) powTwo: straightforward call of pow(2)
> 6) square: straightforward call of square()
>
> Test #1 represents current performance of multiplying two identical instances without squaring code.
> Test #2 represents performance after the patch when squaring code is *not* used, i.e., measures effect of val == this equality check.
> Test #4 represents performance after the patch when squaring code *is* used for the case of mag.length >= 8.
> Tests #3, #5, and #6 are for informative purposes.
>
> The following bit lengths were tested:
>
> 32, 64, 96, 128, 160, 192, 224, 256, 288, 320, 384, 416, 448, 480, 512, 768, 1024, 1280, 1536.
>
> The following JMH parameters were used across all runs:
>
> # Forks: 5
> # Warmup: 5 iterations, 1 s each
> # Measurement: 8 iterations, 3 s each
> # Benchmark mode: Throughput, ops/time
>
> Two sets of runs were performed on each of two platforms, one single-threaded and one with number of threads equal to the number of hardware cores, 4 in one case (Linux) and 8 in the other (Mac OS X).
>
> Linux system: 4 X Intel(R) Core(TM)2 Quad CPU    Q6600  @ 2.40GHz.
> Mac system: 8 X Intel(R) Xeon(R) CPU           E5520  @ 2.27GHz
>
> Summaries of the aggregate tests results are available at [2], [3], [4], and [5] in terms of 99% confidence intervals in operations per millisecond.
>
> The results suggest that the effect of the equality test (val == this) is insignificant. Significant performance improvement was however observed for squaring of values with int array magnitude length >= 8. The performance gain was up to 150-200% for the largest bit length tested (1536). Larger bit lengths were not tested as those would enter the current range of Karatsuba multiplication (>= 1600 bits).
>
> While not pertinent to this review per se, it should be noted that the performance of pow(2) approaches that of square() as the bit length increases. It might be worth a subsequent investigation to determine whether there is a second threshold beyond which pow(2) overtakes square() altogether.
>
> Results for the same set of tests on a Windows 4 X Core-i7 860 2.8Ghz should be available tomorrow. More limited testing previously performed on Windows produced in relative terms results similar to the those obtained on Linux and Mac OS X.
>
> Lastly, I am not sure that the @implNote is necessary or even desirable here and if so whether a CCC request would be in order. Also note that if there were any doubt as to the exact threshold which ought to be used, then a slightly higher value than 8 could be used or the threshold test could be changed to a strict ">" instead of ">=".
>
> Thanks,
>
> Brian
>
> [1] http://openjdk.java.net/projects/code-tools/jmh/
> [2] http://cr.openjdk.java.net/~bpb/4891331/linux-threads-1.html
> [3] http://cr.openjdk.java.net/~bpb/4891331/linux-threads-4.html
> [4] http://cr.openjdk.java.net/~bpb/4891331/macosx-threads-1.html
> [5] http://cr.openjdk.java.net/~bpb/4891331/macosx-threads-8.html