1

I have the following implementation of simple sort algorithms (bubble, select, insert). My goal: measure execution time for these methods on the same random-generated array data with Integer elements. Array size is 10_000.

public void sortBubble() {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - 1 - i; j++) {
            if (data[j].compareTo(data[j + 1]) > 0) {
                swap(j, j + 1);
            }
        }
    }
}

public void sortSelect() {
    for (int i = 0; i < size - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < size; j++) {
            if (data[j].compareTo(data[minIndex]) < 0) {
                minIndex = j;
            }
        }
        swap(minIndex, i);
    }
}

public void sortInsert() {
    for (int i = 1; i < size; i++) {
        E temp = data[i];
        int in = i;
        while (in > 0 && data[in - 1].compareTo(temp) >= 0) {
            data[in] = data[in - 1];
            in--;
        }
        data[in] = temp;
    }
}

private void swap(int indexA, int indexB) {
    E temp = data[indexA];
    data[indexA] = data[indexB];
    data[indexB] = temp;
}

How I generate data for sorting:

Random random = new Random();
for (int i = 0; i < ARRAY_CAPACITY; i++) {
    int value = random.nextInt(MAX_VALUE);
    array.add(value);
}

When I use Java 8, my common stable result is the insertion sort is the fastest one. For example:

Sort Bubble took time: 381384 micros.
Sort Select took time: 100343 micros.
Sort Insert took time: 45580 micros.

But when I run the same code on Java 14 and more, suddenly (for me) the selection sort is faster than the insert one:

Sort Bubble took time: 521345 micros.
Sort Select took time: 119718 micros.
Sort Insert took time: 144706 micros.

I've checked a code several times: there are no differences and unusual cases in how I run this code. This issue is reproduced stably. I guess, it's related to changes since the 14th Java version, but I have no idea what exactly. Do you know what can be the main reason for that?

Thanks in advance.

Oleg Krylov
  • 35
  • 6
  • 2
    Did you write a proper microbenchmark? And in particular: did you give the code the time to "get hot"? – Turing85 May 23 '21 at 23:10
  • 3
    No offence meant, but you aren't doing this right. Performance testing java is *much* more complicated than this. Your array is tiny, you don't warm-up or cool down. You haven't measured anything at all like this. Your results are meaningless. You should ignore them. – Software Engineer May 23 '21 at 23:10
  • This [Oracle article](https://www.oracle.com/technical-resources/articles/java/architect-benchmarking.html) details some of the issues benchmarking like this. [JMH](https://openjdk.java.net/projects/code-tools/jmh/) gives a way to get around these. – BeUndead May 23 '21 at 23:24
  • 1
    And please read: [How do I write a correct micro-benchmark in Java?](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) – Turing85 May 23 '21 at 23:25
  • 1
    For what it's worth, the whole point of improving Java is to... well, improve Java. Improvement means, among other things, better performance from existing code. Improvements don't necessarily have to be uniform; it's entirely possible (and in fact, rather likely) for performance improvements to have better effects in one situation than in another. – Robert Harvey May 24 '21 at 02:40

0 Answers0