14 марта 2014 г.

JPoint 2014

Кстати, если кто еще не в курсе: jpoint 2014 будет в Москве. 18 апреля в Radisson Славянская. В этом году я там как участник, а не докладчик, но там и без меня хорошо: Роман будет рассказывать теорию моделей памяти, а Глеб распускать кишки HotSpot и показывать как оно там все реализовано. Из остальных уже заявленных докладов я лично собираюсь послушать Паньгина (про расследование heap dump он уже не первый раз рассказывает, но я не попадал), Бреслава про дизайн языков программирования, и Дударева про уязвимости нулевого дня. (Не так давно на хабре была переводная статья, где автор жаловался, что никто из джава-экспертов не умеет валить JVM -- надеюсь, Михаил меня научит, а то стыдно как-то). Ну, там еще расписание смотреть надо будет...

4 февраля 2014 г.

How fast the logger could be?

В начале декабря у нас тут случилась своя маленькая и уютненькая внутренняя конференция, на которой я рассказывал про быстрое логгирование. Поскольку конференция внутренняя, часть информации под NDA, так что просто выложить презентацию я не могу, но общие моменты попробую описать.

Задача взялась вполне себе из практики: есть приложение, которое зарабатывает бабло наносит пользу человечеству. У этого приложения есть legacy-версия, которая уж сколько-то лет в работе, и есть новая, с 0 переписанная (в основном мной) версия, которая сейчас готовится ее сменить на боевом посту. Разумеется, возникает масса вопросов вида "а почему вот в новой версии у этой транзакции результат чуть не такой, как в старой?". И приходится много времени шароебиться по логам, выясняя, как и что происходило. И, конечно, регулярно думаешь, что вот если бы еще здесь, здесь, и вот здесь дополнительно ключевые параметры сбрасывать в лог, то расследование было бы в разы быстрее и проще.

Казалось бы, в чем проблема-то? Проблема в том, что заказанное среднее время обработки транзакции в приложении <100us (мы пока до него не дотягиваем, но стараемся). В этих условиях приходится быть довольно экономным. Примерная стоимость вызова log4j.info() в асинхронном режиме где-то 5мкс — особо не разбежишься. Новая версия приложения давно уже использует gflogger как основной инструмент для логгирования, но даже здесь стоимость вызова примерно 1мкс, что, конечно, гораздо лучше, но все-таки еще многовато. Хочется же уместить 30-100 вызовов логгера в <10us (т.е. <10% целевого времени ответа). Другими словами, мне нужно решение для логгирования, которое требует 100-300нс/запись. Так вот, вопрос — можно ли так сделать?

В принципе, примерный маршрут виден: многие вещи уже обкатаны Володей при разработке gflogger-а. Garbage-free API, GC-free реализация с преаллоцированными буферами — все это себя вполне хорошо зарекомендовало. Но gflogger все-таки делался по принципу "возьмем log4j, отрежем весь явно лишний функционал, а так же еще что под руку попадется, и реализуем остальное". Большое преимущество такого подхода "сверху вниз" — короткий путь "до рынка": тот же gflogger начали использовать уже через пару месяцев после начала его разработки. Недостаток же в том, что в большой системе с обширным функционалом довольно сложно понять, кто какой вклад в производительность вносит. Просто-напросто слишком много вариантов того, что можно убрать/добавить/сделать иначе. Поэтому лично я предпочитаю вести ОКР в обратном направлении, снизу вверх — от примитивов, шаг за шагом собирая нужный мне комплект функционала, с постоянным бенчмаркингом. Чудеса случаются и здесь, но в целом, мне кажется, такой маршрут дает гораздо более понятную картину.

Собственно, так я здесь и сделал: поставил себе задачу собрать асинхронный логгер с gflogger-like API, на базе кольцевого буфера, с записью в один-единственный файл. Вообще-то, до записи как раз руки и не дошли, потому что меня больше интересовала не пропускная способность (по всем прикидкам она более чем достаточна для моих целей), а накладные расходы рабочих потоков, т.е. время вызова log.message(...).

Что получилось: удалось добиться ~150ns/message в 4-х поточном случае.

Что использовал и на какие компромиссы пришлось пойти:
  • Multi-threaded claiming: я рассказывал про это еще полтора года назад на jug-е: можно сильно улучшить масштабирование, и, что еще важнее, уменьшить простои потоков (т.е. приблизить к wait-free) если вместо общего на всех курсора publishedSequence использовать флаг в каждой конкретной записи.
  • Только примитивные аргументы. Во-первых это в целом упростило API. Во-вторых с примитивными аргументами можно заранее вычислить нужный размер записи. Без этого пришлось бы либо выделять по-максимуму, с запасом, либо сначала писать все во временный буфер, а потом копировать в основной.
  • Компактное представление записи: я не форматирую сообщение прямо в рабочем потоке, я пишу в буфер непосредственно messageId+arguments Во-первых, это гораздо компактнее, чем готовое сообщение (чаще всего, но не всегда — нашел у себя в проекте пару изощренных контрпримеров), а размер сообщения сильно влияет на время записи. А во-вторых, снимает с рабочих потоков задачу форматирования. Разумеется, это так легко и эффективно получилось только вкупе с предыдущим пунктом — если добавлять кроме примитивов хотя бы даже строки, подозреваю, эффективность заметно упадет.
  • Вариабельный размер записи. Это интересная тема, про которую меня регулярно спрашивали в контексте дизраптора и кольцевых буферов вообще. На пальцах казалось, что ничего принципиально сложного нет, но случая проверить до сих пор не выпадало. На первый взгляд непонятно, зачем это здесь, но я прицеливался в то, чтобы на каком-то этапе в будущем можно было использовать в качестве буфера memory-mapped file, и тогда оставлять много пустых мест кажется плохой идеей. Исходя из этой задумки я и решил, что вот он мой шанс наконец-то попробовать. Реализовывать эту штуку было очень интересно, но возникает много тонкостей. В целом мой вывод: для себя интересно, но если нет реальной необходимости, на работе лучше не заморачиваться и использовать записи фиксированного размера, гораздо проще выходит

На чем в основном тратим время? Вполне предсказуемо: где-то 2/3 времени примерно поровну делят между собой addAndGet на выделении записи и собственно запись данных в буфер. Остальная треть приходится на все остальное, типа thread local-ов и прочих накладных расходов. В принципе, у меня есть идея как несколько ускорить выделение записей, но надо еще думать.

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

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

10 ноября 2012 г.

Для тех, кто не решился написать ответы к предыдущему посту

Моя душа несколько успокоилась, когда все комментировавшие предыдущий пост дали правильные ответы. А то я так часто слышу про vwrite hb vread, что начал сомневаться, помнит ли вообще кто-то, что это не совсем верное утверждение.

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

Другими словами, не существует никаких ребер happens-before между строками кода в программе — ребра существуют в конкретном сценарии выполнения этого кода (в оригинале звучит как execution — сценарий, или маршрут выполнения. Но однажды я услышал термин "трасса над кодом", и он подкупил меня своей образностью, так что я часто использую его). Нет HB между какой-то волатильной записью и каким-то волатильным чтением, есть HB между событием волатильной записи некоторого значения, и событием волатильного чтения его же (из той же переменной, понятно).

А вот вопрос немного сложнее:

Thread 1

Thread 2

volatile int va;
int a;

va = 1;
a = 10;
va = 1;

if( va == 1 ){
int la = a;
}
Какие ребра существуют здесь?

7 ноября 2012 г.

Если вы знаете, что такое happens-before...

...то ответьте мне на несколько простых вопросов. Дан такой код:


Thread 1

Thread 2

volatile int va;

va = 10;

int b = va;


Вопросы (отвечать желательно по порядку, не забегая вперед):
  1. Какие здесь есть межпоточные ребра HB?
  2. Может ли в b оказаться что-то, кроме 10?
  3. Может ли в b оказаться 0?
  4. Изменится ли что-либо, если здесь заменить volatile store на lazySet?

18 октября 2012 г.

Off-heap: троллинг 70-го уровня

Последнее время я часто сталкиваюсь с идеей off-heap storage в java. Это когда DirectByteBuffer/Unsafe используют для организации данных вне java heap. Предположительно, это должно радикально снизить нагрузку на GC, да и, в некоторых случаях, сам доступ к данным ускорить. Сам я к этой идее относился довольно скептически: на мой взгляд у нее довольно узкая область применимости, и усилиями разработчиков JVM она становится с каждым годом еще уже. Мне кажется, многие, кто смотрит в сторону off-heap просто еще не разобрались толком, что можно делать на чистой java. Но пока это были все теоретические предположения — с Unsafe я проводил лишь один небольшой эксперимент, и, хоть предположения он, косвенно, и подтвердил, но одного эксперимента для выводов явно недостаточно. А сделать серьезный бенчмарк как-то было лениво.

И вот судьба подбросила мне шанс :) Если вы читаете мой блог, вы наверняка смутно помните Мартина Томпсона, автора Disruptor-а. Он, как это не удивительно, тоже тот еще графоман, и ведет свой блог. Вот сегодня, собственно, появилась интересная статья Compact Off-Heap Structures/Tuples In Java. Я не буду пересказывать статью, чай, английский все знают, сами почитайте. Вкратце, Мартин сравнивает организацию массива структур (т.е. объектов только с примитивными полями) на чистой яве, и выделяя через Unsafe.allocateMemory кусок off-heap memory, и сохраняя туда данные в C-стиле через соответствующие методы Unsafe.putLong/putInt....

И в его бенчмарках разница получается просто невероятная: off heap подход более чем в 40 раз быстрее! Мой червячок сомнения на этом месте внезапно вырос до 40-ка метрового глиста: нет, я догадываюсь, что Unsafe может дать какой-то прирост в определенных случаях, но в 40 раз??? Мартин, да ты что, охуелбелены объелся? Да, java-объекты "толще" чем C-структуры, да, они менее локально расположены в памяти — но в 40 раз хуже? Масла в огонь подлило то, что Мартин уже не первый раз демонстрирует в блоге бенчмарки, написанные "на отъебись".

В общем, я решил что мое время настало: я скопировал бенчмарки Мартина, и начал их копать...
...Копать пришлось недолго, изюминка лежала на поверхности: во время выполнения бенчмарка Мартин включил и время инициализации "хранилища". В случае с off-heap это был просто Unsafe.allocateMemory(2.5Gb) + запись данных, а в случае с plain java это была аллокация массива на 50М элементов, и аллокация 50 миллионов объектов (+ запись данных, конечно)! Да, конечно, аллокация в яве очень быстрая — но если что-то даже очень быстрое повторить 50 миллионов раз... Кроме того, очевидно, ~2Гб аллоцируемых объектов не вместятся в молодое поколение. Значит прямо параллельно с аллокацией будет запускаться minor GC, копировать объекты из поколения в поколение, переводить их в old gen, дефрагментировать память... В общем, я убрал инициализацию из измеряемого участка, и разница внезапно драматически сократилась — навскидку где-то до 30-40%.

На этом можно было бы успокоиться, но мне показалось, что я вижу еще несколько грязных моментов в дизайне бенчмарков, и мне хотелось их исправить. Кроме того, хотелось потестить еще одну, свою реализацию хранилища: на базе long[]. Она давно напрашивалась — фактически, каждый раз, когда я слышу про off heap мне хочется спросить, пробовали ли авторы реализовать все то же самое, только не над off heap memory, а сначала над обычным byte[]/int[]/long[]? Так можно было бы сравнить, какой прирост мы получаем от уменьшения уровня абстракции (отказ от объектов с именованными полями доступных по ссылке, в пользу прямой адресации ячеек какого-то примитивного типа, лежащих последовательным куском в памяти), а какой — от того, что сами ячейки мы располагаем за пределами управляемой кучи.

В общем, я переписал бенчмарки на свой лад, и начал играться. И обнаружилось много вкусного :)

Во-первых, Мартин, похоже, недостаточно долго гонял бенчмарки. Я, как это часто делаю, проводил измерения в двух вложенных циклах: на каждой итерации внешнего цикла я пересоздаю хранилище заново, и делаю с этим хранилищем несколько итераций внутреннего цикла. На каждой итерации внутреннего цикла я сначала записываю какие-то данные в хранилище, потом их же оттуда считываю. Таким образом, у меня получалось на каждый запуск JVM 13 раз пересозданное хранилище, и по 7 прогонов с каждым экземпляром. Я не выделяю отдельно прогрев — просто вывожу все результаты, и смотрю, с какой итерации они более-менее стабилизируются. У меня они стабилизировались с 20 итерации (со 100М записей, против 50М у Мартина). А в оригинальных бенчмарках всего-то было по 5 итераций. Есть хороший шанс, что Мартин тестировал какой-то полу-интерпретируемый код.

Во-вторых, в случае с обычными джава-объектами (в управляемой куче) первая итерация с пересозданным хранилищем часто обрабатывается медленнее, до 1.5-2 раз, чем последующие (даже когда, по всем признакам, JIT уже завершил свое темное дело). Что это такое я точно сказать не могу, но моя версия — это недозавершенный GC. То есть параллельно с первым прогоном на новом хранилище еще идут фоновые сборки, доперемещающие какие-то объекты между поколениями, да еще есть дефрагментация старого поколения. Очевидно, если объекты туда-сюда перемещаются, работа с ними будет медленнее. Ко второму прогону все уже стабилизируется, объекты плотно упакованы в old gen, и работа с ними становится быстрее. Опять же, поскольку Мартин создавал новое хранилище на каждый прогон, то в случае с in-heap хранилищем он, похоже, измерял его производительность как раз в таком переходном режиме.

Теперь что у меня получилось в итоге. Измерялось время (ms), уходящее на обработку 100M записей. Три участника забега: DirectMemory (aka off-heap), Pojo (plain java), LongArray (на базе long[]). Два режима: чтение и запись. Оркестр, фанфары...

Direct Pojo LongArray
Read 278±113 376±161 234±95
Write 639±270 753±320 325±133


Любопытно. Нет, то, что невероятное преимущество off-heap развеялось как дым — лично для меня не особо удивительно. Примерно в 1.5 раз быстрее на чтение, примерно на 20% на запись — это звучит более-менее разумно. Это легко понять, объяснить и даже предсказать, если вспомнить, что java-объект будет по размеру где-то на 1/3 больше, чем его off-heap коллега — за счет object header и всего подобного. Больше размер, больше памяти сканировать, здесь все понятно.

А вот для меня оказалось очень интересно (и неожиданно) что long[] хранилище обставило с внушительным разрывом всех остальных. Я ожидал, что pojo будет отставать от Unsafe на 30-50%, а long[]-based будет немного отставать от Unsafe (за счет range-check, и за счет конверсий int/char <-> long). Но, похоже, я недооценил во-первых насколько лихо JIT сейчас расправляется с range check. Во-вторых — мое предположение, что JIT, сообразив, что я гоняю его линейно по массиву, что-то еще наоптимизировал из этого. То ли просто loop unrolling, то ли префетчинг. Вроде бы, правда, префетчинг JIT не вставляет, полагается на аппаратный, но чем черт не шутит?

UPD: Как мне совершенно правильно указал в комментариях Олег (а люди с другими именами — куда смотрели, а?) я в реализации LongArrayTradeArray спорол хуйнюдопустил непростительную ошибку с вычислением индекса в массиве. Скорректированная версия дает несколько другие результаты:

Direct Pojo LongArray
Read 278±113 376±161 273±114
Write 639±270 753±320 333±140
В итоге общий вывод мало изменяется — все равно long[] в одном порядке с DirectMemory. Но непонятно откуда взявшийся прирост при этом пропадает (Олег сообщает, что на его JVM long[] даже на 10% медленнее direct). С одной стороны расклад становится понятнее, никаких сюрпризов. С другой — оригинальный срыв покровов, конечно, выглядел интереснее. Эх, я начинаю понимать Мартина... :)


Тут хочется добавить, что массив long[] — это один-единственный объект, так что, очевидно, он мало напряжет GC. Правда, это верно только для old gen — потому что в young gen работает копирующий GC, которому важен размер объекта, а не только количество объектов/ссылок — но для больших структур данных это, опять же, не очень актуально, очевидно они будут использоваться достаточно долго, чтобы твердо укорениться в old gen (кроме того, действительно большие структуры данных уже изначально не поместятся в young gen, и будут сразу аллоцированы в old generation). То есть такой подход, использующий обычный java-массив, и по нагрузке на GC не должен уступать off heap подходу. Остается еще тема с размером доступной памяти — массивы-то в яве ограничены 2G элементов. И если вам нужно больше 16Гб (2G*long) данных одним куском — вам нужно либо таки идти за пределы кучи, либо вводить дополнительный уровень косвенности, собирая структуру из нескольких массивов (как это делают в HugeCollections) — это, очевидно, несколько просадит производительность.

P.S. Код бенчмарков здесь, если кому вдруг интересно

P.P.S. Да, а Мартин — он, похоже, так троллит и пиарится. Вряд ли инженер его уровня не знает, как писать правильные бенчмарки. Скорее, ему просто впадлу все это расписывать в блоге, а 40 раз звучит ярче, чем 30% :)

14 октября 2012 г.

StampedLock

На днях в concurrency-interest Даг Ли объявил о выходе альфа-версии StampedLock-a. Это довольно интересный вариант ReadWriteLock-а, с возможностью ультра-оптимистичных чтений практически без contention. Он дает ограниченную функциональность обычного ReadWriteLock (в частности, нет reentrancy), но добавляет методы tryOptimisticRead()/validate(stamp), и tryConvertToWriteLock(stamp). По-сути, это попытка сделать версионную структуру данных: каждый захват блокировки возвращает уникальный (ну, почти — это все-таки обычный long, который через пару лет непрерывного использования может начать повторяться) идентификатор. Этот идентификатор можно рассматривать как номер текущей версии данных, защищаемых данной блокировкой. И, используя этот идентификатор можно делать очень дешевое спекулятивное чтение:
private long x, y;
...
double distanceFromOriginV1() { // A read-only method
     long stamp;
     if ((stamp = sl.tryOptimisticRead()) != 0L) { // optimistic
       double currentX = x;
       double currentY = y;
       if (sl.validate(stamp))
         return Math.sqrt(currentX * currentX + currentY * currentY);
     }
     stamp = sl.readLock(); // fall back to read lock
     try {
       double currentX = x;
       double currentY = y;
         return Math.sqrt(currentX * currentX + currentY * currentY);
     } finally {
       sl.unlockRead(stamp);
     }
}

(Пример из javadoc). Как можно видеть, такое спекулятивное чтение довольно громоздко с точки зрения кода. Кроме того, код этот нужно писать очень аккуратно: в частности, все необходимые вам чтения должны быть выполнены между tryOptimisticLock()/validate(stamp). Это не кажется большим ограничением, пока не заметишь, что "все" означает "прямо совсем все, вплоть до примитивных типов". В примере выше все поля и так примитивны, и эта тонкость не бросается в глаза. Сложность возникает если поля -- это ссылки на объекты (например, на массив). Так вот, в этом случае вы не можете прочитать, скажем, ссылку на объект, и после validate(stamp) прочитать поля этого объекта, и как-то их использовать! Вы должны добраться до реально необходимых вам в дальнейшем примитивных полей (или ссылок — но только в том случае, если вы дальше ссылки используете только для сравнения, но не для разыменования с целью доступа к полям объекта по ссылке). Более того, вы не можете внутри блока tryOptimisticLock()/validate(stamp) делать ничего, что не сможете откатить, если validate(stamp) не пройдет. Собственно, лучше там вообще ничего кроме чтений не делать. Блок tryOptimisticLock()/validate(stamp) — это способ получить непротиворечивое представление данных, а все операции с этими данными лучше делать после, когда успешный validate(stamp) даст вам право считать, что полученные данные действительно не противоречивы (==нет шанса, что кто-то вклинился, и изменил часть их, пока вы дочитывали другую часть).

Собственно, что здесь самое интересное. Дело в том, что, если опустить детали, то весь этот tryOptimisticLock()/validate(stamp) реализуется очень просто:
class StampedLock{
   private volatile long stamp;
   public long tryOptimisticRead(){
       return stamp;
   }
   public boolean validate(final long stamp){
       return this.stamp == stamp;
   }
}
Как можно видеть, основная особенность этого кода, по сравнению с обычным ReadWriteLock в том, что здесь нет ни одной записи. Это и есть та самая killing feature StampedLock-а, из-за которой весь сыр-бор. Она дает самое идеальное масштабирование чтений в многопроцессорном окружении, которое только возможно, ибо чистые чтения скалируются так хорошо, как это только возможно.

Казалось бы, если все так круто, почему это 100 лет назад еще не реализовано? Ответ очень простой: вот прямо так это работать не будет. Точнее, JMM не гарантирует, что это будет работать. Тонкость в деталях: чтобы чтения, выполненные между tryOptimisticLock() и validate(stamp) гарантировали непротиворечивое представление данных, нужно чтобы эти чтения нельзя было вынести из блока tryOptimisticLock()/validate(stamp). Так вот, волатильное чтение в tryOptimisticLock() гарантирует, что идущие после него обычные чтения не могут быть вынесены до него — тут все хорошо. Но волатильное чтение с проверкой в validate(stamp) не гарантирует, что обычные чтения, идущие до него в program order не будут переставлены после него! JMM не запрещает рантайму преобразовать вот этот код
private long x, y;
...
double distanceFromOriginV1() {
     long stamp;
     if ((stamp = sl.tryOptimisticRead()) != 0L) { // optimistic
       double currentX = x;
       double currentY = y;
       if (sl.validate(stamp))
         return Math.sqrt(currentX * currentX + currentY * currentY);
     }
}
Вот в такой:
private long x, y;
...
double distanceFromOriginV1() { // A read-only method
     long stamp;
     if ((stamp = sl.tryOptimisticRead()) != 0L) { // optimistic
       if (sl.validate(stamp)){
         //чтения вынесены из защищенного блока!
         double currentX = x;
         double currentY = y;
         return Math.sqrt(currentX * currentX + currentY * currentY);
       }
     }
}
И это и есть та причина, по которой StampedLock до сих пор не был реализован в JDK, а все попытки его реализовывать самостоятельно либо были некорректными, либо таки-использовали запись в своих версиях validate(). (Еще одной причиной, наверняка, является ультра-консервативность авторов j.u.c: они стараются не включать в стандартную библиотеку код со сложными сценариями использования. Хотя последнее время им приходится)

Собственно, как раз недавно я читал статью Hans Boehm-а, где он анализировал этот самый StampedLock, и пришел к выводу, что нет способа реализовать его без записей используя примитивы, задаваемые JMM. Просто в JMM нет операций, которые бы имели семантику чтения, и при этом давали бы двусторонний барьер памяти. В рамках JMM нужно как минимум что-то вроде CAS(stamp, stamp), чтобы одновременно проверить значение, и эмулировать double-sided membar — но это-таки будет запись (да плюс еще #lock на шине), и это гробит всю идею write-less read locking.

Тогда вопрос, как же это сделал Даг Ли? Ответ простой: Даг читер :) Он воспользовался тем, что, хотя JMM этого и не требует, и не гарантирует, но фактически Unsafe.getLongVolatile() таки имеет семантику двустороннего барьера. Разумеется, чтобы это знать, и чтобы быть уверенным, что в дальнейшем семантика не поменяется — надо быть на короткой ноге с авторами JVM. И это именно то, чем Даг может похвастаться :) Что позволено Юпитеру...

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

9 октября 2012 г.

Видео с jug.ru

Уже готово. Огромное спасибо организаторам. Сам еще не смотрел :)

Посмотреть видео на сайте Лекториума

5 октября 2012 г.

Thread affinity binding

По следам выступления на jug.ru:

Меня спрашивали, как я задаю affinity потокам в яве в бенчмарках. Начнем с того, что из чистой явы это сделать нельзя. Но если нельзя, а очень хочется — то таки можно. Долгое время я пользовался на скорую руку сварганенным методом, подсмотренным где-то на stackoverflow. Потом какое-то время участвовал в разработке библиотеки Java-Thread-Affinity, от Питера Лоурея. В принципе, она довольно неплоха, и я могу ее вполне рекомендовать.

Однако, на мой взгляд, она предлагает слишком высокоуровневый подход. Мне самому кажется более привлекательной идея сначала разработать достаточно универсальное низкоуровневое API — просто удобным образом оттранслировать в яву стандартную функциональность ОС. А уж потом на этом фундаменте экспериментировать с различными вариантами высокоуровневого API. Потому что мне видится, что высокоуровневых API может быть несколько вариантов, под разные задачи, а вот низкоуровневое определяется системными возможностями, и разнообразие здесь существенно меньше, и легче найти такой вариант, который будет подходить для всех. Так что еще какое-то время назад я озадачился разработкой low-level affinity API.

Текущий (по-правде говоря — довольно черновой) вариант можно посмотреть здесь.

Как подключить?
Через maven:
<repository>
   <id>java-affinity-binding.googlecode.com</id>
   <name>AB Repository for Maven</name>
   <url>http://java-affinity-binding.googlecode.com/svn/repo/</url>
</repository>
...
<dependency>
   <groupId>org.affinity</groupId>
   <artifactId>affinity</artifactId>
   <version>0.1.1-SNAPSHOT</version>
</dependency>
Как пользоваться?
Стартовая точка — статическая фабрика ThreadAffinityUtils. Через интерфейс CPULayoutService можно получить список доступных вычислительных блоков (CPU), а ThreadAffinityService позволяет задать список ядер, на которых текущий поток может выполняться.
final ThreadAffinityService affinityService = ThreadAffinityUtils.defaultAffinityService();
if( affinityService.isActuallyAvailable() ) {
   final CPULayoutService layout =ThreadAffinityUtils.defaultLayoutService();
   final CPU cpu = layout.cpu( 0 );
   affinityService.restrictCurrentThreadTo( cpu );
} else {
   System.out.println( "Affinity binding is not supported by current OS" );
}
Как это работает?
Да просто дергаем sched_setaffinity на POSIX-системах, и SetThreadAffinityMask на Windows. Дергаем через JNA, это позволяет не связываться с JNI напрямую, и не возиться самим с поддержкой различных платформ и компиляцией бинарников под каждую (этот гемморой берут на себя авторы JNA, за что им большое человеческое спасибо, искренняя уважуха, лучи добра и дай бог жену хорошую)
Но ведь JNA медленнее JNI?
Да, медленнее. Но мне кажется, здесь это не принципиально — часто перепривязывать потоки с ядра на ядро не очень хорошая идея, скорее всего эти операции вообще будут делаться всего несколько раз за все время жизни потока. Так что несколько дополнительных миллисекунд погоды не делают
Где это работает?
На Windows и Linux точно. По-идее, будет работать так же на любых POSIX системах, но есть свои нюансы. Например, на Mac OS не работает — несмотря на то, что sched_setaffinity там есть, но семантика у него иная, нам не подходящая.
Ограничения
В текущей версии задавать привязку можно только для текущего потока (того, который вызывает .restrictCurrentThreadTo()). Для вмешательства в другой поток нужно узнать его native thread id, а как это сделать "снаружи" этого потока я пока не нашел. Thread.getId() возвращает просто порядковый номер потока в JVM, он не имеет ничего общего с native tid. Конечно, узнать список tid-ов текущего процесса можно — но ведь надо как-то отобразить их на джавовские потоки... В общем, привязать, скажем, GC к какому-то ядру пока не получится, получится только те потоки, в код которых вы можете вставить соответствующие вызовы

Код использовался в бенчмарках, но еще ни разу не использовался в рабочих приложениях. Если что — похороны за ваш счет.

15 сентября 2012 г.

AtomicFieldUpdater optimized

AtomicXXXFieldUpdater — чудесные классы, открывающие значительную часть магии Unsafe без проблем с безопасностью и переносимостью. К сожалению, есть некоторая цена. Вот цитата из AtomicLongFieldUpdater.CASUpdater:

public void lazySet(T obj, long newValue) {
  if (obj == null || obj.getClass() != tclass || cclass != null) 
    fullCheck(obj);
           
  unsafe.putOrderedLong(obj, offset, newValue);
}
private void ensureProtectedAccess(T obj) {
  if (cclass.isInstance(obj)) 
    return;
  throw new RuntimeException (
        new IllegalAccessException("Class " + cclass.getName() + 
            " can not access a protected member of class " + tclass.getName() +
            " using an instance of " + obj.getClass().getName()
        )
  );
}
private void fullCheck(T obj) {
  if (!tclass.isInstance(obj))
    throw new ClassCastException();
  if (cclass != null)
    ensureProtectedAccess(obj);
}  

Выглядит все довольно страшно, хотя на практике в большинстве случаев все закончится на первых трех проверках: (obj == null || obj.getClass() != tclass || cclass != null). Эффект от них невелик, в моих бенчмарках замена AtomicUpdater на Unsafe давала 15-20% максимум в очень нагруженном конкурентном коде. По-видимому, дело в том, что результат этих проверок в правильно написанном коде всегда одинаков (false), поэтому предсказатель ветвлений в процессоре довольно быстро сообразит, какая из веток реализуется со 100% вероятностью, и будет спекулятивно выполнять код дальше. Тем не менее, иногда не хочется терять и этих процентов.

Хорошая новость состоит в том, что AtomicLongFieldUpdater — абстрактный класс, и никто не мешает вам написать свою реализацию. Например, взять за основу AtomicLongFieldUpdater.CASUpdater, и просто выбросить все "лишние" проверки. Результат будет практически drop-in-replacement для большинства сценариев использования.

Разумеется, у меня сразу возникла мысль сделать какую-то свою фабрику, на замену AtomicLongFieldUpdater.newUpdater(...), которая по-умолчанию делегировала бы к AtomicLongFieldUpdater.newUpdater, а при указании специального свойства -Djava.concurrent.run-faster начинала бы использовать оптимизированную версию. Плохая новость состоит в том, что так не получается: в конструкторе AtomicFieldUpdater-а проверяется, что вы можете создать AtomicUpdater только для того поля, которое вы и так можете видеть из создающего кода. Если я собираюсь обновлять private поле, то AtomicUpdater для него я смогу создать только изнутри этого же класса. И значит выбор реализации AtomicUpdater-а придется делать внутри каждого класса, его использующего.

4 августа 2012 г.

HotSpot OSR

Довольно старая уже, но от этого ничуть не менее интересная статья в блоге Cliff Click (это главный инженер Azul) про тонкости JIT-компиляции.

Клифф рассказывает чем отличается "обычная" компиляция метода, и компиляция в режиме On-the-stack-Replacement (OSR), и почему эту разницу стоит иметь в виду.

Обычная компиляция случается когда JVM обнаруживает, что какой-то метод достаточно горячий, чтобы его имело смысл скомпилировать. Для этого с каждым методом связывается счетчик, который считает число вызовов метода, и число обратных переходов (backedge) (т.е. переходов "назад" по потоку инструкций) внутри метода (sic!). Вторая часть может показаться непонятной, но это просто способ считать итерации циклов, если они в методе есть. Таким образом метод будет считаться горячим не только если он часто вызывается, но и если сам он вызывается не очень часто, но внутри него есть достаточно "тяжелые" циклы.

Когда счетчик перевалит за какой-то порог (скажем, 10 000) — последовательность байт-кодов метода ставится в очередь на компиляцию. При первой же возможности JIT до нее доберется, скомпилирует, и заменит ссылку в таблице методов на оптимизированную версию. И при очередном, 11 042-м вызове исполнение пойдет уже в скомпилированный и оптимизированный метод.

Здесь все круто, но есть одно "но": чтобы подменить интерпретируемую версию компилированной нужно "выйти и снова зайти" — выполнение метода должно завершиться, и тогда очередной вызов этого метода будет уже выполнять скомпилированный код. А что делать, если внутри метода тяжелые циклы — ждать пока он в интерпретируемом режиме завершится? "Клинический" случай это когда я прямо в main написал какой-то сложный алгоритм с тройной вложенности циклом — получается, у меня вообще нет шансов увидеть его скомпилированным.

Чтобы JIT в таких ситуациях не ударял в грязь лицом, ему нужно уметь заменять версии метода на лету, прямо по ходу его выполнения. Именно такая махинация и называется подменой "на стеке", On the Stack Replacement, OSR.

Надо сразу сказать, что задача эта в общем случае очень нетривиальна, ведь скомплированная версия должна полностью "принять в наследство" от интерпретируемой текущее состояние выполнения. Но скомпилированная и интерпретируемая версии кода могут (и почти наверняка будут) очень по-разному это состояние хранить. Клифф приводит в пример простейший цикл вычисления хэш-кода строки: hash = hash*31 + ary[i]; — состояние интерпретатора будет состоять из hash, arr, i, в то время как JIT скорее всего будет хранить что-то вроде hash, p = A+12+i*2, и инкрементить p+=2 на каждой итерации. Если здесь переход вам кажется несложным, то представьте, что будет если JIT еще и развернет (unroll) цикл? Получается, для OSR мало сгенерировать сам код метода — нужно еще и сгенерировать код-"адаптер", который сможет преобразовать состояние интерпретатора в тот вид, который нужен скомпилированной версии. Но генерация такого адаптера для произвольной точки кода будет очень сложной. Проще заранее фиксировать некий набор safepoint-ов, в которых только и можно "переключаться" — тогда задача становится обозримой.

Собственно, "обычный" (не-OSR) компилятор использует в качестве таких safepoint-ов границы между методами. OSR же добавляет возможность переключаться на backedge-ах циклов.

До сих пор была довольно общеизвестная информация, ее давно и много где можно встретить. А вот что интересно: поскольку обычная и OSR компиляция стартуют с разных точек в коде, то для одного и того же метода в режиме обычной и OSR компиляции JIT получает на вход разные последовательности байткодов. OSR получает как бы "вывернутую" изнутри наружу версию кода. И результат компиляции может довольно сильно отличаться. Клифф сначала приводит простой пример: вот так выглядит код метода с простым циклом
i=0;
    loop:
    if(P) goto done;
      S3; A[i++];
    goto loop; // <<--- OSR HERE
    done:
    S2;
А так он будет выглядеть для JIT-а в случае OSR компиляции:
A=value on entry from interpreter;
    i=value on entry from interpreter;
    goto loop;
    loop:
    if(P) goto done;
      S3; A[i++];
    goto loop;
    done:
Здесь пока все довольно прозрачно: это все еще очевидно цикл прохода по массиву с шагом 1, и все оптимизации к нему все еще применимы. Но вот если взять вложенный цикл все становится сложнее:
loop1:
    if(P1) goto done1;
      S1; i=0;
      loop2:
      if(P2) goto done2;
        S3; A[i++];
      goto loop2; // <<--- OSR HERE
      done2:
      S2;
    goto loop1;
    done1:
Если представить себе, как будет выглядеть этот цикл с точки зрения OSR (это требует некоторого напряжения):
A=...value on entry from interpreter...
    i=...value on entry from interpreter...
    goto loop2;
    loop2:
    if(P2) goto done2;
      S3; A[i++];
    goto loop2;
      done2:
      S2;
      goto loop1;
      loop1:
      if(P1) goto done1;
      S1; i=0;
    goto loop2;
    done1:
   ....
Здесь уже не так-то просто разглядеть структуру цикла по массиву. Чуть упростив
A=...value on entry from interpreter...
    i=...value on entry from interpreter...
    loop2:
      if(P2) {
        S2;
        if(P1) goto done1;
        S1; i=0;
      } else {
        S3; A[i++];
      }
    goto loop2;
    done1:
    ....
В чем здесь проблема? — проблема в том, что эвристики компилятора уже не узнают здесь "итерацию по массиву". А значит у нас не будет range check elimination, и, возможно, еще каких-то вкусных плюшек. Производительность этого кода может быть раза в 2-3 хуже, чем не-OSR версии.

Что можно сделать, чтобы избежать такой ситуации? Клифф рекомендует вместо "цикл внутри цикла внутри цикла" организовывать код как "цикл внутри функции внутри цикла внутри функции" -- т.е. выделять каждый потенциально тяжелый цикл в отдельный метод. Во-первых, так увеличивается вероятность, что внутренний цикл будет скомпилирован в не-OSR режиме, а во-вторых, метод с одним циклом, даже вывернутый наизнанку OSR-ом, все равно остается достаточно простым для компилятора.

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

31 июля 2012 г.

Disruptor 3.0

ТАСС уполномочен заявить, что скоро выходит третья версия Disruptor-a. Michael Barker, который его сейчас развивает, дразнится — обещает прирост в производительности почти вдвое.

Если честно, мне сложно представить, чем еще можно ускорить простейший single publisher single subscriber случай. Но одно предположение у меня есть. Когда я гонял бенчмарки перед JavaOne, я пробовал заменять AtomicLongFieldUpdater.lazySet() на Unsafe.putOrderedLong(). Это то же самое по смыслу, но отсутствуют различные проверки доступа и type-safety. Разница была довольно существенной. Правда, не вдвое, процентов на 20-25. Но, поскольку больше возможностей я не вижу, то я ставлю на то, что в третьей версии Disruptor появится магический класс sun.misc.Unsafe.

Хотя будет гораздо интереснее, если я ошибусь, и будет что-то новенькое :)

28 июля 2012 г.

Синтаксический сахарочек

Вообще, java нас не балует синтаксическим сахаром. Лично мне это даже очень нравится — терпеть не могу выкапывать суть под горой сладкого. Из-за этого отказался от мысли перейти на Scala — побоялся диабет схватить. Но иногда хочется все-таки сделать своему компоненту такой сладенький интерфейс, чтобы пальчики оближешь. И когда я нахожу в аскетической джаве какую-нибудь карамельку — я очень радуюсь :)

Например, есть у нас такой класс-мэппер
public class Mapping{
  public String map(final String arg1, final String arg2);
}
И есть какая-то реализация, скажем SimpleImmutableMapping, и хочется сделать для его конфигурирования фабрику-билдер, типа вот такой:
public class MappingBuilder{
    public MappingBuilder map( final String arg1 ){...}
    public MappingBuilder with( final String arg2 ){...}
    public MappingBuilder to( final String mapping ){...}

    public Mapping build(){...}
}
...
final Mapping mapping = new MappingBuilder()
                           .map( "A" ).with( "B" ).to("ab")
                           .map( "C" ).with( "D" ).to("cd")
                           .map( "E" ).with( "F" ).to("ef")
                           .build();
Что мне здесь не нравится? — мне не нравится дуракоустойчивость. Особенно мне не нравится то, что ее здесь нет, и это хорошо видно на скриншоте справа (Да, это у меня такая цветовая схема, нет, глаза не устают, да, мне нравится, идите в жопу).
Что будет, если я вызову в этой точке .build()? Очевидно, ничего хорошего. В лучшем случае уже во время выполнения вылетит IllegalStateException("Can't build mapping with supplied data: first argument is not enough"). Это если я позаботился о том, как мой объект себя ведет, если его используют "неправильно". В более реальном случае будет что-нибудь вроде NullPointerException из недр метода .build(). В самом паршивом случае здесь все отработает без ошибок, а веселье начнется при использовании созданного Mapping-а где-нибудь совсем в другом месте.

Так вот, я раньше думал, что устроить в подобном Builder-е проверку времени выполнения — на яве не получится. А оказывается можно — правда так гемморойно как и все у нас, джавистов:
public class SimpleMapping {

  //код самого мэппера -- скучный и банальный
  .....

  //а вот дальше начинается треш и содомия
  //уберите от монитора женщин и детей, и глубоко вдохните 

  public interface FirstArgumentGivenState {
    public SecondArgumentGivenState with( final String arg2 );
  }

  public interface SecondArgumentGivenState {
    public FullMappingGivenState to( final String mapping );
  }

  public interface FullMappingGivenState {
    public Mapping build();
    public FirstArgumentGivenState map( final String arg1 );
  }

  private static class Builder implements
      FirstArgumentGivenState,
      SecondArgumentGivenState,
      FullMappingGivenState {

    public FirstArgumentGivenState map( final String arg1 ) {
      ...
      return this;
    }

    public SecondArgumentGivenState with( final String arg2 ) {
      ...
      return this;
    }

    public FullMappingGivenState to( final String mapping ) {
      ...
      return this;
    }

    public Mapping build() {
      ...
    }
  }

  public static FullMappingGivenState builder() {
    return new Builder();
  }
}
....
final Mapping mapping = SimpleMapping.builder()
    .map( "A" ).with( "B" ).to( "ab" )
    .map( "C" ).with( "D" ).to( "cd" )
    .map( "E" ).with( "F" ).to( "ef" )
    .build();
Попробуйте теперь вызвать что-то неправильно :)

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


По-правде, я не уверен, что придумать такое было хорошей идеей — встреть я такой адъ в чужом коде, матерился бы в голос. А ведь самому-то теперь будет сложно удержаться :)

Если серьезно, то мне кажется, делать такое в каждом Builder-е это over-engeneering. Сложность понимания "как, и зачем, черт подери, такое здесь наворочено" не окупает небольшого увеличения дуракоустойчивости. Но вот если какая-нибудь изолированная, часто используемая библиотека... Тогда к странным типам возвращаемых значений у методов Builder-а можно и привыкнуть, а вот compile time safety при широком использовании может вполне себя окупить.

Если что — похороны за ваш счет. Я предупреждал :)

UPD:Как мне подсказывает Александр в комментариях — это уже описано как паттерн Wizard. Было бы слишком оптимистично ожидать, что такую штуку еще никто не придумал. Статью рекомендую прочитать, примеры там забавные.