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

[Dmitry Nadezhin]

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