I am currently taking a Data Structures class and, as you may expect, one of the things we have to do is write some of the common sorts. In writing my insertion sort algorithm, I noticed in ran significantly faster than that of my instructor's (for 400000 data points it took my algorithm about 30 seconds and his about 90). I emailed him my code and the same results happened when they were both running on the same machine. We managed to waste more than 40 minutes slowly changing his sorting method into mine until it was exactly the same, word for word, except for one seemingly arbitrary thing. First, here is my insertion sort code:
public static int[] insertionSort(int[] A){
//Check for illegal cases
if (A == null || A.length == 0){
throw new IllegalArgumentException("A is not populated");
}
for(int i = 0; i < A.length; i++){
int j = i;
while(j > 0 && A[j - 1] > A[j]){
int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp;
j--;
}
}
return A;
}
Now at this point his code was exactly the same as mine except for the lines where we swap A[j] and A[j - 1]. His code did the following:
int temp = A[j - 1];
A[j - 1] = A[j];
A[j] = temp;
We found that those 3 lines are the culprits. My code was running significantly faster because of this. Perplexed, we ran javap -c to get the byte code for a simple program that just had a main which contained an array declaration, a variable declaration for int j and the 3 lines of code for swapping as I wrote them and as he wrote them. Here is the byte code for my swapping method:
Compiled from "me.java"
public class me {
public me();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: sipush 10000
3: newarray int
5: astore_1
6: bipush 10
8: istore_2
9: aload_1
10: iload_2
11: iaload
12: istore_3
13: aload_1
14: iload_2
15: aload_1
16: iload_2
17: iconst_1
18: isub
19: iaload
20: iastore
21: aload_1
22: iload_2
23: iconst_1
24: isub
25: iload_3
26: iastore
27: return
}
And my instructor's method's byte code:
Compiled from "instructor.java"
public class instructor {
public instructor();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: sipush 10000
3: newarray int
5: astore_1
6: bipush 10
8: istore_2
9: aload_1
10: iload_2
11: iconst_1
12: isub
13: iaload
14: istore_3
15: aload_1
16: iload_2
17: iconst_1
18: isub
19: aload_1
20: iload_2
21: iaload
22: iastore
23: aload_1
24: iload_2
25: iload_3
26: iastore
27: return
}
I don't see any real difference between these byte codes. What might cause this strange behavior (my code still ran ~3 times faster than his and as to be expected this difference got more drastic as we feed the algorithms larger arrays)? Is this simply a strange quirk of Java. Furthermore, does this happen on your computer? For reference, this was run on a MacBook Pro mid 2014 and my code is exactly as it appears here and his code was deduced to exactly the code as it appears here except for those 3 lines.
[EDIT] Here are my test classes:
public class Tester1 {
public static void main(String[] args){
int[] A = new int[400000];
for(int i = 0; i < A.length; i++){
A[i] = (int) (Math.random() * Integer.MAX_VALUE);
}
double start = System.currentTimeMillis();
insertionSort(A);
System.out.println("My insertion sort took " + (System.currentTimeMillis() - start) + " milliseconds.");
}
public static int[] insertionSort(int[] A){
//Check for illegal cases
if (A == null || A.length == 0){
throw new IllegalArgumentException("A is not populated");
}
for(int i = 0; i < A.length; i++){
int j = i;
while(j > 0 && A[j - 1] > A[j]){
int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp;
j--;
}
}
return A;
}
}
And the second file:
public class Tester2 {
public static void main(String[] args){
int[] A = new int[400000];
for(int i = 0; i < A.length; i++){
A[i] = (int) (Math.random() * Integer.MAX_VALUE);
}
double start = System.currentTimeMillis();
otherInsertion(A);
System.out.println("Other insertion sort took " + (System.currentTimeMillis() - start) + " milliseconds.");
}
public static int[] otherInsertion(int[] A){
//Check for illegal cases
if (A == null || A.length == 0){
throw new IllegalArgumentException("A is not populated");
}
for(int i = 0; i < A.length; i++){
int j = i;
while(j > 0 && A[j - 1] > A[j]){
int temp = A[j - 1];
A[j - 1] = A[j];
A[j] = temp;
j--;
}
}
return A;
}
}
And the outputs (with no arguments, just java Tester1 and java Tester2):
My insertion sort took 37680.0 milliseconds.
Other insertion sort took 86358.0 milliseconds.
These were run as 2 separate files in 2 different JVMs.
[j-1]last, which is not read on the next iteration. On the contrary, your instructor's code does read what was just stored in the previous iteration, so perhaps it suffers from what's called a load-hit-store. – Heteromerousjcounts backwards, so[j-1]is read on the next iteration. So load-hit-stores weren't it. FWIW, here's OpenJDK's machine code dump. – Heteromerous