Почему clone() - лучший способ для копирования массивов?

Ответ 1

Я хотел бы рассказать о том, почему clone() - это самый быстрый способ скопировать массив, чем System.arraycopy(..) или другие:

1. clone() не нужно выполнять проверку типов перед копированием исходного массива в пункт назначения, как указано здесь. Он просто просто выделяет новое пространство памяти и присваивает ему объекты. С другой стороны, System.arraycopy(..) проверяет тип и затем копирует массив.

2. clone() также нарушает оптимизацию, чтобы исключить избыточное обнуление. Как вы знаете, каждый выделенный массив в Java должен быть инициализирован с помощью 0s или соответствующих значений по умолчанию. Однако JIT может избежать обнуления этого массива, если видит, что массив заполняется сразу после создания. Это делает его определенно быстрее по сравнению с изменением значений копирования с существующими 0s или соответствующими значениями по умолчанию. При использовании System.arraycopy(..) тратит значительное количество времени на очистку и копирование инициализированного массива. Для этого я выполнил некоторые контрольные тесты.

@BenchmarkMode(Mode.Throughput)
@Fork(1)
@State(Scope.Thread)
@Warmup(iterations = 10, time = 1, batchSize = 1000)
@Measurement(iterations = 10, time = 1, batchSize = 1000)
public class BenchmarkTests {

    @Param({"1000","100","10","5", "1"})
    private int size;
    private int[] original;

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

    @Benchmark
    public int[] SystemArrayCopy() {
        final int length = size;
        int[] destination = new int[length];
        System.arraycopy(original, 0, destination, 0, length);
        return destination;
    }


    @Benchmark
    public int[] arrayClone() {
        return original.clone();
    }

}

Вывод:

Benchmark                        (size)   Mode  Cnt       Score      Error  Units
ArrayCopy.SystemArrayCopy            1  thrpt   10   26324.251 ± 1532.265  ops/s
ArrayCopy.SystemArrayCopy            5  thrpt   10   26435.562 ± 2537.114  ops/s
ArrayCopy.SystemArrayCopy           10  thrpt   10   27262.200 ± 2145.334  ops/s
ArrayCopy.SystemArrayCopy          100  thrpt   10   10524.117 ±  474.325  ops/s
ArrayCopy.SystemArrayCopy         1000  thrpt   10     984.213 ±  121.934  ops/s
ArrayCopy.arrayClone                 1  thrpt   10   55832.672 ± 4521.112  ops/s
ArrayCopy.arrayClone                 5  thrpt   10   48174.496 ± 2728.928  ops/s
ArrayCopy.arrayClone                10  thrpt   10   46267.482 ± 4641.747  ops/s
ArrayCopy.arrayClone               100  thrpt   10   19837.480 ±  364.156  ops/s
ArrayCopy.arrayClone              1000  thrpt   10    1841.145 ±  110.322  ops/s

В соответствии с выводами я получаю, что clone почти в два раза быстрее от System.arraycopy(..)

3. Кроме того, использование метода ручного копирования, такого как clone(), приводит к более быстрому выводу, поскольку ему не нужно делать какие-либо вызовы VM (в отличие от System.arraycopy()).

Ответ 2

С одной стороны, clone() не нужно выполнять проверку типа, которую выполняет System.arraycopy().

Ответ 3

Я хочу исправить и дополнить предыдущие ответы.

• Object.clone использует неконтролируемую реализацию System.arraycopy для массивов;
• Основным улучшением производительности Object.clone является инициализация RAW-памяти напрямую. В случае System.arraycopy он также пытается комбинировать инициализацию массива с операцией копирования, как мы видим в исходном коде, но также выполняет различные дополнительные проверки для этого, в отличие от Object.clone. Если вы просто отключите эту функцию (см. Ниже), производительность будет очень близкой (в частности, на моем оборудовании).
• Еще одна интересная вещь о Young vs Old Gen. Если исходный массив выровнен и внутри старого Gen, оба метода имеют близкую производительность.
• Когда мы копируем примитивные массивы, System.arraycopy всегда использует generate_unchecked_arraycopy.
• Это зависит от аппаратных/OS-зависимых реализаций, поэтому не доверяйте критериям и предположениям, проверяйте сами.

Объяснение

Прежде всего, метод клонирования и System.arraycopy являются внутренними. Object.clone и System.arraycopy используют generate_unchecked_arraycopy. И если мы пойдем глубже, мы увидим, что после этого HotSpot выбирает конкретную реализацию, зависящую от ОС и т.д.

Longly. Посмотрите код Hotspot. Прежде всего, мы увидим, что Object.clone(LibraryCallKit:: inline_native_clone) использует generate_arraycopy, который используется для System.arraycopy в случае -XX: -ReduceInitialCardMarks. В противном случае он выполняет LibraryCallKit:: copy_to_clone, который инициализирует новый массив в RAW-памяти (если -XX: + ReduceBulkZeroing, который включен по умолчанию). В отличие от System.arraycopy напрямую использует generate_arraycopy, попробуйте проверить ReduceBulkZeroing (и многие другие случаи) и также устраните обнуление массива с упомянутыми дополнительными проверками, а также проведет дополнительные проверки, чтобы убедиться, что все элементы инициализированы, в отличие от Object.clone. Наконец, в лучшем случае оба из них используют generate_unchecked_arraycopy.

Ниже я показываю некоторые ориентиры, чтобы увидеть этот эффект на практике:

• Первый - просто простой тест, единственное отличие от предыдущего ответа, что массивы не отсортированы; Мы видим, что arraycopy медленнее (но не два раза), результаты - https://pastebin.com/ny56Ag1z;
• Во-вторых, я добавляю параметр -XX: -ReduceBulkZeroing, и теперь я вижу, что производительность обоих методов очень близка. Результаты - https://pastebin.com/ZDAeQWwx;
• Я также предполагаю, что мы будем иметь разницу между Old/Young, из-за выравнивания массивов (это особенность Java GC, когда мы вызываем GC, выравнивание массивов изменяется, его легко наблюдать, используя JOL). Я был удивлен, что производительность стала такой же, как правило, и понижением для обоих методов. Результаты - https://pastebin.com/bTt5SJ8r. Для кого, кто верит в конкретные числа, пропускная способность System.arraycopy лучше, чем Object.clone.

Первый контрольный показатель:

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.options.OptionsBuilder;

import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;

@State(Scope.Benchmark)
@BenchmarkMode(Mode.All)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class CloneVsArraycopy {

    @Param({"10", "1000", "100000"})
    int size;

    int[] source;

    @Setup(Level.Invocation)
    public void setup() {
        source = create(size);
    }

    @Benchmark
    public int[] clone(CloneVsArraycopy cloneVsArraycopy) {
        return cloneVsArraycopy.source.clone();
    }

    @Benchmark
    public int[] arraycopy(CloneVsArraycopy cloneVsArraycopy) {
        int[] dest = new int[cloneVsArraycopy.size];
        System.arraycopy(cloneVsArraycopy.source, 0, dest, 0, dest.length);
        return dest;
    }

    public static void main(String[] args) throws Exception {
        new Runner(new OptionsBuilder()
                .include(CloneVsArraycopy.class.getSimpleName())
                .warmupIterations(20)
                .measurementIterations(20)
                .forks(20)
                .build()).run();
    }

    private static int[] create(int size) {
        int[] a = new int[size];
        for (int i = 0; i < a.length; i++) {
            a[i] = ThreadLocalRandom.current().nextInt();
        }
        return a;
    }

}

Запуск этого теста на моем ПК, я получил это - https://pastebin.com/ny56Ag1z. Разница не такая большая, но все же существует.

Второй критерий я добавлю только один параметр -XX: -ReduceBulkZeroing и получил эти результаты https://pastebin.com/ZDAeQWwx, Нет, мы видим, что для Young Gen разница намного меньше.

В третьем тесте я изменил только метод настройки и включил опцию ReduceBulkZeroing:

@Setup(Level.Invocation)
public void setup() {
    source = create(size);
    // try to move to old gen/align array
    for (int i = 0; i < 10; ++i) {
        System.gc();
    }
}

Разница намного меньше (возможно, в интервале ошибок) - https://pastebin.com/bTt5SJ8r.

Отказ от ответственности

Это также может быть неправильно. Вы должны сами проверить.

Кроме того,

Я думаю, интересно посмотреть на процесс тестирования:

# Benchmark: org.egorlitvinenko.arrays.CloneVsArraycopy.arraycopy
# Parameters: (size = 50000)

# Run progress: 0,00% complete, ETA 00:07:30
# Fork: 1 of 5
# Warmup Iteration   1: 8,870 ops/ms
# Warmup Iteration   2: 10,912 ops/ms
# Warmup Iteration   3: 16,417 ops/ms <- Hooray!
# Warmup Iteration   4: 17,924 ops/ms <- Hooray!
# Warmup Iteration   5: 17,321 ops/ms <- Hooray!
# Warmup Iteration   6: 16,628 ops/ms <- What!
# Warmup Iteration   7: 14,286 ops/ms <- No, stop, why!
# Warmup Iteration   8: 13,928 ops/ms <- Are you kidding me?
# Warmup Iteration   9: 13,337 ops/ms <- pff
# Warmup Iteration  10: 13,499 ops/ms
Iteration   1: 13,873 ops/ms
Iteration   2: 16,177 ops/ms
Iteration   3: 14,265 ops/ms
Iteration   4: 13,338 ops/ms
Iteration   5: 15,496 ops/ms

Для объекта Object.clone

# Benchmark: org.egorlitvinenko.arrays.CloneVsArraycopy.clone
# Parameters: (size = 50000)

# Run progress: 0,00% complete, ETA 00:03:45
# Fork: 1 of 5
# Warmup Iteration   1: 8,761 ops/ms
# Warmup Iteration   2: 12,673 ops/ms
# Warmup Iteration   3: 20,008 ops/ms
# Warmup Iteration   4: 20,340 ops/ms
# Warmup Iteration   5: 20,112 ops/ms
# Warmup Iteration   6: 20,061 ops/ms
# Warmup Iteration   7: 19,492 ops/ms
# Warmup Iteration   8: 18,862 ops/ms
# Warmup Iteration   9: 19,562 ops/ms
# Warmup Iteration  10: 18,786 ops/ms

Мы можем наблюдать снижение производительности здесь для System.arraycopy. Я видел подобную картину для Streams, и в компиляторах была ошибка. Полагаю, это тоже может быть ошибкой в ​​компиляторах. Во всяком случае, странно, что после 3-х разгонов производительность понижается.

UPDATE

Что такое typechecking

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.options.OptionsBuilder;

import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicLong;

@State(Scope.Benchmark)
@BenchmarkMode(Mode.All)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class CloneVsArraycopyObject {

    @Param({"100"})
    int size;

    AtomicLong[] source;

    @Setup(Level.Invocation)
    public void setup() {
        source = create(size);
    }

    @Benchmark
    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    public AtomicLong[] clone(CloneVsArraycopyObject cloneVsArraycopy) {
        return cloneVsArraycopy.source.clone();
    }

    @Benchmark
    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    public AtomicLong[] arraycopy(CloneVsArraycopyObject cloneVsArraycopy) {
        AtomicLong[] dest = new AtomicLong[cloneVsArraycopy.size];
        System.arraycopy(cloneVsArraycopy.source, 0, dest, 0, dest.length);
        return dest;
    }

    public static void main(String[] args) throws Exception {
        new Runner(new OptionsBuilder()
                .include(CloneVsArraycopyObject.class.getSimpleName())
                .jvmArgs("-XX:+UnlockDiagnosticVMOptions", "-XX:+PrintInlining", "-XX:-ReduceBulkZeroing")
                .warmupIterations(10)
                .measurementIterations(5)
                .forks(5)
                .build())
                .run();
    }

    private static AtomicLong[] create(int size) {
        AtomicLong[] a = new AtomicLong[size];
        for (int i = 0; i < a.length; i++) {
            a[i] = new AtomicLong(ThreadLocalRandom.current().nextLong());
        }
        return a;
    }

}

Разница не наблюдается - https://pastebin.com/ufxCZVaC. Я полагаю, что объяснение простое, так как System.arraycopy является горячим внутренним в этом случае, реальная реализация будет просто встроена без каких-либо типов и т.д.

Примечание

Я согласился с Radiodef, вам было бы интересно прочитать сообщение в блоге, автор этого блога является создателем (или одним из создателей) JMH.

Ответ 4

Что касается копирования, то System.arrayCopy является самым быстрым, а затем и сейчас.

• System.arrayCopy не создает новый массив и не может быть избит с использованием скорости копирования.
• Arrays.copyOf просто создает массив и вызывает arrayCopy. Удобство.
• Array.clone является высокоэффективным, но ему нужно очистить скопированные данные до всех кеш-памяти процессора.

Если вы можете использовать код для повторного использования массива с помощью arrayCopy, перейдите к нему. В противном случае я лично рекомендую copyOf с учетом восходящего тренда ядер процессора и потому, что клон считается старым и проблематичный в целом - главный пункт блог Джоша Блоха, который начал этот вопрос.

В отличие от общих мыслей, фактические контуры копирования (тип проверен или нет) не являются байт-кодом Java и не оптимизируются по точкам доступа. Циклы кодируются в С++ и представляют собой реализацию jvm на уровне низкого уровня.

Длинный ответ:

Этот ответ основан на ссылке на исходный код OpenJDK 8 и который, насколько я знаю, должен быть тем же самым для Sun.

Копия массива, возможно, более сложная, чем большинство людей думают. На уровне кода C его можно разделить на три случая:

• Примитивные массивы скопированы непосредственно с цикл копирования.
• Массивы объектов того же класса или подкласса для суперклассического массива также скопированы непосредственно.
• В противном случае между массивами разных классов выполняется проверка типа на каждый элемент.

Таким образом, абсолютная скорость копирования массива сильно зависит от типа массива. Однако относительная скорость трех методов клонирования не возникает, поскольку все они решаются на один и тот же цикл копирования, встроенный цикл С++ или сборки. Таким образом, разная скорость связана главным образом с накладными расходами и другими факторами.

• System.arrayCopy - это, в основном, проверки типов и длины, а затем прямо в контур копирования, В моих собственных тестах arrayCopy всегда быстрее других двух методов, значительно превышающих допустимые пределы ошибок.

• Arrays.copyOf просто вызывает System.arrayCopy - после создания нового массива. Обратите внимание, что он не вызывает Array.clone. В отличие от Radiodef comment, нет никаких признаков того, что Java 8 будет обходить инициализацию нуля.

• Array.clone интересен. Он напрямую вызывает распределение кучи и цикл копирования с минимальными проверками. Таким образом, его создание массива должно быть быстрее, чем Arrays.copyOf, а его копия выполняется быстрее, чем System.arrayCopy, если не быстрее.

Но в моих тестах Array.clone немного медленнее, чем copyOf.

Я подозреваю, что из-за барьер памяти после копии. Как и конструктор, clone будет следить за тем, чтобы скопированные данные были видны для всех потоков, которые не выполняются ни System.arrayCopy, ни Array.copyOf. Это означает, что Array.clone необходимо потратить время на ожидание кэша ЦП для обновления.

Если это так, результат Array.clone vs Arrays.copyOf зависит от того, будет ли кеш-флеш clone быстрее, чем накладные расходы copyOf, и должен быть зависимым от платформы.

Кроме этого, поскольку клонирование всегда приводит к массиву того же типа, все три метода в конечном итоге используют один и тот же цикл копирования.

Если вы хотите только скопировать, arrayCopy всегда быстрее, просто потому, что он не создает новый массив. В остальном, если список рассылки java - это что-то, что нужно сделать, выбор между Arrays.copyOf и Array.clone должен быть в основном вопросом вкуса.

Результат и код теста jmh ниже.

• Односторонние тесты возвращают скопированный массив.
• Двухсторонние тесты перезаписывают источник копирования, который заставляет следующий клон копировать "новые" данные.
• NoClone не клонирует ничего и является мерилом, чтобы убедиться, что скорость выше.

Как указано, Clone и CopyOf - это близкая гонка, и ваш пробег может меняться.

/* # Run complete. Total time: 00:06:44

Benchmark                               Mode  Cnt          Score         Error  Units
MyBenchmark.ArrayCloneByteOneWay       thrpt   20    1048588.503 ±    2608.862  ops/s
MyBenchmark.ArrayCloneByteTwoWay       thrpt   20     523782.848 ±    1613.823  ops/s
MyBenchmark.ArrayCloneObjOneWay        thrpt   20     260903.006 ±    1311.827  ops/s
MyBenchmark.ArrayCloneObjTwoWay        thrpt   20     129448.639 ±    1179.122  ops/s
MyBenchmark.ArraysCopyOfByteOneWay     thrpt   20    1065995.804 ±    2197.919  ops/s
MyBenchmark.ArraysCopyOfByteTwoWay     thrpt   20     533025.610 ±    2831.955  ops/s
MyBenchmark.ArraysCopyOfObjOneWay      thrpt   20     266134.565 ±    1536.756  ops/s
MyBenchmark.ArraysCopyOfObjTwoWay      thrpt   20     130821.380 ±     274.325  ops/s
MyBenchmark.NoClone                    thrpt   20  308776528.157 ± 2546848.128  ops/s
MyBenchmark.SystemArrayCopyByteOneWay  thrpt   20    1232733.367 ±    8439.409  ops/s
MyBenchmark.SystemArrayCopyByteTwoWay  thrpt   20     859387.983 ±    1919.359  ops/s
MyBenchmark.SystemArrayCopyObjOneWay   thrpt   20     239532.442 ±     775.193  ops/s
MyBenchmark.SystemArrayCopyObjTwoWay   thrpt   20     167235.661 ±     503.141  ops/s
*/

import java.util.Arrays;
import java.util.Random;
import org.openjdk.jmh.annotations.*;

@Fork(2) @Warmup(iterations = 5, time = 1) @Measurement(iterations = 10, time = 1)
public class Q46230557 {
   private static final int ARRAY_SIZE = 8192;

   @State(Scope.Thread) public static class Data {
      public byte[] bytes = new byte[ ARRAY_SIZE ];
      public Object[] objs = new Object[ ARRAY_SIZE ];
      @Setup public void setup() {
         final Random RNG = new Random();
         RNG.nextBytes( bytes );
         for ( int i = 0 ; i < ARRAY_SIZE ; i++ )
            objs[i] = RNG.nextInt();
      }
   }

   @Benchmark public byte[] NoClone( final Data data ) {
      return data.bytes;
   }

   @Benchmark public byte[] SystemArrayCopyByteOneWay( final Data data ) {
      final byte[] dest = new byte[ ARRAY_SIZE ];
      System.arraycopy( data.bytes, 0, dest, 0, ARRAY_SIZE );
      return dest;
   }

   @Benchmark public byte[] SystemArrayCopyByteTwoWay( final Data data ) {
      final byte[] buf = new byte[ ARRAY_SIZE ];
      System.arraycopy( data.bytes, 0, buf, 0, ARRAY_SIZE );
      System.arraycopy( buf, 0, data.bytes, 0, ARRAY_SIZE );
      return data.bytes;
   }

   @Benchmark public byte[] ArraysCopyOfByteOneWay( final Data data ) {
      return Arrays.copyOf( data.bytes, ARRAY_SIZE );
   }

   @Benchmark public byte[] ArraysCopyOfByteTwoWay( final Data data ) {
      final byte[] buf = Arrays.copyOf( data.bytes, ARRAY_SIZE );
      return data.bytes = Arrays.copyOf( buf, ARRAY_SIZE );
   }

   @Benchmark public byte[] ArrayCloneByteOneWay( final Data data ) {
      return data.bytes.clone();
   }

   @Benchmark public byte[] ArrayCloneByteTwoWay( final Data data ) {
      final byte[] buf = data.bytes.clone();
      return data.bytes = buf.clone();
   }

   @Benchmark public Object[] SystemArrayCopyObjOneWay( final Data data ) {
      final Object[] dest = new Object[ ARRAY_SIZE ];
      System.arraycopy( data.objs, 0, dest, 0, ARRAY_SIZE );
      return dest;
   }

   @Benchmark public Object[] SystemArrayCopyObjTwoWay( final Data data ) {
      final Object[] buf = new Object[ ARRAY_SIZE ];
      System.arraycopy( data.objs, 0, buf, 0, ARRAY_SIZE );
      System.arraycopy( buf, 0, data.objs, 0, ARRAY_SIZE );
      return data.objs;
   }

   @Benchmark public Object[] ArraysCopyOfObjOneWay( final Data data ) {
      return Arrays.copyOf( data.objs, ARRAY_SIZE );
   }

   @Benchmark public Object[] ArraysCopyOfObjTwoWay( final Data data ) {
      final Object[] buf = Arrays.copyOf( data.objs, ARRAY_SIZE );
      return data.objs = Arrays.copyOf( buf, ARRAY_SIZE );
   }

   @Benchmark public Object[] ArrayCloneObjOneWay( final Data data ) {
      return data.objs.clone();
   }

   @Benchmark public Object[] ArrayCloneObjTwoWay( final Data data ) {
      final Object[] buf = data.objs.clone();
      return data.objs = buf.clone();
   }
}

Ответ 5

Разница в производительности возникает из-за пропуска шага, где массив обнуляется.

public static int[] copyUsingArraycopy(int[] original)
{
    // Memory is allocated and zeroed out
    int[] copy = new int[original.Length];
    // Memory is copied
    System.arraycopy(original, 0, copy, 0, original.length);
}

public static int[] copyUsingClone(int[] original)
{
    // Memory is allocated, but not zeroed out
    // Unitialized memory is then copied into
    return (int[])original.clone();
}

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

int[] backBuffer = new int[BUFFER_SIZE];
int[] frontBuffer = new int[BUFFER_SIZE];

...

// Swap buffers
int[] temp = frontBuffer;
frontBuffer = backBuffer;
backBuffer = temp;
System.arraycopy(frontBuffer, 0, backBuffer, 0, BUFFER_SIZE);