changeset 18588:8aa1d5a9d447

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>
author bpb
date Mon, 01 Jul 2013 11:30:14 -0700
parents d70aed7424f6
children 8b03e152e2fe
files jdk/src/share/classes/java/math/BigInteger.java
diffstat 1 files changed, 21 insertions(+), 20 deletions(-) [+]
line wrap: on
line diff
--- a/jdk/src/share/classes/java/math/BigInteger.java	Mon Jul 01 14:39:47 2013 +0100
+++ b/jdk/src/share/classes/java/math/BigInteger.java	Mon Jul 01 11:30:14 2013 -0700
@@ -1042,7 +1042,7 @@
      * recalculate powers of radix^(2^n) more than once.  This speeds
      * Schoenhage recursive base conversion significantly.
      */
-    private static ArrayList<BigInteger>[] powerCache;
+    private static volatile BigInteger[][] powerCache;
 
     /** The cache of logarithms of radices for base conversion. */
     private static final double[] logCache;
@@ -1063,14 +1063,12 @@
          * with just the very first value.  Additional values will be created
          * on demand.
          */
-        powerCache = (ArrayList<BigInteger>[])
-            new ArrayList[Character.MAX_RADIX+1];
+        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 ArrayList<BigInteger>(1);
-            powerCache[i].add(BigInteger.valueOf(i));
+            powerCache[i] = new BigInteger[] { BigInteger.valueOf(i) };
             logCache[i] = Math.log(i);
         }
     }
@@ -3454,22 +3452,25 @@
      * 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);
-            }
+    private static BigInteger getRadixConversionCache(int radix, int exponent) {
+        BigInteger[] cacheLine = powerCache[radix]; // volatile read
+        if (exponent < cacheLine.length) {
+            return cacheLine[exponent];
         }
-        else
-            retVal = cacheLine.get(exponent);
-
-        return retVal;
+
+        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. */