Почему Arrays.equals(char [], char []) в 8 раз быстрее всех остальных версий?

Краткая история

Основываясь на моих тестах с несколькими различными реализациями 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[] вариант подавляет все остальные, как показано выше.

Теперь это доминирование разнообразия ~ 8x не распространяется на одну и ту же величину на меньшие или гораздо большие массивы, но оно все же быстрее.

Для небольших массивов кажется, что доминируют постоянные факторы, а для больших массивов начинает появляться полоса пропускания L2/L3 или основной памяти (вы уже можете увидеть последний эффект довольно четко на ранней фигуре, где int[] и особенно long[] массивы начинают ухудшаться в производительности при больших размерах). Здесь рассмотрим тот же тест, но с меньшим малым массивом и большим большим массивом:

Здесь char[] по-прежнему ногами, просто не так много, как раньше. Время для элемента для небольшого массива (всего 16 элементов) примерно в два раза превышает стандартное время, вероятно, из-за функциональных накладных расходов: около 0,5 нс/элемент, вариант char[] все еще занимает всего около 7,2 наносекунды для всего вызова, или около 19 циклов на моей машине - так что небольшое количество накладных расходов метода сильно сокращается во время выполнения (также само по себе эталонные затраты - это несколько циклов).

В большом конце пропускная способность кеша и/или памяти является движущим фактором - вариант long[] занимает почти 2x, если вариант int[]. Варианты short[] и особенно byte[] не очень эффективны (их рабочий набор по-прежнему подходит для L3 на моей машине).

Разница между char[] и всеми остальными достаточно экстремальна, что для приложений, которые полагаются на сравнение массивов (это не так уж и необычно для некоторых конкретных доменов), стоит попытаться получить все ваши данные в char[], чтобы воспользоваться преимуществами. Да.

Что дает? char получает специальное лечение, потому что оно лежит в основе некоторых методов String? Является ли это еще одним примером методов оптимизации JVM, которые сильно пострадали в тестах и ​​не расширяют одну и ту же (очевидную) оптимизацию по отношению к другим примитивным типам (особенно short, которые здесь одинаковы)?

⁰... и что даже не все сумасшедшие - рассматривают различные системы, которые полагаются, например, на (длинное) хэш-сравнение, чтобы проверить, равны ли значения, или хеш-карты, где ключи имеют длинные или переменные размеры.

¹ Я не включил boolean[], float[] и double[] или дважды в результатах, чтобы избежать загромождения графика, но для записи boolean[] и float[] выполнено то же, что и int[], а double[] выполняется так же, как long[]. Это имеет смысл на основе базового размера типов.

² Я немного здесь. Эффект, по-видимому, внезапно изменился, но я фактически не заметил, пока я снова не побежал в тестах после ряда других изменений, что привело к болезненному процессу деления пополам, в котором я определил причинные изменения. Это отличная причина для того, чтобы обеспечить непрерывную интеграцию с измерением производительности.

Ответы

@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

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