Why is the general version 4 times slower than the special version when I deal with the ordered array in the insertion sort I implemented?

Question

I don't think there is any difference between the two methods after full JIT, but the fact is that the time difference between the two methods is four times

What happened here

The implementation of insertion sorting is as follows

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;
            }
        }
    }
}

The test code is as follows

@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;
    }
}

The test results are as follows

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

The test environment is as follows

JMH version: 1.21

VM version: JDK 1.8.0_212, OpenJDK 64-Bit Server VM, 25.212-b04

Answer 1

The general() method isDown = true will sort the array in a descending order while the special() method will sort the array in ascending order. Notice the difference in the if statement: > vs <. general() method with isDown = false would be the same as special() method.

Since the src input array is sorted in ascending order due to Arrays.sort() the isDown = true benchmark runs the worst case scenario (input sorted in opposite direction) while the special() benchmark runs the best case scenario (input already sorted).

If you write a benchmark with both isDown true and false cases:

@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;
}

the results on JDK 11 are:

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

Couple more things:

1. I'm not sure if testing on 5 element sorted arrays is a meaningful test here. Are you trying to test worst case insertion sort performance on small arrays?
2. I'm not sure you should loop inside the @Benchmark method, that's what the other annotations like @Measurement are there for.