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

[Peter Levart]

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