А что мы измеряем, когда измеряем "производительность CAS-а"?

Очередная статья Мартина — продолжение одного из его уже довольно старых экспериментов. Там у него получилось, что простейший бенчмарк скорости выполнения intcementAndGet (==lock xadd) показывает лучшие результаты на процессорах архитектуры Nehalem, нежели на процессорах более свежей (и, вообще говоря, почти везде более производительной) архитектуры Sandy Bridge. Бенчмарк был совершенно тривиальный — сколько-то потоков, тупо делающих __sync_add_and_fetch() одному счетчику — поэтому результаты, конечно, выглядели странно. И вот, больше чем через год, наконец-то странность объяснилась, и объяснение очень интересное — я не могу удержаться, и не разобрать его.

Преамбула

(Для понимания дальнейшего полезно прочитать мой незаконченный цикл про протоколы кэш-когерентности здесь)

Начнем с того, что Read-Modify-Write (RMW) инструкции в кэш-когерентных системах выполняются примерно так:

1. Посылаем системе управления кэшом запрос на кэш-строку, содержащую нужную ячейку памяти в состоянии не ниже E(xclusive).
   
2. Запрос удовлетворяется немедленно, если текущее ядро уже является эксклюзивным владельцем строки (т.е. строка уже в нашем кэше либо в состоянии E, либо в M(odified)
3. Если владелец строки кто-то другой, или владельца вообще нет (еще никто ее не загрузил из основной памяти) — инициируем транзакцию на шине InterConnect с целью таки заполучить нужное. Это называется request for ownership, RFO
4. Убедившись, что текущее ядро является эксклюзивным владельцем нужной строки кэша, мы временно блокируем InterConnect для дальнейших запросов (тем самым не даем никому отобрать у нас только что полученное право собственности)
5. Выполняем Read-Modify-Write как отдельные инструкции — точно так же, как если бы не было никакого atomic. Атомарность будет гарантирована за счет блокировки шины.
6. Убираем сигнал #LOCK с шины

Самой (потенциально) тяжелой частью является пункт 3. Если нужной нам строки ни у кого нет — нам как минимум придется ждать основную память или L2-кэш, которые в разы медленнее L1-кэша. Если же у строки уже есть владелец — все еще гемморойнее, потому что запрос к основной памяти будет этим владельцем прерван, и будет инициирован некий протокол арбитрации — переговоров между ядрами на тему "кто кому и когда эту строку будет передавать".

Если эта часть не нужна (т.е. строка уже у нас в кэше в нужном состоянии) то atomic RWM выполняется не сильно медленнее обычной последовательности RMW. Такой удачный вариант (fast path), не требующий межпроцессорной арбитрации, часто называется "локальным RMW" (вы можете встретить выражения типа "local CAS", например), в противовес "глобальному RMW", который эту арбитрацию включает, и может оказаться в чуть ли не в сотню раз медленнее "локального".

Ближе к сути

Что же случилось с бенчмарком Мартина?

Вот есть у нас 2 потока на разных ядрах, вертящих в цикле getAndAdd. Пусть первое ядро захапало себе нужную строку кэша в E, и делает над ней всякие непотребстваload, add, store. Это будет локальный getAndAdd — строка-то наша. Как долго будет продолжаться это право первой ночи? — Да до тех пор, пока второе ядро у нас строку не отберет. А чтобы ее у нас отобрать, нужно инициировать и пройти до конца всю процедуру арбитрации. Таким образом можно заметить, что чем дольше длятся переговоры, тем больше локальных (быстрых!) getAndAdd успеет сделать ядро. Скажем, если арбитрация стоит 50нс, а локальный getAndAdd — 5нс, то мы успеем сделать 10 локальных операций пока у нас строку не отберут.

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

То есть после каждых 10 локальных операций, стоимостью в 5нс, мы прерываемся на 10(на пересылку "туда")+ 50(на арбитрацию)+10(на пересылку "назад")=70нс — и в это время соседнее ядро делает свои 10 локальных операций. Средняя стоимость одной операции (10*5 + 70) / 10 = 12нс.

А теперь внезапно Sandy Bridge, и гениальные инженеры Интела, заработав седину на висках, заоптимизировали арбитрацию. И теперь арбитрация стоит 10нс (не зря седину заработали, да). И за время этой арбитрации мы успеваем сделать только 2 локальных операции. И теперь после каждых 2х локальных операций по 5нс будет одна пауза в (10 + 10 + 10) = 30нс. Среднее время выполнения getAndAdd (2*5 + 30)/2 = 20нс.

Черт побери. Как-то неаккуратненько вышло.

Особенно любопытно что: легко видеть, что каждый конкретный getAndAdd на Sandy Bridge выполняется не медленнее, чем на Nehalem (а часто и быстрее). Но вот количество "медленных" (глобальных) getAndAdd-ов на Sandy Bridge стало в разы больше, чем было на Nehalem. И именно потому, что каждый конкретный глобальный getAndAdd стал быстрее.

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

Мораль

Это очень красивый эффект, возникающий в некоторых системах, когда оптимизация slow path может ухудшить общую производительность системы, потому что после оптимизации увеличится доля объектов, обрабатываемых по slow path. Очень похожий по сути Парадокс Брайеса существует в транспортных сетях. На еще более похожую ситуацию я сам натыкался, когда анализировал Disrupor — до сих пор бьюсь в экстазе, когда вспоминаю.

Важно, что для возникновения такой парадоксальной ситуации нужно, чтобы система некоторым образом "тупо" саморегулировалась. В парадоксе Брайеса нужно, чтобы водители сами эгоистично выбирали себе маршрут (если ввести внешнее регулирование парадокс пропадает). В случае Disruptor-а важно, чтобы скорость накладаторов/разгребаторов определялась только самим Disruptor-ом, а не, скажем, бизнес-логикой. В случае Мартиновских бенчмарков то же самое — важно, чтобы оба потока фигачили свои getAndAdd так часто, как только можно, а не так часто, как нужно по логике. Т.е. система в режиме насыщения, и каждый тянет одеяло на себя. Если как-то нагрузку упорядочить — ввести Backoff, или какую-то полезную нагрузку — мы получим искомое ускорение, как и ожидалось.