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

Brian Burkhalter brian.burkhalter at oracle.com
Thu Oct 17 19:26:52 UTC 2013


This post concerns this issue:

https://bugs.openjdk.java.net/browse/JDK-4891331

I performed some tests using JMH [1] on Mac OS X [2] and Windows 7 [3]. The tests were equivalent to calling multiply() with argument == this for bit lengths from 32 through 448 without and with this patch applied:

--- a/src/share/classes/java/math/BigInteger.java	Thu Oct 17 11:34:01 2013 -0400
+++ b/src/share/classes/java/math/BigInteger.java	Thu Oct 17 11:45:42 2013 -0700
@@ -1374,6 +1374,10 @@
         if (val.signum == 0 || signum == 0)
             return ZERO;
 
+        if (val == this) {
+            return square();
+        }
+
         int xlen = mag.length;
         int ylen = val.mag.length;

A table of the ratios of throughput with the patch applied to throughput without the patch applied is here:

http://cr.openjdk.java.net/~bpb/4891331/multiply-square.html

The results on the two platforms are consistent in that once the value involved reaches a length of 256 bits (8 ints), the throughput with the patch applied is higher for all larger values. Testing on the Windows machine only also suggests that the sub-unity ratios for lengths under 256 bits is not due to the equality test, but rather to square() in fact being slower than multiply(this) for smaller magnitude values.

Note that the lengths of values used is much smaller than the Karatsuba thresholds so that the "grade-school" algorithms are used in all cases.

Are these results sufficient to justify an "up or down" vote on this patch, is more extensive testing in order, or should this be deferred to a later date?

Thanks,

Brian

[1] http://openjdk.java.net/projects/code-tools/jmh
[2] https://support.apple.com/kb/HT4132 [2.8 GHz]
[3] http://ark.intel.com/products/41316 and https://en.wikipedia.org/wiki/List_of_Intel_Core_i7_microprocessors#.22Lynnfield.22_.2845_nm.29


More information about the core-libs-dev mailing list