src/share/classes/java/math/BigInteger.java

rev 7571 : 8017540: Improve multi-threaded contention behavior of radix conversion cache
Summary: Replace array of ArrayList of BigIntegers with a volatile two-dimensional BigInteger array eliminate the synchronization of getRadixConversionCache()
Reviewed-by: plevart, shade, bpb, alanb
Contributed-by: Peter Levart <peter.levart@gmail.com>, Dmitry Nadezhin <dmitry.nadezhin@oracle.com>, Aleksey Shipilev <aleksey.shipilev@oracle.com>

*** 1040,1050 ****
      /**
       * The cache of powers of each radix.  This allows us to not have to
       * recalculate powers of radix^(2^n) more than once.  This speeds
       * Schoenhage recursive base conversion significantly.
       */
!     private static ArrayList<BigInteger>[] powerCache;
  
      /** The cache of logarithms of radices for base conversion. */
      private static final double[] logCache;
  
      /** The natural log of 2.  This is used in computing cache indices. */
--- 1040,1050 ----
      /**
       * The cache of powers of each radix.  This allows us to not have to
       * recalculate powers of radix^(2^n) more than once.  This speeds
       * Schoenhage recursive base conversion significantly.
       */
!     private static volatile BigInteger[][] powerCache;
  
      /** The cache of logarithms of radices for base conversion. */
      private static final double[] logCache;
  
      /** The natural log of 2.  This is used in computing cache indices. */
*** 1061,1078 ****
          /*
           * Initialize the cache of radix^(2^x) values used for base conversion
           * with just the very first value.  Additional values will be created
           * on demand.
           */
!         powerCache = (ArrayList<BigInteger>[])
!             new ArrayList[Character.MAX_RADIX+1];
          logCache = new double[Character.MAX_RADIX+1];
  
          for (int i=Character.MIN_RADIX; i<=Character.MAX_RADIX; i++)
          {
!             powerCache[i] = new ArrayList<BigInteger>(1);
!             powerCache[i].add(BigInteger.valueOf(i));
              logCache[i] = Math.log(i);
          }
      }
  
      /**
--- 1061,1076 ----
          /*
           * Initialize the cache of radix^(2^x) values used for base conversion
           * with just the very first value.  Additional values will be created
           * on demand.
           */
!         powerCache = new BigInteger[Character.MAX_RADIX+1][];
          logCache = new double[Character.MAX_RADIX+1];
  
          for (int i=Character.MIN_RADIX; i<=Character.MAX_RADIX; i++)
          {
!             powerCache[i] = new BigInteger[] { BigInteger.valueOf(i) };
              logCache[i] = Math.log(i);
          }
      }
  
      /**
*** 3452,3477 ****
       * If this value doesn't already exist in the cache, it is added.
       * <p/>
       * This could be changed to a more complicated caching method using
       * <code>Future</code>.
       */
!     private static synchronized BigInteger getRadixConversionCache(int radix,
!                                                                    int exponent) {
!         BigInteger retVal = null;
!         ArrayList<BigInteger> cacheLine = powerCache[radix];
!         int oldSize = cacheLine.size();
!         if (exponent >= oldSize) {
!             cacheLine.ensureCapacity(exponent+1);
!             for (int i=oldSize; i<=exponent; i++) {
!                 retVal = cacheLine.get(i-1).square();
!                 cacheLine.add(i, retVal);
              }
          }
-         else
-             retVal = cacheLine.get(exponent);
  
!         return retVal;
      }
  
      /* zero[i] is a string of i consecutive zeros. */
      private static String zeros[] = new String[64];
      static {
--- 3450,3478 ----
       * If this value doesn't already exist in the cache, it is added.
       * <p/>
       * This could be changed to a more complicated caching method using
       * <code>Future</code>.
       */
!     private static BigInteger getRadixConversionCache(int radix, int exponent) {
!         BigInteger[] cacheLine = powerCache[radix]; // volatile read
!         if (exponent < cacheLine.length) {
!             return cacheLine[exponent];
          }
+ 
+         int oldLength = cacheLine.length;
+         cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
+         for (int i = oldLength; i <= exponent; i++) {
+             cacheLine[i] = cacheLine[i - 1].pow(2);
          }
  
!         BigInteger[][] pc = powerCache; // volatile read again
!         if (exponent >= pc[radix].length) {
!             pc = pc.clone();
!             pc[radix] = cacheLine;
!             powerCache = pc; // volatile write, publish
!         }
!         return cacheLine[exponent];
      }
  
      /* zero[i] is a string of i consecutive zeros. */
      private static String zeros[] = new String[64];
      static {