Hi,
This version seems correct. Maybe just replace double volatile read at
length re-check with a single one:
private static BigInteger getRadixConversionCache(int radix, int
exponent) {
BigInteger[] cacheLine = powerCache[radix]; // volatile read
if (exponent < cacheLine.length)
return cacheLine[exponent];
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];
}
I like this, since it tries to avoid overwriting larger cacheLines with
smaller ones when unexistent exponents are requested concurrently for
same radix. This is good, since computation for larger exponents takes
quadratically longer time (as Alan Eliasen points out) and possibility
of concurrent threads stomping on each other increases. Re-reading and
cloning powerCache reference at end of computation also takes care of
cacheLines for other radixes that might have expanded while the
computation was taking place. So the only overhead remaining is when
concurrent threads are uselessly computing same results at same time. To
avoid this, locking and waiting would have to be introduced which would
complicate things.
Regards, Peter
On 06/26/2013 08:13 PM, Brian Burkhalter wrote:
So do we have consensus on this version?
Thanks for the lively "conversation."
Brian
On Jun 26, 2013, at 12:05 AM, Aleksey Shipilev wrote:
Yes, like that.
-Aleksey
On 26.06.2013, at 10:53, Dmitry Nadezhin <dmitry.nadez...@gmail.com> wrote:
We could check for the existing cacheLine.length right before installing
the new one
Do you mean something like this ?
BigInteger getRadixConversionCache(int radix, int exponent) {
BigInteger[] cacheLine = powerCache[radix]; // volatile read
if (exponent < cacheLine.length)
return cacheLine[exponent];
int oldLength = cacheLine.length;
cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
for (int i = oldLength; i < exponent + 1; i++)
cacheLine[i] = cacheLine[i - 1].square();
if (exponent >= powerCache[radix].length) { // volatile read again
BigInteger[][] pc = Arrays.copyOf(powerCache);
pc[radix] = cacheLine;
powerCache = pc; // volatile write, publish
}
return cacheLine[exponent];
}
