Charlie Gracie: Current state of JVM Escape Analysis and downstream optimizations

Я уже какое-то время отошел от темы скаляризации и escape-анализа, но тут случайно наткнулся на любопытное видео с JFokus: Чарли Грасье из Микрософта рассказывает, как они для своих целей сделали прототип stack allocation для java 11. И даже не для Graal (где нынче чаще всего делают что-то новое), а для старого-доброго C2. Чарли начинает с краткого обзора escape-анализа и скаляризации в целом, потом кратко рассказывает, как они модифицировали JVM C2, чтобы сделать аллокацию на стеке.

Что это дает: они заинтересованы прежде всего в scala, и для scala-бенчмарков аллокация на стеке дает 5-15% увеличения производительности. Чарли спекулирует, что это прежде всего из-за увеличения кэш-локальности, поскольку объекты, аллоцированные на стеке, всегда будут горячими в кэше, а объекты, аллоцированные в куче, не всегда. Звучит немного странно, потому что стандартная аллокация в джаве (bump the pointer) тоже должна давать довольно хорошо предсказуемый и дружественный для кэширования паттерн доступа — но результаты говорят за себя.

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

Waiting time paradox #4: aftermath

(продолжение серии про парадокс времени ожидания)

…Мне кажется, это поразительный эффект: добавка sleep(5) в цикл обработки задач может уменьшать среднее время обработки. Даже после того, как я уже разобрался с этим эффектом на примере автобусной остановки, я все еще не мог поверить, что такой же эффект будет и в системе с очередью. И, несмотря на все формулы, разобранные примеры и симуляции, на интуитивном уровне я все еще ощущаю это как какой-то трюк. Это и поразительно: хотя логически я все понимаю, могу объяснить, и симуляцию написать, и картинку нарисовать – но моя интуиция все равно отказывается воспринимать это как очевидное.

И ведь происходит все в очень обыденной системе, с которой мы регулярно сталкиваемся в жизни. В математике есть множество выносящих мозг результатов, но многие из них выносят мозг просто потому, что относятся к системам, для которых в повседневной жизни нет аналогов. Парадокс Банаха-Тарского гораздо круче парадокса времен ожидания – но кто из нас в жизни сталкивается с разрезанием сферы на не-измеримые куски? Сама постановка задачи уже далеко выходит за рамки повседневного опыта и бытовой интуиции – не удивительно, что результат получается не интуитивный. Но очередь в Сбербанк, и кассир, который делает между клиентами минутную паузу, а иногда выбегает перекурить на 5 минут, а иногда попить чай на 15 – это обыденная ситуация. И оказывается, что в этой обыденной ситуации скрыто такое нетривиальное поведение!

Waiting time paradox #3: сервера и их очереди

Если происходит что-то странное, значит, где-то рядом автобусная остановка
(Народная мудрость)

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

Представьте себе сервер, на который приходят заявки, и очередь, где заявки могут чуток обождать, пока сервер занят с другими заявками. Не хочется тратить CPU на постоянный опрос очереди busy-loop-ом, поэтому сервер обрабатывает те заявки, которые уже накопились в очереди, а как только заявки в очереди заканчиваются – сервер переключается на какие-то фоновые задачи, а потом на sleep(5). Отоспавшись, сервер возвращается к очереди, и если там что-то накопилось – то все это разгребает, и опять уходит заниматься фоновыми делами + sleep(5), а если ничего не накопилось – так сразу уходит заниматься фоновыми делами и спать. Поддерживает разумный work-life balance:

while( true ){
    task = queue.poll()
    if( task != null ) {
        task.doTheNeedful()
    } else {
        doBackgroundJobs()
        sleep(5)
    }
}

(Полный java-код тут, можно поиграться)

Waiting time paradox #2: почему успешный поиск в хэш-таблице дольше не успешного?

…Продолжение предыдущей статьи про waiting time paradox: на этот раз разберемся, почему успешный поиск в хэш-таблице обычно дольше, чем не-успешный

Возьмем классическую хэш-таблицу с разрешением коллизий цепочками: K пар ключ-значение, B корзинок со связными списками для разрешения коллизий, вот это все. Мы ищем в этой таблице разные ключи (а зачем еще нужна хэш-таблица?). Для каких-то ключей в таблице находится соответствие, для каких-то – нет.

Вопрос: что больше – среднее количество сравнений при успешном поиске, или среднее количество сравнений при неуспешном поиске?

Waiting time paradox #1: автобусы, очереди, и хэш-таблицы

Ничего не доводи до крайности: человек, желающий трапезовать слишком поздно, рискует трапезовать на другой день поутру.
(Козьма Прутков)

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

Теория разбитых окон в применении к разработке

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

Оценки квантилей распределений потока данных

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

Проблема тестирования конфигурации в том, что нет готовой инфраструктуры

Одна из проблем с тестированием конфигурации состоит в том, что нет готовой инфраструктуры

Я имею в виду, что когда вы собираетесь написать тест для кода — у вас уже многое есть. У вас есть какая-то доменная модель, у вас есть какие-то API, у вас есть какие-то builders/wizards/DSL. Да, поверх всего этого, обычно, все равно приходится дописать прослойку вспомогательного кода, предназначенного именно для тестирования (aka "test-harness"), но если основной код спроектирован и написан достаточно хорошо, то эта прослойка довольно тонкая. Условно, процентов 50-80 уже написано, и эти проценты очень облегчают начало.

Configuration as code

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

Сейчас мне кажется, что выносить конфигурацию приложения в текстовые файлы (в том числе xml/json/yaml…) — это сильно переоцененный прием. Настолько переоцененный, что он уже почти антипаттерн. Ну как синглетон — сам по себе вроде неплох, но был период, когда его пользовали где ни попадя, в хвост и гриву. Так же и с конфигурацией в текстовых файлах: якобы это дает гибкость, но эта гибкость на практике оказывается чаще вредной, чем полезной.

"Тестирование конфигурации для java-разработчиков" (Гейзенбаг 2018, Петербург)

Меж тем я тут немного погрузился в тестирование — вплоть до того, что выступал на питерском Гейзенбаге с докладом про тестирование конфигурации. Только вчера вернулся, а сегодня на сайте конференции уже выложили слайды.

Тезисно: я рассказывал о том, что конфигурация это важная часть приложения — такая же важная, как код. Ошибки в конфигурации приводят к некорректной работе сервисов, и/или отказам в обслуживании — ровно так же, как и ошибки в коде.

Но код приложения проходит множество проверок — начиная от компилятора (если вы, конечно, пишете на нормальных языках, а не на JavaScript), и кончая многими уровнями тестов. Конфигурация же, чаще всего, это просто какие-то текстовые файлы (properties, xml, yaml, json...), с очень вольным форматом, практически без валидации. Никаких автоматизированных тестов для нее, как правило, нет.

Про ReentrantReadWriteLock

Отличная история с любимой группы рассылки concurrency-interest.

В библиотеке guava есть класс Striped, предоставляющий разные виды локов, в разбивке по ключам. Сценарий использования, как я его понимаю, такой: есть данные, естественным образом разбитые по ключам К, и эти данные нужно защитить от конкурентного доступа. При этом конкурентный доступ к данным разных ключей вполне допускается. Если использовать одну общую блокировку, то это похоронит весь параллелизм, а заводить по блокировке на каждый ключ может быть слишком накладным, если ключей много. Striped — промежуточный вариант: при создании задается, сколько блокировок вы готовы создать, и дальше все ключи отображаются на этот ограниченный список блокировок. Один и тот же ключ всегда отображается на один и тот же лок, поэтому корректность гарантируется. Разные ключи, очевидно, тоже иногда отображаются на один лок, но не очень часто (~1/stripes). (Если вы смотрели код j.u.c.ConcurrentHashMap, то должны понимать, откуда эта идея, и как примерно она реализована)

Shenandoah на JPoint 2017

Запоздалый отклик на рассказ о Shenandoah на JPoint 2017 и последокладные разговоры. Я не буду пересказывать Алексея — лучше Алексея никто Алексея не перескажет, видео наше все. Здесь мои размышления после, и что мне показалось интересным.

Интересного в Shenandoah много. Для меня в первую очередь интересно, что Шенандо — первый GC в джаве, который не основан на гипотезе о поколениях.

Я начну издалека. Базовый алгоритм для сборки мусора это трассировка ссылок: определяем GC Roots, от них идем по ссылкам, и помечаем достижимые объекты как живые. Но на большой куче трассировка потребует много времени. Если мусор собирать в режиме паузы (Stop The World, SWT), то паузы будут долгими.

GC: golang и прочие

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

Последний месяц-два много шума из-за go. Команда разработчиков go рапортует о том, что в версии 1.5 их GC работает со средними паузами в районе сотен микросекунд, и максимальными < 10 миллисекунд ну и типа это "прорывное решение", "сборщик мусора для следующего десятилетия" и другие громкие заявления. В связи с этим хорошая статья Mike Hearn на medium: Modern Garbage Collection разбирает ситуацию (пока я писал, ее уже перевели на хабре).

Так что насчет производительности?..

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

Видео с jug-ekb

Сентябрьский доклад на jug-ekb. Спасибо организаторам:

Скаляризация Map.get(...) -- продолжение

...которое было задумано сразу после, но неожиданно задержалось: сложная политическая обстановка, на работе завал, в Москве пробки, гомеопаты атакуют, а в фейсбуке регулярно кто-то не прав — как тут найти время?

После прочтения предыдущего поста возникает депрессиявопрос: можно ли как-то добиться стабильной скаляризации ключей? Краткий ответ: нет. Более полный ответ: нет, стабильной скаляризации в JVM (HotSpot) добиться невозможно. JIT — это рулетка. Смиритесь.

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

Скаляризация Map.get(new CompositeKey(key1, key2, ...))

Один из самых интересных примеров из моего последнего доклада на jug-ekb (на JPoint этот пример не влез) это скаляризация композитных ключей в поиске по словарю:

final Map<CompositeKey, V> map = ...;

...
    final CompositeKey key = new CompositeKey( key1, key2, ... );
    final V value = map.get( key );
...

Это весьма частый паттерн: нам нужно отображение вида [key1, key2, key3...] -> value. Наиболее простой и очевидный способ это сделать: как раз таки использовать композитный ключ (кортеж из ключей). Решение отличное по всем показателям, кроме одного: для каждого поиска в словаре придется создавать новый объект.

EnumSet scalarization

В эфире очередной выпуск блогопередачи "скаляризуй меня полностью". На этот раз под мою горячую руку попался EnumSet. Первое, что мне про него было интересно — это, конечно, скаляризация итератора. Ну, потому что по любой коллекции очень удобно ходить циклом foreach, но не всегда хочется за это удобство платить, пусть даже и не дорого:

public static enum Enum3 {
 FIRST,
 SECOND,
 THIRD
}

...

final EnumSet set = EnumSet.allOf( Enum3.class );

...

//benchmark start
long sum = 0;
for( final Enum e : set ) {
   sum += e.ordinal();
}
return sum;
//benchmark end

Tricky scalar replacement: больше-меньше

В предыдущей серии я уже писал, что такой код:

private double allocateConditionally( final ThreadLocalRandom rnd ) {
 final Vector2D v;
 if( rnd.nextBoolean() ) {
  v = new Vector2D( 1, rnd.nextDouble() );
 } else {
  v = new Vector2D( rnd.nextDouble(), 1 );
 }

 return v.length();
}

не скаляризуется — хотя интуитивно кажется, что скаляризация здесь должна быть тривиальной.

А что если немного добавить аллокаций?

private double allocateConditionally2( final ThreadLocalRandom rnd ) {
 final Vector2D result = new Vector2D();

 if( rnd.nextBoolean() ) {
  final Vector2D v = new Vector2D( 1, rnd.nextDouble() );
  result.copyFrom(v);
 } else {
  final Vector2D v = new Vector2D( rnd.nextDouble(), 1 );
  result.copyFrom(v);
 }

 return result.length();
}

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

Escape Analysis & Scalarization (видео с jpoint)

Наконец-то выложили финальное обработанные записи докладов с JPoint. Среди прочих и мой доклад про Escape Analysis и скаляризацию. Кажется, получилось неплохо :)