23 апреля 2012 г.

lazySet: тайные страницы JMM

Подолжая раскрывать темы, недостаточно раскрытые на докладе -- сейчас про lazySet. Тема это непростая, и не потому, что там все сложно, а потому, что нужно повторить основы JMM. У меня уже давно бродит мысль написать цикл статей "Скрытые главы JMM", но все руки не доходят -- это ж надо будет advanced JMM перечитать внимательно и пристально, все теоремы разбирая... Вот, может, в старости...

Так что сейчас будет краткое введение, голопом по европам.

Дисклаймер: все что идет дальше -- это мое личное понимание JMM. Оно может быть неполным, неправильным, и вообще полной херней. Я вас предупреждал!

...Когда пишут про JMM -- почти всегда пишут про частичный порядок "происходит до" (partial happens before order). Это действительно самая ходовая часть JMM -- в большинстве практических случаев достаточно знать правила формирования ребер HB, и счастье будет уже здесь, и моментально.

Но JMM гораздо более сложная конструкция, чем только HB. JMM -- это такой набор ограничений на исполнение java кода. Эти ограничения позволяют сделать одно очень сильное утверждение относительно возможных сценариев его исполнения. А именно: если у нас в коде нет гонок (data race), то любой сценарий исполнения будет sequentially consistent.

По пунктам: что такое гонки (data race)? Пусть у нас в программе есть разделяемая (т.е используемая из >1 потока) переменная, и хоть один поток в нее пишет. Почему важна запись понятно: если никто не пишет, а все только читают, то это не интересно, никаких конфликтов. А вот если есть запись и чтение(-я) -- тогда все любопытнее. Если запись и чтение не упорядочены (через HB) то говорят, что этот набор инструкций (запись и чтения) образует гонку. Код без гонок называется data race free, DRF

В чем проблема с гонками? В том, что в них становятся заметными весь тот треш, угар и содомия (для наших читателей из Питера: здесь нет пропаганды гомосексуализма, я гарантирую это!), которую творят с вашим кодом современные оптимизирующие компиляторы и (в большей степени) современные CPU и контроллеры памяти. Все эти instruction reordering, out-of-order execution, speculative branch prediction, write combining, и прочие ужасы царизма. Это то, что, по-идее, программисту видно быть не должно -- ибо он поседеет, если это увидит. Другими словами: в коде с гонками начинают течь широко используемые абстракции -- что код исполняется так, как вы его написали, что память у нас общая и однородная, и т.п. Вы начинаете видеть грязную кухню реального мира :)

Вернемся к баранам. Что такое sequentially consistent (SC) execution? Неформально: SC для многопоточной программы -- это когда ваш код исполняется так, как будто он исполняется на единственном устройстве выполнения, безо всяких буферов, кэшей и внеочередного выполнения операций. Т.е. каждая инструкция атомарна, и ее результат сразу же доступен (виден) всем остальным потокам. Инструкции выполняются строго в том порядке, как они идут в коде. Переход от исполнения кода одного потока к коду другого возможен только в промежутке между двумя инструкциями. Еще проще -- это back to i386. Разумеется, реально ваш код может исполняться как угодно -- но результат в любой точке должен быть только такой, какой возможен при каком-нибудь SC сценарии.

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

Это вовсе не означает, что в SC программе нельзя сделать ошибки. Это лишь означает, что имея гарантию sequentially consistency можно хоть иногда писать правильный код -- потому что список возможных сценариев выполнения становится хотя бы более-менее обозримым


Теперь, когда мы прониклись величием решаемой JMM задачи, можно уже отметить одну мелочь: для того, чтобы доказать свойство (DRF -> SC) одного частичного порядка HB недостаточно. Нужны еще две важных вещи.

Во-первых это причинность (causality). Неформально: что у любого события есть первопричина. Не допускаются циклы причинности: когда А является причиной для Б, а Б -- является причиной для А. Причинность, в частности, запрещает в яве значениям переменных возникать из воздуха ("out of thin air") -- для любого прочитанного из переменной значения должна существовать в коде программы операция записи, которая это значение туда записала (и она не должна происходить после этого чтения). Для явы это архиважно, потому что если бы значение ссылки могло возникнуть из ниоткуда -- вся безопасность языка и среды накрылась бы медным тазом.

Во-вторых, это Total Synchronization Order. В JMM некоторые операции (захват/освобождение монитора, чтение/запись волатильной переменной, и всякая эзотерика, типа условных "первое/последнее действие в потоке", операция запускающая поток, операция обнаруживающая завершение потока... см подробнее JLS 17.4.2) объявлены как Synchronized Actions. Особенность этих SA в том, что они образуют Total Synchronization Order. Ключевое здесь именно total -- полный порядок, в отличие от partial happens-before order, который частичный порядок.

Частичный порядок означает, что между некоторыми операциями есть точно определенный порядок -- А всегда (во всех сценариях исполнения) идет до Б. А между некоторыми операциями такого однозначного порядка нет -- в одних сценариях исполнения В может идти до Г, в других -- Г до В. И более того -- в одном и том же сценарии исполнения один поток может видеть сначала результат Г, а потом результат В, а другой поток -- сначала результат В, а потом Г. Т.е. порядок В и Г не определен в обоих смыслах: и поскольку он в разных сценариях (запусках) может быть разным, и поскольку даже в одном сценарии он может видиться разным с разных точек зрения.

А вот полный порядок означает, что между любыми двумя операциями всегда есть какой-то порядок. Либо А до Б, либо Б до А -- третьего не дано. И этот порядок всеми виден одинаково.

То есть тот факт, что synchronization actions образуют полный порядок означает (в переводе с математического на русский), что любая пара synchronization actions всегда упорядочена, и этот порядок виден всеми потоками программы одинаково.

Получается, что synchronization actions -- они уже sequentially consistent. И чтобы получить SC для всей программы нам осталось только как-то "растянуть" эту sequentially consistency на все остальные инструкции в коде. И мы это делаем с помощью частичного порядка happens-before -- присоединяя по транзитивности к уже существующим и всегда упорядоченным synchronization actions обычные инструкции. И если нам удастся по транзитивности присоединить все инструкции в программе (а это удастся если в программе нет гонок) -- то мы и получим SC для всей программы в целом!

То есть, если очень кратко -- мы создаем в программе становый хребет из synchronization actions, которые по-определению sequentially consistent. И ребрами HB присоединяем к нему то, что можно присоединить. Если в программе нет гонок -- то нам удастся присоединить все инструкции, и вся программа окажется доказуемо SC.


Зачем вся эта длительная история? Нужно понимать, что обеспечение для целого множества инструкций полного порядка, который одинаково виден всем потокам -- это несколько более сложная штука, чем просто упорядочить пару инструкций в двух конкретных потоках. Вот например:
volatile va = 0;
volatile vb = 1;
a = 0;

//Thread 1:
va = 1;
a = vb;

//Thread 2: 
print( "va=" + va + ", a=" + a ); 
//может ли вывести "va=0, a=1"?


Может этот код вывести "va=1, a=0"? Т.е. может ли быть a = vb переставлено до va = 1?

Обычные ребра HB этого не запрещают: записи идущие после volatile write можно переставлять до нее, а волатильное чтение образует HB только с волатильной записью той же переменной -- чего здесь нет.

Однако если допустить, что такая перестановка возможна и допустима, то мы получаем ситуацию, когда Thread 1 видит (в соответствии со своей внутри-поточной семантикой) сначала волатильную запись va=1, а потом волатильное чтение a=vb. А Thread 2 видит другой порядок -- сначала чтение vb, потом запись va. А это означает, что у нас нет единого, согласованного между всеми потоками порядка SA-операций. То есть такая перестановка недопустима, ее нужно запрещать.

Вот здесь мы подходим (наконец-то! вы там еще не уснули?) различию между volatile write и lazySet.

Для того, чтобы обеспечить обычное ребро HB между volatile write и read одной и той же переменной достаточно всего двух барьеров -- store-store до записи:
membar(store&load|store)
store va

и load-load после чтения:

load va
membar(load|store&load)

Этого достаточно, чтобы все, что было записано до store va было гарантированно видно после load va. Но этого не достаточно, чтобы обеспечить TSO -- нужно еще запретить реордеринг для synchronized actions. И вот для этого нужен дополнительный StoreLoad после записи:

membar( store&load | store )
store va
membar( store | load )

Именно отсутствием этого store-load и отличается lazySet. lazySet не является sychronized action, он не участвует в total synchronization order, и обходится без соответствующего барьера. А store-load -- единственный необходимый явный барьер на x86 (остальные выполняются неявно, в силу довольно большой строгости аппаратной модели памяти x86). Реализуется он как lock add %esp, 0x00 -- и это довольно дорогая операция. Поэтому если вы можете доказать корректность своей программы без того, чтобы какая-то конкретная волатильная запись была частью TSO -- можно на нем сэкономить. Правда, доказать это весьма непросто. Единственный известный мне метод -- это прислать код в concurrency-interest на ревизию Дагу Ли лично :)

[*] JSR-133 Cookbook for compile writers

22 апреля 2012 г.

Код бенчмарков

Отдельные люди на JavaOne после доклада просили выложить код бенчмарков. Вот, код здесь.

Ногами прошу не бить :)

21 апреля 2012 г.

...расследования

Я уже писал, что мне наконец-таки пришла в голову мысль, почему у Disruptor в бенчмарках такой большой статистический разброс. Еще точнее -- это не статистический гауссовский шум, а совершенно отчетливо различные режимы работы -- вот только не было понятно, откуда там внутри, где все просто, берутся еще какие-то режимы. Так вот, разгадка этого явления мне явилась в 5 утра в прошлую среду, во время подготовки слайдов к докладу. В честь такого счастья мне показалось честным рассказать про разгадку сначала на докладе, а уж потом здесь :)

В общем, одна картинка -- стоит тысячи слов. А уж знали бы вы, чего мне стоило выдрать эту картинку из своей презентации! ГуглоДокументы так просто контент не отдают:)

Идея простая. Поскольку бенчмарки у меня без нагрузки, то скорость перемещения курсоров издателя/подписчика определяется, в основном, внутренней механикой. А она у издателя и подписчика почти идентична. Поэтому двигаться они будут примерно с одиноковой скоростью. А значит в установившимся режиме они будут находиться на каком-то более-менее фиксированном растоянии друг от друга. Ну, разумеется, как-то колебаясь вокруг этого среднего расстояния.

Так вот, если это среднее расстояние таково, что записываемые издателем сообщения находятся на другом кэш-лайне, чем читаемые подписчиком -- то все шоколадно, контроллер памяти работает в приемлемом режиме. А вот если расстояние окажется слишком маленьким -- издатель и подписчик будут работать в пределах одного кэш-лайна. А значит -- контроллер памяти будет играть в пинг-понг: издатель будет для записи требовать кэшлайн в в своем кэше в состоянии M, а читатель -- в своем, в состоянии S. Да, это типичный пример false sharing.

Какое расстояние будет в установившемся режиме -- это, как я понимаю, в значительной степени случайность. Как там в переходном режиме система поколбасится -- так и будет. Спонтанное нарушение симметрии, одним словом :) Вот и получается несколько режимов функционирования с разной пропускной способностью -- в зависимости от случайного gap-а между курсорами, сложившегося в переходном процессе.

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

Интересная штука -- когда курсоры идут плотно друг к другу пропускная способность падает. А вот время ответа (latency) -- скорее всего тоже будет падать. Я его не измерял, но кажется очевидным, что чем меньше расстояние между первым и последним курсором в цепочке -- тем быстрее конкретное сообщение будет полностью обработано. А это значит, что бэтчинг здесь это такой размен throughput<->latency. Можно чуть поднять throughput, но ценой увеличения времени обработки одного сообщения. Можно чуть уменьшить время ответа -- но ценой падения и пропускной способности (==менее эффективного использования шины interconnect-а).


И смотрите, как любопытно выходит (дальше мои довольно умозрительные рассуждения): почти наверняка замедление работы в subscriber-batching будет проявляться только в ненагруженном режиме. В нагруженном режиме скорость движения курсоров определяется не их механикой, а нагрузкой -- курсоры двигаются настолько быстро, насколько обработчик успевает делать свою работу. А это значит, что система будет самоподстраивающейся: если нагрузки немного, и обработчики успевают все перемолоть быстро -- они догонят издателя, и будут идти за ним ноздря в ноздрю, уменьшая время ответа. Как только нагрузка вырастает, обработчики начинают не справляться с работой так быстро -- и отстают от издателя. А это сразу дает им чуть-чуть продохнуть за счет более эффективного бэтчинга (больше сообщений за раз) и за счет большего КПД использования interconnect-а. Все это, разумеется, в некоторых, небольших, пределах -- серьезное изменение нагрузки так не скомпенсируешь. Можно даже примерно прикинуть, насколько небольших: худший режим с бэтчингом у нас 15 000 пакетов/мс (~70 нс/пакет), лучший без бэтчинга 35 000 (~30нс/пакет). Разница в 40 нс -- это и есть оценка того, сколько может нам сэкономить сам Disruptor за счет автоматического перехода между режимами.

UPD: Как мне тонко намекнули в комментариях, я забыл важную часть -- гипотеза-то ценна не сама по себе, а тем, что она имеет экспериментальные подтверждения! А именно: если причина ухудшения пропускной способности при включении бэтчинга и нестабильности работы -- действительно такая, как я предположил, то должна быть корреляция между средним расстоянием между курсорами (а схеме это обозначено как gap), и пропускной способностью в конкретном эксперименте. Это можно проверить, и я это проверил. Результат -- вот он (по X -- gap, по Y -- throughput):


По-моему, все очень наглядно. Скачок производительности происходит как раз в области gap=2.5-3.0 Это отлично коррелирует с тем фактом, что размер сообщений у меня примерно 24 байта, т.е. их на 64-байтный кэшлайн умещается как раз чуть меньше 3 штук.

UPD#2: По многочисленным просьбам трудящихся числом 2 -- бенчмарки с пэддингом сообщений. Без batching 19 789 (+/- 483), с batching 20 488 (+/- 1 277).

19 апреля 2012 г.

JavaOne Moscow 2012 -- слайды с презентации

Отчитал вчера "Расчленяя Disruptor" на JavaOne. Слайды здесь. Сразу предупреждаю: слайды делались не по принципу "замена докладчику", а по принципу "лучший копирайт -- это когда без автора не разберешься".

Как разгребу текущие дела -- напишу пару постов по следам. Надо же, наконец, рассказать, почему в бенчмарках Disruptor такая большая дисперсия...

14 апреля 2012 г.

JavaOne 2012, Moscow

Мой личный предварительный маршрут по конференции (общее расписание здесь, и найти его оказалось весьма непросто!):

вторник, синий зал

(если не просплю)
11:30 - 12:25 "JDK8 и дальше" -- посмотрим, что там нам грядущее готовит
12:30 - 13:15 "...от монолитных приложений к модульным" -- ну тоже должно быть любопытно

(постараюсь не проспать)
16:30 - 17:15 "Методология оптимизации производительности"
17:30 - 18:15 "Драконы в домашнем хозяйстве: скалируемся на многоядерных машинах"

Это все Сергей Куксенко и Алексей Шипилёв, они мои любимые спикеры, во-первых по-русски говорят, во-вторых говорят, а не читают -- уже этого достаточно, чтобы к ним заглядывать. Так им этого мало -- они еще и в теме шарят! :)

среда

11:30 ‐ 12:15 "The Garbage‐First" -- тема интересная, я пока довольно мало знаю о G1, любопытно будет послушать. Но, боюсь, здоровый сон окажется важнее :)

14:15 - 15:00 "Fork/Join" -- это опять Алексей, и тема очень интересная -- судя по рассылке concurrency-interest в ForkJoin Даг Ли очень много всяких любопытных идей интегрировал. Более того, все идет к тому, что FJ станет практически умолчанием для распараллеливания. А я его еще и не трогал почти.

15:15 - 16:00 "Многоуровневая компиляция в HotSpot JVM" либо "garbage-free logger" -- вроде бы тут должен быть второй доклад, но в расписании его еще не заменили. Тема с высокопроизводительными приложениями с низким потреблением памяти на яве мне сейчас интересна. Тем более, что с одним из авторов gflogger я знаком -- пойду поддержать.

16:30 - 17:15 "Расчленяя Disruptor: магия и технология высокой производительности" -- по правде говоря, я бы сюда не пошел -- уверен, ничего нового про Disruptor мне там не расскажут. Но поскольку я там спикер -- идти придется. Да и вы тоже приходите -- мне важно ваше присутствие. Только помидоров не берите -- не понадобятся вам там помидоры, вам не до того будет...

17:30 -- 18:15 "Управление памятью в Java: минимизация потребления памяти" -- пойти собираюсь, но не уверен, что буду способен слушать -- после своего доклада я боюсь просто усну.

1 апреля 2012 г.

Скандалы, интриги...

Дошли руки посмотреть на бенчмарки самого Disruptor-а -- у него их есть немного. Сколько я помню, они сравнивали Disruptor vs ArrayBlockingQueue. Но в последних версиях в бенчмарках используются уже LinkedBlockingQueue -- якобы, они быстрее.

Интрига в том, что в их бенчмарках это действительно так -- LBQ стабильно лучше ABQ. Но в моих бенчмарках ситуация ровно обратная -- ABQ стабильно лучше. И я не могу найти причин, почему это так.


UPD: Оказывается, что LBQ быстрее на моем ноуте (Core i7 2GHz), а вот ABQ быстрее на сервере (Xeon E5620 2.4GHz). Подозрение мое падает даже не на то, что это разные модели, а больше на то, что сервер, кажется, ccNUMA, а ноут SMP. Хотя внятно объяснить, как это связано я пока не могу