LMAX trading

Статья про архитектуру трейдинговой платформы LMAX. Кажется, про нее рассказывали на JavaOne, но я пропустил этот доклад. Читать здесь

Несколько любопытных вещей. Во-первых, они ухитряются обрабатывать 6 миллионов транзакций в секунду на обычных серверных Nehalem-ах, при том, что вся бизнес-логика у них в одном потоке. А, да, все это на java.

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

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

Обработчик бизнес-логики -- это, по-сути, message-loop, однопоточный, написаный максимально оптимизированно. Все данные ("мир") он держит исключительно в оперативке, весь код очень простой и максимально короткий, чтобы JIT его наиболее удачно оптимизировал (JIT-friendly code). Это, в частности, и позволило им получить 6 миллионов транзакций в секунду. Но здесь возникает вопрос надежности (устойчивости к сбоям), и вопрос ввода-вывода -- он, по-любому, медленный, и традиционно в одном потоке не делается.

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

Большая часть из обработчиков read-only -- и они вполне себе работают параллельно, загружая разные ядра процессора. В частности, какие-то обработчики дублируют данные на вторичные сервера -- реально в продакшене в каждый момент времени работают 3 территориально разнесенных сервера, с полностью идентичным состоянием -- это решает проблему устойчивости к сбоям. Другие обработчики сохраняют данные в персистентное хранилище -- так что состояние системы (которое, напомню, все в оперативке) в любой момент можно восстановить заново накатив весь лог событий (реально раз в сутки делается снапшот, так что накатывать приходится только за последние сутки). Третьи отправляют часть событий для какого-то анализа и последующей генерации отчетов. И так далее.

Часть обработчиков -- read-write, в частности, те, которые собственно парсят и раскодируют сообщение, превращая его из массива байт в джава-объекты, и в конечном счете, в набор команд для процессора бизнес-логики.

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

Что в итоге: в итоге main code path для обработки входящей транзакции включает в себя начальную предобработку (парсинг/проверка/конвертация в команды), которая делается конвейером параллельных обработчиков, работающих на разных ядрах, и передающих друг другу данные с минимальными накладными расходами (через Disruptor), потом отработку команд центральным процессором бизнес-логики -- который максимально короткий, и работает только с оперативкой, и выдачу результата в выходной Disruptor -- что опять же почти даром. Т.е. этот центральный путь -- максимально короткий, и максимально предсказуемый -- на нем нет ничего, что могло бы вызвать непредсказуемые задержки, ни аллокации больших объемов памяти (что приближает full stop-the-world GC), ни блокировок, ни сетевого ввода-вывода в базу данных. Практически, этот центральный путь не вполне real-time, но что-то очень близкое к тому. Все тяжелые вещи -- типа анализа, без которого все равно не обойтись -- можно вынести на отдельные машины, получающие данные с входного/выходного конвейера -- без малейшей задержки центральной части.

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

Highly Scalable Java: 3

Интереснейшая еще идея была в презентации Клиффа на JavaOne 2008 -- высококонкурентная lock-free очередь, best-effort FIFO, для использования в архитектуре producer-consumer.

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

while( !CAS( items[producerLocalIndex], null, newItem ) ){

  producerLocalIndex = ( producerLocalIndex + 1 ) % items.length;

}

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

Берем мы элементы из очереди аналогично:

do{
  consumerLocalIndex = ( consumerLocalIndex + 1 ) % items.length;
  item = items[consumerLocalIndex];
} while( !CAS( items[consumerLocalIndex], item, null ) );
return item;

(consumerLocalIndex изначально каждый потребитель тоже выбирает случайно).

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

Мне нравится идея. Во-первых, она простая и красивая. Я несколько месяцев назад думал о чем-то похожем в контексте своих идей про синхронизацию без синхронизации, но у меня не было ничего про изменение размера (так было проще), и я больше акцентировался на минимальных накладных расходах, чем на масштабировании до 1000 процессоров, как Клифф. Тем не менее, приятно, когда у умных людей мысли сходятся :)

А еще мне очень понравилось как именно Клифф пришел к этой идее. Логика рассуждений (по крайней мере, как она изложена в презентации) была такой: нам нужна очередь, в которую могут писать/читать много агентов параллельно. Логичная идея -- взять несколько очередей (в идеале -- сколько писателей/производителей) -- массив очередей, и при записи/чтении перебирать очереди. Теперь возьмем число агентов очень большим -- 1000. Во что превратится наш "массив очередей"? Будет очень много очень маленьких (коротких) очередей. Возьмем совсем крайний случай -- очередь может быть либо пустой, либо содержать один элемент, и таких очередей -- дофига. Получаем как раз простой массив, где в ячейке либо null (пусто), либо что-то лежит.

Эта манера рассуждения мне очень напомнила ТРИЗ. Есть там очень похожий прием обострения технического противоречия, доведения до крайности -- "оператор РВС" (размер-время-стоимость).

Что мне в этой идее не очень нравится -- неочевидно, как здесь обеспечить локальность. Т.е. если поток-производитель и поток-потребитель сидят физически на одном ядре, то хотелось бы, чтобы они с большей вероятностью передавали данные друг другу, и только если такой возможности нет -- использовали бы данные других ядер. Так, например, реализованы очереди задач в Fork/Join у Daug Lea. Как реализовать такую штуку в этой модели мне пока неочевидно. Еще более важным это становится если архитектура памяти не SMP, как у AzulBox, а NUMA, что у действительно многоядерных систем встречается гораздо чаще -- тогда, мне кажется, все будет вообще плохо, потому что массив будет скорее всего выделен в локальной памяти инициализирующего потока, а использоваться будет всеми потоками.

Highly Scalable Java: 2

Давно собирался разобраться в устройстве highly scalable java от Cliff Click -- наконец дошли руки.

Итак, Клифф Клик, Главный Инженер (Distinguished Engineer) в компании Azul System. Компания специализируется на готовых решениях для запуска java-приложений. Наисовременейший Azul Box имеет на борту 768 ядер -- специально заточенных под исполнение JVM. Разумеется, JVM у них тоже своя, специальная -- хотя, очевидно, разработана на базе Сановской. Такое количество ядер, конечно, загрузить непросто -- большинство популярных даже высококонкурентных алгоритмов настолько не масштабируются. Клифф предлагает Новый Подход к разработке таких алгоритмов -- на примере своей реализации NonBlockingHashMap (ну и, до кучи, NonBlockingHashSet, и прочих производных).

Подход вкратце описан в презентации на JavaOne 2008, чуть более подробно -- и зубодробительно -- в исходном коде самой библиотеки, которую легко найти в сети. Реализация, которую предлагает Клифф -- lock-free, то есть на каждый шаг кто-нибудь из задействованных потоков прогрессирует.

Идея вкратце: данные храним в простом массиве. Определяем для каждого слота граф состояний, в которых он может находиться в процессе работы -- конечный автомат для каждого слота. Перемещения по ребрам графа состояний выполняются атомарными CAS-ами. CAS либо удался -- тогда мы сменили состояние, либо провалился -- значит, он удался у какого-то другого потока -- отсюда мы получаем общий прогресс и lock freedom. Ключевой момент здесь -- что все, необходимое для определения/изменения текущего состояния слота находится в нем самом -- т.е. все переходы получаются локальными.

Важно: даже традиционно глобальные операции -- такие как resize/rehash/compaction -- здесь организованы так, что распадаются на локальные операции с каждым слотом в отдельности. Соответственно, даже они почти идеально параллелятся между всеми потоками, оперирующими над таблицей.

Собственно, на мой взгляд, это самая интересная часть. В самом деле, реализовать идеально параллелящийся только-на-чтение HashMap совершенно тривиально -- обычный j.u.HashMap вполне сойдет при условии корректной начальной публикации ссылки (safe publishing). Реализовать обновление значений для уже существующих ключей тоже несложно -- один CAS и дело с концом. Удаление в стиле mark removed реализуется так же, как обновление. Все эти операции требуют только локального CAS-а над конкретной ячейкой массива -- ничего сложного.

Но вот изменение размера таблицы -- как следствие роста количества записей, как следствие высокого количества попыток (reprobes count) из-за плохой хэш-функции ключей, для компактификации при большом проценте удаленных записей -- гораздо более сложная операция. Нужно ведь создать новую таблицу, скопировать туда все самые свежие данные старой, и подменить старую таблицу на новую. Главная сложность -- посторонний поток может влезть с обновлением уже после того, как значение какой-то ячейки уже скопировано в новую таблицу, но еще до того, как ссылка на новую таблицу подменит старую -- и тогда его обновление останется в старой таблице, и будет потеряно. Избежать такой ситуации -- огранизовать идеально параллелящееся копирование, не мешая (не блокируя) при этом конкурирующим чтениям/обновлениям/удалениям -- это и есть основной вызов, с которым Клифф работал, и с которым он красиво справился.

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

Что делают при этом конкурирующие операции?

Операции чтения: если видят обычный (непомеченный) слот в исходном массиве -- его и возвращают, поскольку это все еще актуальное значение слота (и это fast path, реализующийся чаще всего -- очень быстрый). Если видят слот "в процессе копирования" -- значит таблица в процессе ресайза, и нужно во-первых, постараться вписаться -- скопировать значение слота в новый массив: CAS(newArray[index], null, oldArray[index]) (почему это обязательно -- потому что тот поток, что пометил старый слот как "в процессе копирования" мог еще не успеть реально его скопировать -- и тогда это за него сделаем мы). Дальше -- независимо от успеха предыдущей операции -- мы просто читаем актуальное значение слота из нового массива.

Операции обновления/удаления (пометки): опять же, если слот в основном массиве еще не помечен -- можно свободно работать с ним, поскольку его еще не скопировали. Если же пометка есть -- мы, так же, как и при чтении, впрягаемся и сами копируем текущее значение -- и потом меняем его на свое новое.

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

Выглядит это очень круто, хотя в реальном коде все значительно сложнее и запутаннее. Например, Клифф очень аккуратно (экономно) расставляет мембары -- а в джаве нет явных мембаров, поэтому в нужных местах ему приходится читать/писать волатильные переменные, иногда совсем ненужные по смыслу кода -- только ради memory ordering effects. Далее -- он не использует j.u.c.AtomicXXX, вместо этого он активно использует s.m.Unsafe, что не добавляет коду краткости. Зачем? Из-за одной тонкости, о которой я недавно писал -- AtomicXXX.CAS() по контракту обязан делать full fence -- хотя здесь он Клиффу часто излишен. А вот относительно s.m.Unsafe.compareAndSwapObject() контракт ничего такого не требует, хотя сановская реализация его по факту делает. И здесь, видимо, Клифф использует финт ушами -- реализация JVM на Azul Box мембара там не делает -- и поэтому на азулах его таблица будет работать еще быстрее.

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

Всю свою жизнь я писал статические классы-утилиты таким образом:

public final class Helpers{
  private Helpers(){
  }
  public static String veryHelpfullMethod(){
  ....
  }
}

Недавно заметил у коллеги в коде такой вариант:

public final class Helpers{
  private Helpers(){
    throw new AssertionError("Not for instantiation!");
  }
}

Взял себе на вооружение. И правда, с нынешним reflection-ом закрытый конструктор уже не гарантирует, что класс невозможно будет создать. А вот так -- final-класс, с единственным конструктором и выбросом исключения -- я уже не могу придумать способа (кроме byte-code-modification, конечно -- но против лома нет приема).

AtomicXXX.lazySet(...)

Еще один любопытный метод в атомиках -- AtomicXXX.lazySet(T value). Присваивает значение переменной "когда-нибудь" (eventually). Спроектирован для end-of-life cleanup в неблокирующих структурах данных, когда надо очистить значение переменной (например, записать туда null), и больше с этой переменной ничего делаться не будет, поэтому в принципе все равно, когда именно значение будет реально записано (и увидено другими потоками), но важно, что когда-нибудь это-таки произойдет (чтобы GC гарантированно мог собрать "отвязанный" объект). По-сути получается, что это non-volatile write в волатильную переменную.

О сколько нам открытий чудных
Готовит javadoc-ов дух...

1024 cores

Интересный блог о параллельном программировании -- 1024 cores

weakCompareAndSet

В классах AtomicXXX, наряду с известным методом compareAndSet (CAS) есть еще довольно странный метод weakCompareAndSet (WCAS). Не так давно я наткнулся на довольно длинную дискуссию в concurrency-interest. Хотя сама дискуссия довольно уже старая (2006г) но для меня содержала много нового, чем хочется поделиться.

Итак, чем отличается weakCAS от обычного CAS?

1. Может откатиться (ничего не изменить и вернуть false) даже если значение expected совпадает с текущим значением в ячейке памяти (другими словами -- может откатиться "без причины")
2. Не создает (=не обязан создавать) ребра happens-before

Теперь чуть подробнее:

С первым пунктом все довольно просто -- обычный CAS откатывается только в случае, значение в ячейке памяти не совпадает с ожидаемым. Если CAS вернул false -- вы можете быть уверены, что actualValue!=expectedValue. В случае с weakCAS такой уверенности нет -- значения могут совпадать, а weakCAS все равно откатится. Разумеется, можно сделать цикл с проверкой, но есть тонкости -- часто доказательство lock-free для алгоритма базируется на том, что CAS либо удался (и тогда текущий поток "продвинулся"), либо нет (и это означает, что "продвинулся" какой-то другой поток) -- в итоге всегда получается общий прогресс. С weakCAS такое рассуждение уже не прокатит -- формально говоря, он может откатываться сколько пожелает.

Второй пункт важнее и интереснее. Обычный CAS имеет семантику volatile read+write. В частности, это означает, что между двумя CAS-ами одной переменной всегда существует ребро happens-before. Именно это позволяет использовать его, например, для создания спин-локов. weakCAS такой семантики не имеет, никаких ребер не создает, и сделать на его основе спин-лок не получится.

Откуда же есть пошел weakCAS? Ну, если верить concurrency-interest, мотивация была в том, что не на всех моделях процессоров есть инструкция вида CAS. На некоторых есть альтернативный вариант -- load-linked/store conditional. CAS и LL/SC эквивалентны в том смысле, что любой алгоритм, который можно реализовать через CAS можно реализовать и через LL/SC. Но при этом LL/SC откатывается если значение по указанному адресу изменялось с момента чтения (т.е. в случае сценария ABA CAS пройдет, а LL/SC откатится). Есть еще варианты -- например, какие-то реализации LL/SC могут откатываться если изменилась любая ячейка памяти, лежащая на той же cache line, что и нужная. Чтобы на этих процессорах эмулировать честный CAS потребуется цикл с перепроверкой. Но в некоторых случаях "честности" и не нужно, и тогда можно использовать слабый CAS без дополнительных оберток.

Вторая тонкость -- на мой взгляд, более важная -- про happens before. Честный CAS, как я уже писал, состоит, собственно, из двух частей: атомарной проверки-и-присвоения, и двустороннего мембара (full fence). И если первая часть как-то очевидна (само название операции об этом и говорит), то вторая -- это некоторое дополнительная фича именно java-api для AtomicXXX. Не во всех процессорах инструкции CAS обязательно выполняют full fence, и, более того, далеко не во всех алгоритмах, требующих атомарной операции compare-and-set, обязательно требуется и full fence в каждом случае. Между тем, full fence это операция, потенциально, с большой латентностью (особенно, если ядер достаточно много). Поэтому, особенно для многоядерных систем, неплохо бы иметь возможность делать CAS без full fence, когда это необходимо. weakCAS именно такую возможность и предоставляет.

Почему тогда weakCAS малоизвестен? Ну просто потому, что в самых распространенных интеловских и AMD-шных процессорах инструкции "CAS без full fence" просто нет -- там есть только LOCK CMPXCHG, который делает точно то, что требуется спецификацией AtomicXXX.compareAndSet(...). Поэтому на этих машинах weakCAS == CAS.

Вторая причина состоит в том, что довольно сложно решить, где именно может быть применим CAS без fence. В concurrent-interest на эту тему пишут, что "если вы не Daug Lea, и у вас нет крайне веских причин оптимизировать какой-то CAS в вашем коде -- забудьте про weakCAS".

Когда же можно подумать об его использовании? Первый, очевидный, случай -- это счетчики. В частности, в дискуссии concurrent-interest выступал Cliff Click, рассказывая, что ему, для Azul box с 700-800 ядрами, требовались performance counter-ы, которые бы как можно меньше тормозили (на Azul, как я понимаю, есть более богатый выбор вариантов инструкции CAS -- и с барьерами, и без них). В самом деле, если все, что вам нужно -- это атомарный инкремент некоторой переменной -- довольно глупо в пару к нему покупать еще и full fence. Особенно если у вас 800 ядер, частенько выполняющих этот инкремент. Более общо: если вам не нужна синхронизация, а нужна только атомарная операция типа "считать-изменить-записать" -- можно использовать weakCAS, и радоваться от мысли, что, если когда-нибудь ваш код будет выполняться на Azul-ах (какая честь для вашего кода!) -- он будет работать быстрее :)

Второй случай, менее очевидный и более сложный -- когда у вас в алгоритме есть несколько последовательных CAS-ов, и вы понимаете, что "ключевым" (linearization point) из них является только какой-то один -- тогда именно его можно оставить честным, а предыдущие -- weakCAS. Мне это напоминает технику synchronization piggybacking.

Вообще, после таких обсуждений я начинаю понимать Daug Lea, который хочет добавить в джаву класс Fences с методами типа orderReads(..), orderWrites(), orderAccesses(), reachabilityFence(..)

Creating memory leaks in java

Любопытное обсуждение на StackOverflow -- какими способами можно создать утечки памяти в джаве. Тут есть некоторая тонкость в том, что именно называть утечками -- большинство описанных техник не приводят к утечкам памяти в том смысле, что объект, занимающий память, остается как-то доступным, просто сильно неочевидным образом. Я бы сказал, что это список (впечатляющий!) всевозможных косяков/багов/bad design в джаве, которые могут привести к застреванию неиспользуемых объектов в куче.

Список, на самом деле, очень впечатляющий -- стыдно сказать, но я даже не предполагал о большинстве из них, тех, что связаны с Thread/ThreadGroup и ClassLoader.

Мне еще понравился вариант с unsafe.allocateMemory(1024*1024);

Highly Scalable Java

Некий Cliff Click из Azul Systems создал небольшую библиотеку очень масштабируемых коллекций (Map, в основном) для java. Очень масштабируемых в том смысле, что он обещает почти линейное масштабирование до 768 процессоров включительно (это Azul box столько содержит -- я сам охренел о том отдельный разговор).

Очень хочу поразбираться, как ему такое удалось. Его презентацию "Towards a Scalable Non-Blocking Coding Style" с JavaOne 2008 можно скачать здесь (архив слайдов JavaOne за 2008 год, по Java SE, его презентация в файле TS-6256).

Тестирование производительности ГСЧ

Как-то раз, на очередном этапе оптимизации в текущем проекте в список hot methods вырвался Random.nextDouble(). Его загнали назад в хвост, но осадочек остался, так что последние пару недель в свободное время я гоняю бенчмарки различных реализаций генераторов случайных чисел. В соревновании участвуют заведомый аутсайдер java.util.Random, плюс два хорошиста из cern.jet.random -- вихрь Мерсена и DRand -- наверное, самый короткий из возможных на джаве (next = current * 0x278DDE6D).

Гоняю я их в многопоточном варианте -- ибо у нас-то симулятор далеко не однопоточный. Стандартный генератор, поскольку он thread-safe (использует AtomicLong) в двух режимах: shared (один на все потоки) и exclusive (на каждый поток свой генератор). Не то, чтобы я собирался в продакшене использовать Random в shared режиме, нет, упаси боже -- но как еще одна реперная точка (наряду с "dummy" ГСЧ) вполне подойдет. Остальные два участника не потокобезопасны, поэтому для них используется только вариант exclusive.

На днях бенчи досчитались, и обнаружились интересные вещи:

В однопоточном варианте все довольно предсказуемо: стандартный ГСЧ немного (на 10%) опережает вихрь Мерсена (при несопоставимом качестве), Drand всех рвет на части, опережая обоих в 3 раза.

jdk-shared с ростом количества потоков быстро деградирует -- на 16 потоках он почти в 60 раз медленнее, чем на одном -- тоже ничего удивительного.

А вот с остальными по мере увеличения количества потоков начинают твориться веселые вещи. И DRand и jdk-exclusive замедлились почти в 10 раз при переходе от 1 потока к 16. Ну замедление при переходе от 8 к 16 еще понятно -- реальных-то ядер на сервере только 8, 16 это с учетом гипертрединга. Но и на 8 потоках замедление почти в 5 раз. False sharing в действии -- генераторы создаются в цикле, каждый из них занимает явно меньше, чем cache-line, так что очевидно они ложатся на одну строку кэша, что не очень здорово.

Косвенно гипотеза подтверждается тем, что вихрь Мерсена (который внутри себя выделяет еще и массив на int[624]) скалировался до 8 ядер почти идеально, и только при переходе к 16 немного просел.

Проверим -- введем поля:

//было new DRand( 1 ); 
new DRand( 1 ){
                    private final long pad0 = 0;
                    private final long pad1 = 0;
                    private final long pad2 = 0;
                    private final long pad3 = 0;
                    private final long pad4 = 0;
                    private final long pad5 = 0;
                    private final long pad6 = 0;
                    private final long pad7 = 0;
                    private final long pad8 = 0;
                    private final long pad9 = 0;
                };

-- ну и с Random такое же. Результаты заметно улучшаются -- и DRand и Mersenne начинают масштабироваться практически идеально вплоть до 8 потоков, и деградируют лишь на 16, что объяснимо.

Остается неразгаданной ситуация с jdk-exclusive. Во-первых производительность продолжает сильно деградировать -- примерно в 3.5 раза с 1 до 8 потоков. Причины этого поведения мне пока непонятны. Плюс здесь еще самый большой статистический разброс результатов: относительная погрешность достигает 50%, отдельные измерения с одинаковыми параметрами дают, в разных заходах, результаты, различающиеся раза в 3. В раздумьях.

P.S. Код здесь

How caching affects hashing

Я как-то уже постил ссылку на статью How caching affects hashing -- но сейчас дошли руки как-то раскрыть тему. О чем там идет речь, и что там любопытного:

Есть у нас такая штука, как хэш-таблица с открытой адресацией. Довольно несложная в реализации штука (особенно если не реализовывать удаление:), и дает чуть ли не самую лучшую производительность поиска -- не асимптотическую, асимптотически-то все хэш-таблицы имеют "в достаточно хорошем мире" O(n), а реальную. Обусловлено это счастье высокой локальностью хранения данных, и, соответственно, высоким КПД использования кэша (cache-hit ratio).

Реализация хэш-таблицы с открытой адресацией требует выбора последовательности проб, которая будет использоваться для разрешения коллизий. Часто используемые варианты:

1. линейное хэширование -- linear probing (H_i(KEY) = (H₀(KEY) + k*i) mod N, где k часто берут =1)
2. двойное хэширование -- linear double hashing (H_i(KEY) = (H₀(KEY) + H₁(KEY)*i) mod N)
3. экспоненциальное хэширование -- exponential double hashing (H_i(KEY) = (H₀(KEY) + H₁(KEY)*aⁱ) mod N, где a -- константа)

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

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

Мы получаем конфликт -- с одной стороны, чем более "случайна" последовательность проб, тем более равномерно ключи распределены по массиву, тем меньше в среднем придется сделать попыток, чтобы найти нужный нам ключ. С другой стороны, чем "случайнее" последовательность проб, тем получаемый алгоритм менее cache-friendly, тем меньше будет КПД использования кэша. Так ежели слон с китом подерутся -- кто кого заборет?

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

А именно: во-первых, при "хорошей" хэш функции и равномерно распределенных ключах разница в длине последовательности проб между линейным и остальными способами хэширования действительно не так велика. Но это при хорошей хэш-функции и равномерных ключах. А если хэш-функцию взять "на четыре с минусом", и ключи не равномерно распределенные, а какие-нибудь более-менее реалистичные, или load factor высокий... то картина становится гораздо более интересной -- линейное хэширование начинает весьма сильно буксовать. Т.е. квадратичное и экспоненциальное хэширование гораздо более толерантны ко всяким real world issues.

Во-вторых, если размер самой таблицы достаточно мал, чтобы она целиком влезла в кэш, то достаточно быстро она там и окажется, и все доступы к ней будут иметь 100% cache-hit, и тогда выигрывает тот алгорим хэширования, у которого меньшая средняя длина последовательности проб -- а это экспоненциальное хэширование. Двойное хэширование лишь чуть-чуть от него отстает, и обычно этим отставанием можно принебречь. Линейное хэширование тихо курит в уголке.

В-третьих, если таблица большая, и целиком в кэш сильно не влазит, то все будет зависеть от длины ключа. Скажем, если cache-line = 64 байта, и мы храним в таблице ссылки (64 бита), то в одну строку влезет 8 ссылок, и в среднем, в случае линейного хэширования с шагом 1 мы будем иметь 3.5 попытки с почти гарантированным кэш-попаданием. Дальше мы уже залезаем на следующую строку, и вероятность ее присутствия в кэше уже примерно такая же, как и любой другой строки. Т.е. выигрыш линейного хэширования не "100% cache-hit", а всего лишь "1 cache-miss на каждые 3.5 проб", что не так впечатляет. А если размер ключа увеличить, то выигрыш и того меньше. При ключе равном по размеру строке кэша линейное хэширование по cache-hit ratio уже мало чем отличается от остальных -- а по среднему количеству попыток, как известно, проигрывает...

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

Про бенчмаркинг высококонкурентного кода

Великолепная статья Дэвида -- про одну из характерных ошибок при бенчмаркинге high-concurrent приложений.

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

Часто оказывается, что ситуацию можно "улучшить" если некоторым способом ограничить степень конкурентности -- например, введя задержки (back-offs). "Улучшить" в том смысле, что производительность, разумеется, все равно не будет далее расти с ростом количества worker-ов, но, по крайней мере, она не будет и падать -- вместо кривой с максимумом и дальнейшим падением мы получим кривую, выходящую на асимптоту.

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

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

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

Этот эффект нужно иметь ввиду при бенчмаркинге конкурентных приложений. Хорошей практикой будет проверять эффект каждого изменения в максимально широком диапазоне конкурентности, а не только для пиковых значений.

"False sharing induced by card table marking"

Интересную штуку вычитал в блоге у David Dice сегодня. Оказывается, в джаве (и, видимо, в других языках, использующих generational GC -- во всяком случае, похоже, что .NET будет страдать от этого в той же степени) записи ссылочных полей, производимые из разных потоков могут "мешать" друг другу (в том смысле, что операции записи будут конкурировать за строки кэша (cache line), создавая трафик на шине InterConnect-а) даже в том случае, когда, казалось бы, между записываемыми полями нет ничего общего. Такая штука обычно называется false sharing, и о ней -- обычно -- упоминают в случае, когда разные потоки пишут в разные участки памяти, но эти участки оказываются на одной строке кэша. Так вот, Дэвид показывает, что в джаве, в силу некоторых особенностей реализации generational GC, "ложное разделение" случается гораздо чаще, чем можно было бы ожидать -- и от этого варианта false sharing уже не избавиться стандартным введением полей (padding).

Небольшое отступление о работе generational GC. Когда сборщик мусора собирается почистить Эдем (minor GC), ему нужно определить, какие объекты из Эдема еще живы. Для этого нужно найти все ссылки, ведущие в Эдем, и исходящие из а) стека б) старшего поколения. Если первое можно сделать простым перебором (стандартный размер стека ~1Mb на поток), то старшее поколение может занимать десятки гигабайт, сканировать его целиком -- убить всю идею быстрой сборки молодняка. Как с этим справляться? Легко заметить, что необходимо сканировать не всю "старую" кучу, а лишь те ссылочные поля в ней, которые изменились со времени последней сборки молодого поколения. Малые сборки случаются часто, да и объектов в молодом поколении не так уж много. Кроме того довольно логично предположить (по-моему, это утверждение называется второй гипотезой о поколениях), что старые объекты редко ссылаются на молодые. Так что можно с высокой степенью уверенности утверждать, что лишь малая часть ссылочных полей объектов из старого поколения будет изменена за это время, и будет требовать перепроверки.

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

Таким образом мы получаем, что каждая операция сохранения ссылки должна сопровождаться изменением dirty-флага соответствующей карты. Эта штука называется write barrier (имеется в виду что объект, в который пишут, находится "за барьером") или write protection.

К этому моменту уже должно быть понятно, откуда в этой схеме возникает false sharing. Если, скажем, у нас размер строки кэша 64 байта, и размер карты 512 байт, то записи ссылочных полей объектов, расположенных в пределах последовательных 64*512=32Кб будут сопровождаться записями dirty flags в пределах одной строки кэша. Если эти записи исходят из различных ядер -- они будут драться за эту строку кэша. Причем изначально -- сразу после аллокации -- такая штука будет происходить редко, потому что аллокация в джаве старается использовать thread local allocation buffer, и объекты, созданные различными потоками будут сильно разнесены в памяти. Но после full (moving) GC, который выполняет дефрагментацию, эти объекты буду "сближены", и вероятность false sharing в старом поколении будет расти.

Что можно с этим сделать? Можно заметить, что большая часть инструкций типа dirty[cardIndex]=1 на самом деле излишни -- можно сильно уменьшить количество записей делая test-and-set: if(!dirty[cardIndex]) -> dirty[cardIndex]=1. Однако это увеличит code path для каждой записи ссылочного поля. Выиграем ли мы в конечном счете от такой оптимизации -- неочевидно.

Дэвид пишет, что они ввели специальный флаг -XX:+UseCondCardMark который включает test-and-set, и позволяет прикинуть полученный бонус. По его словам, в его экспериментах с одной из реализаций concurrent queue на "Sun 256-way Sun/Oracle T5440" (мне бы такой сервер для экспериментов) включение этого флага подняло производительность с 9К до 53К сообщений в миллисекунду -- в 6 раз!

В комментариях Дэвид пишет, что идеальным решением была бы адаптивная оптимизация. Т.е. мы сначала везде генерируем write barrier в виде dirty[cardIndex]=1, потом собираем профиль исполнения, находим те места, где такой барьер вызывает cache contention, и перекомпилируем эти участки с использованием test-and-set. Но когда это будет реализовано -- неизвестно.

altered notify semantics

Читал сегодня Concurrency & Performance, встретил такую фразу:

JSE 6.0 adds to the list of features that can reduce contention: spin-waits (adaptive spinning), lock coarsening lock elimination lock elision (with escape analysis), biased locking, altered notify semantics (less lock jamming)

Вот про altered notify() semantics я первый раз слышу. Что это такое, интересно?

Снова о reflection

Я уже как-то писал, что при перезаписи final полей через reflection "гарантируются все необходимые барьеры памяти". Но я немного пораскинул мозгами, и задался новым вопросом -- а какие именно барьеры здесь необходимы? Ведь все остальные примитивы синхронизации в JMM описываются не через барьеры памяти, а через happens-before-edge -- ребро частичного порядка операций. Т.е. для того, чтобы какая-то операция чтения в одном потоке гарантированно увидела какую-то операцию записи в другом потоке оба потока должны что-то сделать (потому как ребро-то соединяет два узла графа) -- синхронизироваться на одном мониторе, скажем, или читать одну volatile переменную (и тогда и запись и чтение будут волатильными, с соответствующими последствиями в виде, в частности запрета целого класса оптимизаций для них).

Но если я записываю final переменную через reflection -- что должно выступать в роли второго узла для happens-before-edge? Т.е. при каких условиях очередная операция чтения final переменной a из потока Thread2 увидит новое значение этой переменной, записанное туда потоком Thread1 через reflection?

...Потому что если ответ будет в духе "ближайшая же операция чтения" -- то это очень круто, потому что тогда таким образом можно реализовывать ассиметричную синхронизацию. Т.е. скажем, fixed-size hash-map-based cache из недавнего поста можно будет сделать dynamically resizeable без потерь в скорости чтения -- просто при расширении новый, расширенный массив записывать в final поле через reflection.

...Но не очень понятно, как такое можно реализовать технически. Т.е. финальность поля ведь дает возможность JIT-у делать множество специфических оптимизаций (ну, мне так кажется :) ) -- что ж теперь, их все откатывать?

UPD: Как мне правильно подсказали в комментариях -- хрен вам, а не ассиметричная синхронизация. JLS говорит, что единственный способ использовать перезапись final полей корректно -- это выполнять ее сразу после создания объекта, и до того, как ссылка на него будет опубликована и доступна другим (потокам). В остальных случаях значение-то поля запишется, но видимости его никто не гарантирует, просто потому, что JVM не обязана откатывать уже выполненные оптимизации, сделанные в предположении, что значение финальных полей не изменяется. Т.е. мембары-то JVM может и выполнит (а обязана ли?), но если где-то JIT при оптимизации заложился на неизменность значения финального поля, и, скажем, скэшировал его значение в локальную переменную (а то и в регистр процессора) -- то JVM имеет полное право продолжать выполнять этот оптимизированный код, игнорируя тот факт, что значение поля уже изменилось.

Даже более того -- если значение финального поля инициализируется константой (compile-time-constant) -- то даже изменение сразу после создания может не сработать, потому что значение поля в каких-то случаях может быть инлайнировано еще javac.

"Java locks Analysis and Acceleration" by Kiyokuni Kawachiya

Диссертация человека, который активно участвовал в работе над оптимизацией блокировок в IBM JDK. Подробно расписана история и механика (вплоть до псевдокода) различных оптимизаций. В частности, можно найти как подробное описание исходной версии biased locks (с аццкой магией вроде перемещения instruction pointer-а чужого потока), так и более простой и эффективной версии, с возможностью rebiasing-а. В общем, рекомендую -- даже поверхностное чтение сильно улучшает качество картинки по этому вопросу в мозгу.

Качать здесь (.pdf)

Without locks

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

Самый наглядный пример реализации -- ленивый кэш. Вот, например, простейший вариант -- кэшируем только результат последнего вызова:

public class SingleLRUWaitFreeCache<In, Out> implements ICache<In, Out> {
    private final Function<In, Out> function;

    private transient Entry<In, Out> recentUsed = null;

    public static <In, Out> SingleLRUWaitFreeCache<In, Out> create( final Function<In, Out> f ) {
        return new SingleLRUWaitFreeCache<In, Out>( f );
    }

    public SingleLRUWaitFreeCache( final Function<In, Out> function ) {
        checkArgument( function != null, "function can't be null" );
        this.function = function;
    }

    @Override
    public Out get( final In key ) {
        if( key == null ){
            throw new IllegalArgumentException("null keys are not supported");
        }
        final Entry<In, Out> lru = recentUsed;
        if ( lru != null && lru.key.equals( key ) ) {
            //cache hit
            return lru.value;
        } else {
            //cache miss
            final Out value = function.apply( key );
            recentUsed = new Entry<In, Out>( key, value );
            return value;
        }
    }

    @Override
    public void purge() {
        //not strictly correct since recentUsed is not volatile
        recentUsed = null;
    }
}

class Entry<Key, Value> {
    public final Key key;
    public final Value value;

    Entry( final Key key,
               final Value value ) {
        this.key = key;
        this.value = value;
    }
}

Дополнительные условия, при которых это работает:

1. Функция function -- идемпотентна, т.е. ее повторный вызов с теми же аргументами не производит никаких дополнительных изменений в системе, по сравнению с первым вызовом. Лучше всего, чтобы она вообще была "чистой" (pure)
2. function должно быть безопасно вызывать из нескольких потоков в произвольном порядке
3. In/Out должны быть immutable объектами

Что мы получаем в итоге?

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

Так же можно реализовывать кэши произвольного размера -- только размер должен быть известен заранее. Сейчас у меня в голове бродит реализация Scatter/Gatherer на этой же основе.

Еще с JavaOne

Вспомнился еще один вопрос по JMM, который прояснился на JavaOne -- что происходит с гарантиями видимости final полей, которые дает JMM, если final поля перезаписываются через reflection? Оказывается, ведут они себя прилично -- перезапись final полей через reflection гарантирует выполнение всех mambars/fences, необходимых, чтобы перезаписанное значение стало доступным всем потокам.

How Caching Affects Hashing

How Caching Affects Hashing

UPD: Продолжение темы здесь

Finally, there's not currently space in the mark word to support both an identity hashCode() value as well as the thread ID needed for the biased locking encoding. Given that, you can avoid biased locking on a per-object basis by calling System.identityHashCode(o). If the object is already biased, assigning an identity hashCode will result in revocation, otherwise, the assignment of a hashCode() will make the object ineligible for subsequent biased locking. This property is an artifact of our current implementation, of course.отсюда

Вот так-то вот -- либо identityHashCode, либо biased locking -- вы бы что выбрали?