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

[Aleksey Shipilev]

On 06/25/2013 11:38 PM, Peter Levart wrote:
> 
> On 06/25/2013 09:12 PM, Aleksey Shipilev wrote:
>> 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".
> 
> The worst thing that could happen is that each thread would effectively
> have it's private cache.

Right.

That only works if you store the fallback value to cacheLine, and then
back to powerCache, since the second get...() will possibly re-read the
stale cacheLine otherwise. Your version did that. Do we want to store
the retVal?

private static final BigInteger[][] powerCache;

BigInteger getRadixConversionCache(int radix, int exponent) {
  BigInteger retVal = null;
  BigInteger[][] pc = powerCache;
  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;
  } 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();
          }
          cacheLine[exponent] = retVal;
      }
  }

-Aleksey.