Very Strange Efficiency Quirks while Sorting

Question

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.

Answer 1

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