为什么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[]语义上相同的一个版本(并且可以使用相同的底层代码实现,因为签名不会影响equals的行为).

所以我写了一个JMH基准测试的所有原始变种Arrays.equals(...)¹和char[]变异击碎所有其它的,如上图所示.

现在,~8x变种的这种优势并没有扩大到更小或更大的阵列 - 但它仍然更快.

对于小型阵列,似乎常数因素开始占主导地位,对于较大的阵列,L2/L3或主内存带宽开始起作用(您可以在前面的图中清楚地看到后者的影响,其中int[]尤其是long[]阵列开始降低大尺寸的性能).下面是相同的测试,但是有一个较小的小数组和较大的大数组:

在这里,char[]仍然踢屁股,只是没有像以前那么多.小数组(仅16个元素)的每个元素时间大约是标准时间的两倍,可能是由于函数开销:在大约0.5 ns /元素时,char[]整个调用的变量仍然只需要大约7.2纳秒,或大约19纳秒在我的机器上循环 - 所以少量的方法开销会大量削减运行时间(同样,基准开销本身就是几个循环).

在大端,缓存和/或内存带宽是一个驱动因素 - long[]变体几乎是变体的2 倍int[].的short[],尤其是byte[]变种都不是很有效的(他们的工作设置仍然适用于L3在我的机器).

char[]与其他所有应用程序之间的差异非常大,以至于对于依赖于阵列比较的应用程序(对于某些特定域而言,这实际上并不常见),尝试将所有数据char[]用于利用是值得的.呵呵.

是什么赋予了？是否char得到特殊待遇,因为它是某些String方法的基础？它只是JVM优化方法的另一种情况,它在基准测试中受到很大影响,而不是将相同(明显)的优化扩展到其他原始类型(特别short是在这里相同)？

---

⁰ ...并且这甚至都不是那么疯狂 - 考虑各种系统,例如,依赖于(冗长的)散列比较以检查值是否相等,或者哈希映射,其中键是长的或可变大小的.

¹我不包括 boolean[],float[]并且double[]或者在结果双以避免混乱的图表,但对于记录boolean[]和float[]执行相同int[],而double[]所执行的相同long[].根据类型的基础大小,这是有道理的.

²我躺在这里了一下.表现可能会突然发生变化,但在我进行了一系列其他变化之后,我再次运行基准测试后才真正注意到,导致一个痛苦的二分过程,我确定了因果关系的变化.这是进行某种性能测量持续集成的一个很好的理由.

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

这种内在的加入前不久在2008年积极的JVM竞争的时代.JDK 6包含一个特殊的alt-string.jar库,该库由启用-XX:+UseStringCache.我Arrays.equals(char[], char[])从其中一个特殊课程中找到了许多电话- StringValue.StringCache.内在性是这种"优化"的重要组成部分.在现代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为所有类型的非对象数组调用helper方法.此外,vectorizedMismatch它也是一个HotSpot内在函数,它具有使用AVX 的手写程序集实现.

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用于比较.但不管它为什么是内在的,这可能仍然是性能差异的原因.