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.
