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
