Sorting Algorithm Performance Comparisons with Caliper's Micro Benchmarking

After inspired by Martin Thompson's presentation on Performance Testing Java Application, I decided to try out the micro benchmarking framework Caliper on the sorting algorithms that I recently wrote in order to understand better how different sorting algorithms behaves given an array of randomly distributed values.

It was actually a bit involving to find out where I could download the caliper JAR file, as it was not available on their google code base. You can download it from the maven repository, or grab it from my git described at the bottom of this article.

I created a SortingAlgorithmsBenchmark class that extends SimpleBenchmark, and some public methods, whose names have prefix 'time'. Then use the caliper Runner to run the benchmarks on the SortingAlgorithmsBenchmark class, as shown below

import com.google.caliper.Runner;
import com.google.caliper.SimpleBenchmark;
import sorting.*;

import java.util.Arrays;
import java.util.Random;

public class SortingAlgorithmsBenchmark extends SimpleBenchmark {

    private static final int SIZE = 10000;
    private static final int MAX_VALUE = 10000;
    private int[] values;

    @Override
    protected void setUp() throws Exception {
        values = new int[SIZE];
        Random generator = new Random();
        for (int i = 0; i < values.length; i++) {
            values[i] = generator.nextInt(MAX_VALUE);
        }
    }

    public void timeBubbleSort(int reps) {
        for (int i = 0; i < reps; i++) {
            BubbleSort.sort(values);
        }
    }

    public void timeInsertionSort(int reps) {
        for (int i = 0; i < reps; i++) {
            InsertionSort.sort(values);
        }
    }

    public void timeSelectionSort(int reps) {
        for (int i = 0; i < reps; i++) {
            SelectionSort.sort(values);
        }
    }

    public void timeMergeSort(int reps) {
        for (int i = 0; i < reps; i++) {
            MergeSort.sort(values);
        }
    }

    public void timeShellSort(int reps) {
        for (int i = 0; i < reps; i++) {
            ShellSort.sort(values);
        }
    }

    public void timeArraysSort(int reps) {
        for (int i = 0; i < reps; i++) {
            Arrays.sort(values);
        }
    }

    public static void main(String[] args) {
        Runner.main(SortingAlgorithmsBenchmark.class, args);
    }

}

Here are the results when running the benchmarks with a random array of size 10,000. Apparently, bubble sort and selection sort are the slowest of all, with selection sort behaving rather unstable (you will notice the selection sort benchmark is quite different across different runs. It is pleased to see that the sorting algorithm (Dual-Pivot Quick Sort) used by Arrays performs fairly well with a medium size array.

0% Scenario{vm=java, trial=0, benchmark=BubbleSort} 75703105.85 ns; σ=3428843.80 ns @ 10 trials
17% Scenario{vm=java, trial=0, benchmark=InsertionSort} 73305.66 ns; σ=712.37 ns @ 6 trials
33% Scenario{vm=java, trial=0, benchmark=SelectionSort} 49624130.05 ns; σ=345774.06 ns @ 3 trials
50% Scenario{vm=java, trial=0, benchmark=MergeSort} 478932.15 ns; σ=683.99 ns @ 3 trials
67% Scenario{vm=java, trial=0, benchmark=ShellSort} 262061.27 ns; σ=11605.29 ns @ 10 trials
83% Scenario{vm=java, trial=0, benchmark=ArraysSort} 8063.53 ns; σ=20167.07 ns @ 10 trials

    benchmark       us linear runtime
   BubbleSort 75703.11 ==============================
InsertionSort    73.31 =
SelectionSort 49624.13 ===================
    MergeSort   478.93 =
    ShellSort   262.06 =
   ArraysSort     8.06 =

vm: java
trial: 0

Increasing the array size to 100,000, and excluding the bubble sort and selection sort in the benckmarks, we have another set of results, where insertion sort starts to behave terribly in this case, and the dual-pivot quick sort is still the quickest.

0% Scenario{vm=java, trial=0, benchmark=InsertionSort} 2031873339.00 ns; σ=3247182.51 ns @ 3 trials
25% Scenario{vm=java, trial=0, benchmark=MergeSort} 5701257.43 ns; σ=37183.00 ns @ 3 trials
50% Scenario{vm=java, trial=0, benchmark=ShellSort} 2277851.07 ns; σ=21077.62 ns @ 3 trials
75% Scenario{vm=java, trial=0, benchmark=ArraysSort} 210179.59 ns; σ=164843.22 ns @ 10 trials

    benchmark      us linear runtime
InsertionSort 2031873 ==============================
    MergeSort    5701 =
    ShellSort    2278 =
   ArraysSort     210 =

vm: java
trial: 0

You can find the source code for the sorting algorithms here, and the benchmarks runner here, all of which are part of my github project DataStructureAndAlgorithms