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 -- вы бы что выбрали?

Biased locking

У стендов на Java One замечательные люди Алексей Шипилёв и Сергей Куксенко рассказывали много всего интересного. Например, узнал, как именно работает biased locking, и зачем он нужен.

По словам Сергея, история с оптимизацией блокировок началась с того, что лазить syscall-ами в ОС за platform-dependent мьютексами в какой-то момент показалось не очень оптимально -- большое число блокировок берется на малое время, и даже при большом числе потоков contention оказывается весьма мал. Для разруливания этого в JVM были реализованы спин-локи (Сергей называл их thin-locks) -- мы просто заводим поле ownerThreadId, и, пытаясь захватить монитор, CAS(-1, threadId)-им туда свой threadId. Если CAS удался -- мы захватили монитор. Если нет -- мы делаем еще несколько попыток в цикле (а вдруг нынешний владелец отпустит монитор буквально через пару тактов?). Количество итераций это предмет тонкого тюнинга, возможно даже адаптивного, на базе профиля предыдущих попыток. Если даже со спиннингом мы не захватили монитор -- откатываемся к OS-specific locks (Сергей назвал их fat locks).

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

Как я уже говорил, привязанную блокировку можно рассматривать как продолжение спин-лока. Мы захватываем блокировку в собственность (привязываем ее) точно так же, CAS-ом записывая свой threadId. Только в отличие от спин-лока мы не отдаем ее назад. Вместо этого мы рядом заводим дополнительное поле, reetranceCount -- где будет 0, если реально мы сейчас блокировку не используем, и глубина захвата (для поддержания реентрабельности) в случае, если используем. Это поле thread-local, пишется-читается обычными store/load, безо всяких волшебных CAS и специальных мембаров.

Самое интересное здесь это процедура отзыва привязки -- если на привязанную блокировку пришел посторонний поток, и пытается ее взять. Необычно то, что не "владеющий" блокировкой поток ее отдает -- а "пришлый" поток ее "отбирает". Выглядит это так: пришлый смотрит поле типа блокировки -- видит там "biased", смотрит ownerID, и останавливает поток с таким ID (sic!). Остановив этот поток мы гарантируем себя от изменения состояния этого монитора -- ведь только поток-владелец может его изменить. (На самом деле здесь все не так просто. Нам нужно не просто остановить поток, но и вынудить его сбросить в память все свои store buffers -- чтобы убедиться, что он не находится в процессе обновления reentranceCount. Сделать это для другого потока -- довольно нетривиальная задача, для которой готовых решений разработчиками процессоров не предусмотрено. Приходится это делать через совершенно эзотерические, заточенные под конкретный процессор "хаки" -- некоторые действия, у которых основное назначение совсем другое, но побочный эффект которых -- на данной архитектуре -- сброс буферов. Краткий обзор этих хаков, встретившийся мне в статье, способен лишить вас сна на пару дней, и опустить ЧСВ ниже плинтуса) Гарантировав себе stop-the-world для отдельно взятого монитора мы теперь считываем reentranceCount (как я понял, здесь все так легко и просто только в случае архитектур с аппаратной когерентностью кэша -- как интеловские и AMD-шные). Если reentranceCount=0, значит поток-бывший-владелец сейчас монитор не использовал, и мы можем просто сменить тип монитора на thin (spin-lock), захватить его уже на себя, и разбудить назад бывшего владельца. Если же reentranceCount > 0 -- все серьезно, и мы вынуждены откатиться к fat (OS-specific) блокировкам.

Таким образом получается, что для biased locks начальный захват умеренно дорог (один CAS), дальнейший захват очень дешев ( обычный store), отзыв привязки очень дорог (требует syscall для остановки владельца, плюс несколько CAS-ов для смены типа блокировки и захвата под себя).

Любопытные вещи -- biased locks оказывается активируются не сразу ("по-умолчанию") а лишь после некоторого прогрева JVM. Почему так Сергей сказать точно не смог, предположил, что так удается избежать привязки объектов к инициализирующему потоку, который, часто, больше на протяжении всей работы приложения никогда с созданными объектами и не работает. Правда, флагами запуска JVM это можно переопределить.

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

ReentrantLock vs synchronized

Загадочное поведение старых и новых локов в java (регулярно обнаруживаю паттерны, где ReentrantLock быстрее, и так же регулярно -- где выигрывает synchronized) -- наконец-то получило более-менее вменяемое объяснение. Сегодня, на Java One мне рассказали всю правду о том, как и какие локи устроены.

Вкратце, ответ на мой вопрос такой: при малом уровне contention выигрывает synchronized, при большом -- ReentrantLock. synchronized выигрывает за счет того, что для него работает "привязывание" (biased locking) -- для Reentrant такая оптимизация пока не реализована. Reentrant выигрывает за счет того, что для него (в non-fair режиме) реализовано "выхватывание" (bargain) блокировки, когда поток, подошедший на блокировку точно в момент, когда ее освободил другой поток, получит блокировку немедленно, в обход уже, может быть, целой очереди давно ждущих этой блокировки потоков. Это, хотя и "не честно", зато позволяет сэкономить на переключении контекстов потоков.

Никто, разумеется, не отменял бенчмарков в конкретном приложении...

IO performance

Гонял тесты производительности ввода-вывода. Обнаружил интересную деталь -- чтение файлов с использованием обычного streaming-io (Input/OutputStream) замедляется, по мере увеличения буфера чтения. У меня на сервере (linux, RAID5) чтение замедляется почти вдвое при увеличении буфера с 128Кб до 10Мб. Причем это достаточно достоверно заметно во всей серии экспериментов с разными размерами файлов.

А вот чтение с использованием NIO (channels) так же вполне достоверно ускоряется, с увеличением размера буфера (под размером буфера здесь я подразумеваю аргумент count в вызове

FileChannel.transferTo( position, count, target )

. В целом, для чтения NIO быстрее old-school IO примерно на 10-20%

C записью положение более "универсальное" -- максимум скорости в районе размера буфера 128-512Кб, независимо от способа. Разница в скорости IO streams/NIO channels практически отсутствует.

В итоге (для нашего сервера) можно считать, что оптимальное значение "для всех миров" лежит где-то в районе 64-512Кб.

P.S. Да, эти значения актуальны для больших файлов -- > 10Гб. Для мелких файлов планка оптимального размера буфера смещается вниз -- 8-32Кб

Что каждый программист...

...должен знать о плавающей запятой. Увлекся чтением очередной книги из серии. Черт, парни, которые создавали стандарт IEEE 754 -- да они просто гении! Надеюсь, лет через 10-15 я буду способен создавать настолько же продуманные системы.

NaN-ов много, надо это использовать

Сегодня на хабре проскочила замечательная статья Что нужно знать про арифметику с плавающей запятой. Там довольно подробное "человеческое" описание IEEE754, даже немного истории есть. Нет, принципиально нового в ней не так уж много, но все в одном месте, и на русском -- это дорогого стоит. Автору большое спасибо.

Что меня в ней поразило, так это фраза, цитирую:
Неопределенность или NaN (от not a number) – это представление, придуманное для того, чтобы арифметическая операция могла всегда вернуть какое-то не бессмысленное значение. В IEEE754 NaN представлен как число, в котором E=Emax+1, а мантисса не нулевая. Любая операция с NaN возвращает NaN. При желании в мантиссу можно записывать информацию, которую программа сможет интерпретировать. Стандартом это не оговорено и мантисса чаще всего игнорируется.

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

MySQL HandlerSocket

HandlerSocket -- это расширение (плагин) для MySQL, позволяющий делать простые CRUD запросы непосредственно к движку хранения данных MySQL, обходя слой SQL. По словам автора, производительность такого решения в случае, когда данные БД влезают в память выше, чем производительность memcached. При том, что мы сохраняем возможность работать с теми же данными через SQL.

Здесь краткое введение в тему.

А здесь -- драйвер для java. Осталось только найти повод его где-нибудь попользовать

Range check elimination

Узнал приятную новость -- оказывается в OpenJDK JIT умеет делать (пока что простейшие) array range check elimination (пруф). Другими словами -- в простых циклах по массивам вида

for(int i=0;i<arr.length;i++){ 
    arr[i] = ...;
}

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

Пока я, правда, не понял, используется ли это в какой-нибудь release версии JDK.