1. Обзор
В этой статье мы увидим, как иногда ложное совместное использование может обернуть многопоточность против нас.
Во-первых, мы собираемся начать с теории кэширования и пространственной локальности. Затем мы перепишем параллельную утилиту LongAdder и сравним ее с реализацией java.util.concurrent . На протяжении всей статьи мы будем использовать результаты тестов на разных уровнях, чтобы исследовать влияние ложного обмена.
Часть статьи, связанная с Java, сильно зависит от расположения объектов в памяти. Поскольку эти детали макета не являются частью спецификации JVM и оставлены на усмотрение разработчика , мы сосредоточимся только на одной конкретной реализации JVM: HotSpot JVM. Мы также можем использовать термины JVM и HotSpot JVM взаимозаменяемо на протяжении всей статьи.
2. Кэш-линия и когерентность
Процессоры используют разные уровни кэширования — когда процессор считывает значение из основной памяти, он может кэшировать это значение для повышения производительности.
Как оказалось, большинство современных процессоров кэшируют не только запрошенное значение, но и еще несколько ближайших значений . Эта оптимизация основана на идее пространственной локальности и может значительно повысить общую производительность приложений. Проще говоря, кэши процессора работают с строками кэша, а не с отдельными кэшируемыми значениями.
Когда несколько процессоров работают с одними и теми же или соседними участками памяти, они могут в конечном итоге совместно использовать одну и ту же строку кэша . В таких ситуациях важно, чтобы эти перекрывающиеся кэши в разных ядрах были согласованы друг с другом. Акт поддержания такой согласованности называется когерентностью кэша.
Существует довольно много протоколов для поддержания когерентности кеша между ядрами ЦП. В этой статье мы поговорим о протоколе MESI.
2.1. Протокол МЭСИ
В протоколе MESI каждая строка кэша может находиться в одном из следующих четырех различных состояний: Modified, Exclusive, Shared или Invalid. Слово MESI является аббревиатурой этих государств.
Чтобы лучше понять, как работает этот протокол, давайте рассмотрим пример. Предположим, что два ядра собираются читать из соседних областей памяти:
Ядро A считывает значение a из основной памяти. Как показано выше, это ядро извлекает из памяти еще несколько значений и сохраняет их в строке кэша. Затем он помечает эту строку кэша как эксклюзивную , поскольку ядро A является единственным ядром, работающим с этой строкой кэша . Отныне, когда это возможно, это ядро будет избегать неэффективного доступа к памяти, вместо этого читая из строки кэша.
Через некоторое время ядро B также решает прочитать значение b из основной памяти:
Поскольку a и b расположены так близко друг к другу и находятся в одной и той же строке кэша, оба ядра будут помечать свои строки кэша как общие .
Теперь предположим, что ядро A решает изменить значение a :
Ядро A сохраняет это изменение только в своем буфере хранения и помечает свою строку кэша как измененную . Кроме того, оно сообщает об этом изменении ядру B, а это ядро, в свою очередь, помечает свою строку кэша как недействительную .
Вот как разные процессоры обеспечивают согласованность своих кэшей друг с другом.
3. Ложный обмен
Теперь давайте посмотрим, что произойдет, когда ядро B решит перечитать значение b . Поскольку это значение в последнее время не менялось, мы можем ожидать быстрого чтения из строки кэша. Однако природа разделяемой многопроцессорной архитектуры на самом деле опровергает это ожидание.
Как упоминалось ранее, вся строка кэша была разделена между двумя ядрами. Поскольку строка кэша для ядра B теперь недействительна , она должна снова прочитать значение b из основной памяти :
Как показано выше, чтение одного и того же значения b из основной памяти здесь не единственная неэффективность. Этот доступ к памяти заставит ядро A сбросить буфер хранения, так как ядру B необходимо получить самое последнее значение . После сброса и извлечения значений оба ядра получат последнюю версию строки кэша, снова помеченную в общем состоянии:
Таким образом, это приводит к промаху кеша для одного ядра и ранней очистке буфера для другого, даже если два ядра не работали в одной и той же ячейке памяти . Это явление, известное как ложное совместное использование, может отрицательно сказаться на общей производительности, особенно при высоком уровне промахов кэша. Чтобы быть более конкретным, когда эта скорость высока, процессоры будут постоянно обращаться к основной памяти, а не читать из своих кешей.
4. Пример: динамическое чередование
Чтобы продемонстрировать, как ложное совместное использование может повлиять на пропускную способность или задержку приложений, мы собираемся обмануть в этом разделе. Определим два пустых класса:
abstract class Striped64 extends Number {}
public class LongAdder extends Striped64 implements Serializable {}
Конечно, пустые классы не так уж полезны, поэтому давайте скопируем в них немного логики.
Для нашего класса Striped64 мы можем скопировать все из класса java.util.concurrent.atomic.Striped64 и вставить его в наш класс. Не забудьте также скопировать операторы импорта . Кроме того, при использовании 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 и вставим в наш. Опять же, мы должны скопировать операторы импорта .
Теперь давайте сравним эти два класса друг с другом: наш собственный LongAdder и java.util.concurrent.atomic.LongAdder.
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 или eBPF , уже используют этот подход для предоставления полезных показателей. Начиная с Linux 2.6.31, perf является стандартным профилировщиком Linux, способным отображать полезные счетчики мониторинга производительности или PMC.
Таким образом, мы можем использовать события производительности, чтобы увидеть, что происходит на уровне ЦП при запуске каждого из этих двух тестов. Например, если мы запустим:
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.annotation.Contended .
Вопрос только в том, почему эта аннотация не работала в скопипастенной реализации?
7. Познакомьтесь с @Contended
В Java 8 появилась аннотация sun.misc.Contended (в Java 9 она была переупакована в пакет jdk.internal.vm.annotation ) для предотвращения ложного совместного использования .
По сути, когда мы аннотируем поле этой аннотацией, JVM HotSpot добавит некоторые отступы вокруг аннотированного поля . Таким образом, он может убедиться, что поле находится в своей собственной строке кэша. Более того, если мы аннотируем этой аннотацией целый класс, JVM HotSopt добавит один и тот же отступ перед всеми полями .
Аннотация @Contended предназначена для внутреннего использования самим JDK. Таким образом, по умолчанию это не влияет на расположение невнутренних объектов в памяти . Вот почему наш скопипастенный сумматор не работает так же хорошо, как встроенный.
Чтобы снять это внутреннее ограничение , мы можем использовать флаг настройки -XX:-RestrictContended при повторном запуске теста:
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 . На момент написания этой статьи этот флаг принимает значения только от 0 до 8192.
7.2. Отключение @Contended
Также можно отключить эффект @Contended с помощью настройки -XX:-EnableContended . Это может оказаться полезным, когда память находится в большом почете, и мы можем позволить себе немного (а иногда и много) потерять производительность.
7.3. Сценарии использования
После своего первого выпуска аннотация @Contended довольно широко использовалась для предотвращения ложного совместного использования во внутренних структурах данных JDK. Вот несколько ярких примеров таких реализаций:
- Класс
Striped64для реализации счетчиков и накопителей с высокой пропускной способностью . - Класс
Threadдля облегчения реализации эффективных генераторов случайных чисел . - Очередь кражи работы
ForkJoinPool - Реализация
ConcurrentHashMap_ - Двойная структура данных, используемая в классе
Exchanger
8. Заключение
В этой статье мы увидели, как иногда ложное совместное использование может привести к обратному эффекту на производительность многопоточных приложений.
Чтобы сделать ситуацию более конкретной, мы сравнили реализацию LongAdder на Java с ее копией и использовали ее результаты в качестве отправной точки для наших исследований производительности.
Кроме того, мы использовали инструмент perf для сбора статистики о показателях производительности работающего приложения в Linux. Чтобы увидеть больше примеров производительности , настоятельно рекомендуется прочитать блог Branden Greg . Более того, eBPF , доступный с версии ядра Linux 4.4 , также может быть полезен во многих сценариях трассировки и профилирования.
Как обычно, все примеры доступны на GitHub .