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. >