JDK 8 core review request for 6989067 BigInteger's array copiers should be converted to System.arraycopy()

[David Holmes]

On 3/09/2011 9:19 AM, joe.darcy at oracle.com wrote:
> Modified as suggested to use Arrays.copyOf before being pushed.
>
> The performance team recommend to me this class of change be implemented so
> I assume (and hope) the VM properly handles small arrays in a performance
> sense.

I was going to ask about performance here. Of course we should be using 
arraycopy and copyOf et al and if there are performance issues they should 
be fixed in those libraries, but in reality ...

I assume we have some performance benchmarks for BigInteger?

David

> Thanks,
>
> -Joe
>
> On 9/2/2011 3:30 PM, Rémi Forax wrote:
>> On 09/03/2011 12:06 AM, joe.darcy at oracle.com wrote:
>>> Hello.
>>>
>>> Please review this simple patch to replace explicit array copy loops with
>>> System.arraycopy:
>>>
>>> 6989067 BigInteger's array copiers should be converted to System.arraycopy()
>>> http://cr.openjdk.java.net/~darcy/6989067.0/
>>>
>>> Patch below.
>>>
>>> Thanks,
>>>
>>> -Joe
>>
>> Hi Joe,
>> for me, some occurence you can use Arrays.copyOf instead of System.arraycopy
>> in order to avoid to fill (or partially fill part of) the array with zero.
>>
>> manual patch inlined below :)
>>
>>>
>>> --- old/src/share/classes/java/math/BigInteger.java 2011-09-02
>>> 14:48:34.000000000 -0700
>>> +++ new/src/share/classes/java/math/BigInteger.java 2011-09-02
>>> 14:48:34.000000000 -0700
>>> @@ -1612,14 +1612,12 @@
>>> } else { // Array must be resized
>>> if (nBits <= (32-bitsInHighWord)) {
>>> int result[] = new int[nInts+len];
>>> - for (int i=0; i<len; i++)
>>> - result[i] = a[i];
>>> + System.arraycopy(a, 0, result, 0, len);
>>> primitiveLeftShift(result, result.length, nBits);
>>> return result;
>>> } else {
>>> int result[] = new int[nInts+len+1];
>>> - for (int i=0; i<len; i++)
>>> - result[i] = a[i];
>>> + System.arraycopy(a, 0, result, 0, len);
>>> primitiveRightShift(result, result.length, 32 - nBits);
>>> return result;
>>> }
>>> @@ -1908,8 +1906,7 @@
>>>
>>> // Set t to high half of b
>>> int[] t = new int[modLen];
>>> - for(int i=0; i<modLen; i++)
>>> - t[i] = b[i];
>>> + System.arraycopy(b, 0, t, 0, modLen);
>>
>> can be simplified to:
>> int[] t = Array.copyOf(b, modLen);
>>
>>>
>>> // Fill in the table with odd powers of the base
>>> for (int i=1; i<tblmask; i++) {
>>> @@ -2006,14 +2003,12 @@
>>>
>>> // Convert result out of Montgomery form and return
>>> int[] t2 = new int[2*modLen];
>>> - for(int i=0; i<modLen; i++)
>>> - t2[i+modLen] = b[i];
>>> + System.arraycopy(b, 0, t2, modLen, modLen);
>>>
>>> b = montReduce(t2, mod, modLen, inv);
>>>
>>> t2 = new int[modLen];
>>> - for(int i=0; i<modLen; i++)
>>> - t2[i] = b[i];
>>> + System.arraycopy(b, 0, t2, 0, modLen);
>>
>> can be simplified to:
>> t2 = Arrays.copyOf(b, modLen);
>>
>>>
>>> return new BigInteger(1, t2);
>>> }
>>> @@ -2154,8 +2149,7 @@
>>> // Copy remaining ints of mag
>>> int numInts = (p + 31) >>> 5;
>>> int[] mag = new int[numInts];
>>> - for (int i=0; i<numInts; i++)
>>> - mag[i] = this.mag[i + (this.mag.length - numInts)];
>>> + System.arraycopy(this.mag, (this.mag.length - numInts), mag, 0, numInts);
>>>
>>> // Mask out any excess bits
>>> int excessBits = (numInts << 5) - p;
>>> @@ -2221,7 +2215,7 @@
>>> return shiftRight(-n);
>>> }
>>> }
>>> - int[] newMag = shiftLeft(mag,n);
>>> + int[] newMag = shiftLeft(mag, n);
>>>
>>> return new BigInteger(newMag, signum);
>>> }
>>> @@ -2234,8 +2228,7 @@
>>>
>>> if (nBits == 0) {
>>> newMag = new int[magLen + nInts];
>>> - for (int i=0; i<magLen; i++)
>>> - newMag[i] = mag[i];
>>> + System.arraycopy(mag, 0, newMag, 0, magLen);
>>
>> newMag = Arrays.copyOf(magLen + nInts);
>>
>>> } else {
>>> int i = 0;
>>> int nBits2 = 32 - nBits;
>>> @@ -2289,8 +2282,7 @@
>>> if (nBits == 0) {
>>> int newMagLen = magLen - nInts;
>>> newMag = new int[newMagLen];
>>> - for (int i=0; i<newMagLen; i++)
>>> - newMag[i] = mag[i];
>>> + System.arraycopy(mag, 0, newMag, 0, newMagLen);
>>
>> newMag = Arrays.copyOf(newMagLen);
>>
>>> } else {
>>> int i = 0;
>>> int highBits = mag[0] >>> nBits;
>>> @@ -2561,7 +2553,7 @@
>>> if (signum < 0) {
>>> // Check if magnitude is a power of two
>>> boolean pow2 = (Integer.bitCount(mag[0]) == 1);
>>> - for(int i=1; i< len && pow2; i++)
>>> + for (int i=1; i< len && pow2; i++)
>>> pow2 = (mag[i] == 0);
>>>
>>> n = (pow2 ? magBitLength -1 : magBitLength);
>>>
>>
>> Also, this change can have a negative impact because as far as I know
>> system.arraycopy/Arrays.copyOf uses a loop even if the number of iteration
>> is really small. A for loop will be unrolled by the VM.
>>
>> regards,
>> Rémi
>>
>>
>>