为什么 Arrays.equals(char[], char[]) 比其他所有版本快8倍？

Question

简短故事

根据我对几种不同的 Oracle 和 OpenJDK 实现进行的测试，似乎 Arrays.equals(char[], char[]) 比其他类型的所有变体都快约 8 倍。

如果您的应用程序性能与比较数组的相等性密切相关⁰，那么这意味着您几乎希望将所有数据强制转换为char[]，以获得此神奇性能提升。

长故事

最近我在编写一些高性能代码，使用Arrays.equals(...)来比较用于索引结构的键。这些键可能非常长，并且通常仅在后面的字节中有所不同，因此此方法的性能非常重要。

有一段时间我使用的键的类型是char[]，但是随着将服务泛化并避免来自底层byte[]和ByteBuffer的一些拷贝，我将其更改为byte[]。突然间²，许多基本操作的性能下降了约 3 倍。我追溯到上述事实：Arrays.equals(char[], char[])似乎比所有其他Arrays.equals()版本都享有特殊地位，包括取short[]的那个版本，这在语义上是相同的（并且可以使用相同的底层代码实现，因为符号对等式的行为没有影响）。

因此，我编写了一个JMH基准测试来测试所有的Arrays.equals(...)¹原始变量及其char[]的变体表现最优，如上图所示。

现在，这种8倍的优势并没有在较小或较大的数组中同样地延伸到相同的数量级 - 但它仍然更快。

对于小数组来说，似乎常数开始占主导地位，而对于大数组来说，L2 / L3或主内存带宽开始发挥作用（您已经可以在早期的图表中相当清楚地看到后一种效应，在大尺寸时int[]和特别是long[]数组的性能开始下降）。下面是同样的测试结果，但使用了一个较小的小数组和一个较大的大数组：

在此图表中，char[]仍然表现优异，只是不像以前那么明显。小数组的每个元素时间是标准时间的两倍左右（仅有16个元素），这可能是由于函数开销造成的：在每个元素约0.5纳秒的速度下，char[]变体仍然只需要大约7.2纳秒的时间完成整个调用，或者在我的机器上约为19个周期 - 因此少量的方法开销会严重影响运行时间（而基准测试本身的开销也需要几个周期）。

在较大的尺寸上，缓存和/或内存带宽是一个主要因素 - long[]变体需要的时间几乎是int[]变体的两倍。而short[]和特别是byte[]变体并不是很有效（它们的工作集仍适合我机器上的L3）。

char[]和其他所有类型之间的区别是极端的，在那些依赖于数组比较的应用程序中（对于某些特定领域实际上并不那么不寻常），值得尝试将您所有的数据放入char[]以利用它。这是为什么？char是否因为是String方法的基础而获得特殊处理？还是JVM优化了在基准测试中频繁使用的方法，而没有将同样（显而易见的）优化扩展到其他原始类型（特别是此处相同的short）？

---

⁰ ... 这甚至都不算太疯狂——考虑一下各种系统，例如依赖于（冗长的）哈希比较来检查值是否相等的系统，或键为长整型或可变大小的哈希映射。 ¹ 我没有包括boolean[]、float[]和double[]或双精度浮点数在结果中，以避免使图表杂乱无章，但要记录下来boolean[]和float[]与int[]的性能相同，而double[]与long[]的性能相同。这符合类型的底层大小。 ² 我在这里撒了一个小谎。性能可能突然改变，但直到我运行了一系列其他更改后再次运行基准测试时才注意到，导致我确定了因果关系的痛苦二分过程。这是拥有某种类型的性能测量持续集成的一个很好的理由。

- BeeOnRope

---

可能与char被视为无符号有关。 - vsfDawg

@vsfDawg：对于有符号和无符号类型，你应该能够以相同的方式进行等式比较。 - Thilo

是的，位是位。等于操作符没有不同的有符号/无符号行为（这就是为什么short[]没有得到相同的处理方式，因为对于这个操作它是相同的，这使得问题变得更加复杂）。 - BeeOnRope

认真的问题，我并不是在挖苦你：为什么你要用Java写高性能代码？ - nicomp

@nicomp - 实际上，我们大多数人都在一个有限制的世界中工作，包括我们编写软件的语言。事实上，Java处于性能较高的一端（仅次于C / C ++的较慢一侧），许多高性能服务器端软件正在使用它编写。在许多情况下，在适度的努力和专业水平下，由于良好编写的抽象化，它甚至可以胜过低级别的语言（尽管并非总是如此！）。只是为了澄清，您已经将自己的论点推到了极致，并编写了所有内容以定制运行ASIC，对吗？ - BeeOnRope

好奇这篇帖子是否会像得到最高投票的 Stack Overflow 帖子一样。 - Mordechai

Answer 1

@Marco13 的猜测是正确的。HotSpot JVM 对于Arrays.equals(char[], char[])有一个内部方法（即特殊手写实现），但对于其他Arrays.equals方法则没有。

以下JMH基准测试证明，禁用此内部方法使得char[]数组比较与short[]数组比较一样慢。

@State(Scope.Benchmark)
public class ArrayEquals {
    @Param("100")
    int length;

    short[] s1, s2;
    char[] c1, c2;

    @Setup
    public void setup() {
        s1 = new short[length];
        s2 = new short[length];
        c1 = new char[length];
        c2 = new char[length];
    }

    @Benchmark
    public boolean chars() {
        return Arrays.equals(c1, c2);
    }

    @Benchmark
    @Fork(jvmArgsAppend = {"-XX:+UnlockDiagnosticVMOptions", "-XX:DisableIntrinsic=_equalsC"})
    public boolean charsNoIntrinsic() {
        return Arrays.equals(c1, c2);
    }

    @Benchmark
    public boolean shorts() {
        return Arrays.equals(s1, s2);
    }
}

结果：

Benchmark                     (length)  Mode  Cnt   Score   Error  Units
ArrayEquals.chars                  100  avgt   10  19,012 ± 1,204  ns/op
ArrayEquals.charsNoIntrinsic       100  avgt   10  49,495 ± 0,682  ns/op
ArrayEquals.shorts                 100  avgt   10  49,566 ± 0,815  ns/op

这个内部函数在激烈的JVM竞争时期早在2008年就被添加进去了。 JDK 6包含了一个特殊的alt-string.jar库，它通过-XX:+UseStringCache启用。我发现一个特殊类StringValue.StringCache中有许多对Arrays.equals(char[], char[])的调用。这个内部函数是这种"优化"的重要组成部分。在现代JDK中没有了alt-string.jar，但JVM内置函数仍然存在（虽然并不扮演其原来的角色）。

更新

我使用JDK 9-ea+148进行了测试，似乎_equalsC内置函数对性能影响非常小。

Benchmark                     (length)  Mode  Cnt   Score   Error  Units
ArrayEquals.chars                  100  avgt   10  18,931 ± 0,061  ns/op
ArrayEquals.charsNoIntrinsic       100  avgt   10  19,616 ± 0,063  ns/op
ArrayEquals.shorts                 100  avgt   10  19,753 ± 0,080  ns/op

Arrays.equals 方法在JDK 9中已更改实现。

现在对于所有类型的非对象数组，它调用 ArraysSupport.vectorizedMismatch 辅助方法。此外，vectorizedMismatch 也是 HotSpot 内在函数，具有使用 AVX 的 手写汇编 实现。

- apangin

---

如果您禁用某些完全不相关的内在函数，而不是 _equalsC，是否会在基准测试中看到任何意外的交互作用呢？ - user2357112

感谢您将我的猜测详细阐述成一个我认为在各方面都可以接受的答案。我没有预料到这个内置函数会有如此大的影响力。相反，我原本以为其他的“equals”实现会被JIT优化器处理掉，最终结果与内置代码差不多。但是JIT优化器是一只野兽。诚然，我试图找到这个内置函数的实际代码，但没有找到。它似乎深藏在C1/C2优化器基础设施中。 - Marco13

@Marco13 这里是代码链接。 - apangin

顺便说一下，我刚刚测试了JDK 9-EA + 148版本，并且实际上在Arrays.compare的内部和非内部版本之间几乎没有任何区别。 - apangin

实际上，JDK 9拥有新的内建函数来实现快速数组比较。我已经更新了答案。 - apangin

Answer 2

我可能在提供答案时有些冒险，但根据http://hg.openjdk.java.net/jdk8/jdk8/hotspot/file/9d15b81d5d1b/src/share/vm/classfile/vmSymbols.hpp#l756，Arrays#equals(char[], char[])方法被实现为内置函数。

最有可能是因为在所有字符串比较中它具有高度的性能关键性。 <- 至少这一点是错误的。令人惊讶的是，String不使用Arrays.equals进行比较。但无论为什么它是一个内置函数，这仍然可能是性能差异的原因。

- Marco13

---

这引出了一个后续问题：JDK中的“intristic”是什么？ - Thilo

"String#equals"确实有自己的内在属性（根据您链接的文件）。因此，您的推理是正确的。 - Thilo

@Thilo - 内在函数基本上是一种“已知函数”，可以用手动编写的汇编实现来替换相应的Java实现（通常，该方法确实具有字节码实现，但由于内在化而经常不使用）。有时，该方法根本没有Java实现（例如System.arraycopy），因此必须作为内在函数或本地方法实现。 - BeeOnRope

你是正确的。Array.equals(char[], char[]) 内在函数早在2008年就被加入了。根据一个短小的电邮讨论链(链接为：http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/2008-May/000195.html)所述，当时并没有立即产生好处，但在JDK中计划了一些进一步的更改(据说从未发生)。 - apangin

不可否认，直到现在，这个“答案”更像是一个“猜测”。可以尝试使用 PrintCompilation、PrintInlining 和 PrintAssembly 来进行更全面的验证，甚至可以尝试禁用这个内部函数，以确保它确实是提高性能的原因。我希望有人会花些时间来创建一个更确定（和可接受）的答案。 - Marco13

好的，我已经添加了支持您最初猜测的答案。同时，我已经发现了这个内置函数的原始目的。 - apangin

Answer 3

对于字符而言，SSE3和4.1/4.2都非常擅长检查状态变化。JVM生成的字符操作代码更加精细调整，因为这是Java在Web应用程序等方面经常使用的。Java很难针对其他类型的数据进行优化。这就是事物的本质。

Scala和GoSu也表现出了同样的行为。如今大部分传输的信息都是文本形式，所以除非您修改JVM，否则它会针对文本进行调整。正如Marco所提到的，它是一个内在的C函数，意味着它直接映射到高性能向量化指令，如SSE4.x甚至AVX2，如果标准JVM已经得到了如此大的改进。

http://blog.synopse.info/post/2015/06/30/Faster-String-process-using-SSE-4.2-Text-Processing-Instructions-STTNI

http://www.tomshardware.com/reviews/Intel-i7-nehalem-cpu,2041-7.html

严肃地说，SSE4.x不将字符和字节视为等效的数据类型，这就是为什么文本分析更快的原因。此外，对于8位整数比较，直到AVX2才存在相应的指令。

- patrickjp93

---

char是一个16位类型。 - Thilo

Java字符不是8位的，UTF-8也没有涉及。(即使对于Arrays.equals方法，UTF-16也不是很相关，因为其中没有任何关心字符文本解释的内容。) - user2357112

你认为“字符类型”对处理器来说到底是什么，以至于它会与大小相等的整数有所不同？ - user2357112

它被downvote是因为：(1) Arrays.equals不是文本分析函数 (2) 你对特殊文本分析函数的断言并不适用于“char”，因为它是一个16字节的量 - 如果有什么的话，它们只能适用于“byte”，而且 (3) SSE文本方法永远不会对Arrays.equals（又名memcmp）产生影响。 - BeeOnRope

一些讨论和猜测可能会因为链接到包含实际实现的代码，而变得过时，这是apangin在其中一个评论中挖掘出来的。 - Marco13