Руководство по ложному обмену и @Утверждал

Автор оригинала: Ali Dehghani.

1. Обзор

В этой статье мы увидим, как иногда ложное совместное использование может обернуть многопоточность против нас.

Сначала мы немного поговорим о теории кэширования и пространственной локальности. Затем мы перепишем утилиту LongAdder concurrent и сравним ее с реализацией java.util.concurrent . На протяжении всей статьи мы будем использовать результаты тестов на разных уровнях, чтобы исследовать эффект ложного обмена.

Часть статьи, связанная с Java, сильно зависит от расположения объектов в памяти. Поскольку эти детали компоновки не являются частью спецификации JVM и оставлены на усмотрение разработчика , мы сосредоточимся только на одной конкретной реализации JVM: JVM HotSpot. Мы также можем использовать термины JVM и HotSpot JVM взаимозаменяемо на протяжении всей статьи.

2. Строка кэша и согласованность

Процессоры используют разные уровни кэширования — когда процессор считывает значение из основной памяти, он может кэшировать это значение для повышения производительности.

Как оказалось, большинство современных процессоров кэшируют не только запрошенное значение, но и еще несколько близлежащих значений . Эта оптимизация основана на идее пространственной локальности и может значительно повысить общую производительность приложений. Проще говоря, кэши процессора работают в терминах строк кэша, а не отдельных кэшируемых значений.

Когда несколько процессоров работают в одной или соседних ячейках памяти, они могут в конечном итоге использовать одну и ту же строку кэша . В таких ситуациях важно, чтобы эти перекрывающиеся кэши в разных ядрах согласовывались друг с другом. Акт поддержания такой согласованности называется согласованностью кэша.

Существует довольно много протоколов для поддержания согласованности кэша между ядрами процессора. В этой статье мы поговорим о протоколе MESI.

2.1. Протокол MESI

В протоколе MESI каждая строка кэша может находиться в одном из этих четырех различных состояний: Измененном, Исключительном, Общем или Недопустимом. Всемирный МЕССИ – это аббревиатура этих государств.

Чтобы лучше понять, как работает этот протокол, давайте рассмотрим пример. Предположим, что два ядра будут считывать данные из соседних ячеек памяти:

Ядро A считывает значение a из основной памяти. Как показано выше, это ядро извлекает еще несколько значений из памяти и сохраняет их в строке кэша. Затем он помечает эту строку кэша как exclusive , поскольку ядро A является единственным ядром, работающим в этой строке кэша . Отныне, когда это возможно, это ядро будет избегать неэффективного доступа к памяти, вместо этого считывая данные из строки кэша.

Через некоторое время core B также решает прочитать значение b из основной памяти:

Поскольку a и b находятся так близко друг к другу и находятся в одной строке кэша, оба ядра будут помечать свои строки кэша как общие .

Теперь предположим, что ядро A решает изменить значение a :

Ядро A сохраняет это изменение только в буфере хранилища и помечает строку кэша как модифицированный . Кроме того, он сообщает об этом изменении ядру B, и это ядро, в свою очередь, пометит свою строку кэша как недействительный .

Именно так разные процессоры следят за тем, чтобы их кэши были согласованы друг с другом.

3. Ложный обмен информацией

Теперь давайте посмотрим, что произойдет, когда core B решит перечитывать значение b . Поскольку это значение в последнее время не изменилось, мы можем ожидать быстрого чтения из строки кэша. Однако природа общей многопроцессорной архитектуры сводит на нет это ожидание в реальности.

Как упоминалось ранее, вся строка кэша была разделена между двумя ядрами. Поскольку строка кэша для ядра B теперь недопустима|/, она должна снова прочитать значение b из основной памяти :

Как показано выше, чтение одного и того же значения b из основной памяти-не единственная неэффективность здесь. Этот доступ к памяти заставит ядро A очистить буфер хранилища, так как ядру B необходимо получить последнее значение . После очистки и извлечения значений оба ядра снова получат последнюю версию строки кэша, помеченную в состоянии shared :

Таким образом, это накладывает промах кэша на одно ядро и ранний сброс буфера на другое, даже если два ядра не работали в одной и той же ячейке памяти . Это явление, известное как ложный общий доступ, может негативно сказаться на общей производительности, особенно когда частота пропусков кэша высока. Если быть более точным, когда эта скорость высока, процессоры будут постоянно обращаться к основной памяти вместо чтения из своих кэшей.

4. Пример: Динамическое чередование

Чтобы продемонстрировать, как ложное совместное использование может повлиять на пропускную способность или задержку приложений, мы собираемся обмануть в этом разделе. Давайте определим два пустых класса:

abstract class Striped64 extends Number {}
public class LongAdder extends Striped64 implements Serializable {}

Конечно, пустые классы не так уж полезны, поэтому давайте скопируем в них некоторую логику.

Для нашего класса Striped64 мы можем скопировать все из класса java.util.concurrent.atomic.Striped64 | и вставить его в наш класс. Пожалуйста, не забудьте также скопировать инструкции import . Кроме того, при использовании Java 8 мы должны обязательно заменить любой вызов метода sun.misc.Unsafe.getUnsafe() на пользовательский:

private static Unsafe getUnsafe() {
    try {
        Field field = Unsafe.class.getDeclaredField("theUnsafe");
        field.setAccessible(true);

        return (Unsafe) field.get(null);
    } catch (Exception e) {
        throw new RuntimeException(e);
    }
}

Мы не можем вызвать sun.misc.Unsafe.getUnsafe() из нашего загрузчика классов приложений, поэтому нам придется снова обмануть этот статический метод. Начиная с Java 9 , однако та же логика реализована с использованием VarHandles , поэтому нам не нужно будет делать там ничего особенного , и достаточно будет просто скопировать-вставить.

Для класса LongAdder давайте скопируем все из java.util.concurrent.atomic.LongAdder класс и вставьте его в наш. Опять же, мы также должны скопировать операторы import .

Теперь давайте сравним эти два класса друг с другом: наш пользовательский LongAdder и java.util.concurrent.atomic.Давно.

4.1. Контрольный показатель

Чтобы сравнить эти классы друг с другом, давайте напишем простой тест JMH:

@State(Scope.Benchmark)
public class FalseSharing {

    private java.util.concurrent.atomic.LongAdder builtin = new java.util.concurrent.atomic.LongAdder();
    private LongAdder custom = new LongAdder();

    @Benchmark
    public void builtin() {
        builtin.increment();
    }

    @Benchmark
    public void custom() {
        custom.increment();
    }
}

Если мы запустим этот тест с двумя вилками и 16 потоками в режиме тестирования пропускной способности (эквивалент передачи “ – -bm thrpt-f 2-t 16″ аргументов), то JMH выведет эти статистические данные:

Benchmark              Mode  Cnt          Score          Error  Units
FalseSharing.builtin  thrpt   40  523964013.730 ± 10617539.010  ops/s
FalseSharing.custom   thrpt   40  112940117.197 ±  9921707.098  ops/s

Результат вообще не имеет смысла. Встроенная реализация JDK затмевает наше копируемое решение почти на 360% большей пропускной способностью .

Давайте посмотрим на разницу между задержками:

Benchmark             Mode  Cnt   Score   Error  Units
FalseSharing.builtin  avgt   40  28.396 ± 0.357  ns/op
FalseSharing.custom   avgt   40  51.595 ± 0.663  ns/op

Как показано выше, встроенное решение также имеет лучшие характеристики задержки.

Чтобы лучше понять, что такого особенного в этих, казалось бы, идентичных реализациях, давайте рассмотрим некоторые низкоуровневые счетчики мониторинга производительности.

5. Perf События

Для измерения низкоуровневых событий процессора, таких как циклы, циклы остановки, инструкции за цикл, загрузка/пропуски кэша или загрузка/хранение памяти, мы можем запрограммировать специальные аппаратные регистры на процессорах.

Как оказалось, такие инструменты, как perf или eBPF , уже используют этот подход для предоставления полезных показателей. Начиная с Linux 2.6.31, perf является стандартным профилировщиком Linux, способным предоставлять полезные счетчики мониторинга производительности или PMCS.

Таким образом, мы можем использовать события perf, чтобы увидеть, что происходит на уровне процессора при запуске каждого из этих двух тестов. Например, если мы запустим:

perf stat -d java -jar benchmarks.jar -f 2 -t 16 --bm thrpt custom

Perf заставит JMH запустить тесты с копируемым решением и распечатать статистику:

161657.133662      task-clock (msec)         #    3.951 CPUs utilized
         9321      context-switches          #    0.058 K/sec
          185      cpu-migrations            #    0.001 K/sec
        20514      page-faults               #    0.127 K/sec
            0      cycles                    #    0.000 GHz
 219476182640      instructions
  44787498110      branches                  #  277.052 M/sec
     37831175      branch-misses             #    0.08% of all branches
  91534635176      L1-dcache-loads           #  566.227 M/sec
   1036004767      L1-dcache-load-misses     #    1.13% of all L1-dcache hits

Поле L1-dcache-load-misses представляет количество пропусков кэша для кэша данных L1. Как показано выше, это решение столкнулось с примерно одним миллиардом промахов кэша (1 036 004 767, если быть точным). Если мы соберем ту же статистику для встроенного подхода:

161742.243922      task-clock (msec)         #    3.955 CPUs utilized
         9041      context-switches          #    0.056 K/sec
          220      cpu-migrations            #    0.001 K/sec
        21678      page-faults               #    0.134 K/sec
            0      cycles                    #    0.000 GHz
 692586696913      instructions
 138097405127      branches                  #  853.812 M/sec
     39010267      branch-misses             #    0.03% of all branches
 291832840178      L1-dcache-loads           # 1804.308 M/sec
    120239626      L1-dcache-load-misses     #    0.04% of all L1-dcache hits

Мы увидим, что он сталкивается с гораздо меньшим количеством промахов кэша (120 239 626 ~ 120 миллионов) по сравнению с пользовательским подходом. Таким образом, большое количество пропусков кэша может быть причиной такой разницы в производительности.

Давайте копнем еще глубже во внутреннее представление LongAdder , чтобы найти фактического виновника.

6. Пересмотр Динамического Чередования

Файл java.util.concurrent.atomic.LongAdder – это реализация атомарного счетчика с высокой пропускной способностью. Вместо того, чтобы просто использовать один счетчик, он использует их массив, чтобы распределить конкуренцию в памяти между ними. Таким образом, он будет превосходить простые атомарные, такие как AtomicLong в сильно конкурирующих приложениях.

Класс Striped64 отвечает за это распределение конфликтов памяти, и именно так этот класс реализует эти массивы счетчиков :

@jdk.internal.vm.annotation.Contended 
static final class Cell {
    volatile long value;
    // omitted
}
transient volatile Cell[] cells;

Каждая ячейка | инкапсулирует данные для каждого счетчика. Эта реализация позволяет различным потокам обновлять разные ячейки памяти. Поскольку мы используем массив (то есть полосы) состояний, эта идея называется динамическим чередованием. Интересно, что Striped64 назван в честь этой идеи и того факта, что он работает с 64-битными типами данных.

В любом случае, JVM может размещать эти счетчики рядом друг с другом в куче. То есть несколько таких счетчиков будут находиться в одной строке кэша. Поэтому обновление одного счетчика может привести к аннулированию кэша для соседних счетчиков .

Ключевой вывод здесь заключается в том, что наивная реализация динамического чередования будет страдать от ложного совместного использования. Однако, добавив достаточное количество отступов вокруг каждого счетчика, мы можем убедиться, что каждый из них находится в своей строке кэша, тем самым предотвращая ложное совместное использование :

Как оказалось, @ jdk.internal.vm.аннотация.Утвержденная аннотация отвечает за добавление этого дополнения.

Вопрос только в том, почему эта аннотация не сработала в копируемой реализации?

7. Познакомьтесь с @Contended

Java 8 представила sun.misc.Оспариваемая аннотация (Java 9 переупаковала ее в пакет jdk.internal.vm.annotation ) для предотвращения ложного совместного использования .

В принципе, когда мы аннотируем поле этой аннотацией, JVM HotSpot добавит некоторые отступы вокруг аннотированного поля . Таким образом, он может убедиться, что поле находится в своей собственной строке кэша. Более того, если мы аннотируем весь класс этой аннотацией, JVM Hotspot добавит одно и то же заполнение перед всеми полями .

Аннотация @Contended предназначена для внутреннего использования самим JDK. Таким образом, по умолчанию это не влияет на расположение памяти не внутренних объектов . Вот почему наш сумматор с копированием не работает так же хорошо, как встроенный.

Чтобы удалить это внутреннее ограничение , мы можем использовать флаг -XX:- RestrictContended tuning при запуске бенчмарка:

Benchmark              Mode  Cnt          Score          Error  Units
FalseSharing.builtin  thrpt   40  541148225.959 ± 18336783.899  ops/s
FalseSharing.custom   thrpt   40  546022431.969 ± 16406252.364  ops/s

Как показано выше, теперь результаты бенчмарка намного ближе, и разница, вероятно, заключается в небольшом шуме.

7.1. Размер заполнения

По умолчанию аннотация @Contended добавляет 128 байт заполнения. Это в основном потому, что размер строки кэша во многих современных процессорах составляет около 64/128 байт .

Это значение, однако, настраивается с помощью флага -XX:ContendedPaddingWidth |/tuning. На момент написания этой статьи этот флаг принимает только значения от 0 до 8192.

7.2. Отключение @Contended

Также можно отключить эффект @Contended с помощью настройки -XX:-Enable Contended |. Это может оказаться полезным, когда память находится на высоком уровне, и мы можем позволить себе потерять немного (а иногда и много) производительности.

7.3. Примеры использования

После его первого выпуска аннотация @Contended довольно широко использовалась для предотвращения ложного совместного использования во внутренних структурах данных JDK. Вот несколько примечательных примеров таких реализаций:

• Класс Striped64 для реализации счетчиков и аккумуляторов с высокой пропускной способностью
• Класс Thread для облегчения реализации эффективных генераторов случайных чисел
• ForkJoinPool очередь на кражу работы
• Реализация ConcurrentHashMap
• двойная структура данных используется в обменнике классе

8. Заключение

В этой статье мы рассмотрели, как иногда ложное совместное использование может привести к контрпродуктивным последствиям для производительности многопоточных приложений.

Чтобы сделать вопросы более конкретными, мы сравнили реализацию LongAdder в Java с ее копией и использовали ее результаты в качестве отправной точки для наших исследований производительности.

Кроме того, мы использовали инструмент perf для сбора некоторых статистических данных о показателях производительности запущенного приложения в Linux. Чтобы увидеть больше примеров perf, настоятельно рекомендуется прочитать блог Брандена Грега . Кроме того, eBPF , доступный с ядра Linux версии 4.4 , также может быть полезен во многих сценариях трассировки и профилирования.

Как обычно, все примеры доступны на GitHub .