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

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