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.
>
