RFR 4641897: Faster string conversion of large integers (original) (raw)

Dmitry Nadezhin dmitry.nadezhin at gmail.com
Sun Jun 23 03:41:18 UTC 2013

Sorry, I missed line "pc[radix] = cacheLine;" in the method "getRadixConversionCache();" in the previous post. Here is the corrected patch. *** Alan Eliasen's BigInteger.java --- BigInteger.java patched according to Aleksey's advice

*** 1038,1048 **** /** * 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[] 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. */

--- 1038,1048 ---- /** * 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. */

*** 1059,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 = (ArrayList[]) ! 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(1); ! powerCache[i].add(BigInteger.valueOf(i)); logCache[i] = Math.log(i); } }

  /**

--- 1059,1074 ---- /* * 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); } }

  /**

*** 3450,3473 **** * If this value doesn't already exist in the cache, it is added. *

* This could be changed to a more complicated caching method using * Future. */ ! private static synchronized BigInteger getRadixConversionCache(int radix, ! int exponent) { BigInteger retVal = null; ! ArrayList 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. */

--- 3448,3472 ---- * If this value doesn't already exist in the cache, it is added. *

* This could be changed to a more complicated caching method using * Future. */ ! private static 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; // publish by volatile write ! } else ! retVal = cacheLine[exponent];

      return retVal;
  }

  /* zero[i] is a string of i consecutive zeros. */

On Sat, Jun 22, 2013 at 3:59 PM, Dmitry Nadezhin <dmitry.nadezhin at gmail.com>wrote:

Thank you, Aleksey!

Alan said: "I'm willing to review any rewrites that people might suggest". Here is a concretization of Aleksey's patch for Alan's review. *** Alan's BigInteger.java --- BigInteger.java patched according to Aleksey's advice *************** *** 1038,1048 **** /** * 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[] 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. */ --- 1038,1048 ---- /** * 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. */ *************** *** 1059,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 = (ArrayList[]) ! new ArrayList[Character.MAXRADIX+1]; logCache = new double[Character.MAXRADIX+1]; for (int i=Character.MINRADIX; i<=Character.MAXRADIX; i++)_ _{_ _! powerCache[i] = new ArrayList(1); ! powerCache[i].add(BigInteger.valueOf(i)); logCache[i] = Math.log(i); } } /** --- 1059,1074 ---- /* * 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.MAXRADIX+1][]; logCache = new double[Character.MAXRADIX+1]; for (int i=Character.MINRADIX; i<=Character.MAXRADIX; i++)_ _{_ _! powerCache[i] = new BigInteger[] { BigInteger.valueOf(i) };_ _logCache[i] = Math.log(i);_ _}_ _}_ _/**_ _***************_ _*** 3450,3473 ****_ _* If this value doesn't already exist in the cache, it is added._ _*

* This could be changed to a more complicated caching method using * Future. */ ! private static synchronized BigInteger getRadixConversionCache(int radix, ! int exponent) { BigInteger retVal = null; ! ArrayList 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. */_ _--- 3448,3471 ----_ _* If this value doesn't already exist in the cache, it is added._ _*

* This could be changed to a more complicated caching method using * Future. */ ! private static 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; } ! powerCache = pc; // publish by writing volatile variable ! } else ! retVal = cacheLine[exponent]; return retVal; } /* zero[i] is a string of i consecutive zeros. */

On Sat, Jun 22, 2013 at 2:54 PM, Aleksey Shipilev <_ _aleksey.shipilev at oracle.com> wrote: On 06/22/2013 02:50 PM, Aleksey Shipilev wrote: > On 06/22/2013 08:06 AM, Dmitry Nadezhin wrote: >> Alexey, >> >> Each possible radix has its cacheLine in the cache. >> >> Cache contents looks like >> BigInteger[][] powerCache = new BigInteger[37] { >> /0/ null, >> /1/ null, >> /2/ new BigInteger[] { 2, 4, 16, 256, 32768, ... }, >> /3/ new BigInteger[] { 3, 9, 81, ... }, >> /4/ new BigInteger[] { 4, 16, 256, ... } >> /5/ new BigInteger[] { 5, 25, 625, ... }, >> /6/ new BigInteger[] { 6 }, >> /7/ new BigInteger[] { 7 }, >> . . . >> /36/ new BigInteger[] { 36 } >> }; >> >> Is there an idiom for a list/array of volatile references ? > > AtomicReferenceArray is your friend there. Although I'm not sure why you > need the list of volatile references in this case. Placing volatile to > the root reference resolves the race. > >> I am not sure that such naive code works: >> volatile BigInteger[][] powerCache = .., > > Why wouldn't it work? > > volatile T[][] cache; > > T[] get(int index) { > T[][] lc = cache; > if (index >= lc.length) { // need resizing > lc = generateNew(index << 1);_ _> cache = lc; > } > return lc[index]; > } > > If you need to populate the 2nd level, then you have to have the final > volatile write to the cache.Thecorrespondingcache. The corresponding cache.Thecorrespondingcache volatile read > makes the update on 2nd level visible. > > T get(int index1, index2) { > T[][] lc = cache; > if (index1 >= lc.length) { // needs resizing > lc = generateNewT2(index1 << 1);_ _> cache = lc; > } > T[] lt = lc[index2]; > if (index2 >= lt.length) { // needs resizing > lt = generateNewT1(index2 << 1);_ _> lc[index2] = lt; > cache = lc; // publish > } > return lt[index2]; > }

Of course, there is a series of typos. Should instead be: T get(int index1, index2) { T[][] lc = cache; if (index1 >= lc.length) { // needs resizing lc = <generatenewT[][]ofsize>((index1 << 1) + 1);_ _cache = lc;_ _}_ _T[] lt = lc[index2];_ _if (index2 >= lt.length) { // needs resizing lt = <generatenewT[]ofsize>((index2 << 1) + 1); lc[index1] = lt; cache = lc; // publish } return lt[index2]; } -Aleksey.

More information about the core-libs-dev mailing list