为什么当我在我实现的插入排序中处理有序数组时，通用版本比特殊版本慢 4 倍?

Question

我认为完全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，OpenJDK 64 位服务器虚拟机，25.212-b04

Answer 1

general()方法isDown = true将按降序对数组进行排序，而special()方法将按升序对数组进行排序。请注意if语句中的区别：>vs<。general()方法isDown = false方法将与special()方法相同。

由于src输入数组由于Arrays.sort()而按升序排序，因此isDown = true基准运行最坏情况(输入以相反方向排序)，而special()基准运行最佳情况(输入已排序)。

如果您编写同时包含isDowntrue和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这样的其他注释的作用。