JDK-6195753 : (coll) Arrays.sort(Object[]) should eschew clone() in favor of new Object[]+System.arraycopy()
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util:collections
  • Affected Version: 5.0,6
  • Priority: P4
  • Status: Closed
  • Resolution: Not an Issue
  • OS: generic,linux
  • CPU: generic,x86
  • Submitted: 2004-11-16
  • Updated: 2012-10-08
  • Resolved: 2007-06-03
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 7
7Resolved
Related Reports
Relates :  
JDK-6182955 - Enum.hashCode() could be seven times faster
Relates :  
JDK-6428387 - array clone() much slower than Arrays.copyOf
Relates :  
JDK-5072831 - (coll) Please add Collections.toArray
Relates :  
JDK-6359820 - arraycopy slower on 32-bit amd64 -server than -client on some array sizes
Description
Josh Bloch writes:

Wolfgang,

   Hi.  The reason is that I thought that cloning the array was faster
when I wrote the code.  I was wrong.  Unless I'm missing something,
this should be fixed.  I'm copying Martin Buchholz at Sun in the hopes
that he'll fix it or pass it on to someone else at Sun to fix.  I'm
copying Neal and Doug because I think they'll be interested.

       Regards,

       Josh


On Mon, 15 Nov 2004 18:11:17 -0800, Wolfgang Hoschek <###@###.###> wrote:

>> Josh,
>> just a quick question since you're probably busy.
>> 
>> In java.util.Arrays.sort(Object[]) and range based cousin, to set up
>> the temporary buffer array, why not simply use "new Object[size]" and
>> then System.arraycopy instead of clone() or reflection in
>> cloneSubArray()? My understanding is that System.arraycopy is faster
>> than clone().
>> 
>> When frequently sorting small arrays on jdk 1.5.0 server, VM clone()
>> shows up with 14% when profiling with the non-perturbing flags '-server
>> -agentlib:hprof=cpu=samples,depth=10'
>> 
>> This is with our binary xml codec:
>> http://dsd.lbl.gov/nux/api/nux/xom/binary/BinaryXMLCodec.html
>> 
>> TRACE 300256:
>>          java.lang.Object.clone(Object.java:Unknown line)
>>          java.util.Arrays.sort(Arrays.java:1219)
>>          nux.xom.binary.BinaryXMLCodec.packSort(BinaryXMLCodec.java:560)
>>          nux.xom.binary.BinaryXMLCodec.serialize(BinaryXMLCodec.java:469)
>>          nux.xom.tests.BinaryXMLTest.main(BinaryXMLTest.java:115)
>> 
>> Thanks,
>> Wolfgang.

###@###.### 2004-11-16 04:44:31 GMT
Comments
EVALUATION Now that 6428387: array clone() much slower than Arrays.copyOf has been fixed, all methods of copying arrays are equally performant, so there is no reason to uglify the code for performance. Closing as Not a Defect.
03-06-2007
EVALUATION I've done some more microbenchmarking ------------------------------------- import java.util.*; public class ArrayCopyMicroBenchmark { abstract static class Job { private final String name; Job(String name) { this.name = name; } String name() { return name; } abstract void work() throws Throwable; } private static void collectAllGarbage() { try { for (int i = 0; i < 2; i++) { System.gc(); System.runFinalization(); Thread.sleep(10); } } catch (InterruptedException e) { throw new Error(e); } } /** * Runs each job for long enough that all the runtime compilers * have had plenty of time to warm up, i.e. get around to * compiling everything worth compiling. * Returns array of average times per job per run. */ private static long[] time0(Job ... jobs) throws Throwable { final long warmupNanos = 10L * 1000L * 1000L * 1000L; long[] nanoss = new long[jobs.length]; for (int i = 0; i < jobs.length; i++) { collectAllGarbage(); long t0 = System.nanoTime(); long t; int j = 0; do { jobs[i].work(); j++; } while ((t = System.nanoTime() - t0) < warmupNanos); nanoss[i] = t/j; } return nanoss; } private static void time(Job ... jobs) throws Throwable { long[] warmup = time0(jobs); // Warm up run long[] nanoss = time0(jobs); // Real timing run final String nameHeader = "Method"; int nameWidth = nameHeader.length(); for (Job job : jobs) nameWidth = Math.max(nameWidth, job.name().length()); final String millisHeader = "Millis"; int millisWidth = millisHeader.length(); for (long nanos : nanoss) millisWidth = Math.max(millisWidth, String.format("%d", nanos/(1000L * 1000L)).length()); final String ratioHeader = "Ratio"; int ratioWidth = ratioHeader.length(); String format = String.format("%%-%ds %%%dd %%.3f%%n", nameWidth, millisWidth); String headerFormat = String.format("%%-%ds %%-%ds %%-%ds%%n", nameWidth, millisWidth, ratioWidth); System.out.printf(headerFormat, "Method", "Millis", "Ratio"); // Print out absolute and relative times, calibrated against first job for (int i = 0; i < jobs.length; i++) { long millis = nanoss[i]/(1000L * 1000L); double ratio = (double)nanoss[i] / (double)nanoss[0]; System.out.printf(format, jobs[i].name(), millis, ratio); } } private static int intArg(String[] args, int i, int defaultValue) { return args.length > i ? Integer.parseInt(args[i]) : defaultValue; } private static void deoptimize(Object[] a) { for (Object x : a) if (x == null) throw new Error(); } public static void main(String[] args) throws Throwable { final int iterations = intArg(args, 0, 100000); final int size = intArg(args, 1, 1000); final Object[] array = new Object[size]; final Random rnd = new Random(); for (int i = 0; i < array.length; i++) array[i] = rnd.nextInt(size); time( new Job("arraycopy") { void work() { Object[] a = array; for (int i = 0; i < iterations; i++) { Object[] t = new Object[size]; System.arraycopy(a, 0, t, 0, size); a = t;} deoptimize(a);}}, new Job("copyOf") { void work() { Object[] a = array; for (int i = 0; i < iterations; i++) a = Arrays.copyOf(a, size); deoptimize(a);}}, new Job("clone") { void work() { Object[] a = array; for (int i = 0; i < iterations; i++) a = a.clone(); deoptimize(a);}}, new Job("loop") { void work() { Object[] a = array; for (int i = 0; i < iterations; i++) { Object[] t = new Object[size]; for (int j = 0; j < size; j++) t[j] = a[j]; a = t;} deoptimize(a);}} ); } } ------------------------------------- solaris-sparc $ bench() { jver 6 javac ArrayCopyMicroBenchmark.java && iterations=$1 size=$2 && for f in -client -server; do echo $f iterations=$iterations size=$size; jver 6 java $f ArrayCopyMicroBenchmark $iterations $size; done }; bench 10000000 1; bench 10000 1000 -client iterations=10000000 size=1 Method Millis Ratio arraycopy 1570 1.000 copyOf 3043 1.938 clone 8378 5.335 loop 889 0.566 -server iterations=10000000 size=1 Method Millis Ratio arraycopy 894 1.000 copyOf 1010 1.131 clone 8537 9.549 loop 781 0.874 -client iterations=10000 size=1000 Method Millis Ratio arraycopy 126 1.000 copyOf 127 1.011 clone 120 0.952 loop 356 2.824 -server iterations=10000 size=1000 Method Millis Ratio arraycopy 190 1.000 copyOf 193 1.011 clone 128 0.675 loop 302 1.582 linux-amd64 $ bench() { jver 6 javac ArrayCopyMicroBenchmark.java && iterations=$1 size=$2 && for f in -client -server; do echo $f iterations=$iterations size=$size; jver 6 java $f ArrayCopyMicroBenchmark $iterations $size; done }; bench 10000000 1; bench 10000 1000 -client iterations=10000000 size=1 Method Millis Ratio arraycopy 280 1.000 copyOf 303 1.083 clone 2056 7.325 loop 254 0.907 -server iterations=10000000 size=1 Method Millis Ratio arraycopy 281 1.000 copyOf 307 1.095 clone 2072 7.373 loop 257 0.917 -client iterations=10000 size=1000 Method Millis Ratio arraycopy 63 1.000 copyOf 63 1.002 clone 64 1.013 loop 100 1.573 -server iterations=10000 size=1000 Method Millis Ratio arraycopy 59 1.000 copyOf 59 1.000 clone 64 1.086 loop 99 1.685 Bottom line: For short arrays, clone() is always much slower, while for long arrays there is no difference on linux-amd64, and clone() is significantly faster on solaris-sparc! I think the right place to fix this is in hotspot. There is no inherent reason for one of these to be slower than the other. Perhaps this bug should be closed as a dup of 6428387
22-09-2006
EVALUATION Please see 6359820 and the microbenchmark provided therein. Instead of clone(), the recommended method for array copying today is Arrays.copyOf(), which is currently the fastest method, and is likely to get faster in the future. clone() is currently slightly slower than Arrays.copyOf(), but that is also likely to get fixed in some future release. Admittedly, I haven't benchmarked small arrays -- that might be worth doing, using the same microbenchmark program.
30-12-2005
EVALUATION Sounds like a good idea if provided we back it by benchmarks that shows actual reduction in execution time. ###@###.### 2004-11-16 05:02:05 GMT I made a simple micro benchmark: import static java.util.Arrays.sort; import static java.lang.System.nanoTime; public class Test { static final String[] a1 = { "a", "b" }; static final String[] a2 = { "c", "d" }; static final String[] a3 = { "e", "f" }; static final String[] a4 = { "g", "h" }; static final String[] a5 = { "i", "j" }; static void test() { sort(a1); sort(a2); sort(a3); sort(a4); sort(a5); } public static void main(String... args) { for (int i = 0 ; i < 1000; i++) test(); long time = nanoTime(); for (int i = 0 ; i < 1000; i++) test(); time = nanoTime() - time; System.out.printf("time: %d\n", time); } } Using this method: private static <T> T[] copy(T[] a) { return cloneSubarray(a, 0, a.length); } The proposed solution adds an additional overhead of 20%-30%: $ for f in 1 2 3; do > java -Djava.endorsed.dirs=copy Test > java -Djava.endorsed.dirs=clone Test > done time: 9311000 time: 7996000 time: 9355000 time: 6230000 time: 9337000 time: 7994000 One possible explanation could be that new Object[] will have to zero out the new allocated array whereas clone can skip that part. This could make clone twice as fast as new Object[] + arraycopy. ###@###.### 2004-11-16 06:08:09 GMT I'm reopening this to do some further investigations. ###@###.### 2004-11-17 06:20:08 GMT
16-11-2004