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

[Aleksey Shipilev]

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.