What about such code ?
BigInteger getRadixConversionCache(int radix, int exponent) {
BigInteger retVal = null;
BigInteger[][] pc = powerCache; // volatile read
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;
}
synchronized (pc) {
if (pc[radix].length < cacheLine.length) {
pc[radix] = cacheLine;
powerCache = pc; // volatile write, publish
}
}
} else {
retVal = cacheLine[exponent];
}
return retVal;
}
Is dummy volatile write necessary inside synchronized block ?
powerCache = pc; // volatile write, publish
On Tue, Jun 25, 2013 at 11:12 PM, Aleksey Shipilev <
aleksey.shipi...@oracle.com> wrote:
> On 06/25/2013 08:29 PM, Brian Burkhalter wrote:
> > Hi Aleksey,
> >
> > On Jun 25, 2013, at 1:40 AM, Aleksey Shipilev wrote:
> >
> >> Thanks! Looks good to me.
> >
> > Cool!
>
> Hold on now. Similar to what Peter suggests in the separate thread,
> there is the data race between 3458 and 3466:
>
> 3455 private static BigInteger getRadixConversionCache(int radix,
> int exponent) {
>
> 3456 BigInteger retVal = null;
> 3457 BigInteger[][] pc = powerCache; // volatile read
> 3458 BigInteger[] cacheLine = pc[radix];
> 3459 int oldSize = cacheLine.length;
> 3460 if (exponent >= oldSize) {
> 3461 cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
> 3462 for (int i = oldSize; i <= exponent; i++) {
> 3463 retVal = cacheLine[i - 1].square();
> 3464 cacheLine[i] = retVal;
> 3465 }
> 3466 pc[radix] = cacheLine;
> 3467 powerCache = pc; // publish by volatile write
> 3468 } else {
> 3469 retVal = cacheLine[exponent];
> 3470 }
>
> The observable behavior in one of the threads:
> a) reading cacheLine in 3458
> b) figuring the cacheLine.length is N
> c) querying cacheLine[N-1]
> d) since new cacheLine is published via data race, can see
> (cacheLine[N-1] == null)
> e) boom! NPE in caller.
>
> That's the only trouble I see. BigInteger is effectively final and
> publishable by data race. array.length is good even when published via
> data race. Note that this particular trouble have no chance to manifest
> itself on x86 (modulo some runtime optimizations), because the stores
> are ordered there.
>
> Unfortunately, solving this "cleanly" requires the final-like semantics
> for $cacheLine, which lends itself into creating the wrapper around
> BigInteger[]. It seems simpler to fallback and recover while the data
> race resolves, e.g.:
>
> private static volatile BigInteger[][] powerCache;
>
> BigInteger getRadixConversionCache(int radix, int exponent) {
> BigInteger retVal = null;
> BigInteger[][] pc = powerCache; // volatile read
> 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;
> powerCache = pc; // volatile write, publish
> } 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();
> }
> }
> }
> return retVal;
> }
>
> (In retrospect, this seems the variation on Peter's idea, but fallback
> code is much simpler)
>
> 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".
>
> I haven't tested this code, so...
>
> -Aleksey.
>
