JDK 8 RFR 8022181: Tune algorithm crossover thresholds in BigInteger

Joseph Darcy joe.darcy at oracle.com
Mon Dec 2 21:09:57 UTC 2013


Hi Brian,

The new thresholds look reasonable, as is planned follow-up tuning in JDK 9.

Thanks,

-Joe

On 12/2/2013 12:54 PM, Brian Burkhalter wrote:
> Hello,
>
> 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.
>
> Thanks,
>
> Brian




More information about the core-libs-dev mailing list