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<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];
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);
}
}
/**
--- 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.
* <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. */
--- 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
<dmitry.nadez...@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<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];
>
> 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);
> }
> }
>
> /**
> --- 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.
> * <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. */
> --- 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.shipi...@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.
>>
>
>
