19 июля 2013 г.

Data races is pure evil

Nondeterminism is unavoidable, but data races are pure evil (by Hans Boehm) -- любопытная статья, которая висит у меня в закладках несколько месяцев.

Ханс пишет про то, что многие люди пытаются уйти от синхронизации к data race based протоколам во имя увеличения масштабируемости (scalability). И это совершенно не оправдано — мало того, что код с гонками получается ошибочным в 9 случаях из 10, так еще и надежды на масштабируемость — это, по большей части, лишь фантазии. Ханс обращает внимание на важную вещь: синхронизация это (вообще говоря) локальная операция. То есть, в идеальном мире, она вносит только локальные задержки, но не уменьшает масштабируемость.

...Некоторое время назад, когда наткнулся на идею weak caches, я был очень вдохновлен идеей отказа от синхронизации для улучшения производительности. Дополнительным аргументом было то, что в распределенных системах как раз много внимания уделялось eventually-consistent алгоритмам и структурам данных, и мне казалось очевидным, что и многопоточное программирование должно двигаться туда же. Ведь в чем принципиальная разница между синхронизацией двух ядер в многоядерной машине, и синхронизацией двух узлов кластера, расположенных на разных континентах?

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

В контексте же многопоточного программирования с разделяемой памятью, синхронизация — это совсем про другое (и для многих этот факт является большим сюрпризом). Здесь инструкции синхронизации означают всего лишь локальный запрет на переупорядочивания операций. Как я уже не раз писал, если я выдаю барьер памяти — это не означает, что я требую немедленно синхронизироваться с основной памятью, или кэшами соседних процессоров, это всего лишь означает, что я требую, чтобы эта синхронизация, когда бы она не произошла — выполнялась в определенном порядке. И это не какая-то там теория, все так на практике и есть: когда, на x86, вы выдаете lock add %esp, 0 — никакой глобальной синхронизации не происходит, процессор просто сбрасывает свой store buffer в свой же локальный кэш. Ни в основную память, ни в кэши соседних процессоров эти данные никто немедленно отправлять не будет (разумеется, на архитектурах без аппаратной кэш-когерентности, типа ARM-ов, этот процесс может выглядеть иначе — я точно не знаю, как).

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

Так вот, в дискуссиях вокруг многопоточного программирования часто возникают спекуляции на тему дороговизны этих самых инструкций синхронизации. И важно понимать следующее: да, в начале "эры multicore" инструкции синхронизации стоили довольно дорого. Еще несколько лет назад на x86 CAS стоил под 100нс. Но все эти годы инженеры не лаптем щи хлебали -- на Core i7 uncontended CAS стоит всего ~3ns! Это примерно 6-8 "средних" инструкций (К этим бенчмаркам стоит относиться с осторожностью — слишком они искусственные. В более реальных условиях я бы ожидал цифры в 2-3 раза больше -- но это все равно не так уж страшно). И это не предел — нет никаких фундаментальных причин, почему бы инструкциям синхронизации не стоить как обычным инструкциям.

А вот для скорости работы шины InterConnect-а фундаментальные ограничения есть — скорость света, как минимум. И из общих соображений понятно, что скорость обмена данными с соседними ядрами скорее всего всегда будет оставаться в разы, а то и в десятки раз меньше, чем скорость обмена данными внутри ядра. И отсюда уже становится очевидным, что полная стоимость обмена данными между процессорами (упорядочивание + физическая передача) упирается прежде всего в стоимость передачи данных по шине, и лишь во вторую очередь в стоимость инструкций синхронизации.

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

Но это еще не все. Ведь как организованы алгоритмы с гонками? В алгоритмах без гонок мы упорядочиваем передачу данных release/acquire барьерами. В алгоритмах с гонками мы никак передачу не упорядочиваем, но на принимающей стороне мы вынуждены строить такую логику, которая сумеет разобраться с приходящими данными, в каком бы порядке они не появились. И это значит, что на принимающей стороне должна быть какая-то дополнительная логика, умеющая разбирать, образуют ли видимые сейчас данные что-то согласованное, что уже можно использовать, или надо еще подождать, пока придут недостающие кусочки. Говоря совсем просто — это будет цепочка условных переходов, spin-loop-ов на наборе ожидаемых полей.

А теперь, зная, что современные процессоры не любят условные переходы, особенно слабопредсказуемые (а spin-loop на 3-4 полях, с барьером компилятора, с backoff-ом — будет, как мне кажется, довольно сложным для предсказания), и зная, что инструкции синхронизации стоят всего-то ~10-20 обычных инструкций — есть ли основания полагать, что алгоритм с гонками будет хоть чуть-чуть быстрее нормального, корректно синхронизированного кода? Ну, я думаю, есть такие основания — для самых простейших случаев, вроде упомянутого String.hashCode(). Но вряд ли таких случаев много. И более того, перспективность этого направления близка к нулю, потому что инструкции синхронизации будут еще больше дешеветь, и смысла от их устранения будет все меньше.

Почему же тогда считается, что синхронизация уменьшает масштабируемость? Ну потому, что инструкции синхронизации это лишь одна из составляющих многопоточных алгоритмов, а еще одна, практически неотъемлемая, их часть это ожидание нужного состояния. Скажем, если брать блокировки, то ненагруженная (uncontended) блокировка на масштабируемость мало влияет, масштабируемость начинает серьезно страдать, как только какие-то потоки вынуждены ждать на блокировке. Spinning, обращение к планировщику задач, переключения контекста — вот это ухудшает масштабируемость

То есть eventually-consistent алгоритмы — это совсем иное, чем data race. Цель EC в уменьшении количества обменов данными, и в разработке алгоритмов, которые остаются рабочими (а структуры данных — в некотором роде согласованными) даже если какие-то данные сильно запоздали. В этом смысле ближайшая аналогия, мне кажется, это wait-free алгоритмы, где каждый поток может прогрессировать вне зависимости от других потоков, поддерживая структуру данных внутренне согласованной.

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


P.S. Надо, конечно, помнить, что в реальной жизни всегда есть ньюансы. Например, теоретически-то инструкции синхронизации являются локальными. Но на практике HotSpot для реализации volatile на x86 использует lock xadd, который на короткое время блокирует шину глобально. Почему? Потому что mfence который вроде бы и есть полный двусторонний барьер, и специально для этого и предназначен (и не блокирует шину) в каких-то деталях не совместим с тем, что требует JMM, и приходится пользоваться тем, что попалось под руку.

Кроме того, бывают ситуации, где вы вынуждены использовать слишком сильный примитив синхронизации, просто потому, что более слабого в вашем распоряжении нет. Например, в JMM нет инструкции синхронизации, обеспечивающей только двусторонний барьер чтения (без записи). Это не позволяло реализовать очень эффективный версионный ReadLock. (Пока не пришел Даг Ли, и не создал такую инструкцию как раз под этот случай — но на все случаи Дагов не напасешься ведь)

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

  1. Осуждаю, не прочитав еще статью. :-)
    Вернее выводы. Вернее брюзжу. Технология внезапно навернула еще один круг и нынешний SMP это уже multisocket-SMP. А там синхронизации снова неожиданно обретают глобальный смысл.
    А Мартин по прежнему меряет тесты на конфигурациях популярных в Disruptor'овские времена (не в смысле Nehalem, а в смысле без выхода в QPI).
    CAS - 3ns это конечно хорошо, но на multisocket'е там другие цифры http://htor.inf.ethz.ch/publications/img/ramos-hoefler-cc-modeling.pdf получатся.
    Возможно Haswell принесет всем нам больше счастья.

    ОтветитьУдалить
    Ответы
    1. Насчет 3ns/CAS я сам пишу, что это выглядит не очень реалистично.

      А вот насчет multisocket-SMP -- я, честно говоря, не очень понимаю о чем вы, и почему это возвращает синхронизации глобальный статус?

      Ссылка очень любопытная, спасибо за нее

      Удалить
    2. Ну потому, что межпроцессорный TSO гарантируется только через LOCK. Я знаю вам претят низменные рассуждения на уровне реордерингов и конкретных реализаций, но морально я готов обсуждать только Intel. :-)

      Удалить
    3. Ну почему претят -- когда речь идет о _корректности_ я готов говорить только в рамках JMM, если же речь идет о производительности то понятно что нужно учитывать детали реализации.

      Если вы про тот #LOCK который в lock add, то я в деталях не знаю, что именно он блокирует -- вообще доступ к шине или запросы на конкретный кэш-лайн. Но в любом случае он 1) все равно не означает физического обмена данными 2) он не требует участия других ядер -- т.е. если другие ядра в этот конкретный момент к шине не лезут, то они этот сигнал вообще не заметят, он никак не скажется на их производительности. Т.е. я хочу сказать, что выполнение lock add включает некую глобальную координацию, но не требует глобальной скоординированной _работы_ всех ядер -- я так понимаю. Соответственно, если у вас не весь код только на одних volatile-ах написан, то вы о-о-очень редко будете натыкаться на уменьшение масштабируемости из-за столкновения #LOCK-ов от разных ядер. Масштабируемость будет страдать в гораздо большей степени от насыщения шины физическими пересылками данных.

      Удалить
    4. #LOCK порождает RFO (read for ownership), RFO переводит соответсвующие cache linе'ы всех Core в состояние Exclusive Access, затем происходит модификация и cache line'ы остальных ядер меняют состояние на Invalid state. В случае multisocket, каждое изменение состояния - это рассылка сообщений MESI протокола, которое проходит через QPI. А QPI имеет конечную пропускную способность и ненулевую latency.

      Удалить
    5. По-моему, вы что-то странное пишете. Не #LOCK порождает RFO (request for ownership), а любая запись порождает RFO, потому что требует кэш-лайн в эксклюзивном состоянии. И кэшлайны "всех ядер" не могут быть в E, именно потому, что Е -- эксклюзивное состояние, и только одно ядро может иметь строку в таком состоянии.

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

      Удалить
    6. из http://software.intel.com/sites/products/collateral/hpc/vtune/performance_analysis_guide.pdf
      "All instructions containing a lock prefix will
      result in a (RFO) since they always result in a write to the cache line."
      Прошу прощения, неточно выразился, естественно E только у одного. Но при lock перфиксе все равно придется поднять #LOCK на шине. В мануале несколько расплывчато написано: "For the P6 and more recent processor families, if the area of memory being locked during a LOCK operation is
      cached in the processor that is performing the LOCK operation as write-back memory and is completely contained
      in a cache line, the processor may not assert the LOCK# signal on the bus." К сожалению больше информации о том когда это may случается пока найти не удалось.

      Удалить
    7. Любая запись требует RFO, и следовательно любая ReadModifyWrite инструкция тоже его требует как минимум на финальной стадии. А скорее всего они все выдают RFO сразу, потому что нет никакого смысла запрашивать кэшлайн в S для чтения, и потом его эскалировать до E на записи, если ты заранее уже знаешь, что запись пойдет сразу после чтения -- экономнее сразу требовать кэшлайн в E. Таким образом, опять же, locked инструкции не порождают никакого дополнительного трафика на шине, по сравнению с не-locked (кроме, может быть, самого сигнала #LOCK).

      Про приведенный вами отрезок -- если у вас уже кэшлайн в M, то ваш контроллер памяти слушает шину на предмет запросов к нему, и когда кто-то другой запрашивает эти данные из памяти -- вы этот запрос прерываете, и инициируете сброс данных в память. Так вот, как я понимаю, если у вас сейчас над этим кэшлайном выполняется locked-инструкция -- вы можете воспользоваться тем же механизмом: бить по рукам всем запрашивающим этот же кэшлайн, но ничего никуда не сбрасывать, пока инструкция не завершится. Тогда вам не нужен никакой #LOCK на шине. Это получается такой спекулятивный вариант блокировки: вместо того, чтобы заранее всем объявить "это мое" (поднять #LOCK) вы ничего никому не говорите, но если кто-то пытается взять -- бьете его по рукам. Поскольку rmw-инструкции обычно короткие (если данные уже в локальном кэше) такая спекуляция имеет смысл. Но это мое понимание, я могу ошибаться

      Удалить
  2. Извините, ответил не на ваш пост, а на что-то в своей голове. Видимо среагировал на "3ns CAS", а не на весь пост. Но ссылка в моем предыдущем комментарии - полезная.

    ОтветитьУдалить
  3. Руслан, если есть минута - посмотрите, пожалуйста на мой простейший вопрос: http://stackoverflow.com/questions/19007614/visualvm-in-my-heapdump-string-variables-are-always-null , не могу понять почему не вижу строк в HeapDump в тривиальном коде.. дело в каких-то оптимизациях?

    ОтветитьУдалить