RFR 8017540: Improve multi-threaded contention behavior of BigInteger.toString() radix conversion cache
Peter Levart
peter.levart at gmail.com
Tue Jun 25 20:56:01 UTC 2013
On 06/25/2013 10:34 PM, Peter Levart wrote:
>
> On 06/25/2013 09:50 PM, Aleksey Shipilev wrote:
>> On 06/25/2013 11:38 PM, Peter Levart wrote:
>>> On 06/25/2013 09:12 PM, Aleksey Shipilev wrote:
>>>> It might be a good idea to turn $powerCache final, not volatile, since
>>>> the code will recover anyway. The trouble I'm seeing is weak enough
>>>> hardware, which will never see the updated value of cacheLine, always
>>>> falling back. Hence, I'm keen to keep "volatile".
>>> The worst thing that could happen is that each thread would effectively
>>> have it's private cache.
>> Right.
>>
>> That only works if you store the fallback value to cacheLine, and then
>> back to powerCache, since the second get...() will possibly re-read the
>> stale cacheLine otherwise. Your version did that. Do we want to store
>> the retVal?
>
> My version does store the value back (new cacheLine array into
> powerCache slot and the calculated value(s) into existing/new
> cacheLine), so the only possibility to read the seemingly empty
> cacheLine is when another thread resizes it and installs new version.
> This can only happen about 52 times until the resizing factor 1.5
> expands array to length 2^31...
>
>> private static final BigInteger[][] powerCache;
>>
>> BigInteger getRadixConversionCache(int radix, int exponent) {
>> BigInteger retVal = null;
>> BigInteger[][] pc = powerCache;
>> BigInteger[] cacheLine = pc[radix];
>> int oldSize = cacheLine.length;
>> if (exponent >= oldSize) {
>> cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
>> for (int i = oldSize; i <= exponent; i++) {
>> retVal = cacheLine[i - 1].square();
>> cacheLine[i] = retVal;
>> }
>> pc[radix] = cacheLine;
>> } else {
>> retVal = cacheLine[exponent];
>> if (retVal == null) {
>> // data race, element is not available yet,
>> // compute on the fly
>> retVal = BigInteger.valueOf(radix);
>> for (int c = 0; c < exponent; c++) {
>> retVal = retVal.square();
>> }
>> cacheLine[exponent] = retVal;
>> }
>> }
>>
>> -Aleksey.
>>
>
> This is getting similar to my version, but you're not storing
> intermediate values back into cacheLine. Each exponent requested must
> re-compute intermediate values again and again.
Sorry, you are storing back when resizing. And you are resizing for
every exponent that is bigger that previous requested (cached). This can
lead to many resizings.
Besides, I think that this version still has a data-race dereferencing
array, followed by reading of array elements:
Thread A:
pc = powerCache;
Thread B:
pc = powerCache;
cacheLine = pc[radix];
oldSize = cacheLine.length;
// enter if, since exponent >= oldSize
cacheLine = copyOf(cacheLine, exponent+1);
// ...for loop filling cacheLine...
pc[radix] = cacheLine;
Thread A:
cacheLine = pc[radix]; // this can read new cacheLine constructed
by Thread B (data-race)
oldSize = cacheLine.length;
// enter if, since exponent >= oldSize
cacheLine = copyOf(cacheLine, exponent+1); // here the copying can
read null slots even for indexes < oldSize
for (int i = oldSize; i <= exponent; i++) {
retVal = cacheLine[i - 1].square(); // possible NPE!
>
>
> Regards, Peter
>
More information about the core-libs-dev
mailing list