System.arrayCopy is slow

Question

Я пытался измерить производительность System.arrayCopy vs Arrays.copyOf, чтобы правильно выбрать один из них. Только ради бенчмарка я также добавил ручную копию, и результат удивил меня. Очевидно, что мне не хватает чего-то действительно важного, не могли бы вы рассказать мне, что это такое? Реализация следующая (см. Первые 4 метода).

public class ArrayCopy { 

    public static int[] createArray(int size) { 
     int[] array = new int[size]; 
     Random r = new Random(); 
     for (int i = 0; i < size; i++) { 
      array[i] = r.nextInt(); 
     } 
     return array; 
    } 

    public static int[] copyByArraysCopyOf(int[] array, int size) { 
     return Arrays.copyOf(array, array.length + size); 
    } 

    public static int[] copyByEnlarge(int[] array, int size) { 
     return enlarge(array, size); 
    } 

    public static int[] copyManually(int[] array, int size) { 
     int[] newArray = new int[array.length + size]; 
     for (int i = 0; i < array.length; i++) { 
      newArray[i] = array[i]; 
     } 
     return newArray; 
    } 

    private static void copyArray(int[] source, int[] target) { 
     System.arraycopy(source, 0, target, 0, Math.min(source.length, target.length)); 
    } 

    private static int[] enlarge(int[] orig, int size) { 
     int[] newArray = new int[orig.length + size]; 
     copyArray(orig, newArray); 
     return newArray; 
    } 

    public static void main(String... args) { 
     int[] array = createArray(1000000); 
     int runs = 1000; 
     int size = 1000000; 
     System.out.println("****************** warm up #1 ******************"); 
     warmup(ArrayCopy::copyByArraysCopyOf, array, size, runs); 
     warmup(ArrayCopy::copyByEnlarge, array, size, runs); 
     warmup(ArrayCopy::copyManually, array, size, runs); 
     System.out.println("****************** warm up #2 ******************"); 
     warmup(ArrayCopy::copyByArraysCopyOf, array, size, runs); 
     warmup(ArrayCopy::copyByEnlarge, array, size, runs); 
     warmup(ArrayCopy::copyManually, array, size, runs); 
     System.out.println("********************* test *********************"); 
     System.out.print("copyByArrayCopyOf"); 
     runTest(ArrayCopy::copyByArraysCopyOf, array, size, runs); 
     System.out.print("copyByEnlarge"); 
     runTest(ArrayCopy::copyByEnlarge, array, size, runs); 
     System.out.print("copyManually"); 
     runTest(ArrayCopy::copyManually, array, size, runs); 
    } 

    private static void warmup(BiConsumer<int[], Integer> consumer, int[] array, int size, int runs) { 
     for (int i = 0; i < runs; i++) { 
      consumer.accept(array, size); 
     } 
    } 

    private static void runTest(BiConsumer<int[], Integer> consumer, int[] array, int size, int runs) { 
     ThreadMXBean threadMXBean = ManagementFactory.getThreadMXBean(); 
     long currentCpuTime = threadMXBean.getCurrentThreadCpuTime(); 
     long nanoTime = System.nanoTime(); 
     for (int i = 0; i < runs; i++) { 
      consumer.accept(array, size); 
     } 
     System.out.println("-time = " + ((System.nanoTime() - nanoTime)/10E6) + " ms. CPU time = " + ((threadMXBean.getCurrentThreadCpuTime() - currentCpuTime)/10E6) + " ms"); 
    } 
} 

Результат показывает, что ручное копирование выполняется около 30% лучше, как показано ниже:

****************** warm up #1 ****************** 
****************** warm up #2 ****************** 
********************* test ********************* 
copyByArrayCopyOf-time = 162.470107 ms. CPU time = 153.125 ms 
copyByEnlarge-time = 168.6757949 ms. CPU time = 164.0625 ms 
copyManually-time = 116.3975962 ms. CPU time = 110.9375 ms 

Я очень смущен, потому что я думал (и, вероятно, я до сих пор), что из-за System.arrayCopy его nativity является наилучшим способом копирования массива, но я не могу объяснить этот результат.

Answer 1

На самом деле, HotSpot компилятор достаточно умен, чтобы раскатать и векторизации ручной цикл копирования - поэтому код результата, кажется, хорошо оптимизирован.

Почему System.arraycopy более медленный? Это изначально родной метод, и вы должны платить за собственный вызов, пока компилятор не оптимизирует его как JVM.

Однако, в вашем тесте у компилятора нет такой возможности для оптимизации, потому что метод enlarge не вызывается достаточно много раз (т. Е. Он не считается горячим).

Я покажу вам забавный трюк, чтобы заставить оптимизировать. Rewrite enlarge метод следующим образом:

private static int[] enlarge(int[] array, int size) { 
    for (int i = 0; i < 10000; i++) { /* fool the JIT */ } 

    int[] newArray = new int[array.length + size]; 
    System.arraycopy(array, 0, newArray, 0, array.length); 
    return newArray; 
} 

Пустой цикл вызывает переполнение backedge счетчик, который, в свою очередь, запускает компиляцию enlarge метода. Пустой цикл затем исключается из скомпилированного кода, поэтому он безвреден. Теперь метод enlarge получает около в 1,5 раза быстрее, чем ручной цикл!

Важно, чтобы System.arraycopy сразу же следовал за new int[]. В этом случае HotSpot может оптимизировать избыточное обнуление нового выделенного массива. Знаете, все объекты Java должны быть обнулены сразу после создания. Но поскольку компилятор обнаруживает, что массив заполнен сразу после создания, он может исключить обнуление, тем самым делая код результата еще быстрее.

P.S. Сравнительный тест @assylias хорош, но он также страдает от того, что System.arraycopy не является неотъемлемой частью больших массивов. В случае небольших массивов arrayCopy эталон называется много раз в секунду, JIT считает его горячим и хорошо оптимизируется. Но для больших массивов каждая итерация длиннее, поэтому в секунду происходит намного меньше итераций, а JIT не обрабатывает arrayCopy как горячий.

Answer 2

Используя JMH, получить результаты, приведенные в таблице ниже (это размер массива, оценка это время в микросекундах, ошибка показывает доверительный интервал на 99,9%):

Benchmark    (size) Mode Cnt  Score  Error Units 
ArrayCopy.arrayCopy  10 avgt 60  0.022 ± 0.001 us/op 
ArrayCopy.arrayCopy  10000 avgt 60  4.959 ± 0.068 us/op 
ArrayCopy.arrayCopy 10000000 avgt 60 11906.870 ± 220.850 us/op 
ArrayCopy.clone_   10 avgt 60  0.022 ± 0.001 us/op 
ArrayCopy.clone_  10000 avgt 60  4.956 ± 0.068 us/op 
ArrayCopy.clone_  10000000 avgt 60 10895.856 ± 208.369 us/op 
ArrayCopy.copyOf   10 avgt 60  0.022 ± 0.001 us/op 
ArrayCopy.copyOf  10000 avgt 60  4.958 ± 0.072 us/op 
ArrayCopy.copyOf  10000000 avgt 60 11837.139 ± 220.452 us/op 
ArrayCopy.loop    10 avgt 60  0.036 ± 0.001 us/op 
ArrayCopy.loop   10000 avgt 60  5.872 ± 0.095 us/op 
ArrayCopy.loop  10000000 avgt 60 11315.482 ± 217.348 us/op 

В вещество, цикл, кажется, работает немного лучше, чем arrayCopy для больших массивов - возможно, потому, что JIT неплохо оптимизирует такой простой цикл. Для меньших массивов arrayCopy кажется лучше (хотя разница довольно мала).

Обратите внимание, однако, что клон, по-видимому, всегда соответствует или лучше других вариантов, в зависимости от размера. Поэтому я бы пошел на клоун, который также бывает проще в использовании.

---

Для справки, тестирования кода, работать с -wi 5 -w 1000ms -i 30 -r 1000ms -t 1 -f 2 -tu us:

@State(Scope.Thread) 
@BenchmarkMode(Mode.AverageTime) 
public class ArrayCopy { 

    @Param({"10", "10000", "10000000"}) int size; 

    private int[] array; 

    @Setup(Level.Invocation) public void setup() { 
    array = new int[size]; 
    for (int i = 0; i < size; i++) { 
     array[i] = i; 
    } 
    } 

    @Benchmark 
    public int[] clone_() { 
    int[] copy = array.clone(); 
    return copy; 
    } 

    @Benchmark 
    public int[] arrayCopy() { 
    int[] copy = new int[array.length]; 
    System.arraycopy(array, 0, copy, 0, array.length); 
    return copy; 
    } 

    @Benchmark 
    public int[] copyOf() { 
    int[] copy = Arrays.copyOf(array, array.length); 
    return copy; 
    } 

    @Benchmark 
    public int[] loop() { 
    int[] copy = new int[array.length]; 
    for (int i = 0; i < array.length; i++) { 
     copy[i] = array[i]; 
    } 
    return copy; 
    } 
}