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

[Dmitry Nadezhin]

We have two versions after private discussion with Aleksey.

BigInteger getRadixConversionCache(int radix, int exponent) {
  BigInteger[][] pc = powerCache; // volatile read
  BigInteger[] cacheLine = pc[radix];
  if (exponent < cacheLine.length)
      return cacheLine[exponent];

  int oldSize = cacheLine.length;
  cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
  for (int i = oldSize; i < exponent + 1; i++)
      cacheLine[i] = cacheLine[i - 1].square();

  pc = Arrays.copyOf(powerCache);
  pc[radix] = cacheLine;
  powerCache = pc; // volatile write, publish
  return cacheLine[exponent];
}

BigInteger getRadixConversionCache(int radix, int exponent) {
  BigInteger[][] pc = powerCache; // volatile read
  BigInteger[] cacheLine = pc[radix];
  if (exponent < cacheLine.length)
      return cacheLine[exponent];

  int oldSize = cacheLine.length;
  cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
  for (int i = oldSize; i < exponent + 1; i++)
       cacheLine[i] = cacheLine[i - 1].square();

  synchronized (BigInteger.class) {
    if (powerCache[radix].length < cacheLine.length) {
      pc = Arrays.copyOf(powerCache);
      pc[radix] = cacheLine;
      powerCache = pc; // volatile write, publish
    }
  }
  return powerCache[radix][exponent];
}

The first version is simpler but sometimes a thread may discard powers with
larger exponents computed by another thread.
A thread may discard only powers computed by itself In the second version.


On Tue, Jun 25, 2013 at 11:53 PM, Aleksey Shipilev <
aleksey.shipilev at oracle.com> wrote:

> On 06/25/2013 11:36 PM, Dmitry Nadezhin wrote:
> > 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;
> > }
>
> Still the same race. The reader thread sees the full-length cacheLine
> early, but the elements are not yet there.
>
> > Is dummy volatile write necessary inside synchronized block ?
> >           powerCache = pc; // volatile write, publish
> >
>
> Yes, since you need to have the matched synchronized(pc) otherwise to
> produce the pairwise "acquire".
>
> -Aleksey.
>
>