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

[Peter Levart]

On 06/25/2013 09:50 PM, Aleksey Shipilev wrote:
> On 06/25/2013 11:38 PM, Peter Levart wrote:
>> On 06/25/2013 09:12 PM, Aleksey Shipilev wrote:
>>> It might be a good idea to turn $powerCache final, not volatile, since
>>> the code will recover anyway. The trouble I'm seeing is weak enough
>>> hardware, which will never see the updated value of cacheLine, always
>>> falling back. Hence, I'm keen to keep "volatile".
>> The worst thing that could happen is that each thread would effectively
>> have it's private cache.
> Right.
>
> That only works if you store the fallback value to cacheLine, and then
> back to powerCache, since the second get...() will possibly re-read the
> stale cacheLine otherwise. Your version did that. Do we want to store
> the retVal?

My version does store the value back (new cacheLine array into 
powerCache slot and the calculated value(s) into existing/new 
cacheLine), so the only possibility to read the seemingly empty 
cacheLine is when another thread resizes it and installs new version. 
This can only happen about 52 times until the resizing factor 1.5 
expands array to length 2^31...

> 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);
>        for (int i = oldSize; i <= exponent; i++) {
>            retVal = cacheLine[i - 1].square();
>            cacheLine[i] = retVal;
>        }
>        pc[radix] = cacheLine;
>    } else {
>        retVal = cacheLine[exponent];
>        if (retVal == null) {
>            // data race, element is not available yet,
>            // compute on the fly
>            retVal = BigInteger.valueOf(radix);
>            for (int c = 0; c < exponent; c++) {
>                retVal = retVal.square();
>            }
>            cacheLine[exponent] = retVal;
>        }
>    }
>
> -Aleksey.
>

This is getting similar to my version, but you're not storing 
intermediate values back into cacheLine. Each exponent requested must 
re-compute intermediate values again and again.


Regards, Peter