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

[Peter Levart]

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.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];
>>>> }
>