Why the execution time of a program changes significantly?

Question

I'd like to test the execution time of different sorting algorithms and I found an interesting problem. When I run the program multiple times, say the insert sorting, the first one or two times cost much more time than later ones. This scenario happens when the size of array is big, also different sizes have different effect on the execution time.

public static void insertSort(int[] array){
    for(int i = 1; i<array.length; i++){
        int current = array[i];
        int j = i-1;
        while((j>=0)&&(array[j]>current)){
            array[j+1] = array[j];
            array[j] = current; 
            j--;
        }
    }
}

public static void multiTimes(int size){
    Random r = new Random();    
    int a[] = new int[size];
    int b[] = new int[size];
    for(int j = 0; j<size; j++)
        a[j] = r.nextInt(size); 

    long startTime, endTime = 0;

    b = Arrays.copyOf(a, a.length);
    startTime=System.nanoTime();  
    insertSort(b);
    endTime=System.nanoTime();  
    System.out.println("Insert  "+(endTime-startTime)+"   ns"); 

    b = Arrays.copyOf(a, a.length);
    startTime=System.nanoTime();  
    insertSort(b);
    endTime=System.nanoTime();  
    System.out.println("Insert  "+(endTime-startTime)+"   ns"); 

    b = Arrays.copyOf(a, a.length);
    startTime=System.nanoTime();  
    insertSort(b);
    endTime=System.nanoTime();  
    System.out.println("Insert  "+(endTime-startTime)+"   ns"); 

    b = Arrays.copyOf(a, a.length);
    startTime=System.nanoTime();  
    insertSort(b);
    endTime=System.nanoTime();  
    System.out.println("Insert  "+(endTime-startTime)+"   ns"); 

    b = Arrays.copyOf(a, a.length);
    startTime=System.nanoTime();  
    insertSort(b);
    endTime=System.nanoTime();  
    System.out.println("Insert  "+(endTime-startTime)+"   ns"); 

    b = Arrays.copyOf(a, a.length);
    startTime=System.nanoTime();  
    insertSort(b);
    endTime=System.nanoTime();  
    System.out.println("Insert  "+(endTime-startTime)+"   ns");
}

Size: 100
Insert 77908 ns
Insert 82573 ns
Insert 75109 ns
Insert 76508 ns
Insert 91902 ns
Insert 78840 ns

Each time the execution time is similar.

size: 1000:
Insert 6256400 ns
Insert 5674659 ns
Insert 188938 ns
Insert 188004 ns
Insert 187071 ns
Insert 186605 ns

size: 2000:
Insert 7961037 ns
Insert 6590889 ns
Insert 793538 ns
Insert 793072 ns
Insert 793072 ns
Insert 792138 ns

We can see that for the size of 1000, 2000 or more, the results are quite interesting. The execution time of first two times are about 30 times more than later executions (size = 1000).

Note:

1. Language: Java JDK7; IDE: Eclipse; Platform: Win8.1;
2. For each size, many experiments are tested and the results are quite similar. Although the execution time has some randomness, but it cannot explain why first two times are similar and more than 30x longer than later ones.
3. A possible reason may be the array is already in data cache so later executions cost less time. I'm not sure if there are other reasons.

PS: After I tested insert sort, I found it even confusing in quick sort.

public static void quickSort(int a[], int left, int right){
    if(right<=left)
        return;
    int temp[] = new int[right-left+1];
    for(int i = left; i<=right; i++)
        temp[i-left] = a[i];
    int pivot = a[left];
    int subr = right, subl = left;
    for(int i = left+1; i<=right;i++){
        if(temp[i-left]>pivot)
            a[subr--] = temp[i-left];
        else
            a[subl++] = temp[i-left];
    }
    a[subl] = pivot;
    quickSort(a, left, subl-1);
    quickSort(a, subr+1, right);
}

Size = 1000:
Qs 888240 ns
Qs 2218734 ns
Qs 2179547 ns
Qs 2132896 ns
Qs 2146890 ns
Qs 2212670 ns

Size = 500:
Qs 432924 ns
Qs 406799 ns
Qs 941889 ns
Qs 1103302 ns
Qs 1101436 ns
Qs 1086042 ns

When the size is around [200, 2000], the first several times cost less time than later ones, which is opposite than insert sort. When size increases to more than 2000, it is similar to scenarios in insert sort in which later executions cost less time.

Answer 1

When you remove the complete method body of your sort method and call it with your current code, you will notice the same effect - on a smaller scale:

Insert  1488   ns
Insert  353   ns
Insert  246   ns
Insert  240   ns
Insert  224   ns
Insert  212   ns

If you are now going to remove the attribute int[] array as well, you will still notice the same effect:

Insert  1452   ns
Insert  342   ns
Insert  232   ns
Insert  203   ns
Insert  228   ns
Insert  209   ns

So, obviously this behaviour is independent from the data(-sate), the memory allocation or the duplication of some values already present in memory.

Obviously, with only having the method stub

public static void insertSort(){

}

left, it needs to have something todo with the method declaration itself. As AlexR already Stated, Java has a JIT-Compiler. And since there is nothing left about data there could be only ONE reason for this behaviour: Runtime Optimization.

• Java is compiled code, meaning the written Java-Soure is compiled to a lower level language when building the application.
• When a language is compiled there can be various steps of abstraction. Every single character needs (ultimately) be translated from a human readable code to "zeros" and "ones" - with a language dependent number of layers in between.
• Since you do not know the runtime-data at design time, it can not be translated down to 1 and 0 - so the code remains somewhere in between. (but it can be translated further during runtime, when you finally KNOW the data and have repeated access to the same method with the same data!)
• One thing that is in common for every language: Same input equals same output.
• Therefore every layer might have its own (internal) cache to speed up things and reduce CPU/memory load.

Just like you can reuse a object within java to avoid reloading from the database, every layer in between can reuse bits and bytes that have already been used.

(Viewing this effect from the database's point of view would raise the same question: Why does the first time the string is displayed take 125ms, and every other time just 5ms?)

---

Imagine a room of 10 people and you are asking one person: What's the average age in here? - The person would need to ask everyone for his age, perform some calculations in order to answer with 25.

If you would ask again - without having ANYTHING changed - The answer would be present immediately. (Copying the array would be a room switch while maintaining the same persons)

But if you would change the persons (regardless if keeping or changing the room) - the whole algorithm needs to be executed again.

And this example has just one layer in between (the asked person) that might remember already asked questions.

Answer 2

There can be a lot of reasons but in your case I believe this is the effect of JIT (Just In Time Compiling) that compiles into native code most recently used fragments of byte code. This is the reason that first 2 executions are slower. They are done by JVM that interprets java byte code. Then JIT compiles your sorting algorithm into native code and JVM executes it that gives significant performance benefit.