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
