find min max in an array of integer, performance issue

Question

I wrote these two methods here to find min and max. #2 is based on this answer from this post here.

private static Pair classicMinMax(int[] elements) {
    int min = MAX_VALUE;
    int max = MIN_VALUE;

    for (int i = 0; i < elements.length; i++) {
        int e = elements[i];
        if (e < min) min = e;
        if (e > max) max = e;
    }
    return new Pair(min, max);

}

private static Pair divideAndConquer(int[] elements) {
    int min = MAX_VALUE;
    int max = MIN_VALUE;

    for (int i = 0; i < elements.length - 1; i += 2) {
        int a = elements[i];
        int b = elements[i + 1];

        if (a > b) {
            if (b < min) min = b;
            if (a > max) max = a;
        } else {
            if (a < min) min = a;
            if (b > max) max = b;
        }
    }

    if (elements.length % 2 != 0) {
        int lastElement = elements[elements.length - 1];
        if (lastElement < min) min = lastElement;
        if (lastElement > max) max = lastElement;
    }
    return new Pair(min, max);
}

If I run simple benchmarks like this:

@Test
public void timingsBoth() throws Exception {

    int size = 1000;

    for (int i = 1000; i < 10_000; i += 1000) {
        int arraySize = size * i;
        System.out.println("step is " + arraySize);

        List<Integer> list = new ArrayList<>(arraySize);
        int[] elements = new int[arraySize];
        for (int k = 0; k < arraySize; k++) {
            list.add(k);
        }

        Collections.shuffle(list);
        Integer[] integers = list.toArray(new Integer[0]);
        for (int k = 0; k < arraySize; k++) {
            elements[k] = integers[k];
        }

        long start = currentTimeMillis();
        classicMinMax(elements);
        long stop = currentTimeMillis();
        long result = stop - start;
        System.out.println("classic is " + result);

        start = currentTimeMillis();
        divideAndConquer(elements);
        stop = currentTimeMillis();
        result = stop - start;
        System.out.println("divideAndConquer is " + result);
    }
}

}

And I'm usually getting this result:

step is 1000000 classic is 8 divideAndConquer is 11 step is 2000000 classic is 2 divideAndConquer is 5 step is 3000000 classic is 11 divideAndConquer is 17 step is 4000000 classic is 5 divideAndConquer is 10 step is 5000000 classic is 4 divideAndConquer is 16 step is 6000000 classic is 6 divideAndConquer is 14 step is 7000000 classic is 6 divideAndConquer is 18 step is 8000000 classic is 8 divideAndConquer is 20 step is 9000000 classic is 8 divideAndConquer is 24

Did I get the algorithm wrong? I was expecting at least a similar result.

Answer 1

Ok, following advices from the comments I think I did a better benchmark. What I used is Java Microbenchmark Harness. I never used it before so I based my test on this handy tutorial.

What I did was creating a JMH test like follows:

public class MinMaxBenchmark {

    @State(Scope.Benchmark)
    public static class MyState {

        int arraySize = 50_0000;
        int[] elements = new int[arraySize];

        @Setup(Level.Trial)
        public void doSetup() {
            List<Integer> list = new ArrayList<>(arraySize);
            for (int k = 0; k < arraySize; k++) {
                list.add(k);
            }
            Collections.sort(list);
            Integer[] integers = list.toArray(new Integer[0]);
            for (int k = 0; k < arraySize; k++) {
                elements[k] = integers[k];
            }

        }
    }


    @Benchmark @BenchmarkMode(Mode.SampleTime   ) @OutputTimeUnit(TimeUnit.MILLISECONDS)
    public Pair classic(MyState state) {
        return classicMinMax(state.elements);
    }
    @Benchmark @BenchmarkMode(Mode.SampleTime) @OutputTimeUnit(TimeUnit.MILLISECONDS)
    public Pair divide(MyState state) {
        return divideAndConquer(state.elements);
    }

}

I put special attention to create the array (input data) outside the benchmark creating a @State with a @Setup method for initialization. Than I wrote the to @Benchmark methos. I was really careful in returning the result so dead code could be avoided (it's all in the tutorial).

With this setup I run several trials. This one is the last attempt:

Benchmark Mode Cnt Score Error Units MinMaxBenchmark.classic sample 994028 0.202 ± 0.001 ms/op MinMaxBenchmark.classic:classic·p0.00 sample 0.153 ms/op MinMaxBenchmark.classic:classic·p0.50 sample 0.180 ms/op MinMaxBenchmark.classic:classic·p0.90 sample 0.259 ms/op MinMaxBenchmark.classic:classic·p0.95 sample 0.311 ms/op MinMaxBenchmark.classic:classic·p0.99 sample 0.409 ms/op MinMaxBenchmark.classic:classic·p0.999 sample 0.567 ms/op MinMaxBenchmark.classic:classic·p0.9999 sample 0.942 ms/op MinMaxBenchmark.classic:classic·p1.00 sample 2.617 ms/op MinMaxBenchmark.divide sample 1226029 0.164 ± 0.001 ms/op MinMaxBenchmark.divide:divide·p0.00 sample 0.126 ms/op MinMaxBenchmark.divide:divide·p0.50 sample 0.149 ms/op MinMaxBenchmark.divide:divide·p0.90 sample 0.201 ms/op MinMaxBenchmark.divide:divide·p0.95 sample 0.230 ms/op MinMaxBenchmark.divide:divide·p0.99 sample 0.327 ms/op MinMaxBenchmark.divide:divide·p0.999 sample 0.522 ms/op MinMaxBenchmark.divide:divide·p0.9999 sample 0.945 ms/op MinMaxBenchmark.divide:divide·p1.00 sample 3.199 ms/op

Where actually the divide is only losing on p1.00 (I need to find the meaning).

So I guess it was a problem of the way I handled benchmarking.

Thank you for the help in the comments, especially @alfasin.