RFR 4641897: Faster string conversion of large integers

[Aleksey Shipilev]

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.