23 мая 2019 г.

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-код тут, можно поиграться)

5 мая 2019 г.

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

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

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

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

30 апреля 2019 г.

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


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

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

8 апреля 2019 г.

Разбитые окна

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

20 августа 2018 г.

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

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

28 июля 2018 г.

Снова про конфигурацию

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

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

12 июня 2018 г.

Configuration as code

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

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

20 мая 2018 г.

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


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

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

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

3 декабря 2017 г.

Про ReentrantReadWriteLock

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

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

23 июня 2017 г.

Shenandoah на JPoint 2017

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

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

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

10 января 2017 г.

GC: golang и прочие

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

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

4 декабря 2016 г.

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

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

29 ноября 2016 г.

Видео с jug-ekb

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

25 ноября 2016 г.

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

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

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

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

8 октября 2016 г.

Скаляризация 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. Наиболее простой и очевидный способ это сделать: как раз таки использовать композитный ключ (кортеж из ключей). Решение отличное по всем показателям, кроме одного: для каждого поиска в словаре придется создавать новый объект.

12 августа 2016 г.

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

30 июня 2016 г.

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();
}
В этом коде на одну точку аллокации больше — но все эти аллокации успешно скаляризуются. В общем-то, ничего особо удивительного: здесь каждая ссылочная переменная в любых сценариях исполнения всегда адресует один-единственный объект, поэтому никаких сложностей у скаляризации не возникает :)

21 июня 2016 г.

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

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

25 марта 2016 г.

А почему бы не аллоцировать на стеке?

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

Насколько я понимаю, одного простого ответа на это "почему" нет. Более того, существовали прототипы стековой аллокации — в одной из статей по EA авторы упоминают, что их прототип делал по результатам EA именно стековую аллокацию (правда, тот прототип был на базе IBM JVM).

22 февраля 2016 г.

Tricky scalar replacement

...Однако, насяльника, код сильно сложный, синтаксический дерево большой, корень толстый, ссылка туда гоняй, сюда гоняй, одну присвояй, другую присовояй, моя не понимать...
Допустим, у нас есть класс Vector2D, типа такого:
public static final class Vector2D {
 private double x;
 private double y;

 public Vector2D( final double x,
                  final double y ) {
  this.x = x;
  this.y = y;
 }

 public Vector2D add( final Vector2D other ) {
  return new Vector2D(
    x + other.x,
    y + other.y
  );
 }

 public void addAccumulate( final Vector2D other ) {
  x = x + other.x;
  y = y + other.y;
 }

 public double dot( final Vector2D other ) {
  return x * other.x + y * other.y;
 }

 public double length() {
  return Math.sqrt( this.dot( this ) );
 }
}
(Конкретные детали не важны, нужен класс без сложной логики и коллекций внутри)