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 вакансии у нас сейчас открыты. Можно прямо мне и писать — а то у меня еще много интересных идей для собеседования есть :)