RFR 8017540: Improve multi-threaded contention behavior of BigInteger.toString() radix conversion cache (original) (raw)

Peter Levart peter.levart at gmail.com
Tue Jun 25 21:21:54 UTC 2013

On 06/25/2013 10:54 PM, Aleksey Shipilev wrote:

Trying to improve this yields the code very similar to http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-June/018368.html, although not as effective on slow path:

private static final BigInteger[][] powerCache; BigInteger getRadixConversionCache(int radix, int exponent) { BigInteger retVal = null; BigInteger[][] pc = powerCache; BigInteger[] cacheLine = pc[radix]; int oldSize = cacheLine.length; if (exponent >= oldSize) { cacheLine = Arrays.copyOf(cacheLine, exponent + 1); } retVal = cacheLine[exponent]; if (retVal == null) { retVal = BigInteger.valueOf(radix); for (int i = 0; i < exponent + 1; i++) { cacheLine[i] = retVal; retVal = retVal.square(); } pc[radix] = cacheLine; } return retVal; } -Aleksey.

I think this is correct from logical standpoint. But not very effective. Think of single-threaded usage first. You resize for every exponent that is bigger than biggest requested so-far. And each time you request exponent that is bigger or equal to the biggest requested so far, you recalculate all squares (the last one calculated is not stored!!!).

I think it pays back if you search backwards from requested exponent to the biggest non-null slot, and only recalculate those that are not calculated yet. The search, although linear, is nothing compared to the recalculation of the same number of slots that were searched-back.

Regards, Peter

More information about the core-libs-dev mailing list