Name: jl125535 Date: 01/28/2003


FULL PRODUCT VERSION :
java version "1.4.1_01"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.1_01-b01)
Java HotSpot(TM) Client VM (build 1.4.1_01-b01, mixed mode)


FULL OPERATING SYSTEM VERSION :
It is irrelevant what OS you use, but mine happens to be
Windows 98 [Version 4.10.2222]


A DESCRIPTION OF THE PROBLEM :
The implementation of
    System.arraycopy
is suboptimal.

The current version is strictly a native method; in your
source code, it is declared as
    public static native void arraycopy(...);

The problem with this is that there is a fairly stiff
penalty for making a native method call. Therefore, for
small arrays, it is actually slower to call System.arraycopy
than it is to do an array copy explicitly in your code (i.e.
purely in Java).

But it does not have to be this way! It should be trivial
for you to reimplement System.arraycopy as a real Java
method which checks the length of the array, and does the
copying explicitly in Java for small arrays or passes the
arrays to a native method if they are large enough.

You would get a decent performance boost in MANY areas of
Java if you were to do this. (I just did a search thru your
source code, and found 564 occurences of System.arraycopy;
does that say something? And many of the uses are in
extremely common classes like ArrayList and Vector!)

In the Source Code section below, I paste some of my own
benchmarking code. On my box, using the client JVM, I found
that a purely native System.arraycopy only makes sense for
arrays of length 32 or so.


REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
Compile and execute the code below to explore the point at which a pure Java
array copy becomes less efficient than a native call.



// Copyright (c) 2001 Brent Boyer. All Rights Reserved.


/**
* This code benchmarks the performance of copying an array purely in Java versus
* copying it with System.arraycopy.
* <p>
* If available on the executing platform, it may be very useful to perform
* benchmarks with the server JVM as well as the default client JVM.
*/
public class BenchmarkArrayCopy {


/**
* This constant specifies the minimum number of times that a task to be
benchmarked must run before
* an actual timing measurement should be done.
* This is done both to load all relevant classes as well as to warm up hotspot
before doing a measurement.
*/
private static final int MIN_WARMUP_CALLS = 100;


/**
* This constant specifies the minimum time that a task to be benchmarked must
run to assure accurate timing measurements.
* It must be set reasonably large to deal with the low resolution clocks
present on many platforms
* (e.g. typical windoze boxen have error around 10s of ms?).
* The units of this constant are milliseconds.
*/
private static final int MIN_BENCHMARK_TIME = 2*1000;


public static final void main(String[] args) throws Exception {
findWhenSystemBeatsJava();
//exploreScalingOfSystemArrayCopy();
}


private static final void findWhenSystemBeatsJava() throws IllegalStateException {
for (int i = 1; true; i++) {
System.out.println();

double javaTime = benchmarkTask( new JavaArrayCopy(i) );
System.out.println("Time to copy an int[" + i + "] purely in Java: " +
javaTime + " us");

double systemTime = benchmarkTask( new SystemArrayCopy(i) );
System.out.println("Time to copy an int[" + i + "] using System.arraycopy: "
+ systemTime + " us");

if (systemTime < javaTime) {
if (i == 1)
throw new IllegalStateException("found that System.arraycopy beats a pure
Java copy even for an array of length 1");
else {
System.out.println();
System.out.println("System.arraycopy first beats a pure Java copy for int
arrays of length = " + i);
break;
}
}
}
// +++ the above algorithm could be more efficient (e.g. first find an upper
bound using doubling or array length, and then use bisection to find exact
crossover)
}
// 2002/11/10 result: System.arraycopy first beats pure Java array copy for
array length around 32, give or take a factor of 2


/**
* This method finds how the execution time of System.arraycopy scales versus
array length.
* (The execution time for small arrays is dominated by the overhead of making a
native call, not array length.
* For large arrays, this overhead is minimal and the scaling should become linear.)
*/
private static final void exploreScalingOfSystemArrayCopy() {
for (int i = 1; i < 1024*1024; i *= 2) {
System.out.println();
double systemTime = benchmarkTask( new SystemArrayCopy(i) );
System.out.println("Time to copy an int[" + i + "] using System.arraycopy: "
+ systemTime + " us");
}
}
// 2002/11/10 result: linear behavior starts for array lengths around 512, give
or take a factor of 2


/**
* Measures how long it takes to execute the run method of the task arg.
* <p>
* This method uses the MIN_WARMUP_CALLS and MIN_BENCHMARK_TIME constants to
obtain accurate results.
* <p>
* This method explicitly requests garbage collection before doing each benchmark.
* Therefore, unless you actually want to include the effect of garbage
collection in the benchmark,
* the JVM should use a "stop-the-world" garbage collector, if it is available.
* (Usually it is. With Sun's tools, this is, in fact, the default garbage
collector type.)
* The type of garbage collectors to avoid are incremental, concurrent, or
parallel ones.
* <p>
* @return average execution time of a single invocation of task.run, in
microseconds
* @see #MIN_WARMUP_CALLS
* @see #MIN_BENCHMARK_TIME
*/
private static final double benchmarkTask(Runnable task) {
int numberOfRuns = MIN_WARMUP_CALLS;
while (true) {
System.gc();
long t1 = System.currentTimeMillis();
for (int i = 0; i < numberOfRuns; i++) {
task.run();
}
long t2 = System.currentTimeMillis();

long testRunTime = t2 - t1;
if ( (numberOfRuns > MIN_WARMUP_CALLS) && (testRunTime > MIN_BENCHMARK_TIME) ) {
//System.out.println("numberOfRuns required = " + numberOfRuns);
return (testRunTime*1000.0)/numberOfRuns;
}
else {
numberOfRuns *= 2;
}
}
}


private static final class JavaArrayCopy implements Runnable {
private final int[] source;
private final int[] target;

JavaArrayCopy(int arrayLength) {
source = new int[arrayLength];
target = new int[arrayLength];
}

public void run() {
for (int i = 0; i < target.length; i++) {
target[i] = source[i];
}
}
}


private static final class SystemArrayCopy implements Runnable {
private final int[] source;
private final int[] target;

SystemArrayCopy(int arrayLength) {
source = new int[arrayLength];
target = new int[arrayLength];
}

public void run() {
System.arraycopy(source, 0, target, 0, target.length);
}
}


}
---------- END SOURCE ----------

CUSTOMER WORKAROUND :
You can do the onerous array length and explicit Java copy
checks yourself, at the cost of more code and likely bugs.
(Review ID: 166922)
======================================================================