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. Было бы слишком оптимистично ожидать, что такую штуку еще никто не придумал. Статью рекомендую прочитать, примеры там забавные.

21 июля 2012 г.

Cache coherency #3: false sharing

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

False sharing

...Или ложное разделение. По-правде, не очень понятно, почему именно ложное — оно самое что ни на есть настоящее, только неожиданное. Что такое true sharing? — Это когда у нас есть ячейка памяти, используемая одновременно более чем одним потоком. В предыдущих статьях я уже рассказывал, что конкурентный доступ на чтение протоколы когерентности разруливают без особого труда, а вот конкурирующие чтение и запись, и особенно запись и запись заставляют их попотеть — здесь все понятно. А false sharing это когда ячейки памяти разные, но физически попадают на один и тот же cache line. С точки зрения программиста — никакого разделения данных нет, никакого конкурирующего доступа тоже. А с точки зрения подсистемы памяти каждый cache line — это одна ячейка, и операции доступа к разным частям одной строки кэша из разных ядер конкурируют друг с другом за эту ячейку-строку. И неожиданно оказывается, что обычная запись в какую-то локальную (казалось бы) переменную стоит в несколько раз дороже, чем должна была бы:
int threadId = 0, 1, 2, ... THREADS_COUNT;
int distance = 1..8; 
long[] area = new long[THREADS_COUNT*distance];

for(int i=0...Inf){
   area[threadId*distance] = i;
}
(Готовый к исполнению код здесь). Если увеличивать distance, то можно наблюдать, как время на выполнение цикла уменьшается, вплоть до distance=8 — для интелловских архитектур, где cache line 64 байта. (Строго говоря, нужно еще убедиться, что все потоки сели на разные физические ядра, но как правило, в случае незагруженной машины системный планировщик их сам так и раскидает)

Вообще, про false sharing не писал уже только ленивый. Я лично эту тему мусолил аж 4 раза, даже тэг для этого специальный завел. Поэтому я здесь хочу остановиться на другом вопросе, который мне как-то задали в комментариях: если все так легко может стать так плохо, почему это редко когда заметно? (Есть, конечно, вариант, что не замечают потому что и не смотрят — но это недостаточно сексуальный вариант)

У false sharing есть два ощутимых эффекта: увеличение в разы времени выполнения конкретной операции записи (memory latency), и увеличение нагрузки на шину. Чтобы заметить увеличение нагрузки на шину нужно либо специально ее мониторить, либо уже использовать шину близко к режиму насыщения. Но интелловский InterConnect имеет пропускную способность что-то вроде 20Гб/с в каждую сторону — а это 20 миллионов килобайтных сообщений в секунду (в нереальном случае 100% КПД). Не то, чтобы это было недостижимо круто, но не каждая птица долетит до середины Днепракаждое приложение подходит хотя бы близко к тому, чтобы насытить шину.

А что насчет memory latency? Ну, проблема медленной памяти перед разработчиками процессоров стоит уже лет 15, за это время было придумано масса трюков, позволяющих ее как-то обойти. Часть из них — те, что про введение иерархии кэшей — в случае с false sharing не помогут, потому что они сами и являются причиной. Но на уровне процессора остается еще пара тузов в рукаве, связанных с асинхронным выполнением операций с памятью. Например, современные процессоры содержат блок префетчинга, который может предсказать доступ к памяти до того, как исполнение дойдет до соответствующей инструкции, и отправить запрос на упреждающее чтение нужного блока в кэш. Другой пример: инструкции записи тоже обычно не ждут, пока запись фактически будет выполнена — команда на запись просто сохраняется в т.н. store buffer-е, и исполнение идет дальше, а команды из буфера спускаются контроллеру памяти в асинхронном режиме.

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

И отсюда можно попробовать порасуждать на тему, в каких случаях false sharing имеет наибольшую вероятность стать заметным.

Во-первых, когда нам важно именно время выполнения конкретной (небольшой) операции (latency, response time), а не пропускная способность в целом (throughput). Если наша операция содержит всего-то пару сотен инструкций, и несколько обращений к памяти, то заметное удорожание даже одного из этих обращений все-таки будет заметно. Процессору просто не за чем будет спрятать замедлившуюся операцию. Да, он может параллельно начать выполнять инструкции хоть из другого потока (через hyper threading), тем самым удерживая на уровне общую пропускную способность — но время выполнения конкретной операции от этого не уменьшится. Мы можем получить такую картину: система по-прежнему выполняет N операций в секунду, только время одной операции выросло с 1мкс до 2мкс. Поскольку далеко не каждого волнует время выполнение конкретной операции (особенно, когда масштаб этого времени — микросекунды), то на этой стадии false sharing часто остается просто незамеченным.

Дальше идут ситуации, когда операции с false sharing составляют заметную долю всех операций (по крайней мере, на критическом маршруте). Это как раз пример выше. Почему false sharing там заметен? Потому что там, кроме самой записи, только обвязка цикла, которая едва тянет на пару тактов. И одна-единственная запись, которая contended (счетчик цикла скорее всего будет сидеть в регистре). Даже если запись идет в L1 (~5ns) — она здесь будет доминирующей, и никакие трюки этого не замаскируют, потому что маскировать нечем. И если запись станет в разы дороже — это будет просто бросаться в глаза.

Ну и последний очевидный вариант — это когда у вас шина памяти уже близка к насыщению, и тут еще добавляется false sharing, и все становится грустно.

Т.е. получается, что в первую очередь false sharing беспокоит тех, кто разрабатывает latency-critical системы, и уж во-вторую — тех, кто разрабатывает очень high throughput, где-то близко к пиковой производительности железа.

P.S. Есть у меня еще такая любопытна идея: кажется, что чем мягче аппаратная модель памяти, тем больше у процессора возможностей "прятать" memory latency. Т.е. и прятать false sharing у него тоже больше возможностей. Однако сравнивать разные процессоры сложновато — они обычно отличаются слишком много чем, не только моделью памяти (да и где бы их все взять для тестов-то). Но можно ужесточить аппаратную модель памяти программно — расставляя барьеры памяти. Если взять тот пример, выше, и вместо обычной записи в ячейку массива делать volatile store (придется заменить массив на AtomicIntegerArray, или дергать Unsafe.putIntVolatile) — то сопутствующий lock xadd скорее всего приведет к принудительному сбросу store buffer-а. А значит не будет возможности отложить запись на "попозже", ее придется делать синхронно. Кажется, что это сделать false sharing еще более заметным.

Еще интереснее будет проверить это для Disruptor-а. На Java One меня спрашивали, почему padding в моих экспериментах никак себя не проявил — вот я сейчас думаю, что причина может быть как раз в том, что я экспериментировал с padding после того, как заменил volatile store для курсоров на lazySet (что эффект от оптимизаций некоммутативен — это не новость). Будет интересно, как появится возможность, проверить, что получится если сделать наоборот: вернуть volatile store, и поиграться с padding.

P.P.S. Вообще-то, эта статья планировалась как продолжение цикла про cache coherency. И про false sharing задумывалось как вступление и разминка. Но я что-то увлекся, и false sharing вылез на место главного героя, не оставив места запланированным атомикам. Ну я и подумал — пусть остается как есть, а атомики получат свою главную роль чуть позже :)

17 июня 2012 г.

Simple concurrent caches

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

Есть у нас доменный объект CurrencyEntity:
public final class Entity {
 private final String isoCode;

 public Entity( final String isoCode ) {
  this.isoCode = isoCode;
 }

 @Override
 public boolean equals( final Object o ) {
  if( this == o ) {
   return true;
  }
  if( !(o instanceof Entity )) {
   return false;
  }

  final Entity entity = ( Entity ) o;

  if( !isoCode.equals( entity.isoCode ) ) {
   return false;
  }

  return true;
 }

 @Override
 public int hashCode() {
  return isoCode.hashCode();
 }
}
(важно, что объект immutable). На вход (из сети, например) программа получает Entity в виде String isoCode, но внутри, понятно, хочется оперировать type-safe представлением. Однако создавать каждый раз новый экземпляр Entity не хочется -- зачем нагружать лишний раз GC? Кроме того, известно, что реально различных isoCode не так уж много -- ну, скажем, штук 100-200. Вот как бы так их кэшировать, чтобы кэш и конкурентным был, и накладные расходы минимальны (иначе кэшировать смысла нет -- создать/удалить такой мелкий объект чего-то стоит, но не так уж дорого)?

Вариант решения:
public class FastConcurrentEntityCache{
 private static final Object FREE = null;

 private final Entity[] entries;

 public FastConcurrentEntityCache( final int size ) {
  checkArgument( size > 1, "size[%s] must be >1", size );

  entries = new Entity[size];
 }

 public Entity get( final String isoCode ) {
  final int hash = isoCode.hashCode() & 0x7fffffff;

  final int length = entries.length;
  final int index = hash % length;

  Entity cur = entries[index];

  if( cur == FREE ) {
   //cache miss
   return evaluateAndStore( isoCode, index );
  } else if( cur.isoCode.equals( isoCode ) ) {
   //cache hit
   return cur;
  } else {// already FULL, must probe

   // compute the double hash
   final int probe = 1 + ( hash % ( length - 2 ) );
   int probedIndex = index;
   for( int i = 0; i < entries.length; i++ ) {
    probedIndex -= probe;
    if( probedIndex < 0 ) {
     probedIndex += length;
    }
    cur = entries[probedIndex];
    if( cur == FREE ) {
     //cache miss
     return evaluateAndStore( isoCode, probedIndex );
    } else if( cur.isoCode.equals( isoCode ) ) {
     //cache hit
     return cur;
    }
   }
   //cache miss, and cache is full 
   throw new IllegalStateException( "Cache[size:"+entries.length+"] is full: ["+isoCode+"]" );
  }
 }

 private Entity evaluateAndStore( final String isoCode,
                                  final int index ) {
  final Entity entity = new Entity( isoCode );
  entries[index] = entity;
  return entity;
 }

 public void purge() {
  Arrays.fill( entries, null );
 }
}

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

Подробности

Вопрос: Почему это работает? Ответ: А почему бы и нет? ;)

Вообще-то стоило бы чуть подробнее остановиться на том, как именно оно работает. Обычно предполагается, что если объект уже есть в кэше, то при запросе именно он и вернется. Но в данном случае, из-за отсутствия синхронизации, состав кэша может разными потоками видиться по-разному, так что понятие "объект есть в кэше" становится не очень определенным. Так что работать это будет так: если объект есть в кэше, и виден текущему потоку -- вернется он. Если не виден (или вообще нет) -- будет создан новый экземпляр. То есть кэш не сохраняет идентичность (preserve identity) -- для одного и того же ключа isoCode в программе могут существовать несколько разных экземпляров Entity.

Второй важный момент это то, что Entity -- immutable. В многопоточном окружении запись entries[index] = entity -- это публикация ссылки на объект. Без дополнительной синхронизации (а где она? а нет ее!) это будет публикация через data race. И только особые гарантии JMM для immutable объектов дают нам возможность утверждать, что если другой поток увидел ссылку на Entity, то он увидит через нее полностью инициализированный объект.

Собственно, здесь две ключевых идеи. Во-первых, ослабление семантики -- отказ от принципа один тюбик в одни зубы "для каждого ключа значение создается строго однажды". Во-вторых, использование immutable объектов для безопасной публикации через data race. Эти две идеи в сумме и позволяют обойтись без синхронизации.

Что еще можно с этим сделать?

Приведенная реализация подразумевает работу в стационарном режиме: через какое-то время все isoCode будут программе знакомы, и соответствующие Entity закэшированы, и видимы всем потокам единообразно. Т.е. через какое-то время новые экземпляры Entity создаваться перестанут. При этом важно, чтобы мы изначально угадали с размером кэша.

Но это не единственный вариант использования. Бывает другая задача: множество объектов в принципе не ограничено, но известно, что чаще всего используются недавние объекты. Т.е. хочется LRU кэш. И такое тоже можно:

public class FastLRUEntityCache{
 private static final Object FREE = null;

 private final Entity[] entries;

 public FastLRUEntityCache( final int size ) {
  checkArgument( size > 1, "size[%s] must be >1", size );

  entries = new Entity[size];
 }

 public Entity get( final String isoCode ) {
  final int hash = isoCode.hashCode() & 0x7fffffff;

  final int length = entries.length;
  final int index = hash % length;

  Entity cur = entries[index];

  if( cur == FREE ) {
   //cache miss
   return evaluateAndStore( isoCode, index );
  } else if( cur.isoCode.equals( isoCode ) ) {
   //cache hit
   return cur;
  } else {// already FULL, replace
   return evaluateAndStore( isoCode, index );
  }
 }

 private Entity evaluateAndStore( final String isoCode,
                                  final int index ) {
  final Entity entity = new Entity( isoCode );
  entries[index] = entity;
  return entity;
 }

 public void purge() {
  Arrays.fill( entries, null );
 }
}

Я убрал разрешение коллизий (probing). Теперь, если место для объекта уже занято -- мы просто затираем предыдущего жильца. Этот вариант, в отличие от предыдущего не страдает от запаздывающей синхронизации состояния кэша между потоками -- он ей наслаждается. В самом деле, разные потоки будут просто видеть свои LRU объекты!

Вопрос: А если у меня объект не immutable? Ответ: Если он не immutable, но фактически не меняется -- можно просто создать обертку

public class Freezer<T>{
   public final T item;
   public Freezer(final T item){
    this.item = item;
   }
}

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

Вопрос: А можно сделать кэш resizeable? Ответ: Можно, конечно. Но придется делать поле entities volatile -- что несколько увеличит стоимость обращения к кэшу. Я не стал с этим возиться.

Для пуристов, поясняю: да, сам по себе volatile load на широко используемых архитектурах ничего дополнительного не стоит, в сравнении с обычным load. Но он запрещает некоторые оптимизации. Например:

for( over 9000 ){
  final String isoCode = ...;
  final Entity entity = cache.get(isoCode);
  ...
}
Если entries является final (да и просто non-volatile), то компилятор может вынести его чтение за цикл. Если же entries volatile -- оно будет считываться на каждой итерации. Т.е. мы можем сэкономить что-то вроде (L1 load - register load) * (over 9000) тактов :)

Философское заключение про data race

Как мы могли увидеть, существование в програме data race сам по себе не является приговором "программа некорректная". Но существование гонки, как правило, резко увеличивает размер графа состояний программы, количество возможных сценариев выполнения. Если это не было предусмотрено -- есть близкая к 100% вероятность упустить какие-то сценарии, нарушающие заложенные в код инварианты. Но если распоряжаться гонками аккуратно, то можно осмысленно создать ситуацию, где граф состояний даже с гонкой остается обозримым. И тогда можно увидеть возможности для вот таких вот простых и эффективных решений.

Это я так, типа, хвастаюсь :)

20 мая 2012 г.

Тестирование и документирование

Я уже давно хожу с этой мыслью — решил про нее написать, и освободить в голове место для новых мыслей :)

Помимо основной задачи — проверять корректность работы и описывать работу приложения — у тестирования и документирования есть еще одна очень важная функция. Эта функция — давать разработчику возможность посмотреть на свой код, на свою архитектуру, с альтернативных точек зрения. Мне кажется, эту функцию часто недооценивают (если вообще про нее помнят) — а между тем она, кажется, очень важна. Может быть, иногда важнее основной. Я уверен, что хорошую архитектуру вообще невозможно создать без того, чтобы в процессе работы над ней смотреть на нее с 2-3-4 разных точек зрения.

Вот в ТРИЗ есть такой "оператор РВС" (размер-время-стомость) — психологический прием, помогающий взглянуть на решаемую задачу с нескольких непривычных точек зрения. Я бы его так и называл — оператор сдвига точки зрения :) Часто он помогает увидеть возможность для очень сильного решения. Вот кажется, что тестирование и документирование могут выполнять роль такого "оператора сдвига точки зрения" в разработке (хотя, собственно, сам РВС вполне можно использовать тоже).

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

В этом смысле тесты работают даже если их никто не запускает. А документация работает, даже если ее потом никто и не читает :)

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

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

6 мая 2012 г.

Вдогонку про публикацию

Вдогонку к предыдущему посту, и к вот этому посту Алексея. Для прояснения ситуации.

Итак, вот это
public class T {
   public int field1;
 
   public T( final int field1 ){
      this.field1 = field1;
   }
}
 
//...где-то в дебрях тундры...
public T sharedRef;
 
sharedRef = new T( 10 );
 
НЕбезопасная публикация

Вот это:
public class T {
   public int field1;
 
   public T( final int field1 ){
      this.field1 = field1;
   }
}
 
//...где-то в дебрях кода...
public volatile T sharedRef;
 
sharedRef = new T( 10 );
 
безопасная публикация -- потому что через volatile-ссылку.

Вот это:
public class T {
   public final int field1;
 
   public T( final int field1 ){
      this.field1 = field1;
   }
}
 
//...где-то в дебрях кода...
public T sharedRef;
 
sharedRef = new T( 10 );
 
безопасная публикация -- потому что для final-полей особые гарантии.

А вот это:
public class T {
   public volatile int field1;
 
   public T( final int field1 ){
      this.field1 = field1;
   }
}
 
//...где-то в дебрях кода...
public T sharedRef;
 
sharedRef = new T( 10 );
 

НЕбезопасная публикация -- потому что обычные записи (sharedRef=new T()) можно переставлять до волатильных записей! Поэтому волатильность поля field1 не гарантирует нам, что ссылка на объект T будет опубликована после инициализации этого поля.

UPD: В данном конкретном случае, когда в классе всего одно поле — публикация таки безопасна. Дискуссию по этому поводу можно прочитать здесь, а формальное доказательство здесь. Однако неочевидно, можно ли перенести это рассуждение на классы со "смешанным составом" полей (volatile+non volatile)

UPD по просьбам читателей: вот это
public class T {
   private int field1;
 
   public T( final int field1 ){
      synchronized( this ) {
         this.field1 = field1;
      }
   }
    
   public synchronized int getField1(){
      return this.field1;
   }
   
   public synchronized void setField1( final int field1 ){
      this.field1 = field1;
   }
}
 
//...где-то в дебрях кода...
public T sharedRef;
 
sharedRef = new T( 10 );
 
Это такая хитрая штука: формально публикация небезопасна, но фактически это ненаблюдаемо -- если вы не полезете к field1 какими-нибудь неправославными методами, то для доступа через геттер/сеттер все безопасно.

3 мая 2012 г.

(Un)Safe publication

Безопасная/небезопасная публикация ссылок — источник огромного количества ошибок в многопоточном коде. Мне иногда кажется, что таких ошибок вообще большинство. Т.е. если программист обладает >= базовыми знаниями по concurrency в яве, то почти наверняка он все равно частенько будет писать код, некорректный по JMM, и в большинстве случаев некорректность будет связана именно с понятием небезопасной публикации.

Да что я все о каких-то абстрактных программистах рассказываю. Давайте честно: unsafe publishing я регулярно обнаруживаю в своем собственном коде, и если бы только старом... Так нет — это, наверное, единственная ошибка, которую я продолжаю регулярно, раз за разом совершать при написании многопоточного кода.

Для такой распространенности есть две большие причины. Во-первых, публикация ссылки — это обманчиво простая операция. Не, ну что может быть проще, чем просто присвоить ссылку на объект какому-то полю, а? Очень сложно постоянно держать в памяти, что если этим присвоением ты делаешь объект доступным другому потоку — то вокруг сразу начинают виться драконы (да, да, и те самые тоже), и простая операция моментально становится очень непростой с точки зрения JMM.

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

Чуть подробнее...

(Не)Безопасная публикация

//есть у нас такой класс
public class T {
   public int field1;

   public T( final int field1 ){
      this.field1 = field1;
   }
}

//...где-то в дебрях кода...
public T sharedRef;

//Thread 1
sharedRef = new T( 10 ); //а почему бы и не 10? 42 сегодня взяла отгул

//Thread 2
System.out.println( "sharedRef.field1 = " + sharedRef.field1 );


Какие варианты вывода мы здесь можем наблюдать в соответствии с JMM?

Подразумеваемый вариант — все будет хорошо, ожидаемо выведется "10". Оставим эту скукотищу для стариков и женщин. Мы молоды духом, и готовы к приключениям — нам пожалуйста чтобы все ломалось, разрушалсь, взрывалось и горело, и чтобы еще секса побольше...

Ок, у меня есть специально для вас сценарий повеселее: NullPointerException. Сценарий здесь тоже довольно очевиден — поток №2 может прочитать значение sharedRef до того, как поток №1 туда запишет что-то. В таком случае поток №2 увидит значение по-умолчанию, null.

Мы такого варианта не хотим, поэтому делаем так:

//Thread 2
if( sharedRef != null ){
    System.out.println("sharedRef.field1 = " + sharedRef.field1 );
} else {
    //...
}

Увы, но здесь уже начинаются чудеса. А именно — мы все еще можем увидеть NPE в этом коде! Почему? Да потому что второе чтение sharedRef может вернуть совсем не то значение, что первое. В потоке №1 у нас есть две записи в sharedRef: первая, неявная — запись значения по-умолчанию (null). Вторая, явная — запись ссылки на созданный объект. С точки зрения потока №2 эти записи никак не упорядочены (==нет ребер hb, обязующих его видеть записи именно в "нужном" порядке), и он вполне может увидеть сначала запись sharedRef=new T(), и только потом sharedRef=null.

Disclaimer: Я не уверен на 100% действительно ли JMM допускает такие перестановки. Некоторые уважаемые люди с этим не согласны, а процедура определения возможных трасс для кода с гонками в JMM исключительно ебанутаясложная, и строго ее проходить никому не охота. Но для дальнейшего это не суть важно

Ок, это легко вылечить:

//Thread 2
final T localRef = sharedRef;
if( localRef != null ){
    System.out.println("sharedRef.field1 = " + localRef.field1 );
} else {
    //...
}

мы прикрыли свою задницу от NPE, и теперь уже можем сосредоточиться на выводимых значениях. А значений, увы, мы можем увидеть больше одного. Мы можем увидеть в выводе sharefRed.field1 = 10 — как и ожидалось. Неожиданным может быть то, что мы можем видеть и вывод sharefRed.field1 = 0. Причина все та же. Короткая строчка sharedRef = new T(10) на самом деле это целый ряд операций: (выделение памяти, заполнение полей значениями по-умолчанию, выполнение конструктора, запись ссылки в sharedRef). То, что в коде потока 1 они идут именно в таком порядке не означает, что поток 2 их увидит так же. Он совершенно спокойно может увидеть сначала присвоение ссылки на "пустой" объект с дефолтными значениями полей (увидеть ссылку до присвоения полям начальных значений он не может — это JMM явно запрещает). Более того, если бы в T было больше одного поля (field1, field2, field3...) мы могли бы увидеть в потоке 2 любую комбинацию из инициализированных/неинициализированных полей.

Эти вот два примера — это и есть суть того, что называется небезопасной публикацией, или, неформально, публикацией "через data race" (где здесь гонка — надеюсь, очевидно).

Смотрите, какая штука: в рамках каждого отдельного потока все инструкции упорядочены по happens-before (порядок HB согласован с т.н. program order — порядком инструкций в коде программы). И когда мы в потоке 2 читаем значение, записанное потоком 1 в sharedRef в строчке 14 — кажется очевидным, что раз мы его прочитали, значит эта запись произошла до нашего чтения! То есть интуитивное восприятие последовательности событий подсказывает, что сам факт чтения создает нам ребро HB — которое как раз и необходимо, чтобы весь код стал корректно синхронизированным.

И вот эта-то трактовка, кажущаяся настолько интуитивной-интуитивной, что даже в доказательстве не нуждается — она-то как раз и совершенно не верна. Фактический порядок исполнения инструкций в конкретном запуске программы — это совсем другое, нежели формальный порядок happens-before, верный для любого запуска этой программы на любом железе и под любой JVM. Это очень важный момент: если вы в ходе исполнения программы зафиксировали, что какое-то событие А произошло до события Б — это вовсе не значит, что можно утверждать, что A hb B.

Есть одно важное исключение — семантика final полей. Если бы поле field1 было бы финальным — то как раз сам факт чтения ненулевого значения sharedRef действительно порождал бы HB. Но это особое ребро HB, некоммутативное с обычными — подробнее я уже писал здесь.

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

Где-то я эту хрень уже видел...

Ну конечно. Unsafe publishing — это основа того, почему не работает double-checking locking:
private static DCLSingleton singleton = null;
public static DCLSingleton getInstance(){
   if( singleton == null ){
       synchronized( DCLSingleton.class ){
          if( singleton == null ){
              singleton = new DCLSingleton();
          }
       }
   }
   return singleton;
}

вот если какой-то поток видит singleton != null до захвата монитора — то он может видеть эту ссылку через data race. Как следствие — ссылка-то будет не нулевая, а вот содержимое может быть каким угодно.

Сюда же относится SettableFuture из этого поста — вот этот вариант:
public class SettableFuture<V> implements Future<V> {
    private V slot;

    public V get() throws InterruptedException, ExecutionException {
        synchronized( this ) {
            while ( slot == null ) {
                wait();
            }
        }
        return slot;
    }

    public void set( final V value ) {
        slot = value;
        synchronized( this ) {
            notifyAll();
        }
    }
}

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

Ан нет, не можем. Потому что если ссылка на этот объект будет опубликована небезопасно — методы объекта вызванные из не-инициализировавших потоков могут увидеть частично завершенную инициализацию.

Пуленепробиваемо потокобезопасный объект в яве можно создать лишь двумя способами. Первый, и самый лучший — делать его immutable. Для объектов с final полями при условии корректной инициализации Священное ПисаниеJMM отдельной главой гарантирует их безопасную работу в многопоточном окружении, даже при передаче через data race. Благослови боже immutability.

Второй, довольно некрасивый — защищать монитором все методы и еще и все конструкторы. Эта тема некоторое время муссировалась в cuncurrency-interests, и в итоге все Пророки согласились, что объект, у которого все поля закрыты, доступ к ним только через методы, а все методы и конструкторы защищены монитором — будет корректно работать, как его не передавай.

Проблема с этим, вторым, методом — в том, что о нем почти никто не знает. Существуют тонны примитивно-потокобезопасных объектов, со всеми методами synchronized, но много ли вы видели объектов с защищенным конструктором? Более того, в ранних версиях одной из священных книг (чуть ли не "Философии джавы") было даже указано, что синхронизировать конструктор нет смысла, и что это явная ошибка. Это было до ревизии модели памяти в 1.5, но кто заметил? Даже синтаксический сахар synchronized как аттрибут метода на конструктор не распространяется...

Представьте, сколько сейчас по разным библиотекам разбросано классов, которые их авторы предполагали потокобезопасными — хотя они таковыми не являются? Тут и сон с аппетитом потерять недолго.

Почему же это не тревожит широкие народные массы?

По легенде, в одном из советских НИИ годов 60-х висел плакат с летящим шмелем, и надписью: "Большая масса тела шмеля вкупе с малой несущей поверхностью его крыльев не позволяет шмелю летать. Но шмель не знает об этом, и летает только поэтому"
Ну, во-первых, потому что во многих православных паттернах работы с многопоточностью безопасность публикации обеспечивается их авторами. И работает, даже если использующий эти паттерны программист вообще не задумывается о безопасной публикации. Например, многие ли задумываются о том, что передавая в Executor Runnable со ссылкой на какие-то данные, которые нужно обработать, мы тем самым публикуем ссылку на эти данные для потоков внутри Executor-а? Между тем это именно публикация ссылки, и она безопасна — потому что об этом позаботились разработчики Executor-а.

А вот вторая причина интереснее и скандальнее. Во всем виноват Интел и его монополия :)

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

"Write once — run everywhere" — красивый, но весьма условный слоган. Везде — это где именно? Вот лично я только однажды в жизни запускал ява-код на не-x86 архитектуре — когда игрался с J2ME. А если ограничиться SE/EE — кто запускал свой код не на интелловской архитектуре? Думаю, почти никто. Если я ошибаюсь — отпишитесь в комментариях, мне любопытно в скольких неожиданных местах ваш код начал внезапно глючить :)

А что такого плохого у нас с Intel? Да все у нас хорошо, даже слишком. У интелловских x86 архитектур (т.е. не-Intanium) очень жесткая аппаратная модель памяти: total store order, TSO. Это означает, если очень упрощенно, что интелловские (и не только интелловские — архитектура x86 стандарт де-факто для большого куска рынка) процессоры выполняют записи всегда в том порядке, в котором они идут в коде программы. Другая формулировка: все потоки в системе видят все записи в одном и том же порядке, и этот порядок согласован с порядком соответствующих инструкций записи в коде потоков. Это уже гораздо больше, чем требует JMM от кода, выполняемого без дополнительных инструкций синхронизации. В частности, для случая небезопасной публикации это означает, что публикация в железной модели памяти x86 всегда безопасна. И единственным источником непредсказуемости остается JIT — который тоже может переставлять инструкции.

Может-то он может, да будет ли? Ну вот давайте, для примера, рассмотрим тот же DCL. Если взять псевдокод — getInstance() будет выглядеть примерно так (это дикая помесь байткода с явой и ассемблером — но вроде суть понятна):
if( DCLSingleton.instance != null ) 
   jmp #end;

monitorEnter DCLSingleton.class;
if( DCLSingleton.instance != null )
   monitorExit DCLSingleton.class;
   jmp #end;

localRef = allocate( sizeof(T) );
call DCLSingleton.<init>( localRef );
DCLSingleton.instance = localRef;

monitorExit DCLSingleton.class;

end:
   return DCLSingleton.instance;
Если JIT сгенерирует прямо и непосредственно вот это — то на x86 все будет в шоколаде, ни один котенок не пострадает, никакой возможности увидеть ссылку на недоинициализированный объект не будет, потому что присвоение ссылки в shared variable идет после вызова конструктора, и x86 сам записи не переставляет — значит все потоки увидят именно сначала те записи, которые выполнены в рамках конструктора, а уж потом публикацию ссылки.

Разумеется, JIT мог бы сам переставить запись DCLSingleton.instance = localRef до вызова конструктора. Но для JIT это будет довольно опасная оптимизация, потому что он же не знает, что там, внутри DCLSingleton.<init>( localRef )? Может, там программист заложился на то, что instance == null — тогда, переставив запись JIT нарушит intra-thread semantics. Поэтому сделать такое он может только если ему на стадии оптимизации текущего метода доступна информация о коде конструктора. Современные JIT-ы не выполняют межпроцедурную оптимизацию, поэтому информацию о коде вызываемого метода JIT может получить только если он еще раньше принял решение встроить (inline) вызываемый метод. Тогда код конструктора становится частью кода текущего метода, и JIT может убедиться, что упреждающая запись instance ничего не нарушит.

А зачем бы JIT-у встраивать вызов конструктора? Встраивание — это агрессивная оптимизация, применяемая для очень горячего кода. Но ведь вся идея DCL в том-то и состоит, чтобы сделать синхронизированный код не горячим. Я уж молчу, что суть синглетона в том, чтобы конструктор вообще вызвался только один раз.

Это все мои, довольно спекулятивные предположения о том, как именно работает JIT. Они могут быть неверными в деталях, но суть остается та же — JIT довольно редко делает что-то, что нарушает hardware TSO. Один уважаемый человек™ рассказывал, что он как-то потратил день чтобы так написать DCL, чтобы он ломался бы хотя бы один раз на миллиард вызовов.

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

UPD: Перечитал и ужаснулся — какое-то неверное представление тут создается :) Что я здесь хотел сказать: что есть очевидный, но довольно узкий сегмент высоконагруженного, высококонкурентного кода, в котором небезопасная публикация будет довольно стабильно генерировать ошибки даже на x86. В "обычном" же малонагруженном коде — типа начальной инициализации — в силу жесткости аппаратной модели памяти x86, и в силу того, что наиболее агрессивные оптимизации JIT применяет только к горячему коду небезопасность публикации будет незаметна. Она либо вообще не будет создавать ошибок, либо будет создавать их настолько редко и невоспроизводимо, что вы скорее примете их за баги в JVM/железе.

Тогда зачем мне весь этот гемморой?

В самом деле, возникает немного крамольная мысль: насколько оно полезно с практической точки зрения — писать корректный по JMM код? Если ошибки будут возникать только в лабораторных условиях в одном случае из миллиарда — так может я лучше потрачу время на поиск логических ошибок в коде, которые будут проявляться чаще? Система в целом не сильнее своего самого слабого звена — это применимо как к производительности, так и к надежности. Насколько оправдано тратить время на избавление от гонок в коде, если есть такие источники ненадежности как общий недостаток мозгов у разработчиков, ошибки в JVM, баги в железе и нашествие помидоров-убийц?

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

Дело еще и в том, что, по поему мнению, правила существуют не для того, чтобы их соблюдать, а для того, чтобы в обязательном порядке включать голову когда собираешься их нарушить. Нарушение JMM по незнанию или невнимательности — это именно недосмотр, ошибка. Нарушение JMM с осознанием того, какие выгоды ты от этого получаешь, и какие косяки где и как могут возникнуть в твоем коде — это вполне нормальная инженерная практика. Лично я предпочитаю знать, какие места в моем коде опасны, а так же почему они опасны, насколько опасны, и почему я их в таком виде оставил.

Мы не будем вечно сидеть на TSO. Поддержание такой строгой модели памяти стоит довольно недешево, и сильно ограничивает дальнейшее увеличение количества ядер. У интела уже есть Itanium с ослабленной моделью памяти, очевидно будут и другие модели. Кроме того на рынок серверов сейчас активно лезет ARM — и скорее всего таки пролезет. Ну и Азул тот же самый... Все идет к тому, что иметь дело с ослабленными аппаратными моделями памяти нам все равно придется — и мне кажется, лучше готовиться к этому заранее.

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