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. (Пока не пришел Даг Ли, и не создал такую инструкцию как раз под этот случай — но на все случаи Дагов не напасешься ведь)