为什么Arrays.equals（char[]，char[]）比所有其他版本快8倍？

arrays performance optimization java

2022-09-01 17:31:28

短篇小说

根据我对一些不同的Oracle和OpenJDK实现的测试，似乎Arrays.equals（char[]，char[]）在某种程度上比其他类型的所有其他变体快8倍。

如果应用程序的性能与比较数组的相等性高度相关^{为 0}，则意味着您几乎希望将所有数据强制放入，只是为了获得这种神奇的性能提升。char[]

说来话长

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

有一次，我使用了类型的键，但作为泛化服务的一部分，为了避免从和的底层源复制一些副本，我将其更改为。突然²，许多基本操作的性能下降了约3倍。我追溯了上面提到的事实：似乎比所有其他版本享有特殊的地位，包括语义上相同的版本（并且可以使用相同的底层代码实现，因为符号性不会影响equals的行为）。char[]byte[]ByteBufferbyte[]Arrays.equals(char[], char[])Arrays.equals()short[]

因此，我编写了一个 JMH 基准测试来测试 ¹ 的所有原始变体，并且该变体会粉碎所有其他变体，如上所示。Arrays.equals(...)char[]

现在，~8倍品种的这种主导地位并没有以相同的幅度扩展到更小或更大的阵列 - 但它仍然更快。

对于小型阵列，恒定因子似乎开始占主导地位，而对于较大的阵列，L2/L3 或主内存带宽开始发挥作用（在上图中，您已经可以非常清楚地看到后一种影响，其中阵列（尤其是阵列）在大尺寸下的性能开始下降）。下面看一下相同的测试，但使用较小的小数组和较大的大数组：int[]long[]

在这里，还在踢屁股，只是没有以前那么多了。小数组（只有16个元素）的每元素时间大约是标准时间的两倍，可能是由于功能开销：在大约0.5 ns /元素时，变体在整个调用中仍然只需要大约7.2纳秒，或者在我的机器上大约需要19个周期 - 所以少量的方法开销会占用很多运行时（此外，基准开销本身是几个周期）。char[]char[]

在大端，缓存和/或内存带宽是一个驱动因素 - 变体的长度几乎是变体的2倍。特别是变体不是很有效（它们的工作集仍然适合我机器中的L3）。long[]int[]short[]byte[]

与所有其他应用程序之间的差异非常大，以至于对于依赖于数组比较的应用程序（对于某些特定域来说，这实际上并不罕见），尝试将所有数据都放入其中以利用是值得的。哼。char[]char[]

什么原因？是否因为某些方法的基础而受到特殊对待？这是否只是JVM优化方法的另一种情况，这些方法在基准测试中受到严重打击，并且没有将相同（明显）的优化扩展到其他基元类型（特别是这里相同的基元类型）？charStringshort

⁰ ...这甚至不是那么疯狂 - 考虑各种系统，例如，依靠（冗长的）哈希比较来检查值是否相等，或者哈希映射，其中键很长或大小可变。

^{1 个}我没有在结果中包含和/或 double，以避免图表混乱，但对于记录和执行相同，而执行相同。根据类型的基础大小，这是有道理的。boolean[]float[]double[]boolean[]float[]int[]double[]long[]

^{阿拉伯数字}我在这里撒谎了一点。性能可能突然发生了变化，但我实际上并没有注意到，直到我在一系列其他变化之后再次运行基准测试，导致一个痛苦的对等分过程，我确定了因果变化。这是进行某种类型的性能衡量持续集成的重要原因。

答案 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

这个内在功能很久以前就是在2008年激烈的JVM竞争时代添加的。JDK 6 包含一个由启用的特殊库。我发现从这些特殊类之一中调用了许多 - .内在是这种“优化”的重要组成部分。在现代JDK中，没有更多，但JVM内部函数仍然存在（虽然没有发挥其原始作用）。alt-string.jar-XX:+UseStringCacheArrays.equals(char[], char[])StringValue.StringCachealt-string.jar

更新

我已经用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.equalsJDK 9 中的实现已更改。

现在，它为所有类型的非对象数组调用 ArraysSupport.vectorizedMismatch 帮助器方法。此外，它还是一个 HotSpot 内部函数，它具有使用 AVX 的手写程序集实现。vectorizedMismatch

答案 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