Re: 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.da...@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.da...@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