Sorting time always different from first sort

Question

I wrote couple sorting algorithm. I want to compare their sorting times, at least nearly. But after first loop all sorting times decreasing except StoogeSort. I think something optimizating at background but which measure should I consider? First one or the others? And why is this happening?

    public static void main(String[] args) {
    RandomNumber rn = new RandomNumber();

    Scanner sc = new Scanner(System.in);
    while(true){
        System.out.println("Enter the input size.");
        int n = sc.nextInt();
        int[] experimentalArray = rn.experimentalArrayGenerator(n);



        Stopwatch sw1 = new Stopwatch();
        StoogeSort ss = new StoogeSort(experimentalArray.clone());
        System.out.println("StoogeSort : " + sw1.elapsedTime() + " µs");

        Stopwatch sw2 = new Stopwatch();
        RadixSort rs = new RadixSort(experimentalArray.clone());
        System.out.println("RadixSort : " + sw2.elapsedTime() + " µs");

        Stopwatch sw3 = new Stopwatch();
        ShakerSort shs = new ShakerSort(experimentalArray.clone());
        System.out.println("ShakerSort : " + sw3.elapsedTime() + " µs");

        Stopwatch sw4 = new Stopwatch();
        MaximumSubarray ms = new MaximumSubarray();
        int a = ms.maxSubArraySum(experimentalArray.clone());
        System.out.println("MaximumSubarray : " + sw4.elapsedTime() + " µs");
        System.out.println("------------------------------------------------------");
    }
}

Output after 4 loop:

Sorting random number arrays will almost never take the same amount of time. — Konstantinos Kamaropoulos, Mar 24 '17 at 15:31
But this is weird. Just the first one different from others. — Pareidolia, Mar 24 '17 at 15:33
Take for example the array [1,2,3,4,5,6,7,8,9,10]. How many itterations would an algorithm take to sort it? Then consider the array [10,5,3,7,2,8,1,9,6,4]. Would it take the same amount of time? — Konstantinos Kamaropoulos, Mar 24 '17 at 15:34
Aside from anything else, the first execution path will involve different JITting, quite possibly different GC experiences etc. — Jon Skeet, Mar 24 '17 at 15:34

score 1 · Answer 1 · answered Mar 24 '17 at 16:14

Microbenchmarking is a complicated matter as many factors influence the execution time (e.g. just-in-time compilation and garbage collection as noted by Jon Skeet in the comments).

You should read this document by Peter Sestoft if you want to gain an understanding of how you should approach microbenchmarking.

Quoting the abstract of the document here, as the document is an external resource:

Sometimes one wants to measure the speed of software, for instance, to measure whether a new way to solve a problem is faster than the old one. Making such time measurements and microbenchmarks requires considerable care, especially on managed platforms like the Java Virtual Machine and Microsoft’s Common Language Infrastructure (.NET), or else the results may be arbitrary and misleading.

Here we give some advice on running microbenchmarks, in particular for managed platforms. Most examples are in Java but the advice applies to any language executed on a managed platform, including Scala, C# and F#. This version uses Java functional interfaces and requires Java 8.

Sorting time always different from first sort

1 Answers1

Linked