14 сентября 2011 г.

False sharing

Размышляю на досуге про false sharing в его простейшем смысле -- про данные, принадлежащие одной строке кэша. Обычно предлагается с этим бороться введением полей (padding) -- добить объект фиктивными полями типа, скажем, long до обычного размера строки в 64 байта. Проблем с этим методом -- не оберешься. Даже если забыть на минутку про то, насколько такая вещь как padding (тем более -- "в рукопашную") не вписывается в концепцию java как высокоуровневого языка, остается еще масса вопросов:

Переносимость: cache-line имеет разный размер на разных процессорах -- от 32 до 128 байт. Можно, конечно, закладываться на максимальный размер, но тратить 128 байт на каждую конкурентную переменную может оказаться многовато. Дело не в том, что это много само по себе -- память нынче дешевая. Дело в том, что это же априори горячие в кэше данные. Т.е. это не 128 байт из основной памяти, которой десятки гигабайт, это 128 байт из кэша первого уровня -- который все еще весьма невелик. Но даже если и так -- кто гарантирует, что завтра не появится процессор со строкой 256 байт? Если приблизиться к реалиям -- по факту везде, где я встречал padding он сделан из расчета на строку в 64 байта. То есть даже на существующих процессорах со строкой кэша длиннее этой -- производительность резко просядет. А ведь я еще нигде не видел, чтобы размер полей можно было хоть как-то "настраивать" -- да и сделать это довольно непросто.

Надежность: padding нынче делается просто набором неиспользуемых примитивных полей. Еще когда я впервые увидел этот трюк где-то в недрах JDK у меня возник вопрос -- а почему собственно JIT не выкинет эти поля нафиг? Ведь даже моя IDE очевидно мне подчеркивала их как неиспользуемые, уж JIT-то должен был бы это увидеть. И если он на данный момент этого не делает -- что будет, если в очередном обновлении он таки научится? Собственно, похоже это произошло: Martin Thompson, один из авторов disruptor уже жалуется, что используемый ими ранее простой padding в очередном обновлении Java 7 работать перестал. Чтобы таки надурить компилятор им пришлось наследовать PaddedAtomicLong от AtomicLong, и делать padding через 6 штук public volatile long (Кстати, почему их 6 а не 7 -- для меня загадка. Могу только предположить, что Мартин заложился на то, что еще 8 байт уйдет на object header. Надо ли говорить, что закладываться на такие детали внутренней реализации JVM не очень надежно?). Пока что это работает -- непонятно только, насколько долго будет.

Или вот такой вопрос -- ну хорошо, добили мы свой объект полями до размера строки. Но ведь мы не можем (из java) гарантировать, по какому адресу будет расположен наш объект. Нам ведь никто не гарантирует, что в памяти наш объект будет выравнен по границе строк. Реально он может оказаться половиной на одной строке, половиной -- на второй. Да, мы можем быть уверены, что если у нас есть два точно таких же объекта, то их одинаковые поля (в предположении что они всегда идут в одном и том же порядке) точно на одной строке не окажутся. То есть, если взять этот самый PaddedAtomicLong -- покуда мы реально используем только "первый" из составляющих его 7 long-ов , мы можем быть уверены, что false sharing это не про нас. Но если бы мы хотели использовать уже 2 его long-а ("первый" и "второй") -- отсутствие false sharing уже не гарантируется, поскольку "второй" может оказаться уже на следующей строке, и на этой же строке может уместиться начало уже другого PaddedAtomicLong, и наш "второй" будет конфликтовать с его "первым". Поэтому, если мы в самом деле хотим избежать false sharing здесь, нам нужен padding с обеих сторон -- и до "защищаемых" нами полей, и после них, размером заведомо больше половины строки в каждом случае.

Но даже это еще не решает проблемы окончательно, потому что у нас ведь в приложении не только одни PaddedAtomicLong-и существуют. Если мы возьмем, для примера, тот же disruptor -- есть еще и объекты сообщений, которые тоже модифицируются (потенциально) многими потоками. И вполне может так случиться, что на одной строке кэша окажется кусок от MyEvent, и начало от PaddedAtomicLong, как раз где самое важное для нас поле value и лежит. И все усилия Мартина и команды по мегаоптимизации своего dsiruptor-а пойдут прахом моментально и внезапно.

...А самое поганое здесь, на мой взгляд, это то, что сам-то disruptor пишет уже упомянутый Мартин Томпсон, который и знает много, и может себе позволить потратить недели на тонкую оптимизацию и выяснение причин каких-либо тормозов. А вот MyEvent будет создавать обычный прикладной программист, у которого скорее всего ни квалификации такой нет, ни времени на исследования. И вероятность того, что этот программист будет свои MyEvent защищать от false sharing мала.

...Но даже если он и будет это делать -- он ведь еще должен это делать таким же способом, как Мартин. Про что я говорю -- я говорю про то, что если, скажем, наш гипотетический программист Вася будет защищать свои MyEvent от false sharing с помощью двустороннего padding-а размером чуть больше полстроки (как я описывал выше) -- то все равно он не избежит кары небесной, ибо Мартин свои объекты защищает односторонним padding-ом. Легко понять, что в этом случае на одной строке не могут оказаться используемые поля от двух разных MyEvent, точно так же как и от двух разных PaddedAtomicLong, но могут оказаться используемые поля от одного MyEvent и другого PaddedAtomicLong. По-сути получается, что страдает инкапсуляция.

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

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

Идеальный вариант, разумеется, чтобы JIT сам определял, какие объекты испытывают наибольшее давление false sharing, и прямо в рантайме перемещал их в памяти так, чтобы это давление уменьшить. Мне этот вариант не очень нравится просто потому, что непонятно, за что тогда будут платить деньги мне вряд ли это будет реализовано скоро, и еще более вряд ли скоро и качественно.

Более реальный вариант: хочется стандартную аннотацию типа @PreventFalseSharing (хотелось бы для нее какое-нибудь название, больше отражающее идею, нежели реализацию), особым образом интерпретируемую JIT-ом -- он для таких объектов использует отдельный аллокатор, как минимум размещающий их строго по границам строк, и не позволяющий никому более использовать место, остающееся до целого количества строк (хотя это уже и не обязательно -- первой части уже будет достаточно, чтобы такие объекты гарантированно не конфликтовали хотя бы между собой). Сюда же можно добавить и включение для ссылочных полей таких объектов оптимизацию write barrier-а в виде test-and-mark вместо только mark. Ну и так далее -- думаю, там еще много чего можно добавить.

Причем на первое время такую штуку можно сделать вообще отдельно от Oracle -- сделать byte-code preprocessor, который при загрузке классов ищет соответствующую аннотацию, и модифицирует байт-код соответствующих классов, добавляя фиктивные поля. Можно даже сделать автоматическое определение размера строки кэша -- через нативный вызов, например. Потом можно прикрутить обработку к javac -- опять же под worst-case, но хотя бы исходный код не будет загрязнен всякими непонятными полями. И уж на последнем этапе можно перевести обработку на уровень JVM/JIT.

Вот такие вот эротические фантазии меня последнее время посещают.

UPD: По сообщениям из заслуживающих доверия источников, в казематах оракла суровыми инженерами сана, там заточенными, обсуждается аннотация @Contended, реализующая что-то вроде варианта 2. Так что не пройдет и 10 лет, как, возможно, мы узрим свет в окошке...

13 комментариев:

  1. А мы тут как раз с Дагом и прочими ВМщиками и обсуждаем аннотацию @Contended, чтобы она подсказывала JVM, что пора объект поместить в свой собственный кэш-лайн. Работаем ;)

    ОтветитьУдалить
  2. > Надежность: padding нынче делается просто набором неиспользуемых примитивных полей. Еще когда я впервые увидел этот трюк где-то в недрах JDK у меня возник вопрос -- а почему собственно JIT не выкинет эти поля нафиг?

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

    ОтветитьУдалить
  3. Правда? Это было бы очень круто -- уж только ленивый не пишет сейчас про false sharing, а защита от него все еще через жопу. Уж если делать джаву lingua franca для conrurrency, то такие вещи просто необходимы

    ОтветитьУдалить
  4. >Фокус не выйдет.

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

    ОтветитьУдалить
  5. > Правда? Это было бы очень круто -- уж только ленивый не пишет сейчас про false sharing, а защита от него все еще через жопу.

    Дык. Думаешь, Мартин единственный такой умный? Про такой паддинг известно уже давно:

    http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/jsr166e/Striped64.java?view=markup

    Дело всё-таки в том, что JVM переупорядочивает поля, чтобы их по-плотнее упаковать, не нарушая alignment'а. Поля одинакового типа с одинаковыми модификаторами оно переупорядочивать скорее всего не будет, ибо сортировщик полей там более-менее устойчивый. Пока.

    ОтветитьУдалить
  6. > Вроде бы ничего такого, чем JIT не мог бы справиться.

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

    ОтветитьУдалить
  7. >Дык. Думаешь, Мартин единственный такой умный? Про такой паддинг известно уже давно:

    Какой -- такой? Если ты имеешь в виду паддинг вообще как защиту от false sharing -- так это вроде еще с 1.5 в исходниках j.u.c можно увидеть. А если конкретный способ -- так у мартина другой паддинг, односторонний (p1-p6), здесь же я вижу как раз двусторонний (p1-p6, q1-q6). Ну только вопрос же в том, что ни тот ни тот к другому размеру строки не адаптируются. Правда я с Striped64 еще толком не разобрался, вроде там видна какая-то адаптация по профилю спиннига...

    >Да, действительно. Все эти случаи покрываются деоптом по доступу к полю.

    Ну собственно не очень понятно _зачем_ делать такую оптимизацию -- все-таки 99% что если человек оставил лишнее поле в классе, то оно ему зачем-то нужно, и лишь 1% что это он про него просто забыл (да и то -- лишь в ничтожном проценте случаев это будет хоть как-то заметно в конечном приложении) -- т.е. это кажется просто не стоящим свеч. Но судя по тому, что у Мартина перестал работать обычный паддинг -- какой-то вариант такой оптимизации все-таки реализован?

    ОтветитьУдалить
  8. > Ну собственно не очень понятно _зачем_ делать такую оптимизацию -- все-таки 99% что если человек оставил лишнее поле в классе, то оно ему зачем-то нужно, и лишь 1% что это он про него просто забыл.

    Ну, это не совсем правда. Частенько в полях лежат кеши, типа String.hashcode, и зачем лишний раз целых 32/64 бита на объект дополнительно держать?

    ОтветитьУдалить
  9. Односторонний паддинг не очень-то помогает, когда ты не контролируешь размещение объектов в памяти.

    Вот два кеш-лайна, по 64 байта. Одна чёрточка -- это long. "WWWW" -- кусок чужого объекта, потенциально апдейтящийся.

    |--------|--------|

    вот удачный односторонний паддинг:
    |h******x|----WWWW|

    а вот неудачный:

    |---h****|**x-WWWW|

    С двухсторонним куда лучше:

    |h*******|x*******|

    |----h***|****x***|****WWWW|

    Наверняка же ж Мартин попал на случай, когда рядом с ним оказался бешено апдейтящися объект, и это был НЕ PaddedAtomicLong :)

    ОтветитьУдалить
  10. >Ну, это не совсем правда. Частенько в полях лежат кеши, типа String.hashcode, и зачем лишний раз целых 32/64 бита на объект дополнительно держать?

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

    ОтветитьУдалить
  11. >Односторонний паддинг не очень-то помогает, когда ты не контролируешь размещение объектов в памяти.

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

    >Наверняка же ж Мартин попал на случай, когда рядом с ним оказался бешено апдейтящися объект, и это был НЕ PaddedAtomicLong

    Так я не знаю, на что попадал Мартин -- это я сам придумал ситуацию, когда Мартинов дизайн паддинга не спасет его код от интерференции с чужими апдейтами :)

    ОтветитьУдалить
  12. Доброго времени суток. Читал ряд статей на Вашем блоге, очень интересно, спасибо. У меня есть меленький вопрос, который не дает мне спокойно жить. Вопрос связан с false sharing на volatile переменных.
    Есть программа, вот гист: https://gist.github.com/gitjs77/4808722b35b2e18f5b5821d29f013713

    8 лонговских volatile полей. 2 потока с псевдологикой работы с этими полями.
    Если потоки работают с полями, которые рядом - на одной кэш линии, то прослеживается false sharing.
    Если работают с переменными на разной кэш линии - быстродействие растет раза в 3-4.
    Вопрос в следующем, никак не могу связать знания про volatile с кэш линиями. volatile же подразумевает работу непосредственно с памятью, каким образом тут фигурируют кэш и кэш линии. Если будет возможность в двух словах или просто ссылку на источник. Спасибо.

    ОтветитьУдалить
    Ответы
    1. Я не уверен, что понял, в чем именно вопрос, но я попробую.

      Короткий ответ: на железе интела вы (как правило) не можете записать "непосредственно в память". Вы пишете всегда в некий композит из основной памяти и нескольких уровней кэшей, а дальше он уже сам внутри разбирается.

      Длинный ответ: volatile не подразумевает "работу непосредственно с памятью", он подразумевает определенные ограничения/гарантии на то, кто увидит записанные значения. Эти ограничения/гарантии прописаны в JMM, и я не хочу здесь повторяться с их описанием, потому что это немаленькая тема, тем более что она уже много где расписана (в том числе и у меня). Важно то, что эти гарантии ничего не говорят про "непосредственно память".

      Вместо этого говорится (если упростить и опустить детали), что такие-то чтения _увидят_ значения, записанные такими-то записями. Как именно JVM реализует это требование -- оставляется на откуп ее инженерам. Почему? Потому что это оставляет инженерам много возможностей для оптимизации, и адаптации к конкретному железу.

      На практике, если мы говорим про Intel, то у них вся подсистема памяти (кэши L1/L2/L3+RAM, взаимодействие между ними, система поддержания актуальности, MESI-протокол взаимодействия между кэшами разных ядер...) весьма сильно "спрятана" от программиста, абстрагирована за простыми инструкциями типа "записать значение в ячейку памяти по такому-то адресу". А что там под капотом делается -- в принципе, оно известно, но у программиста есть весьма ограниченное количество способов на это как-то повлиять.

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

      Тут мы и возвращаемся к volatile. Его реализация в JVM для x86 вовсе не пытается записать в основную память. То, что JVM делает -- это убеждается, что записанное значение не застряло в регистрах процессора, и его же store buffers. А вот как только значение просочилось в подсистему памяти -- дальше его путешествием по разным кэшам и шинам уже управляет железо, и интеловское железо нам гарантирует, что мы всегда прочитаем из этой ячейки памяти правильное значение.

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

      Удалить