为什么clone()是复制数组的最佳方法？

Question

这对我来说是一种耻辱,但我不知道:

您应该使用clone来复制数组,因为这通常是最快的方法.

正如Josh Bloch在本博客中所述:http://www.artima.com/intv/bloch13.html

我总是用System.arraycopy(...).这两种方法都是原生的,所以可能没有深入到我无法弄清楚的库的来源,为什么会如此.

我的问题很简单:为什么它是最快的方式？ 有什么区别System.arraycopy？这里 解释了不同之处,但它没有回答为什么Josh Bloch认为clone()最快的方式.

Answer 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()).

Answer 2

一方面，clone()不必进行类型检查System.arraycopy()。

Answer 3

我想纠正和补充以前的答案。

1. Object.clone 对数组使用未经检查的 System.arraycopy 实现；
2. Object.clone的主要性能提升，是直接初始化RAW内存。在 System.arraycopy 的情况下，它也尝试将数组初始化与复制操作结合起来，正如我们在源代码中看到的那样，但与 Object.clone 不同，它也为此做了不同的额外检查。如果您只是禁用此功能（见下文），那么性能会非常接近（尤其是在我的硬件上）。
3. 一件更有趣的事情是关于 Young 与 Old Gen。如果源数组对齐并位于 Old Gen 内部，则两种方法的性能都很接近。
4. 当我们复制原始数组时，System.arraycopy 总是使用 generate_unchecked_arraycopy。
5. 它取决于硬件/操作系统相关的实现，所以不要相信基准测试和假设，请自行检查。

解释

首先 clone 方法和 System.arraycopy 是内在函数。Object.clone 和 System.arraycopy 使用 generate_unchecked_arraycopy。如果我们更深入，我们可以看到在 HotSpot 之后选择具体的实现，依赖于操作系统等。

长。让我们看看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。

下面我展示了一些基准测试来查看这种对实践的影响：

1. 第一个只是简单的基准测试，与之前的答案唯一不同的是，数组没有排序；我们看到 arraycopy 较慢（但不是两次），结果 - https://pastebin.com/ny56Ag1z；
2. 其次，我添加了选项 -XX:-ReduceBulkZeroing，现在我看到两种方法的性能非常接近。结果 - https://pastebin.com/ZDAeQWwx；
3. 我还假设我们会有 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次预热后性能下降。

更新

什么是类型检查

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的创建者（或创建者之一）。