23 июня 2011 г.

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

Как-то раз, на очередном этапе оптимизации в текущем проекте в список 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. Код здесь

22 июня 2011 г.

How caching affects hashing

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

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

Реализация хэш-таблицы с открытой адресацией требует выбора последовательности проб, которая будет использоваться для разрешения коллизий. Часто используемые варианты:
  1. линейное хэширование -- linear probing (Hi(KEY) = (H0(KEY) + k*i) mod N, где k часто берут =1)
  2. двойное хэширование -- linear double hashing (Hi(KEY) = (H0(KEY) + H1(KEY)*i) mod N)
  3. экспоненциальное хэширование -- exponential double hashing (Hi(KEY) = (H0(KEY) + H1(KEY)*ai) 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 уже мало чем отличается от остальных -- а по среднему количеству попыток, как известно, проигрывает...

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

21 июня 2011 г.

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

Великолепная статья Дэвида -- про одну из характерных ошибок при бенчмаркинге 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. Но когда это будет реализовано -- неизвестно.

20 июня 2011 г.

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 я первый раз слышу. Что это такое, интересно?

1 июня 2011 г.

Снова о 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.