On 06/27/2013 08:37 AM, Peter Levart wrote:
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 the other hand, it doesn't complicate thing too much. So if this
extra CPU time proves to be a problem, here's a variation of above code
which prevents multiple threads from calculating the same result at the
same time, by serializing computation with precise granularity:
private static class Node {
final BigInteger value;
Node next;
Node(BigInteger value) { this.value = value; }
}
private static volatile Node[][] powerCache;
static {
powerCache = new Node[Character.MAX_RADIX + 1][];
for (int i = Character.MIN_RADIX; i <= Character.MAX_RADIX; i++) {
powerCache[i] = new Node[]{new Node(BigInteger.valueOf(i))};
}
}
private static BigInteger getRadixConversionCache(int radix, int
exponent) {
Node[] cacheLine = powerCache[radix]; // volatile read
if (exponent < cacheLine.length)
return cacheLine[exponent].value;
int oldLength = cacheLine.length;
cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
Node prevNode = cacheLine[oldLength - 1];
for (int i = oldLength; i <= exponent; i++) {
Node node;
synchronized (prevNode) {
node = prevNode.next;
if (node == null) {
node = new Node(prevNode.value.pow(2));
prevNode.next = node;
}
}
cacheLine[i] = prevNode = node;
}
Node[][] pc = powerCache; // volatile read again
if (exponent >= pc[radix].length) {
pc = pc.clone();
pc[radix] = cacheLine;
powerCache = pc; // volatile write, publish
}
return cacheLine[exponent].value;
}
This variation differs only in a subtelty. It wraps each BigInteger with
a Node, which has a link to next node in chain. Computation of next node
is serailized using previous node as a lock. So although Nodes can end
up in several arrays (which are used as index for quick access), there
is only a single growing chain of Nodes per radix and each Node is
computed by single thread.
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];
}
