Arrays中的远古智慧

副标题Collection.toArray(new T[0]) 还是 Collection.toArray(new T[size])? 这是个问题。

前言

这篇文章翻译自Arrays of Wisdom of the Ancients。上个星期同事在看阿里巴巴Java开发手册（详尽版）时，看到了这一条规则：

Java开发手册

出于好奇google了集合转数组最佳实践相关的说法，发现了Arrays of Wisdom of the Ancients这一篇文章。这是一篇篇幅很长的文章，作者通过一系列实验后得出的最后结论是反直觉的：toArray(new T[0])比toArray(new T[list.size()])更高效。

为什么要翻译这篇文章？

作为一名后端工程师，我接触过很多工具，不管用的是开源工具或自研系统都可能需要根据自身的应用场景做系统调优。为了调优做大大小小的微基准测试、压力测试、集成测试也是非常常见的。
尽管做过很多次基准测试，但很多时候得到结果就算完成了，只知其然，不知其所以然。这篇文章让我很欣赏的地方在于：它是一系列完整的实验，有严谨的实验过程，从立论（凭直觉猜测结果）、如何论证（设计实验，用什么工具、什么方法证明或证反）到最后总结定论。也介绍了多种用于分析微基准测试的工具。翻译出来是希望更多人看到它，学习优秀的性能测试方法。然而这篇文章涉及了许多底层的知识，比如JVM是如何分配数组对象的、cpu offload 、JNI调用、JVM编译生成汇编代码...等。由于自身水平有限，可能存在翻译错误、曲解了作者的意思的情况，强烈建议有兴趣的同学直接看原文。下面是翻译的正文。

介绍

Java语言和JDK Class Library有两种不同但有关联的方式来把元素组合在一起：arrays和Collections。两者都各有优劣，因此两者在真实的程序中都很常见。为了帮助实现两种类型数据的互相转换，jdk提供了把array转换成Collection(e.g. Arrays.asList)和把Collection复制到Array(e.g. 好几个Collection.toArray的方法)的标准实现。这篇文章中，我们尝试回答一个有争议的问题：哪种toArray方式更高效？

API设计

盲目调用Collection中的toArray 、或者遵循我们从其它工具或google搜索中得到的任何建议似乎是件很平常的事情。但是，如果我们查看Collection.toArray系列方法，我们可以看到两个独立的方法：

public interface Collection<E> extends Iterable<E> {

    /**
     * Returns an array containing all of the elements in this collection.
     *
     * ...
     *
     * @return an array containing all of the elements in this collection
     */
    Object[] toArray();

    /**
     * Returns an array containing all of the elements in this collection;
     * the runtime type of the returned array is that of the specified array.
     * If the collection fits in the specified array, it is returned therein.
     * Otherwise, a new array is allocated with the runtime type of the
     * specified array and the size of this collection.
     *
     * ...
     *
     * @param <T> the runtime type of the array to contain the collection
     * @param a the array into which the elements of this collection are to be
     *        stored, if it is big enough; otherwise, a new array of the same
     *        runtime type is allocated for this purpose.
     * @return an array containing all of the elements in this collection
     * @throws ArrayStoreException if the runtime type of the specified array
     *         is not a supertype of the runtime type of every element in
     *         this collection
     */
    <T> T[] toArray(T[] a);

这些方法表现得略微不同是有一定原因的。泛型类型擦除造成的性能影响迫使我们使用实际的参数来精确解释目标数组类型。另外,简单地将toArray()返回的Object[]转换为ConcreteType[]是不可行的，因为运行时必须保证类型安全，像这样的数组类型转换将导致ClassCastException。这么做可以避免恶意代码通过在Object[]数组中放置非ConcreteType来规避类型安全。把数组作为参数的toArray方法可以把结果都放在一个预先设置好长度的数组中。

事实上，古人的智慧可能会告诉我们，为了获得最好的性能，我们应该提供预先设置好长度的数组(甚至是长度为零的数组！)。IntelliJIDEA 15建议传递预先分配好长度的数组,而不是偷懒传一个长度为零的数组。它解释说，Library必需通过反射调用才能分配给定的运行时类型数组,这显然要让你付出代价。而PMD的OptimizableToArrayCall规则告诉我们同样的情况，但似乎也暗示新分配的“空”数组会因为长度不足而被丢弃，我们应该通过传递预先分配长度的目标数组来避免这种情况。古人到底有多聪明？

Figure 1. IntelliJ IDEA 15 tries to help us

Figure 2. PMD 5.4.1 tries to help me

性能测试

实验设计

在开始实验之前，我们需要先了解这个实验的自由度。至少有三个条件需要考虑：

集合大小。 PMD的规则告诉我们分配会被丢弃的数组(长度过短的数组)毫无意义。这意味着我们的实验需要覆盖一些小集合，以查看“无偿”数组实例化的影响。我们还希望看到大集合的性能，而我们预计元素复制成本是影响性能的主要因素。当然，我们还要测试长度位于两者之间的值，以避免掉进“性能甜蜜点”。
toArray()参数的类型。当然，我们希望尝试toArray方法调用的所有变体。尤其是零大小数组调用与预先分配大小的数组调用，但非类型化的toArray方法也很有趣。
集合中的toArray()实现。IDEA认为，反射数组实例化可能要付出昂贵代价。因此，我们需要调查实际使用的集合的实现逻辑。大多数集合与抽象集合相同：在后一种情况下分配Object[]或T[]数组，实际上，就是使用java.lang.Reflt.Array：newInstance方法 - 分配T[]数组，然后通过迭代器，逐个将元素复制到目标数组中。

public abstract class AbstractCollection {
  public <T> T[] toArray(T[] a) {
    int size = size();
    T[] r = (a.length >= size) ?
             a : (T[])Array.newInstance(a.getClass().getComponentType(), size);
    Iterator<E> it = iterator();
    for (int i = 0; i < r.length; i++) {
      ...
      r[i] = (T)it.next();
    }
    return ... r;
  }
}

有的集合，比如 ArrayList, 只是简单地把他们的内部成员变量数组复制到目标数组中。

public class ArrayList {
  public <T> T[] toArray(T[] a) {
    if (a.length < size) {
      // Arrays.copyOf would do the Array.newInstance
      return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    }
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size) {
      a[size] = null;
    }
    return a;
  }
}

ArrayList是最常用的集合之一，因此我们想看看无处不在的ArrayList和类似HashSet这样的通用的、基于抽象集合toArray()方法支持的集合是如何执行的。

基准测试

根据上述观察，我们制定了如下的JMH基准测试

@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Fork(value = 3, jvmArgsAppend = {"-XX:+UseParallelGC", "-Xms1g", "-Xmx1g"})
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)
public class ToArrayBench {

    @Param({"0", "1", "10", "100", "1000"})
    int size;

    @Param({"arraylist", "hashset"})
    String type;

    Collection<Foo> coll;

    @Setup
    public void setup() {
        if (type.equals("arraylist")) {
            coll = new ArrayList<Foo>();
        } else if (type.equals("hashset")) {
            coll = new HashSet<Foo>();
        } else {
            throw new IllegalStateException();
        }
        for (int i = 0; i < size; i++) {
            coll.add(new Foo(i));
        }
    }

    @Benchmark
    public Object[] simple() {
        return coll.toArray();
    }

    @Benchmark
    public Foo[] zero() {
        return coll.toArray(new Foo[0]);
    }

    @Benchmark
    public Foo[] sized() {
        return coll.toArray(new Foo[coll.size()]);
    }

    public static class Foo {
        private int i;

        public Foo(int i) {
            this.i = i;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Foo foo = (Foo) o;
            return i == foo.i;
        }

        @Override
        public int hashCode() {
            return i;
        }
    }
}

实验结果

实验运行环境为 i7-4790K, 4.0 GHz, Linux x86_64, JDK 9b99 EA ,我们得到如下实现结果（平均运行时间，数值越小越好）:

Benchmark            (size)     (type)  Mode  Cnt      Score    Error  Units

# ---------------------------------------------------------------------------

ToArrayBench.simple       0  arraylist  avgt   30    19.445 ±   0.152  ns/op
ToArrayBench.sized        0  arraylist  avgt   30    19.009 ±   0.252  ns/op
ToArrayBench.zero         0  arraylist  avgt   30     4.590 ±   0.023  ns/op

ToArrayBench.simple       1  arraylist  avgt   30     7.906 ±   0.024  ns/op
ToArrayBench.sized        1  arraylist  avgt   30    18.972 ±   0.357  ns/op
ToArrayBench.zero         1  arraylist  avgt   30    10.472 ±   0.038  ns/op

ToArrayBench.simple      10  arraylist  avgt   30     8.499 ±   0.049  ns/op
ToArrayBench.sized       10  arraylist  avgt   30    24.637 ±   0.128  ns/op
ToArrayBench.zero        10  arraylist  avgt   30    15.845 ±   0.075  ns/op

ToArrayBench.simple     100  arraylist  avgt   30    40.874 ±   0.352  ns/op
ToArrayBench.sized      100  arraylist  avgt   30    93.170 ±   0.379  ns/op
ToArrayBench.zero       100  arraylist  avgt   30    80.966 ±   0.347  ns/op

ToArrayBench.simple    1000  arraylist  avgt   30   400.130 ±   2.261  ns/op
ToArrayBench.sized     1000  arraylist  avgt   30   908.007 ±   5.869  ns/op
ToArrayBench.zero      1000  arraylist  avgt   30   673.682 ±   3.586  ns/op

# ---------------------------------------------------------------------------

ToArrayBench.simple       0    hashset  avgt   30    21.270 ±   0.424  ns/op
ToArrayBench.sized        0    hashset  avgt   30    20.815 ±   0.400  ns/op
ToArrayBench.zero         0    hashset  avgt   30     4.354 ±   0.014  ns/op

ToArrayBench.simple       1    hashset  avgt   30    22.969 ±   0.221  ns/op
ToArrayBench.sized        1    hashset  avgt   30    23.752 ±   0.503  ns/op
ToArrayBench.zero         1    hashset  avgt   30    23.732 ±   0.076  ns/op

ToArrayBench.simple      10    hashset  avgt   30    39.630 ±   0.613  ns/op
ToArrayBench.sized       10    hashset  avgt   30    43.808 ±   0.629  ns/op
ToArrayBench.zero        10    hashset  avgt   30    44.192 ±   0.823  ns/op

ToArrayBench.simple     100    hashset  avgt   30   298.032 ±   3.925  ns/op
ToArrayBench.sized      100    hashset  avgt   30   316.250 ±   9.614  ns/op
ToArrayBench.zero       100    hashset  avgt   30   284.431 ±   6.201  ns/op

ToArrayBench.simple    1000    hashset  avgt   30  4227.564 ±  84.983  ns/op
ToArrayBench.sized     1000    hashset  avgt   30  4539.614 ± 135.379  ns/op
ToArrayBench.zero      1000    hashset  avgt   30  4428.601 ± 205.191  ns/op

# ---------------------------------------------------------------------------

实验结果表明，simple 性能完胜其它实现，然而，反直觉的是，zero 竟然比sized 性能更好。

实验到这个阶段，大部分人都会犯这样的错误：把这些数据当成事实。但这些数据只是数据，它们不能说明任何东西,除非我们明白得到这些结果的原因。

仔细观察这些数据，我们想得到两个主要问题的答案：

为什么simple比zero和sized都快
为什么zero比sized快？

解决这两个问题是让我们理解发生了什么的关键

对于任何优秀的性能工程师来说，在开始调查之前应该尝试猜出答案、然后找出实际答案，来训练直觉。花几分钟给这些问题找出合理的假设答案。你要做什么实验来证实这些假设？什么样的实验能够证伪它们？

不是分配压力

先来一个简单的假设：分配压力。人们会猜测不同的分配压力会造成不同的性能影响。事实上，一些GC敏感的服务同样是GC受限的，即性能瓶颈是GC。

通常基准测试GC限制的服务是很简单的。在我们的场景下，我们用单线程来跑基准测试代码，这使得GC线程可以自由地在单独的核上运行，使用多个GC线程来处理单个基准测试线程的垃圾。添加更多的基准测试线程将使它们:a)与GC线程竞争CPU时间，从而隐式地影响GC时间;b)产生更多的垃圾，从而使每个应用程序线程的GC线程的有效数量下降，加剧内存管理成本。

这是我们通常希望在单线程和多线程(饱和)模式下运行基准测试的原因之一:在饱和模式下运行可以捕获系统正在执行的任何“隐藏”cpu offload活动。

但在我们的例子中，我们可以走捷径直接估计分配压力。因为，JMH有一个-prof gc分析器，它侦听gc事件，将它们相加，并将分配/流失率归一化为基准操作数，从而为每个@Benchmark调用提供分配压力。

Allocation pressure (the table shows only "gc.alloc.rate.norm" metric)
Benchmark           (size)     (type)  Mode  Cnt    Score    Error  Units

# ------------------------------------------------------------------------

ToArrayBench.simple      0  arraylist  avgt   30    16.000 ± 0.001  B/op
ToArrayBench.sized       0  arraylist  avgt   30    16.000 ± 0.001  B/op
ToArrayBench.zero        0  arraylist  avgt   30    16.000 ± 0.001  B/op

ToArrayBench.simple      1  arraylist  avgt   30    24.000 ± 0.001  B/op
ToArrayBench.sized       1  arraylist  avgt   30    24.000 ± 0.001  B/op
ToArrayBench.zero        1  arraylist  avgt   30    40.000 ± 0.001  B/op

ToArrayBench.simple     10  arraylist  avgt   30    56.000 ± 0.001  B/op
ToArrayBench.sized      10  arraylist  avgt   30    56.000 ± 0.001  B/op
ToArrayBench.zero       10  arraylist  avgt   30    72.000 ± 0.001  B/op

ToArrayBench.simple    100  arraylist  avgt   30   416.000 ± 0.001  B/op
ToArrayBench.sized     100  arraylist  avgt   30   416.000 ± 0.001  B/op
ToArrayBench.zero      100  arraylist  avgt   30   432.000 ± 0.001  B/op

ToArrayBench.simple   1000  arraylist  avgt   30  4016.001 ± 0.001  B/op
ToArrayBench.sized    1000  arraylist  avgt   30  4016.001 ± 0.002  B/op
ToArrayBench.zero     1000  arraylist  avgt   30  4032.001 ± 0.001  B/op

# ------------------------------------------------------------------------

ToArrayBench.simple      0    hashset  avgt   30    16.000 ± 0.001  B/op
ToArrayBench.sized       0    hashset  avgt   30    16.000 ± 0.001  B/op
ToArrayBench.zero        0    hashset  avgt   30    16.000 ± 0.001  B/op

ToArrayBench.simple      1    hashset  avgt   30    24.000 ± 0.001  B/op
ToArrayBench.sized       1    hashset  avgt   30    24.000 ± 0.001  B/op
ToArrayBench.zero        1    hashset  avgt   30    24.000 ± 0.001  B/op

ToArrayBench.simple     10    hashset  avgt   30    56.000 ± 0.001  B/op
ToArrayBench.sized      10    hashset  avgt   30    56.000 ± 0.001  B/op
ToArrayBench.zero       10    hashset  avgt   30    56.000 ± 0.001  B/op

ToArrayBench.simple    100    hashset  avgt   30   416.000 ± 0.001  B/op
ToArrayBench.sized     100    hashset  avgt   30   416.001 ± 0.001  B/op
ToArrayBench.zero      100    hashset  avgt   30   416.001 ± 0.001  B/op

ToArrayBench.simple   1000    hashset  avgt   30  4056.006 ± 0.009  B/op
ToArrayBench.sized    1000    hashset  avgt   30  4056.007 ± 0.010  B/op
ToArrayBench.zero     1000    hashset  avgt   30  4056.006 ± 0.009  B/op

# ------------------------------------------------------------------------

实验结果表示，分配压力在三种toArray方法中几乎没有差别。zero在一些组别中比其它两个多16byte , 这是"redundant" array allocation导致的。（给读者的练习：为什么zero在Hashset的表现中和其它两个一致？）。但是，我们之前的吞吐量基准测试的结果是zero更快，而不是慢，正如分配压力假说所预测的那样。因此，分配压力不能解释我们看到的现象。

性能分析

在我们的领域里，我们可以跳过建立假设, 直接用厉害的工具来进行分析。如果我们用后见之明，直接得出结论，这一节可能会更短。但这篇文章的重点之一是展示分析这些基准的方法。

Meet VisualVM (and other Java-only profilers)

最明显的方法就是用java profiler连接一个基准测试中的JVM,看看里面发生了什么。在保证通用性的前提下，我们以JDK自带的VisualVM分析器为例，这样大多数安装了java的环境都可以使用它。

VisualVM使用起来非常简单：开启进程，开启VisualVM(如果JDK在你的PATH环境变量里，直接使用jvisualvm即可), 从列表中选择一个VM,然后点击"Sample"->"CPU Sampling"采集，然后享受结果吧。下图是我们的实验结果：

Figure 3. VisualVM profile snapshot for the "ToArrayBench.simple" case and ArrayList of size 1000

Emmm... 信息量很大。

大多数java profilers都有内部偏见，因为它们要么检测代码，从而推测真实结果，要么在代码中指定的位置(例如safepoints)取样，从而也会歪曲结果。在我们上面的例子中，虽然大部分工作是在simple()方法中完成的，但profiler将工作误归为持有基准循环的…_jmhStub方法所有。
但这不是核心问题。对我们来说，最成问题的部分是缺少任何可以帮助我们回答性能问题的低级细节。你能在上面的分析快照中看到任何可以验证我们案例中任何合理假设的东西吗?　不能，因为数据太粗糙了。注意，在更高的工作负载下，偏见效应影响可忽略不计。

Meet JMH -prof perfasm

微基准测试工具为探索微基准测试底层细节的需求提供了明确的分析、检验方法。比如JMH,有一个内嵌的"perfasm" 分析器用于从VM转储PringAssembly 、添加perf_event计数器注释、打印热点。perf_event提供了一个基于硬件计数器的非侵入式的采样分析器,正是我们对细粒度性能工程的要求。

下面是实验的输出结果

$ java -jar target/benchmarks.jar zero -f 1 -p size=1000 -p type=arraylist -prof perfasm
....[Hottest Region 1].......................................................................
 [0x7fc4c180916e:0x7fc4c180920c] in StubRoutines::checkcast_arraycopy

StubRoutines::checkcast_arraycopy [0x00007fc4c18091a0, 0x00007fc4c180926b]
  0.04%                  0x00007fc4c18091a0: push   %rbp
  0.06%    0.01%         0x00007fc4c18091a1: mov    %rsp,%rbp
  0.01%                  0x00007fc4c18091a4: sub    $0x10,%rsp
  0.02%    0.01%         0x00007fc4c18091a8: mov    %r13,(%rsp)
  0.14%    0.02%         0x00007fc4c18091ac: mov    %r14,0x8(%rsp)
  0.07%    0.02%         0x00007fc4c18091b1: lea    (%rdi,%rdx,4),%rdi
  0.01%                  0x00007fc4c18091b5: lea    (%rsi,%rdx,4),%r13
                         0x00007fc4c18091b9: mov    %rdx,%r14
  0.02%                  0x00007fc4c18091bc: neg    %rdx
  0.01%    0.01%   ╭     0x00007fc4c18091bf: jne    0x00007fc4c18091de
                   │     0x00007fc4c18091c5: xor    %rax,%rax
                   │     0x00007fc4c18091c8: jmpq   0x00007fc4c1809260
                   │     0x00007fc4c18091cd: data16 xchg %ax,%ax
 19.30%   19.73%   │↗↗↗  0x00007fc4c18091d0: mov    %eax,0x0(%r13,%rdx,4)
  5.96%    6.89%   ││││  0x00007fc4c18091d5: inc    %rdx
                   ││││  0x00007fc4c18091d8: je     0x00007fc4c1809233
  3.84%    4.92%   ↘│││  0x00007fc4c18091de: mov    (%rdi,%rdx,4),%eax
  5.83%    6.56%    │││  0x00007fc4c18091e1: test   %rax,%rax
                    ╰││  0x00007fc4c18091e4: je     0x00007fc4c18091d0
 14.88%   20.52%     ││  0x00007fc4c18091e6: mov    0x8(%rax),%r11d
 15.11%   19.60%     ││  0x00007fc4c18091ea: shl    $0x3,%r11
 10.65%   11.80%     ││  0x00007fc4c18091ee: cmp    %r8,%r11
  0.01%              ╰│  0x00007fc4c18091f1: je     0x00007fc4c18091d0
                      │  0x00007fc4c18091f3: cmp    (%r11,%rcx,1),%r8
                      ╰  0x00007fc4c18091f7: je     0x00007fc4c18091d0
                         0x00007fc4c18091f9: cmp    $0x18,%ecx
                         0x00007fc4c18091fc: jne    0x00007fc4c1809223
                         0x00007fc4c1809202: push   %rax
                         0x00007fc4c1809203: mov    %r8,%rax
                         0x00007fc4c1809206: push   %rcx
                         0x00007fc4c1809207: push   %rdi
                         0x00007fc4c1809208: mov    0x20(%r11),%rdi
                         0x00007fc4c180920c: mov    (%rdi),%ecx
.............................................................................................
 75.96%   90.09%  <total for region 1>

实验结果表明，程序中最热点的部份在方法StubRoutines::checkcast_arraycopy中。我们稍后再详细分析，但主要问题是，我们的性能现象表现在生成代码(generated code)中，甚至可能不是java支持的生成代码。虽然本文的进一步推论可以通过perfasm来重现，但我想着眼于另一种更传统、可扩展高负载的方法。

Meet Solaris Studio Performance Analyzer

想象一下，我们需要一个没有偏见的Java/native代码可用的，硬件计数器可选的分析器？真的有一个这样的APP。它的名字容易让人误解，叫Solaris Studio Performance Analyzer,但它同样可用于Linux系统。

适合用于分析程序的workflow有好多,以下是我们在实验中最常用的。分析器由两个不同的部分组成：一个用于收集性能数据的收集器和一个处理分析结果的分析器GUI。用命令行收集工具是很方便的，因为你可以给这些常用的命令设置好用的别名。

$ tail ~/.bashrc
# Collect Java+native, clock profiling
alias 'perfanal'="collect -o test.1.er -S on -j on -A on "

# Collect native only (useful when loading *lots* of classes
# -- avoids profiler's JVMTI hooks overheads), clock profiling
alias 'perfanal-native'="collect -o test.1.er -S on -j off -A on "

# Collect Java+native, hardware counter profiling
alias 'perfanal-hwc'="collect -o test.1.er -S on -j on -A on -h cycles,on,insts,on "

# Collect native only, hardware counting profiling
alias 'perfanal-hwc-native'="collect -o test.1.er -S on -j off -A on -h cycles,on,insts,on "

这些别名让你可以快速地把分析器连接到JMH

$ perfanal-hwc java -jar benchmarks.jar -f 1 -p size=1000 -p type=arraylist

这个命令会在当前工作目录生成一个test.${n}.er的结果文件，你可以用分析器GUI打开它。

Figure 4. ArrayList (size = 1000), toArray().

在simple中，我们最热点的代码是jint_disjoint_arraycopy,看起来这个方法实现的是非连续(disjoint)数组的"int" arraycopy,

注意：分析器是如何处理Java代码(org.openjdk...), 虚拟机native代码(ParallelTaskTerminator::.. 和SpinPause) ,和调用call_stub生成的汇编代码(e.g. jint_disjoint_arraycopy)的。在复杂的场景下,调用树会同时展示java代码和native代码，当我们调试JNI/JNA时非常有用。调用树把jint_disjoint_arraycopy当作一个叶子方法(leaf function)。这个方法没有其它的指示，但你可能通过Hotspot源码库搜索，找到stubRoutines.hpp。里面说"StubRoutines提供了编译代码和运行时系统所使用的装配例程的入口点。平台特定的入口点是在平台特定的内部类中定义的。", 编译阶段和运行阶段都使用它来优化一些操作，特别是arraycopy。

Figure 5. ArrayList (size = 1000), toArray(new T[list.size()]).

在sized中，我们看到和simple不一样的arraycopy方法checkcast_arraycopy, 以及Java代码sized()方法。

Figure 6. ArrayList (size = 1000), toArray(new T[0]).

在zero中，我们找到另一个类似的方法checkcast_arraycopy_uninit。看起来和checkcast_arraycopy差不多，但"uninit"是什么? 注意这里Java函数不是热点方法了。

这些方法的名称已经很直白了，但是在我们使用另一个厉害的分析器功能前这些都是猜测。当我们选中一个方法，然后点击"Disassembly"视图，我们看到..

Figure 7. simple case disassembly.

jint_disjoint_arraycopy使用AVX进行向量化拷贝！难怪这么快: 它大段地复制了内存。

Figure 8. zero case disassembly

zero disassembly(把高级代码编译成低级代码?)视图展示了非向量化的checkcast_arraycopy_uninit。它都做了什么？这个循环看起来和地址30~51拷贝的关,但看起来没有向量化。要理解这个方法做了什么需要更多的VM内部知识。通常，你可以通过连接java 代码来assembly(ps:把汇编反编译成高级代码?) ,但VM stubs和java代码没有关联。你也可以跟踪VM源码来生成stub。这里我们选择耐心地看代码。

循环通过movl(%rdi,%rdx,4),%eax读取，通过movl %eax, 0(%r13,%rdx,4)定入，%rdx在增加-- 这表明%rdx是循环计数器。把当前的内容读到%eax后，我们检查是否为null,然后从偏移0x8加载一些内容, shift it, 然后和其它东西做比较。这就是加载一个class word，将其展开，并对其进行类型检查。

你可以通过JOL来查看java对象运行时的表示。看一下这个例子JOLSample_11_ClassWord example.

Figure 9. sized case disassembly, arraycopy stub

sized有两个热点，一个是checkcast_arraycopy ，和zero一样。但我们看到另一个热点:

Figure 10. sized case disassembly, Java code

大多数Cpu Cycles都花费在repz stosb。如果不看生成代码，这个方法比较难理解。prefetchnta在HotSpot-generated代码中通常是"allocation prefetch"(见command line docs,"-XX:Allocate..."), 和对象分配关联。事实上，我们在%r9有一个"新"对象地址，并放入了mark word,class word然后用repz stosb对存储空间清零－－相当于memset to zero。分配本身是一个数组分配，我们看到的是数组归零。你可以在Why Nothing Matters: The Impact of Zeroing中看详细解析。

初步见解

综上，我们有了初步见解：

simple比sized和zero快主要因为使用的向量化数组复制比用类型检查数组复制快很多
zero 比sized快是因为zero神奇地躲避array zeroing。而“反射”数组创建似乎根本不影响zero性能。

用HashSet重做实验这部分留给读者。结果应该基本和我们的初步见解一致。

后续行动

在很多情况下，继续跟进当前的发现来确定这个结论有多通用，你是否真的了解了背后的原因是非常有意义的。但要小心的是，这可能是个性能工程的兔子洞(兔子洞:指的是是很难搞的事情，一时半会解决不了的问题), 你永远到不了洞底，只能停止探索。

New Reflective Array

首先，让我们来解构"反射数组创建是很慢的"这个直觉。我们知道，很多Collection初始化一个给定类型数组时用的都是Array.newInstance(Class<?>,int)－－我们先来试试这个。用同样的压测方法来设计实验，但只留下newInstance代码。

@Warmup(iterations = 10, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 10, time = 1, timeUnit = TimeUnit.SECONDS)
@Fork(value = 3, jvmArgsAppend = {"-XX:+UseParallelGC", "-Xms1g", "-Xmx1g"})
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)
public class ReflectiveArrayBench {

    @Param({"0", "1", "10", "100", "1000"})
    int size;

    @Benchmark
    public Foo[] lang() {
        return new Foo[size];
    }

    @Benchmark
    public Foo[] reflect() {
        return (Foo[]) Array.newInstance(Foo.class, size);
    }
}

现在看下实验结果会发现，"language"和反射调用的性能几乎一样。

Benchmark                     (size)  Mode  Cnt    Score    Error  Units

# default
ReflectiveArrayBench.lang          0  avgt    5   17.065 ±  0.224  ns/op
ReflectiveArrayBench.lang          1  avgt    5   12.372 ±  0.112  ns/op
ReflectiveArrayBench.lang         10  avgt    5   14.910 ±  0.850  ns/op
ReflectiveArrayBench.lang        100  avgt    5   42.942 ±  3.666  ns/op
ReflectiveArrayBench.lang       1000  avgt    5  267.889 ± 15.719  ns/op

# default
ReflectiveArrayBench.reflect       0  avgt    5   17.010 ±  0.299  ns/op
ReflectiveArrayBench.reflect       1  avgt    5   12.542 ±  0.322  ns/op
ReflectiveArrayBench.reflect      10  avgt    5   12.835 ±  0.587  ns/op
ReflectiveArrayBench.reflect     100  avgt    5   42.691 ±  2.204  ns/op
ReflectiveArrayBench.reflect    1000  avgt    5  264.408 ± 22.079  ns/op

为什么会这样？我昂贵的反射调用去哪里了？要想长话短说，你通常可以通过这些步骤来把这种“古怪”的现象一分为二。首先，google/记住很长一段时间Reflection调用会被inflated(当某个地本地方法调用次数超出阈值时，会从昂贵的JNI调用膨胀为与JNI无关的生成代码的调用)。关闭反射膨胀后，实现结果如下：

Benchmark                     (size)  Mode  Cnt    Score   Error  Units

# -Dsun.reflect.inflationThreshold=2147483647
ReflectiveArrayBench.reflect       0  avgt   10   17.253 ± 0.470  ns/op
ReflectiveArrayBench.reflect       1  avgt   10   12.418 ± 0.101  ns/op
ReflectiveArrayBench.reflect      10  avgt   10   12.554 ± 0.109  ns/op
ReflectiveArrayBench.reflect     100  avgt   10   39.969 ± 0.367  ns/op
ReflectiveArrayBench.reflect    1000  avgt   10  252.281 ± 2.630  ns/op

hm...不是这个原因。我们再看一下源码：
jdk/src/java.base/share/classes/java/lang/reflect/Array.java

class Array {
    public static Object newInstance(Class<?> componentType, int length)
        throws NegativeArraySizeException {
        return newArray(componentType, length);
    }

    @HotSpotIntrinsicCandidate // <--- 哦？这是个啥?
    private static native Object newArray(Class<?> componentType, int length)
        throws NegativeArraySizeException;
}

jdk/src/java.base/share/classes/jdk/internal/HotSpotIntrinsicCandidate.java

/**
 * The {@code @HotSpotIntrinsicCandidate} annotation is specific to the
 * HotSpot Virtual Machine. It indicates that an annotated method
 * may be (but is not guaranteed to be) intrinsified by the HotSpot VM. A method
 * is intrinsified if the HotSpot VM replaces the annotated method with hand-written
 * assembly and/or hand-written compiler IR -- a compiler intrinsic -- to improve
 * performance. The {@code @HotSpotIntrinsicCandidate} annotation is internal to the
 * Java libraries and is therefore not supposed to have any relevance for application
 * code.
 */
public @interface HotSpotIntrinsicCandidate { ... }

(注释中的意思大概直接调用 JVM 内部实现(可能是手写的汇编代码或中间代码)，不走常规 JNI lookup，来提高性能。)

所以,Array.newArray是VM自己才知道的方法。有意思，我们来看下VM中的实现:
hotspot/src/share/vm/classfile/vmSymbols.hpp

  do_intrinsic(_newArray, java_lang_reflect_Array, newArray_name, newArray_signature, F_SN) \
   do_name(     newArray_name,       "newArray")                                            \
   do_signature(newArray_signature,  "(Ljava/lang/Class;I)Ljava/lang/Object;")              \

Instrinsic?让我把你关了吧：

# -XX:+UnlockDiagnosticVMOptions -XX:DisableIntrinsic=_newArray
ReflectiveArrayBench.reflect       0  avgt    5   67.594 ± 4.795  ns/op
ReflectiveArrayBench.reflect       1  avgt    5   69.935 ± 7.766  ns/op
ReflectiveArrayBench.reflect      10  avgt    5   73.588 ± 0.329  ns/op
ReflectiveArrayBench.reflect     100  avgt    5   86.598 ± 1.735  ns/op
ReflectiveArrayBench.reflect    1000  avgt    5  409.786 ± 9.148  ns/op

啊哈！找到你了！toArray方法被VM特殊处理了，并且产生了的相同的生成代码。但先别根据你在网上看到的解释来猜测它到底干了什么。我们先来看一下性能分析器的分析结果:

Figure 11. _newArray intrinsic enabled

Figure 12. _newArray intrinsic disabled

有什么区别？当intrinsic关闭后，我们看到Java方法Array.newArray调用JVM_NewArray本地方法,再调用VM的Reflection::...，再然后向GC申请空间来分配数组。这就是人们曾经见过的昂贵的"Array.newArray"调用了。

但是，这个昂贵的调用在 JDK-6525802就修复了。我们稍后会回归几个历史版本的jdk看看。

Empty Array Instantiation

现在，让我们将注意力转移到数组实例化成本上。在我们跳到零化消去之前，理解分配本身是如何工作的是很重要的。事后来看，我们想要测量恒定大小的数组和非恒定大小的数组(这些数组的大小并不是静态的)。编译器能基于这些已知条件做点什么吗?

先来看看，我们构建了一个这样的JMH基准测试（为了让它看起来短一点，我用伪代码来描述）

@Warmup(iterations = 10, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 10, time = 1, timeUnit = TimeUnit.SECONDS)
@Fork(value = 3, jvmArgsAppend = {"-XX:+UseParallelGC", "-Xms1g", "-Xmx1g"})
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)
public class EmptyArrayBench {

#for L in 0..512
    int v$L = $L;

    @Benchmark
    public Foo[] field_$L() {
        return new Foo[v$L];
    }

    @Benchmark
    public Foo[] const_$L() {
        return new Foo[$L];
    }
#done

结果如下：

Benchmark                 Mode  Cnt   Score   Error  Units

# -----------------------------------------------------------

EmptyArrayBench.const_000  avgt   15    2.847 ± 0.016  ns/op
EmptyArrayBench.const_001  avgt   15    3.090 ± 0.020  ns/op
EmptyArrayBench.const_002  avgt   15    3.083 ± 0.022  ns/op
EmptyArrayBench.const_004  avgt   15    3.336 ± 0.029  ns/op
EmptyArrayBench.const_008  avgt   15    4.618 ± 0.047  ns/op
EmptyArrayBench.const_016  avgt   15    7.568 ± 0.061  ns/op
EmptyArrayBench.const_032  avgt   15   13.935 ± 0.098  ns/op
EmptyArrayBench.const_064  avgt   15   25.905 ± 0.183  ns/op
EmptyArrayBench.const_128  avgt   15   52.807 ± 0.252  ns/op
EmptyArrayBench.const_256  avgt   15  110.208 ± 1.006  ns/op
EmptyArrayBench.const_512  avgt   15  171.864 ± 0.777  ns/op

# -----------------------------------------------------------

EmptyArrayBench.field_000  avgt   15   16.998 ± 0.063  ns/op
EmptyArrayBench.field_001  avgt   15   12.400 ± 0.065  ns/op
EmptyArrayBench.field_002  avgt   15   12.651 ± 0.332  ns/op
EmptyArrayBench.field_004  avgt   15   12.434 ± 0.062  ns/op
EmptyArrayBench.field_008  avgt   15   12.504 ± 0.049  ns/op
EmptyArrayBench.field_016  avgt   15   12.588 ± 0.065  ns/op
EmptyArrayBench.field_032  avgt   15   14.423 ± 0.121  ns/op
EmptyArrayBench.field_064  avgt   15   26.145 ± 0.166  ns/op
EmptyArrayBench.field_128  avgt   15   53.092 ± 0.291  ns/op
EmptyArrayBench.field_256  avgt   15  110.275 ± 1.304  ns/op
EmptyArrayBench.field_512  avgt   15  174.326 ± 1.642  ns/op

# -----------------------------------------------------------

Oops.看起来field_*在小数组长度的实验中输了。这是为什么呢？ -prof perfasm输出结果如下：

Hottest allocation code in const_0008:

  2.30%    1.07%  0x00007f32cd1f9f76: prefetchnta 0xc0(%r10)
  3.34%    3.88%  0x00007f32cd1f9f7e: movq   $0x1,(%rax)
  3.66%    4.39%  0x00007f32cd1f9f85: prefetchnta 0x100(%r10)
  1.63%    1.91%  0x00007f32cd1f9f8d: movl   $0x20018fbd,0x8(%rax)
  1.76%    2.31%  0x00007f32cd1f9f94: prefetchnta 0x140(%r10)
  1.52%    2.14%  0x00007f32cd1f9f9c: movl   $0x8,0xc(%rax)
  2.77%    3.67%  0x00007f32cd1f9fa3: prefetchnta 0x180(%r10)
  1.77%    1.80%  0x00007f32cd1f9fab: mov    %r12,0x10(%rax)
  4.40%    4.61%  0x00007f32cd1f9faf: mov    %r12,0x18(%rax)
  4.64%    3.97%  0x00007f32cd1f9fb3: mov    %r12,0x20(%rax)
  4.83%    4.49%  0x00007f32cd1f9fb7: mov    %r12,0x28(%rax)
  2.03%    2.71%  0x00007f32cd1f9fbb: mov    %r8,0x18(%rsp)
  1.35%    1.25%  0x00007f32cd1f9fc0: mov    %rax,%rdx

Hottest allocation code in field_0008:

 0.02%           0x00007f27551fb424: prefetchnta 0xc0(%r11)
  5.53%    7.55%  0x00007f27551fb42c: movq   $0x1,(%r9)
  0.02%           0x00007f27551fb433: prefetchnta 0x100(%r11)
  0.05%    0.06%  0x00007f27551fb43b: movl   $0x20018fbd,0x8(%r9)
           0.01%  0x00007f27551fb443: mov    %edx,0xc(%r9)
  2.03%    1.78%  0x00007f27551fb447: prefetchnta 0x140(%r11)
  0.04%    0.07%  0x00007f27551fb44f: mov    %r9,%rdi
  0.02%    0.02%  0x00007f27551fb452: add    $0x10,%rdi
  0.02%    0.01%  0x00007f27551fb456: prefetchnta 0x180(%r11)
  1.96%    1.05%  0x00007f27551fb45e: shr    $0x3,%rcx
  0.02%    0.02%  0x00007f27551fb462: add    $0xfffffffffffffffe,%rcx
  0.01%    0.03%  0x00007f27551fb466: xor    %rax,%rax
  0.01%           0x00007f27551fb469: shl    $0x3,%rcx
  1.96%    0.06%  0x00007f27551fb46d: rep rex.W stos %al,%es:(%rdi) ; <--- huh...
 39.44%   78.39%  0x00007f27551fb470: mov    %r8,0x18(%rsp)
  8.01%    0.18%  0x00007f27551fb475: mov    %r9,%rdx

进一步分析得到，const_*在达到一定阈值之后会切换到rep stos(和大多数memset的实现差不多),试图躲过rep stos的设置成本。但field_*的例子中，不知道静态长度，因此总是会执行rep stos,并且在小长度数组情况下影响明显。

这是可以修复的，见 JDK-8146801。但是，固定长度的数组性能总是更好一些。你知道这是怎么应用到toArray情况上的吗？在较小的集合大小时，比较new T[0]或new T[coll.size()]。这就回答了zero在小集合上的“异常”优势。

这又是另一个“编译器能猜测到越多信息，优化效果就越好”的例子。一个更有趣的例子在文章Faster Atomic*FieldUpdaters for Everyone描述。

Uninitialized Arrays

现在，轮到讲zeroing的故事了。Java语言规范里要求，每一个新的数组或对象的准备阶段都需要有初始值（zeros）。因此，在运行阶段必需zero-out这些分配了的内存。但是，如果在对象/数组对其它对象可见之前用一些初始值覆盖该存储，我们就可以将初始化和zeroing合并，从而高效地消除了零值。注意，"可见"在面对异常返回，finalizers和其它VM内部成员时很难定义, 详见: e.g. JDK-8074566。

我们看到zero的例子中躲避了zeroing过程，但sized中却没有，这是为什么？为了找到原因，我们需要评估一下不同的代码中分配数组是怎么实现的。

@Warmup(iterations = 10, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 10, time = 1, timeUnit = TimeUnit.SECONDS)
@Fork(value = 3, jvmArgsAppend = {"-XX:+UseParallelGC", "-Xms1g", "-Xmx1g"})
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)
public class ArrayZeroingBench {
    @Param({"1", "10", "100", "1000"})
    int size;

    Object[] src;

    @Setup
    public void setup() {
        src = new Object[size];
        for (int c = 0; c < size; c++) {
            src[c] = new Foo();
        }
    }

    @Benchmark
    public Foo[] arraycopy_base() {
        Object[] src = this.src;
        Foo[] dst = new Foo[size];
        System.arraycopy(src, 0, dst, 0, size - 1);
        return dst;
    }

    @Benchmark
    public Foo[] arraycopy_field() {
        Object[] src = this.src;
        Foo[] dst = new Foo[size];
        System.arraycopy(src, 0, dst, 0, size);
        return dst;
    }

    @Benchmark
    public Foo[] arraycopy_srcLength() {
        Object[] src = this.src;
        Foo[] dst = new Foo[size];
        System.arraycopy(src, 0, dst, 0, src.length);
        return dst;
    }

    @Benchmark
    public Foo[] arraycopy_dstLength() {
        Object[] src = this.src;
        Foo[] dst = new Foo[size];
        System.arraycopy(src, 0, dst, 0, dst.length);
        return dst;
    }

    @Benchmark
    public Foo[] copyOf_field() {
        return Arrays.copyOf(src, size, Foo[].class);
    }

    @Benchmark
    public Foo[] copyOf_srcLength() {
        return Arrays.copyOf(src, src.length, Foo[].class);
    }

    public static class Foo {}
}

实验结果如下：

Benchmark                (size)  Mode  Cnt    Score    Error  Units
AZB.arraycopy_base            1  avgt   15   14.509 ±  0.066  ns/op
AZB.arraycopy_base           10  avgt   15   23.676 ±  0.557  ns/op
AZB.arraycopy_base          100  avgt   15   92.557 ±  0.920  ns/op
AZB.arraycopy_base         1000  avgt   15  899.859 ±  7.303  ns/op

AZB.arraycopy_dstLength       1  avgt   15   17.929 ±  0.069  ns/op
AZB.arraycopy_dstLength      10  avgt   15   23.613 ±  0.368  ns/op
AZB.arraycopy_dstLength     100  avgt   15   92.553 ±  0.432  ns/op
AZB.arraycopy_dstLength    1000  avgt   15  902.176 ±  5.816  ns/op

AZB.arraycopy_field           1  avgt   15   18.063 ±  0.375  ns/op
AZB.arraycopy_field          10  avgt   15   23.443 ±  0.278  ns/op
AZB.arraycopy_field         100  avgt   15   93.207 ±  1.565  ns/op
AZB.arraycopy_field        1000  avgt   15  908.663 ± 18.383  ns/op

AZB.arraycopy_srcLength       1  avgt   15    8.658 ±  0.058  ns/op
AZB.arraycopy_srcLength      10  avgt   15   14.114 ±  0.084  ns/op
AZB.arraycopy_srcLength     100  avgt   15   79.778 ±  0.639  ns/op
AZB.arraycopy_srcLength    1000  avgt   15  681.040 ±  9.536  ns/op

AZB.copyOf_field              1  avgt   15    9.383 ±  0.053  ns/op
AZB.copyOf_field             10  avgt   15   14.729 ±  0.091  ns/op
AZB.copyOf_field            100  avgt   15   81.198 ±  0.477  ns/op
AZB.copyOf_field           1000  avgt   15  671.670 ±  6.723  ns/op

AZB.copyOf_srcLength          1  avgt   15    8.150 ±  0.409  ns/op
AZB.copyOf_srcLength         10  avgt   15   13.214 ±  0.112  ns/op
AZB.copyOf_srcLength        100  avgt   15   80.718 ±  1.583  ns/op
AZB.copyOf_srcLength       1000  avgt   15  671.716 ±  5.499  ns/op

当然，如果你想学习生成代码来解析你对以上结果的任何猜想，我们已经帮你做了,见JDK-8146828。VM尝试消除尽可能多的零值，因为这个优化是相当有用的－－这就是为什么zero(使用类似copyOf_*)得到了好处的原因了。

但也有例外的情况，在一些情况下，零值没有被有效消除，这是需要被修复的。详见JDK-8146828

Caching the Array

有人会问：给出的zero例子已经被优化得很好了，我们还能进一步地把这个大小为零的数组缓存为静态变量以得到更高的性能吗？这样我们就可以完全避免 stray allocation了?我们来看一看这个zero_cached实验：

@State(Scope.Benchmark)
public class ToArrayBench {

    // Note this is *both* static *and* final
    private static final Foo[] EMPTY_FOO = new Foo[0];

    ...

    @Benchmark
    public Foo[] zero() {
        return coll.toArray(new Foo[0]);
    }

    @Benchmark
    public Foo[] zero_cached() {
        return coll.toArray(EMPTY_FOO);
    }
}

注意这两个例子稍有区别：对于空集合，zero_cached会返回同一个数组,而不是每次调用都会生成一个新数组。如果用户使用数组标识进行某些操作，这可能会有问题。