Почему 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[]. Это имеет смысл на основе базового размера типов.

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

Ответ 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 intrinsic все еще существует (хотя и не играет свою оригинальную роль).

Обновление

Я тестировал то же самое с JDK 9-ea + 148, и кажется, что _equalsC intrinsic делает очень небольшую разницу в производительности.

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.

Ответ 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 для сравнения. Но независимо от того, почему это является неотъемлемой частью, это может быть причиной разницы в производительности.

Ответ 3

Потому что для символов SSE3 и 4.1/4.2 очень хороши при проверке изменения состояния. Сгенерированный JVM код для кода char более настраивается, потому что то, что Java широко используется в веб-приложениях и т.д. Java ужасно оптимизирует для других видов данных. Это просто природа зверя.

Такое же поведение наблюдается и в Scala и GoSu. Основная часть информации в пути в эти дни находится в текстовой форме, поэтому, если вы не измените свою JVM, она настроена на текст. И, как заметил Марко, это внутренняя функция 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.