# RFR 4641897: Faster string conversion of large integers

Sun Jun 23 03:41:18 UTC 2013

```Sorry, I missed line "pc[radix] = cacheLine;" in the method
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<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. */
--- 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<BigInteger>[])
logCache = new double[Character.MAX_RADIX+1];

{
!             powerCache[i] = new ArrayList<BigInteger>(1);
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];

{
!             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.
* <p/>
* This could be changed to a more complicated caching method using
* <code>Future</code>.
*/
!     private static synchronized BigInteger getRadixConversionCache(int
!                                                                    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();
}
!         }
!         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.
* <p/>
* This could be changed to a more complicated caching method using
* <code>Future</code>.
*/
!     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

> 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<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.
> */
> --- 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<BigInteger>[])
> !             new ArrayList[Character.MAX_RADIX+1];
>           logCache = new double[Character.MAX_RADIX+1];
>
>           {
> !             powerCache[i] = new ArrayList<BigInteger>(1);
>               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];
>
>           {
> !             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.
>        * <p/>
>        * This could be changed to a more complicated caching method using
>        * <code>Future</code>.
>        */
> !     private static synchronized BigInteger getRadixConversionCache(int
> !                                                                    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. */
> --- 3448,3471 ----
>        * 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 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. The corresponding \$cache 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 = <generate_new_T[][]_of_size>((index1 << 1) + 1);
>>         cache = lc;
>>      }
>>      T[] lt = lc[index2];
>>      if (index2 >= lt.length) { // needs resizing
>>         lt = <generate_new_T[]_of_size>((index2 << 1) + 1);
>>         lc[index1] = lt;
>>         cache = lc; // publish
>>      }
>>      return lt[index2];
>>   }
>>
>> -Aleksey.
>>
>
>

```