JDK 8 RFR 8022181: Tune algorithm crossover thresholds in BigInteger
joe.darcy at oracle.com
Mon Dec 2 21:09:57 UTC 2013
The new thresholds look reasonable, as is planned follow-up tuning in JDK 9.
On 12/2/2013 12:54 PM, Brian Burkhalter wrote:
> Issue: https://bugs.openjdk.java.net/browse/JDK-8022181
> Webrev: http://cr.openjdk.java.net/~bpb/8022181/webrev/
> Based on numerous micro-benchmark test runs on various operating systems and architectures I would like to propose changing the BigInteger algorithm crossover thresholds as indicated in the webrev from which I excerpt here for convenience:
> - private static final int KARATSUBA_THRESHOLD = 50;
> + private static final int KARATSUBA_THRESHOLD = 80;
> - private static final int TOOM_COOK_THRESHOLD = 75;
> + private static final int TOOM_COOK_THRESHOLD = 240;
> - private static final int KARATSUBA_SQUARE_THRESHOLD = 90;
> + private static final int KARATSUBA_SQUARE_THRESHOLD = 128;
> - private static final int TOOM_COOK_SQUARE_THRESHOLD = 140;
> + private static final int TOOM_COOK_SQUARE_THRESHOLD = 216;
> - static final int BURNIKEL_ZIEGLER_THRESHOLD = 50;
> + static final int BURNIKEL_ZIEGLER_THRESHOLD = 80;
> - private static final int SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 8;
> + private static final int SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 20;
> Each threshold is approximately the smallest value for which no statistically significant performance regression was observed with respect to the baseline. For the Toom-Cook algorithms, the baselines are the respective Karatsuba algorithms; for the other algorithms, the baselines are the respective algorithms previously implemented in BigInteger. Also, these new suggested thresholds were benchmarked against a performance baseline defined by the previous values of the respective thresholds.
> With respect to the potential objection that the proposed thresholds are too high, please note that the values are subject to further refinement in the future. This issue https://bugs.openjdk.java.net/browse/JDK-8029425 has been filed as a reminder to continue to refine these values in the JDK 9 time frame although such fine tuning could as well occur in JDK 8 updates.
More information about the core-libs-dev