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

[Rémi Forax]

On 09/03/2011 01:19 AM, joe.darcy at oracle.com wrote:
> Hi Remi.
>
> 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.

good to know :)

>
> Thanks,
>
> -Joe

cheers,
Rémi

>
> 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
>>
>>
>>