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

27 февраля 2013 г.

А почему компилятор не синхронизирует код за меня?

Основная гарантия, которую дает программисту JMM, это что программы без гонок (data race free) выполняются так, как будто они sequentially consistent. Гонки (data race), напомню, это пара чтение/запись или запись/запись одной переменной, когда операции в этой паре не упорядочены через happens-before. И чтобы их упорядочить, если они еще не, нужно добавить каких-то действий синхронизации.

...Но если это так, то почему бы компилятору самому не находить конфликтующие доступы к данным, и не расставлять бы самому в нужных местах упорядочивающие их барьеры? Да, мы потеряем возможность писать программы с гонками. Ну, проживем без эффективного String.hashCode(), да ленивых кэшей, уж перетопчимся как-нибудь. Зато сколько геммороя сразу пропадет! Большинство разработчиков рассуждают о своем коде исключительно в рамках неявно предполагаемой sequential consistency, хотя вообще-то чтобы так рассуждать, нужно сначала сделать программу корректно синхронизированной. Какое счастье и благолепие настало бы, если бы за этой магией следил бы компилятор, а?

Я давно об этом думал, а вот сегодня прямо явно наткнулся (выделение мое):

In fact, Shasha and Snir show that non-sequentially consistent results can only occur when there is a cycle in the graph of happens-before and conflict edges (if two accesses conflict, there is a conflict edge between them). Therefore, detecting where to place memory barriers is a matter of detecting these cycles, and placing memory barriers accordingly.
...Lee and Padua developed a similar compiler analysis, and showed that minimizing the number of memory barriers using their technique was NP-complete.
[Manson, Pugh, Adve]

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

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

26 февраля 2013 г.

Нет никакой ложки...

...и нет никаких реордерингов. Reordering — это поэтическая метафора. Процессоры вовсе не переставляют инструкции. Процессоры просто выполняют код хуй знает какиначе, чем он написан. Как именно? — да как считают нужным, не нравится — не покупайте. Компиляторы — сюрприз — тоже не переставляют инструкции. Компиляторы делают с вашим кодом что-то противоестественноекакую-то неведомую и непонятную херню. Не верите — выведите дизасм достаточно длинного метода на яве, и попробуйте точно объяснить смысл хотя бы пары дюжин подряд идущих инструкций. Там есть комментарии, но вряд ли это вам поможет. Не нравится — пишите свой, с перестановками и циклами причинности.

В формальной части JMM нет никаких перестановок. Можете перечитать JLS-17.*, термин reordering там используется исключительно в разделах "пояснения и обсуждение", чтобы человеческим языком (ну, тем, что авторы считают человеческим языком) объяснить смысл сформулированных определений.

На этом уровне — на уровне метафоры, наглядного образного объяснения, и существуют разные эвристики, вроде "обычную запись можно переставлять до волатильной, но нельзя после нее". Надо четко понимать, что это именно эвристические правила, а не строгие утверждения. Нигде в JMM вы не найдете утверждения, в каком направлении обычные записи можно или нельзя переставлять с волатильными.

Почему так? Да потому что у понятия reordering слишком расплывчатый смысл. Может ли компилятор переставить инструкцию А с инструкцией Б? — лично мне, как программисту, пофигу, пока я не знаю, что от этого изменится для моей программы. Допустим, компилятор их переставил — значит ли это, что я теперь увижу результат А до результата Б? Вот это тот вопрос, который важен для написания кода, для доказательства сохранения каких-то инвариантов при его выполнении. И если я знаю ответ на этот вопрос, то какая мне разница, в каком порядке переставились инструкции А и Б? Может, сначала А потом Б? А может компилятор выплюнул сначала Б потом А, а потом барьер памяти, сделавший их результат видимым одновременно? А может компилятор выплюнул Б перед А, но процессор его перехитрил, и таки спекулятивно выполнил А перед Б?...

Вот что я имею в виду по расплывчатостью понятия reordering. Именно от всего этого пытается абстрагировать программиста JMM. JMM просто-напросто (да, я издеваюсь) дает возможность для каждой инструкции чтения в программе ответить на вопрос "какую инструкцию записи это чтение может увидеть?" И это именно то, что интересует меня, как программиста.

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

Очень похожая картина, как мне кажется, существует вокруг мифического spurious wakeup. Всем впадлу объяснять очередному поколению программистов тонкую смысловую разницу между "ожиданием определенного состояния (выполнения некого условия)" и "ожиданием извещения" — гораздо проще помянуть про легендарное ВНЕЗАПНО, и заставить писать проверку в цикле. Кажется, если бы spurious wakeup не существовал, его стоило бы придумать хотя бы ради экономии времени.

Точно так же очередное поколение java-программистов поднимает руки перед мистическим семнадцатым разделом JLS, и остается на полумифическом уровне рассуждений о возможных перестановках.


О автор, ты не мудри, ты пальцем покажипрости мне мою глупость, но я так и не понял, может ли великолепная Виртуальная Машина Явы переставлять обычную запись с волатильной?
Позвольте я переформулирую ваш вопрос для наших читателей:


volatile int va = 0;
int a = 0;
a = 42;
va = 1;
if( va == 1 ){
   print a;
}

volatile int va = 0;
int a = 0;
va = 1;
a = 42;
if( a == 42 ){
   print va;
}

Благоволит ли Аллах такому чуду, чтобы код в первом примере выведет 0? И достанет ли ли Его доброты, чтобы и второй код еще раз явил миру ноль — красивейшее из чисел?

Согласно сутре Пророка, в первом примере, для случая well-formed executions это неугодно Аллаху. Во втором примере, в общем случае это возможно (т.е. доказать невозможность в общем случае нельзя), но в частных случаях это тоже может оказаться противным воле Всевышнего (см. пример из предыдущего поста). В обоих случаях все может измениться от воли Его, и более широкого контекста — от кода, который окружает эти инструкции. Так восславим же Аллаха за его доброту!

P.S. Точности ради: говоря о реордерингах, надо упомянуть еще другой уровень — уровень разработчиков JVM. Уровень людей, которым нужно прописать в JIT-е для конкретной архитектуры процессора конкретные правила преобразования кода, правила допустимости или недопустимости каких-то оптимизаций в каком-то контексте, правила расстановки барьеров памяти. Для них как раз актуальна задача "что может, и что должна делать с кодом JVM, чтобы результат выполнения не противоречил гарантиям, предоставляемым JMM?" И здесь reordering обретает конкретный смысл, потому что для известной архитектуры процессора наблюдаемые эффекты от перестановки двух известных инструкций можно узнать из его спецификации. И эти эффекты можно сравнить с тем, что требует JMM, и решить, подходят ли они нам.

15 февраля 2013 г.

Квест по внутренностям JMM: solution

Студентка Люся выучила все билеты по логике и стала мужиком.

Хорошо, давайте разберем предыдущий пост. Для доказательства нам понадобится всего ничего: волос с головы Путина, менструальная кровь девственницыJMM в мягком переплете, и мозг со способностями к математической логике.
Замечание 0:
В JMM есть понятие частичного порядка happens-before. Немного математики: что такое вообще частичный порядок на множестве A? Неформально: частичный порядок означает, что на множестве A задан способ упорядочивания элементов a1 < a2, но упорядочить можно не все элементы множества: есть такие пары (an, am) что для них порядок не определен: не верно ни что (an < am), ни что (am < an). В противовес этому полный порядок, как можно догадаться, это когда все пары сравнимы: для любых элементов множества A всегда либо am < an, либо an < am, третьего не дано.
Замечание 1:
Если у нас есть события записи и чтения одной переменной W: sharedVar = X, R: localVar = sharedVar, то какие значения может прочитать (увидеть) чтение? Согласно JMM, варианта три:
  1. Если W hb R, то R наверняка прочитает (увидит) X (если нет других записей в ту же переменную)
  2. Если !(W hb R), то R может прочитать X, а может и не прочитать -- как звезды лягут (этот случай как раз называется чтением через data race)
  3. Если R hb W, то R никак не может прочитать X (опять же, если нет других записей). Это самый важный для дальнейшего пункт
Замечание 2:
Synchronized actions (к которым принадлежат vstore и vload) образуют total synchronization order, SO. Важно здесь, что это именно полный порядок. То есть для любых двух SA1, SA2 всегда либо SA1 so SA2, либо SA2 so SA1.

Наше оружие — слово божье, и математический аппарат

Код из предыдущего примера, чуть приглаженый и пронумерованный:
(0) AI sharedRef = null; //write default value

Thread 1

Thread 2

(1) localRef = allocate(sizeOf(AI));
(2) localRef.value = 42;
(3) sharedRef = localRef;

(4) localRef2 = sharedRef;
(5) if(localRef2 != null ){
(6)   localValue = localRef2.value;   
    }

Рассмотрим множество трасс над этим кодом, в которых чтение (6) происходит, и видит значение 0:
  1. Чтобы прочитать что угодно из localRef в (6), нужно чтобы чтение (4) вернуло не null (иначе мы не попадем в эту ветку)
  2. Поскольку 0 это не 42, то не верно, что (2) hb (6).
  3. Раз не верно, что (2) hb (6), то не верно и что (2) sw (6), потому что synchronization order вложен в (согласован с) happens-before.
  4. Поскольку (2) и (6) — synchronized actions, то из ![ (2) sw (6) ] => [(6) sw (2) ] => [(6) hb (2)]. Это ключевой, самый нетривиальный пункт — дальше все просто
  5. (4) hb (6) согласно program order (который тоже вложен/согласован с hb)
  6. (2) hb (3) аналогично
  7. По транзитивности: [(4) hb (6)] + [(6) hb (2)] + [(2) hb (3)] => [(4) hb (3)]
  8. Но раз [(4) hb (3)], то чтение (4) никак не может увидеть значение, записанное (3). Значит (4) может прочитать только значение, записанное в (0), то есть null.
  9. А это противоречит первому пункту.
Получается, что предполагаемые нами трассы не могут существовать в рамках ограничений, накладываемых на исполнение кода моделью памяти java.

Dixi


P.S. Да, совсем забыл -- я могу и ошибаться :)

13 февраля 2013 г.

Квест по внутренностям JMM



class AtomicInteger { 
    private volatile int value;
    public AtomicInteger(final int value) {
        this.value = value;
    }
....
}

AtomicInteger sharedRef;

Thread 1

Thread 2

sharedRef = new AtomicInteger(42);

if( sharedRef != null ) {
    System.out.println(sharedRef.get());
}

  1. Может ли этот код вывести 0?
  2. ...Если может — то как? Сможете ли вы теперь теми же глазами смотреть на AtomicInteger?
  3. ...Если нет — то почему?

P.S. Я, если честно, точного ответа не знаю. Хотя пара правдоподобных вариантов у меня есть.

4 февраля 2013 г.

Задача с собеседования: продолжение

Поскольку в комментариях ответ нашли аж несколько раз, то сознаюсь — да, идея в том, что второй процессор это не только дополнительные 600 баксов стоимости и 70Вт энергопотребления, но еще и лишние 32Кб L1 кэша данных (а в Sandy Bridge так и лишние 256Кб L2, потому что там L2 тоже на каждое ядро). Так что, хотя в общем случае логично ожидать, что однопроцессорная версия будет быстрее (потому что не надо тратиться на синхронизацию), но если задача достаточно memory intensive (т.е. мы упираемся в скорость доступа к данным), причем фазы P1 и P2 оперируют разными данными, то в двухпроцессорном варианте данные фазы 1 будут горячими в кэше CPU1, а данные фазы 2 горячими в кэше CPU2. Получим эффективный размер L1 в 64Кб. И эффект от такого "увеличения" кэша может оказаться доминирующим, и оправдать даже расходы на синхронизацию.

Но мне стало интересно, смогу ли я этот эффект поймать в реальности. Реальность, как обычно, оказалась чуть сложнее теории, но в поединке мозга и компьютера мозг опять победил: вот этот код при базовых (тщательно подобранных) настройках дает в синхронном режиме (-Dasync=false) (690 +/- 1%) нс/сообщение, а в асинхронном (560 +/- 8%) нс/сообщение.

Хотелось бы в общих чертах понять, о чем говорит иностранецчто там происходит?

Нужно подобрать некоторую условную memory intensive задачу, и разбить ее на две фазы, каждая из которых обращается к своему куску данных. Я взял кусок данных в виде достаточно большого (сопоставимого с размером L1) массива double[]. Сама "фаза обработки сообщения" состоит из нескольких чтений/записей в ячейки этого массива. "Несколько" выбрано равным 128, и эти 128 ячеек выбираются из всего массива по псевдослучайному алгоритму (типа ЛКГ: I = (A*I) mod C). Сначала первая фаза делает это над своим массивом, потом вторая фаза делает ровно то же самое над своим — и так для каждого сообщения, коих легион 1 000 000 в каждом заходе. Да чего я код надиктовываю:
int index = message.index;
for( int i = 0; i < OPS_PER_MESSAGE; i++ ) {
  index = Math.abs( index * offset ) % DATA_SIZE;
  array[index] += amount;
}

Интересный вопрос №1: если псевдослучайное скакание по массиву заменить на проходку с фиксированным шагом, то разница в производительности практически пропадает. Скорее даже, с небольшим перевесом, почти на грани погрешности, начинает выигрывать синхронный вариант. Почему так? Интересный вопрос №2: если отставить в сторону рассмотренный вариант — какие еще эффекты могут обеспечить преимущество "распараллеленному" варианту последовательного кода? P.S. Да, кстати — мы (Дойче банк) набираем людей. Кажется, 3-4 вакансии у нас сейчас открыты. Можно прямо мне и писать — а то у меня еще много интересных идей для собеседования есть :)

31 января 2013 г.

Задача с собеседования

...Пусть у нас есть некоторая процедура обработки сообщений. Процедура состоит из двух фаз: P1 и P2. Фазы строго последовательны — P2 не может начаться, пока не закончилась P1. У нас есть датацентр, в датацентре — стойка, в стойке — сервер, в сервере — 2 процессора.

Есть два варианта организации процесса обработки:
Дизайн 1 (тривиальный)
Мы просто задействуем одно-единственное ядро, которое последовательно для каждого сообщения выполняет P1 и P2. Второе ядро курит бамбук.
Дизайн 2
P1 вешаем на ядро 1, P2 на ядро 2, между ними организуем какой-то протокол передачи сообщений.
Вопрос — какой вариант будет быстрее? (== меньше времени на обработку одного сообщения, от начала P1 до конца P2)


...те же грабли, но вид сбоку: теперь нас интересует не скорость, а пропускная способность. У нас есть входящий поток сообщений, которые надо разгребать. Опять же, два варианта:
Дизайн 1 (тривиальный)
Каждое ядро обрабатывает половину входящих сообщений, при этом каждое ядро для доставшихся ему сообщений выполняет обе фазы обработки последовательно.
Дизайн 2
Все сообщения идут сначала на ядро 1, которое выполняет фазу P1, потом пересылаются на ядро 2, которое выполняет для них фазу P2

Вопрос — в каком варианте можно достичь бОльшей пропускной способности? (== количество сообщений, обрабатываемых за единицу времени)


Подсказка: правильно заданный вопрос, как обычно, содержит половину ответа. Правильно заданный вопрос, в данном случае, будет "какой дизайн и при каких условиях даст лучший результат?"

UPD: Я упустил отметить, что по замыслу объемы (сложности) фаз примерно равны. Т.е. среднее время выполнения P1 равно среднему времени выполнения P2.

UPD2: В комментариях уже есть хороший ответ, так что не подглядывайте!

28 января 2013 г.

А что мы измеряем, когда измеряем "производительность 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, или какую-то полезную нагрузку — мы получим искомое ускорение, как и ожидалось.