Menu
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.
359
What is the easiest sorting algorithm? Bubble sort is widely recognized as the simplest sorting algorithm out there. Its basic idea is to scan through an entire array and compare adjacent elements and swap them (if necessary) until the list is sorted.
Timsort (derived from merge sort and insertion sort) was introduced in 2002 and while slower than quicksort for random data, Timsort performs better on ordered data. Quadsort (derived from merge sort) was introduced in 2020 and is faster than quicksort for random data, and slightly faster than Timsort on ordered data.
Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical or lexicographical order.
V8 uses Timsort, for example. The spec does not mandate any particular sorting algorithm.
This is the effect of loop unrolling optimization along with common subexpression elimination. Depending on the order of array access instructions, JIT can eliminate redundant loads in one case, but not in the other.
Let me explain in details. In both cases JIT unrolls 4 iterations of the inner loop.
E.g. for your case:
while (j > 3) {
if (A[j - 1] > A[j]) {
int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp; \
} A[j - 1] loaded immediately after store
if (A[j - 2] > A[j - 1]) { /
int temp = A[j - 1];
A[j - 1] = A[j - 2];
A[j - 2] = temp; \
} A[j - 2] loaded immediately after store
if (A[j - 3] > A[j - 2]) { /
int temp = A[j - 2];
A[j - 2] = A[j - 3];
A[j - 3] = temp; \
} A[j - 3] loaded immediately after store
if (A[j - 4] > A[j - 3]) { /
int temp = A[j - 3];
A[j - 3] = A[j - 4];
A[j - 4] = temp;
}
j -= 4;
}
Then JIT eliminates redundant array loads, and the resulting assembly looks like
0x0000000002d53a70: movslq %r11d,%r10
0x0000000002d53a73: lea 0x0(%rbp,%r10,4),%r10
0x0000000002d53a78: mov 0x10(%r10),%ebx ; ebx = A[j]
0x0000000002d53a7c: mov 0xc(%r10),%r9d ; r9d = A[j - 1]
0x0000000002d53a80: cmp %ebx,%r9d ; if (r9d > ebx) {
0x0000000002d53a83: jle 0x0000000002d539f3
0x0000000002d53a89: mov %r9d,0x10(%r10) ; A[j] = r9d
0x0000000002d53a8d: mov %ebx,0xc(%r10) ; A[j - 1] = ebx
; }
0x0000000002d53a91: mov 0x8(%r10),%r9d ; r9d = A[j - 2]
0x0000000002d53a95: cmp %ebx,%r9d ; if (r9d > ebx) {
0x0000000002d53a98: jle 0x0000000002d539f3
0x0000000002d53a9e: mov %r9d,0xc(%r10) ; A[j - 1] = r9d
0x0000000002d53aa2: mov %ebx,0x8(%r10) ; A[j - 2] = ebx
; }
0x0000000002d53aa6: mov 0x4(%r10),%r9d ; r9d = A[j - 3]
0x0000000002d53aaa: cmp %ebx,%r9d ; if (r9d > ebx) {
0x0000000002d53aad: jle 0x0000000002d539f3
0x0000000002d53ab3: mov %r9d,0x8(%r10) ; A[j - 2] = r9d
0x0000000002d53ab7: mov %ebx,0x4(%r10) ; A[j - 3] = ebx
; }
0x0000000002d53abb: mov (%r10),%r8d ; r8d = A[j - 4]
0x0000000002d53abe: cmp %ebx,%r8d ; if (r8d > ebx) {
0x0000000002d53ac1: jle 0x0000000002d539f3
0x0000000002d53ac7: mov %r8d,0x4(%r10) ; A[j - 3] = r8
0x0000000002d53acb: mov %ebx,(%r10) ; A[j - 4] = ebx
; }
0x0000000002d53ace: add $0xfffffffc,%r11d ; j -= 4
0x0000000002d53ad2: cmp $0x3,%r11d ; while (j > 3)
0x0000000002d53ad6: jg 0x0000000002d53a70
Your instructor's code will look different after loop unrolling:
while (j > 3) {
if (A[j - 1] > A[j]) {
int temp = A[j - 1];
A[j - 1] = A[j];
A[j] = temp; <-- another store instruction between A[j - 1] access
}
if (A[j - 2] > A[j - 1]) {
int temp = A[j - 2];
A[j - 2] = A[j - 1];
A[j - 1] = temp;
}
...
JVM will not eliminate the subsequent load of A[j - 1], because there is another store instruction after the previous load of A[j - 1] (though in this particular case such optimization is theoretically possible).
So, the assembly code will have more load instructions, and the performance will be worse:
0x0000000002b53a00: cmp %r8d,%r10d ; if (r10d > r8d) {
0x0000000002b53a03: jle 0x0000000002b53973
0x0000000002b53a09: mov %r8d,0xc(%rbx) ; A[j - 1] = r8d
0x0000000002b53a0d: mov %r10d,0x10(%rbx) ; A[j] = r10d
; }
0x0000000002b53a11: mov 0xc(%rbx),%r10d ; r10d = A[j - 1]
0x0000000002b53a15: mov 0x8(%rbx),%r9d ; r9d = A[j - 2]
0x0000000002b53a19: cmp %r10d,%r9d ; if (r9d > r10d) {
0x0000000002b53a1c: jle 0x0000000002b53973
0x0000000002b53a22: mov %r10d,0x8(%rbx) ; A[j - 2] = r10d
0x0000000002b53a26: mov %r9d,0xc(%rbx) ; A[j - 1] = r9d
; }
0x0000000002b53a2a: mov 0x8(%rbx),%r8d ; r8d = A[j - 2]
0x0000000002b53a2e: mov 0x4(%rbx),%r10d ; r10d = A[j - 3]
Note, that if you run JVM with loop unrolling optimization disabled (-XX:LoopUnrollLimit=0), the performance of both cases will be the same.
P.S. Full disassembly of both methods is available here, obtained using-XX:CompileOnly=Test -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly
78
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
