JMH microbenchmarking recursive quicksort

benchmarking, java, jmh, microbenchmark, quicksort

Solution

Ok, since there really should be an answer here (instead of having to go through the comments below the question), I'm putting it here as I got burned.

An iteration in JMH is a batch of benchmark method invocations (depends on how long an iteration is set to be). So using @Setup(Level.Iteration) will only do setup at the beginning of a sequence of invocations. Since the array is sorted after the first invocation, quicksort is being called on the worst possible scenario (a sorted array) on subsequent invocations. That's why it takes so long or blows the stack.

So a solution is to use @Setup(Level.Invocation). However, as stated in the Javadoc:

**
     * Invocation level: to be executed for each benchmark method execution.
     *
     * <p><b>WARNING: HERE BE DRAGONS! THIS IS A SHARP TOOL.
     * MAKE SURE YOU UNDERSTAND THE REASONING AND THE IMPLICATIONS
     * OF THE WARNINGS BELOW BEFORE EVEN CONSIDERING USING THIS LEVEL.</b></p>
     *
     * <p>This level is only usable for benchmarks taking more than a millisecond
     * per single {@link Benchmark} method invocation. It is a good idea to validate
     * the impact for your case on ad-hoc basis as well.</p>
     *
     * <p>WARNING #1: Since we have to subtract the setup/teardown costs from
     * the benchmark time, on this level, we have to timestamp *each* benchmark
     * invocation. If the benchmarked method is small, then we saturate the
     * system with timestamp requests, which introduce artificial latency,
     * throughput, and scalability bottlenecks.</p>
     *
     * <p>WARNING #2: Since we measure individual invocation timings with this
     * level, we probably set ourselves up for (coordinated) omission. That means
     * the hiccups in measurement can be hidden from timing measurement, and
     * can introduce surprising results. For example, when we use timings to
     * understand the benchmark throughput, the omitted timing measurement will
     * result in lower aggregate time, and fictionally *larger* throughput.</p>
     *
     * <p>WARNING #3: In order to maintain the same sharing behavior as other
     * Levels, we sometimes have to synchronize (arbitrage) the access to
     * {@link State} objects. Other levels do this outside the measurement,
     * but at this level, we have to synchronize on *critical path*, further
     * offsetting the measurement.</p>
     *
     * <p>WARNING #4: Current implementation allows the helper method execution
     * at this Level to overlap with the benchmark invocation itself in order
     * to simplify arbitrage. That matters in multi-threaded benchmarks, when
     * one worker thread executing {@link Benchmark} method may observe other
     * worker thread already calling {@link TearDown} for the same object.</p>
     */

So as Aleksey Shipilev suggests, absorb the array copy cost into each benchmark method. Since you are comparing relative performance, this shouldn't affect your results.

Problem

Hello I'm trying to micro benchmark various sorting algorithms and I got a strange problem with jmh and benchmarking quicksort. Maybe there is something wrong with my implementation. I would be interested if someone could help me to see where is the problem. First of all I use ubuntu 14.04 with jdk 7 and jmh 0.9.1. Here is how I try to do a benchmark: ``` @OutputTimeUnit(TimeUnit.MILLISECONDS) @BenchmarkMode(Mode.AverageTime) @Warmup(iterations = 3, time = 1) @Measurement(iterations = 3, time = 1) @State(Scope.Thread) public class SortingBenchmark { private int length = 100000; private Distribution distribution = Distribution.RANDOM; private int[] array; int i = 1; @Setup(Level.Iteration) public void setUp() { array = distribution.create(length); } @Benchmark public int timeQuickSort() { int[] sorted = Sorter.quickSort(array); return sorted[i]; } @Benchmark public int timeJDKSort() { Arrays.sort(array); return array[i]; } public static void main(String[] args) throws RunnerException { Options opt = new OptionsBuilder().include(".*" + SortingBenchmark.class.getSimpleName() + ".*").forks(1) .build(); new Runner(opt).run(); } } ``` There are other algorithms, but I left them out as they are more or less OK. Now quicksort for some reason is extremely slow. Magnitudes of time slower! And even more - I need to assign more stack space for it to run without StackOverflowException. It looks like for some reason quicksort just does a lot of recursive calls. The interesting thing is that when I simply run algorithm in my main class - it runs fine (with same random distribution and 100000 elements). No need for stack increase and simple nanotime benchmark shows times that are very close to other algorithms. And in benchmark JDK sort is very fast when testing with jmh and much more in line with other algorithms with naive nanotime benchmarking. Am I doing something wrong here or miss something? Here is my quicksort algorithm: ``` public static int[] quickSort(int[] data) { Sorter.quickSort(data, 0, data.length - 1); return data; } private static void quickSort(int[] data, int sublistFirstIndex, int sublistLastIndex) { if (sublistFirstIndex < sublistLastIndex) { // move smaller elements before pivot and larger after int pivotIndex = partition(data, sublistFirstIndex, sublistLastIndex); // apply recursively to sub lists Sorter.quickSort(data, sublistFirstIndex, pivotIndex - 1); Sorter.quickSort(data, pivotIndex + 1, sublistLastIndex); } } private static int partition(int[] data, int sublistFirstIndex, int sublistLastIndex) { int pivotElement = data[sublistLastIndex]; int pivotIndex = sublistFirstIndex - 1; for (int i = sublistFirstIndex; i < sublistLastIndex; i++) { if (data[i] <= pivotElement) { pivotIndex++; ArrayUtils.swap(data, pivotIndex, i); } } ArrayUtils.swap(data, pivotIndex + 1, sublistLastIndex); return pivotIndex + 1; // return index of pivot element } ``` Now I understand that because of my pivot selection my algorithm would be very slow (O(n^2)) if I would run it on already sorted data. But still I run it on randomized one and even when I tried to run it on sorted data in my main method it was much faster that the version with jmh on randomized data. I'm pretty sure I'm missing something here. You can find full project with other algorithms here: https://github.com/ignl/SortingAlgos/

Original source