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

[Peter Levart]

On 06/25/2013 09:09 PM, Alan Eliasen wrote:
> On 06/25/2013 12:13 PM, Peter Levart wrote:
>>              else { // resizing
>>                  // increase by factor of 1.5 (like ArrayList)
>>                  int newLength = oldLength + (oldLength >> 1);
>     We probably don't ever want to extend any row of this cache any more
> than we need to.  The entries in each row of the cache, say for base 10,
> are 10^(2^n) which obviously grows super-exponentially with n.  (And the
> time to perform each squaring to get successive terms will grow
> quadratically or at least subquadratically on top of that, along with
> memory usage which squares with each additional term.)  So we should
> never resize to more entries in that table than we need, and we should
> try to avoid recalculating entries in that table in multiple threads, as
> the cost to calculate them can be high.
>
>     As I noted years ago, the caching behavior is certainly going to be
> one of the most controversial parts of BigInteger improvements.  :)
>

Hi Alan,

That's only the re-sizing of the array, so that it is not needed to be 
performed on each bigger exponent request. My code never calculates 
entries past the requested exponent, but can re-calculate the same 
entries if races occur. The part about resizing the array could be tuned 
(change the factor 1.5 -> 1 and you get the 
only-resize-to-maximum-requested-size  behaviour). The re-calculation 
when concurrent requests are issued for same slot(s) could be avoided 
with CAS-es combined with locking. Perhaps the first few exponents, 
where the .square()s can be (re)computed relatively fast, could be 
cached optimistically to avoid volatile reads/CAS-es on fast paths. When 
the exponent index reaches certain threshold, the strategy could change 
and instead of normal racy reads/writes of BigInteger elements, we could 
CAS Supplier<BigInteger> elements. The Supplier would have a 
synchronized get() method that actually computes the BigInteger and 
returns it and installs the BigInteger into the same slot at the same 
time, so that further accesses only need volatile reads from those slots 
and instanceof BigInteger checks.

Something like that (the 2nd part with Supplier) is implemented in 
java.lang.reflect.Proxy to cache generated proxy classes and makes sure 
that each requested Proxy class is only generated and defined once. This 
case is trickier, because calculation of a particular exponent index 
needs the value from previous exponent index which might be in the 
process of calculation by some other thread, so we need to wait on it to 
finish, but this other thread might be waiting for the third thread 
doing calculation of yet previous exponent, etc... Luckily dependencies 
are ordered so no danger of dead-locks, I think...

Regards, Peter