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

Dmitry Nadezhin dmitry.nadezhin at gmail.com
Tue Jun 25 19:36:54 UTC 2013

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

More information about the core-libs-dev mailing list