RFR 8017540: Improve multi-threaded contention behavior of BigInteger.toString() radix conversion cache (original) (raw)

Peter Levart peter.levart at gmail.com
Thu Jun 27 08:51:45 UTC 2013

Hi,

Expanding on the idea of building single growing linked list of values and treating the array just as index for quick access which can be re-created at any time without synchronization or volatile publication, here's the attempt:

 private static class Node {
     final BigInteger value;
     Node next;
     Node(BigInteger value) { this.value = value; }
 }

 private static final Node[] powerCache;
 private static final Node[][] powerCacheIndex;
 private static final int POWER_CACHE_LINE_CHUNK = 16;

 static {
     powerCache = new Node[Character.MAX_RADIX + 1];
     for (int i = Character.MIN_RADIX; i <= Character.MAX_RADIX; i++) {
         powerCache[i] = new Node(BigInteger.valueOf(i));
     }
     powerCacheIndex = new Node[Character.MAX_RADIX + 1][];
 }

 private static BigInteger getRadixConversionCache(int radix, int

exponent) { Node[] cacheLine = powerCacheIndex[radix]; if (cacheLine != null && exponent < cacheLine.length) { // cache line is long enough Node node = cacheLine[exponent]; if (node != null) { return node.value; } return fillCacheLine(cacheLine, powerCache[radix], exponent); } else { // we need to extend / create cache line cacheLine = new Node[(exponent / POWER_CACHE_LINE_CHUNK +

    • POWER_CACHE_LINE_CHUNK]; BigInteger result = fillCacheLine(cacheLine,

powerCache[radix], exponent); powerCacheIndex[radix] = cacheLine; // install new line return result; } }

 private static BigInteger fillCacheLine(Node[] cacheLine, Node

node0, int exponent) { Node node = cacheLine[0] = node0; for (int i = 1; i <= exponent; i++) { Node nextNode; synchronized (node) { nextNode = node.next; if (nextNode == null) { nextNode = new Node(node.value.square()); node.next = nextNode; } } cacheLine[i] = node = nextNode; } return node.value; }

What do you think?

Regards, Peter

On 06/27/2013 09:27 AM, Peter Levart wrote:

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.MAXRADIX + 1][]; for (int i = Character.MINRADIX; i <= Character.MAXRADIX; 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.nadezhin at 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]; }

More information about the core-libs-dev mailing list