Почему общая версия в 4 раза медленнее, чем специальная версия, когда я работаю с упорядоченным массивом в сортировке вставками, которую я реализовал?

Я не думаю, что есть какая-то разница между двумя методами после полной JIT, но дело в том, что разница во времени между двумя методами составляет четыре раза.

Что здесь случилось

Реализация сортировки вставками выглядит следующим образом.

public class Insert {
    public static void special(int[] unsorted) {
        for (int now = 1; now < unsorted.length; now++) {
            int target = 0;
            final int value = unsorted[now];

            for (int i = now - 1; i >= 0; i--) {
                if (unsorted[i] < value) {
                    target = i + 1;
                    break;
                }
            }
            if (target != now) {
                System.arraycopy(unsorted, target, unsorted, target + 1, now - target);
                unsorted[target] = value;
            }
        }
    }

    public static void general(int[] unsorted, boolean isDown, int start, int end) {
        for (int now = start + 1; now < end; now++) {
            int target = start;
            final int value = unsorted[now];
            if (isDown) {
                for (int i = now - 1; i >= start; i--) {
                    if (unsorted[i] > unsorted[now]) {
                        target = i + 1;
                        break;
                    }
                }
            } else {
                for (int i = now - 1; i >= start; i--) {
                    if (unsorted[i] < unsorted[now]) {
                        target = i + 1;
                        break;
                    }
                }
            }
            if (target != now) {
                System.arraycopy(unsorted, target, unsorted, target + 1, now - target);
                unsorted[target] = value;
            }
        }
    }
}

Код теста выглядит следующим образом

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@State(Scope.Thread)
public class TestInset {
    final int[][] src = new int[100000][5];
    final int[][] waitSort = new int[100000][5];


    @Setup(Level.Trial)
    public void init() {
        Random r = new Random();
        for (int i = 0; i < src.length; i++) {
            src[i] = r.ints(5).toArray();
            Arrays.sort(src[i]);
        }
    }

    @Setup(Level.Invocation)
    public void freshData() {
        for (int i = 0; i < waitSort.length; i++) {
            System.arraycopy(src[i], 0, waitSort[i], 0, src[i].length);
        }
    }

    @Benchmark
    public int[][] general() {
        for (int[] ints : waitSort) {
            Insert.general(ints, true, 0, ints.length);
        }
        return waitSort;
    }

    @Benchmark
    public int[][] special() {
        for (int[] ints : waitSort) {
            Insert.special(ints);
        }
        return waitSort;
    }
}

Результаты теста следующие

Benchmark          Mode  Cnt     Score    Error  Units
TestInset.general  avgt   25  2934.461 ± 13.148  us/op
TestInset.special  avgt   25   682.403 ±  5.875  us/op

Тестовая среда выглядит следующим образом

Версия JMH: 1.21

Версия виртуальной машины: JDK 1.8.0_212, 64-разрядная серверная виртуальная машина OpenJDK, 25.212-b04


java performance jmh
person user10339780    schedule 31.10.2019    source источник
comment
Я такой сонный, что игнорирую isdown=true, это элементарная ошибка   -  person user10339780    schedule 01.11.2019

Ответы (1)


arrow_upward
3
arrow_downward

Метод general() isDown = true сортирует массив в убывающем порядке, а метод special() сортирует массив в возрастающем порядке. Обратите внимание на разницу в выражении if: > и <. Метод general() с isDown = false будет таким же, как метод special().

Поскольку входной массив src отсортирован в порядке возрастания из-за Arrays.sort(), эталонный тест isDown = true выполняет сценарий наихудшего случая (входные данные отсортированы в противоположном направлении), а эталонный тест special() выполняет сценарий наилучшего случая (входные данные уже отсортированы).

Если вы пишете бенчмарк с обоими случаями isDown true и false:

@Benchmark
public int[][] generalIsDown() {
  for (int[] ints : waitSort) {
    Insert.general(ints, true, 0, ints.length);
  }
  return waitSort;
}

@Benchmark
public int[][] generalIsUp() {
  for (int[] ints : waitSort) {
    Insert.general(ints, false, 0, ints.length);
  }
  return waitSort;
}

результаты на JDK 11:

Benchmark                  Mode  Cnt     Score   Error  Units
MyBenchmark.generalIsDown  avgt  100  2738.320 ± 8.678  us/op
MyBenchmark.generalIsUp    avgt  100   697.735 ± 3.902  us/op
MyBenchmark.special        avgt  100   690.968 ± 3.559  us/op

Еще пара вещей:

  1. Я не уверен, что тестирование на 5-элементных отсортированных массивах является здесь значимым тестом. Вы пытаетесь проверить производительность сортировки вставками в наихудшем случае на небольших массивах?
  2. Я не уверен, что вам следует зацикливаться внутри метода @Benchmark, для этого и существуют другие аннотации, такие как @Measurement.
person Karol Dowbecki    schedule 31.10.2019