Cache coherency #3: false sharing

Я долго-долго тупил, но наконец-то решился продолжить серию про кэш-когерентность. Сами базовые протоколы кэш-когерентности мы разобрали — теперь можно посмотреть на всякие любопытные вещи, которые происходят за кулисами, пока мы на сцене делаем что-нибудь совсем обычное.

False sharing

...Или ложное разделение. По-правде, не очень понятно, почему именно ложное — оно самое что ни на есть настоящее, только неожиданное. Что такое true sharing? — Это когда у нас есть ячейка памяти, используемая одновременно более чем одним потоком. В предыдущих статьях я уже рассказывал, что конкурентный доступ на чтение протоколы когерентности разруливают без особого труда, а вот конкурирующие чтение и запись, и особенно запись и запись заставляют их попотеть — здесь все понятно. А false sharing это когда ячейки памяти разные, но физически попадают на один и тот же cache line. С точки зрения программиста — никакого разделения данных нет, никакого конкурирующего доступа тоже. А с точки зрения подсистемы памяти каждый cache line — это одна ячейка, и операции доступа к разным частям одной строки кэша из разных ядер конкурируют друг с другом за эту ячейку-строку. И неожиданно оказывается, что обычная запись в какую-то локальную (казалось бы) переменную стоит в несколько раз дороже, чем должна была бы:

int threadId = 0, 1, 2, ... THREADS_COUNT;
int distance = 1..8; 
long[] area = new long[THREADS_COUNT*distance];

for(int i=0...Inf){
   area[threadId*distance] = i;
}

(Готовый к исполнению код здесь). Если увеличивать distance, то можно наблюдать, как время на выполнение цикла уменьшается, вплоть до distance=8 — для интелловских архитектур, где cache line 64 байта. (Строго говоря, нужно еще убедиться, что все потоки сели на разные физические ядра, но как правило, в случае незагруженной машины системный планировщик их сам так и раскидает)

Вообще, про false sharing не писал уже только ленивый. Я лично эту тему мусолил аж 4 раза, даже тэг для этого специальный завел. Поэтому я здесь хочу остановиться на другом вопросе, который мне как-то задали в комментариях: если все так легко может стать так плохо, почему это редко когда заметно? (Есть, конечно, вариант, что не замечают потому что и не смотрят — но это недостаточно сексуальный вариант)

У false sharing есть два ощутимых эффекта: увеличение в разы времени выполнения конкретной операции записи (memory latency), и увеличение нагрузки на шину. Чтобы заметить увеличение нагрузки на шину нужно либо специально ее мониторить, либо уже использовать шину близко к режиму насыщения. Но интелловский InterConnect имеет пропускную способность что-то вроде 20Гб/с в каждую сторону — а это 20 миллионов килобайтных сообщений в секунду (в нереальном случае 100% КПД). Не то, чтобы это было недостижимо круто, но не каждая птица долетит до середины Днепракаждое приложение подходит хотя бы близко к тому, чтобы насытить шину.

А что насчет memory latency? Ну, проблема медленной памяти перед разработчиками процессоров стоит уже лет 15, за это время было придумано масса трюков, позволяющих ее как-то обойти. Часть из них — те, что про введение иерархии кэшей — в случае с false sharing не помогут, потому что они сами и являются причиной. Но на уровне процессора остается еще пара тузов в рукаве, связанных с асинхронным выполнением операций с памятью. Например, современные процессоры содержат блок префетчинга, который может предсказать доступ к памяти до того, как исполнение дойдет до соответствующей инструкции, и отправить запрос на упреждающее чтение нужного блока в кэш. Другой пример: инструкции записи тоже обычно не ждут, пока запись фактически будет выполнена — команда на запись просто сохраняется в т.н. store buffer-е, и исполнение идет дальше, а команды из буфера спускаются контроллеру памяти в асинхронном режиме.

В итоге получается, что процессор старается не ждать, пока контроллер памяти тупитвертится как белка в колесе, пытаясь разрулить конфликтующие запросы. Он, насколько это возможно, будет обрабатывать другие инструкции, выполнение которых не зависит от результата "застрявшей" операции с памятью. Поэтому, если кроме конфликтующих доступов к памяти ваш код делает еще достаточно много каких-то локальных (неконфликтующих) операций, то процессор сумеет (возможно сумеет) "замаскировать" среди них неожиданное удорожание доступа к какой-то конкретной ячейке памяти.

И отсюда можно попробовать порасуждать на тему, в каких случаях false sharing имеет наибольшую вероятность стать заметным.

Во-первых, когда нам важно именно время выполнения конкретной (небольшой) операции (latency, response time), а не пропускная способность в целом (throughput). Если наша операция содержит всего-то пару сотен инструкций, и несколько обращений к памяти, то заметное удорожание даже одного из этих обращений все-таки будет заметно. Процессору просто не за чем будет спрятать замедлившуюся операцию. Да, он может параллельно начать выполнять инструкции хоть из другого потока (через hyper threading), тем самым удерживая на уровне общую пропускную способность — но время выполнения конкретной операции от этого не уменьшится. Мы можем получить такую картину: система по-прежнему выполняет N операций в секунду, только время одной операции выросло с 1мкс до 2мкс. Поскольку далеко не каждого волнует время выполнение конкретной операции (особенно, когда масштаб этого времени — микросекунды), то на этой стадии false sharing часто остается просто незамеченным.

Дальше идут ситуации, когда операции с false sharing составляют заметную долю всех операций (по крайней мере, на критическом маршруте). Это как раз пример выше. Почему false sharing там заметен? Потому что там, кроме самой записи, только обвязка цикла, которая едва тянет на пару тактов. И одна-единственная запись, которая contended (счетчик цикла скорее всего будет сидеть в регистре). Даже если запись идет в L1 (~5ns) — она здесь будет доминирующей, и никакие трюки этого не замаскируют, потому что маскировать нечем. И если запись станет в разы дороже — это будет просто бросаться в глаза.

Ну и последний очевидный вариант — это когда у вас шина памяти уже близка к насыщению, и тут еще добавляется false sharing, и все становится грустно.

Т.е. получается, что в первую очередь false sharing беспокоит тех, кто разрабатывает latency-critical системы, и уж во-вторую — тех, кто разрабатывает очень high throughput, где-то близко к пиковой производительности железа.

P.S. Есть у меня еще такая любопытна идея: кажется, что чем мягче аппаратная модель памяти, тем больше у процессора возможностей "прятать" memory latency. Т.е. и прятать false sharing у него тоже больше возможностей. Однако сравнивать разные процессоры сложновато — они обычно отличаются слишком много чем, не только моделью памяти (да и где бы их все взять для тестов-то). Но можно ужесточить аппаратную модель памяти программно — расставляя барьеры памяти. Если взять тот пример, выше, и вместо обычной записи в ячейку массива делать volatile store (придется заменить массив на AtomicIntegerArray, или дергать Unsafe.putIntVolatile) — то сопутствующий lock xadd скорее всего приведет к принудительному сбросу store buffer-а. А значит не будет возможности отложить запись на "попозже", ее придется делать синхронно. Кажется, что это сделать false sharing еще более заметным.

Еще интереснее будет проверить это для Disruptor-а. На Java One меня спрашивали, почему padding в моих экспериментах никак себя не проявил — вот я сейчас думаю, что причина может быть как раз в том, что я экспериментировал с padding после того, как заменил volatile store для курсоров на lazySet (что эффект от оптимизаций некоммутативен — это не новость). Будет интересно, как появится возможность, проверить, что получится если сделать наоборот: вернуть volatile store, и поиграться с padding.

P.P.S. Вообще-то, эта статья планировалась как продолжение цикла про cache coherency. И про false sharing задумывалось как вступление и разминка. Но я что-то увлекся, и false sharing вылез на место главного героя, не оставив места запланированным атомикам. Ну я и подумал — пусть остается как есть, а атомики получат свою главную роль чуть позже :)