-1

I have implemented merge sort in Java. Instance of the class is named ms. rArray is a random integer array. For testing i ran it with the following code:

for (int i=0; i<10; i++) {
        System.out.println("Starting Merge Sort");
        testArray = rArray; // Create duplicate for testing
        long startM = System.currentTimeMillis();
        ms.sort(testArray);
        long stopM = System.currentTimeMillis();
        long durationM = stopM-startM;
        System.out.println("Size: " + size + "; Duration: " + durationM + "ms");
        System.out.println("++++++++++++++++++++++++++++++++++++++++++");
    }

Output:

Starting Merge Sort
Size: 1000000; Duration: 5853ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 4527ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 4082ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3000ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 2930ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 2904ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3403ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3570ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 2930ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3133ms

It is the same pattern for every run. Why is it always speeding up? I guess it has to do with the compiler, since Arrays.sort shows the same behaviour. What i don't understand is, if i first run Arrays.sort and then my implementation of merge sort, why is the latter still faster compared to if i run my implementation of merge sort on it's own?

Update

After using System.arraycopy(rArray, 0, testArray, 0, rArray.length); as suggested by Makoto (Thanks!), the output is getting better. But as for Merge sort it remains the same. My implementation of merge sort is not saving the sorting result. So is the reason for this speedup the JIT Warmup?

New Output:

Starting Default Sort
Size: 1000000; Duration: 1799ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 1816ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 945ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 944ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 944ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 943ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 957ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 963ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 964ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 952ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 5913ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3171ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3093ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 4816ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3685ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3094ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3488ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3660ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3094ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3604ms
Community
  • 1
  • 1
NoMorePen
  • 43
  • 2
  • 8
  • 2
    Ten iterations, no JIT warmup...I personally wouldn't trust this benchmark. – Makoto Oct 07 '15 at 16:35
  • How to do JIT warmup? – NoMorePen Oct 07 '15 at 16:37
  • "One possible optimization, used by Sun's HotSpot Java Virtual Machine, is to combine interpretation and JIT compilation. The application code is initially interpreted, but the JVM monitors which sequences of bytecode are frequently executed and translates them to machine code for direct execution on the hardware." -- https://en.wikipedia.org/wiki/Just-in-time_compilation – Andy Thomas Oct 07 '15 at 16:39
  • It's a shame we don't have more code so I could show you a more proper way to do the benchmarking. But, Sem Gnil has answered the question as to *why* it appears to be going faster. If you want to actually copy the contents of the array over to a new one, then use `System.arraycopy(rArray, 0, testArray, 0, rArray.length);` instead. – Makoto Oct 07 '15 at 16:45
  • Thank you. I did change my code accordingly. However, for merge sort it doesn't change the outcome, since my implementation does not save the results to the array. It is just sorting. – NoMorePen Oct 07 '15 at 17:23

3 Answers3

5

testArray = rArray. This will not create a duplicate. It just creates a new reference to the rArray. So, you are sorting already sorted array.

Semyon Tikhonenko
  • 3,872
  • 6
  • 36
  • 61
  • This is likely part of it. Also JIT warmup likely factors in -- that would explain the intermediate runtime of the second run. The duration of these runs is roughly right for JIT to kick in some time during the second sorting run. – John Bollinger Oct 07 '15 at 16:38
  • I forgot to state that my implementation actually does not save the resulting array. After using deep copy, the times remain roughly the same. The reason must be somewhere else - like JIT warmup, etc. – NoMorePen Oct 07 '15 at 17:08
1

Benchmarking in java is in general rather complicated (How do I write a correct micro-benchmark in Java?). Next problem: testArray = rArray; doesn't generate a copy. You're sorting the same array multiple times. After the first run, the array is already sorted.

Community
  • 1
  • 1
0

If you want to clone an ArrayList, you can use this code:

 public static List<Dog> cloneList(List<Dog> list) {
    List<Dog> clone = new ArrayList<Dog>(list.size());
    for(Dog item: list) clone.add(item.clone());
    return clone;
}
user1531914
  • 83
  • 5