Великолепная статья Дэвида -- про одну из характерных ошибок при бенчмаркинге high-concurrent приложений.
Допустим, у нас есть код, который плохо масштабируется. Проще говоря, если построить график в осях "пропускная способность (Y) -- количество worker-ов (Х)", то график будет выпуклым вверх: сначала пропускная способность будет расти, потом достигнет максимума, и начнет убывать. Обычная причина состоит в том, что накладные расходы на взаимодействие между worker-ами начинают доминировать, и съедают весь потенциальный прирост производительности.
Часто оказывается, что ситуацию можно "улучшить" если некоторым способом ограничить степень конкурентности -- например, введя задержки (back-offs). "Улучшить" в том смысле, что производительность, разумеется, все равно не будет далее расти с ростом количества worker-ов, но, по крайней мере, она не будет и падать -- вместо кривой с максимумом и дальнейшим падением мы получим кривую, выходящую на асимптоту.
Допустим теперь, что мы пока еще не сделали эту "оптимизацию", и работаем со своим кодом в той области высокой конкуренции, где его производительность уже деградирует (т.е. меньше максимума). Мы пытаемся его оптимизировать, используя стандартный цикл измерение-анализ-модификация. Тогда легко может оказаться, что какая-нибудь модификация, замедляющая выполнение кода сработает как неявная задержка (back-off), "улучшающая" его конкурентные свойства. "Улучшающая", повторяю, в том лишь смысле, что она перемещает начало деградации на более высокие уровни конкурентности, чем нам сейчас доступны. Платой за это является то, что при меньшей конкурентности производительность будет хуже.
Введение явных задержек, вместо неявной деоптимизации, разумеется лучше -- хотя бы в том смысле, что мы осознаем, что эти задержки полезны только при высокой конкуренции, и можем включать их только при превышении определенного уровня конкурентности -- не оказывая тем самым эффекта на скорость выполнения кода в низкоконкурентном случае.
Похожий эффект может возникать при профилировании -- код, выполняющий измерения (инкрементируемые счетчики, вызываемые callback-и...) так же может выступать в роли источника неявных задержек, улучшающих производительность в области где она начинает падать. Получается "гейзенбаг" в бенчмаркинге: производительность улучшается, когда за системой начинают наблюдать :)
Этот эффект нужно иметь ввиду при бенчмаркинге конкурентных приложений. Хорошей практикой будет проверять эффект каждого изменения в максимально широком диапазоне конкурентности, а не только для пиковых значений.
21 июня 2011 г.
"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. Но когда это будет реализовано -- неизвестно.
Небольшое отступление о работе 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 я первый раз слышу. Что это такое, интересно?
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.
Но если я записываю 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.
7 мая 2011 г.
"Java locks Analysis and Acceleration" by Kiyokuni Kawachiya
Диссертация человека, который активно участвовал в работе над оптимизацией блокировок в IBM JDK. Подробно расписана история и механика (вплоть до псевдокода) различных оптимизаций. В частности, можно найти как подробное описание исходной версии biased locks (с аццкой магией вроде перемещения instruction pointer-а чужого потока), так и более простой и эффективной версии, с возможностью rebiasing-а. В общем, рекомендую -- даже поверхностное чтение сильно улучшает качество картинки по этому вопросу в мозгу.
Качать здесь (.pdf)
Качать здесь (.pdf)
29 апреля 2011 г.
Without locks
Последние несколько недель в голове вертится идея об организации межпоточного взаимодействия без блокировок. Идея эта звучит примерно так "иногда проще сделать что-то самому, чем организовывать протокол для передачи результата от коллеги". На практике это про то, что иногда лучшая синхронизация -- отсутствие таковой. Вместо того, чтобы строго гарантировать, что результат выполнения какой-то задачи будет получен только однажды, только одним потоком, а остальные будут его использовать, мы можем построить систему, где будет более мягкое утверждение -- "если результат уже посчитан одним потоком, и успел стать видимым другому -- он будет использован, если не посчитан, или не успел стать видимым -- значит посчитаем его второй раз, не надорвемся"
Самый наглядный пример реализации -- ленивый кэш. Вот, например, простейший вариант -- кэшируем только результат последнего вызова:
Дополнительные условия, при которых это работает:
Что мы получаем в итоге?
Так же можно реализовывать кэши произвольного размера -- только размер должен быть известен заранее. Сейчас у меня в голове бродит реализация Scatter/Gatherer на этой же основе.
Самый наглядный пример реализации -- ленивый кэш. Вот, например, простейший вариант -- кэшируем только результат последнего вызова:
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;
}
}
Дополнительные условия, при которых это работает:
- Функция function -- идемпотентна, т.е. ее повторный вызов с теми же аргументами не производит никаких дополнительных изменений в системе, по сравнению с первым вызовом. Лучше всего, чтобы она вообще была "чистой" (pure)
- function должно быть безопасно вызывать из нескольких потоков в произвольном порядке
- In/Out должны быть immutable объектами
Что мы получаем в итоге?
- Никаких блокировок
- Задержка с видимостью работает на нас -- если у разных потоков будут свои версии записанного значения, значит у каждого будет своя, самая свежая для него, версия
Так же можно реализовывать кэши произвольного размера -- только размер должен быть известен заранее. Сейчас у меня в голове бродит реализация Scatter/Gatherer на этой же основе.
19 апреля 2011 г.
Еще с JavaOne
Вспомнился еще один вопрос по JMM, который прояснился на JavaOne -- что происходит с гарантиями видимости final полей, которые дает JMM, если final поля перезаписываются через reflection? Оказывается, ведут они себя прилично -- перезапись final полей через reflection гарантирует выполнение всех mambars/fences, необходимых, чтобы перезаписанное значение стало доступным всем потокам.
18 апреля 2011 г.
13 апреля 2011 г.
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 -- вы бы что выбрали?
Вот так-то вот -- либо 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), вместо эскалации до спинлока. Вроде бы такая штука анонсировалась, но работает ли она, и в каких случаях активируется -- неизвестно
По словам Сергея, история с оптимизацией блокировок началась с того, что лазить 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) блокировки, когда поток, подошедший на блокировку точно в момент, когда ее освободил другой поток, получит блокировку немедленно, в обход уже, может быть, целой очереди давно ждущих этой блокировки потоков. Это, хотя и "не честно", зато позволяет сэкономить на переключении контекстов потоков.
Никто, разумеется, не отменял бенчмарков в конкретном приложении...
Вкратце, ответ на мой вопрос такой: при малом уровне contention выигрывает synchronized, при большом -- ReentrantLock. synchronized выигрывает за счет того, что для него работает "привязывание" (biased locking) -- для Reentrant такая оптимизация пока не реализована. Reentrant выигрывает за счет того, что для него (в non-fair режиме) реализовано "выхватывание" (bargain) блокировки, когда поток, подошедший на блокировку точно в момент, когда ее освободил другой поток, получит блокировку немедленно, в обход уже, может быть, целой очереди давно ждущих этой блокировки потоков. Это, хотя и "не честно", зато позволяет сэкономить на переключении контекстов потоков.
Никто, разумеется, не отменял бенчмарков в конкретном приложении...
24 марта 2011 г.
IO performance
Гонял тесты производительности ввода-вывода. Обнаружил интересную деталь -- чтение файлов с использованием обычного streaming-io (Input/OutputStream) замедляется, по мере увеличения буфера чтения. У меня на сервере (linux, RAID5) чтение замедляется почти вдвое при увеличении буфера с 128Кб до 10Мб. Причем это достаточно достоверно заметно во всей серии экспериментов с разными размерами файлов.
А вот чтение с использованием NIO (channels) так же вполне достоверно ускоряется, с увеличением размера буфера (под размером буфера здесь я подразумеваю аргумент count в вызове
C записью положение более "универсальное" -- максимум скорости в районе размера буфера 128-512Кб, независимо от способа. Разница в скорости IO streams/NIO channels практически отсутствует.
В итоге (для нашего сервера) можно считать, что оптимальное значение "для всех миров" лежит где-то в районе 64-512Кб.
P.S. Да, эти значения актуальны для больших файлов -- > 10Гб. Для мелких файлов планка оптимального размера буфера смещается вниз -- 8-32Кб
А вот чтение с использованием 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Кб
3 февраля 2011 г.
Что каждый программист...
...должен знать о плавающей запятой. Увлекся чтением очередной книги из серии. Черт, парни, которые создавали стандарт IEEE 754 -- да они просто гении! Надеюсь, лет через 10-15 я буду способен создавать настолько же продуманные системы.
1 февраля 2011 г.
NaN-ов много, надо это использовать
Сегодня на хабре проскочила замечательная статья Что нужно знать про арифметику с плавающей запятой. Там довольно подробное "человеческое" описание IEEE754, даже немного истории есть. Нет, принципиально нового в ней не так уж много, но все в одном месте, и на русском -- это дорогого стоит. Автору большое спасибо.
Что меня в ней поразило, так это фраза, цитирую:
Неопределенность или NaN (от not a number) – это представление, придуманное для того, чтобы арифметическая операция могла всегда вернуть какое-то не бессмысленное значение. В IEEE754 NaN представлен как число, в котором E=Emax+1, а мантисса не нулевая. Любая операция с NaN возвращает NaN. При желании в мантиссу можно записывать информацию, которую программа сможет интерпретировать. Стандартом это не оговорено и мантисса чаще всего игнорируется.
Что NaN-ов вообще-то много я знал, но что разные NaN-ы можно использовать для передачи каких-то подробностей -- это свежая идея. Нет, конечно, это не для использования в каждодневном программировании, но если есть какая-нибудь часто вызываемая функция, которая возвращает NaN как индикатор "не получилось", то ведь можно вместе с ним передавать, например, конкретную причину. Хотя будет ли это быстрее, чем бросать в таких ситуациях исключение специального типа, с нужной информацией -- вопрос. Нужно потестировать
Что меня в ней поразило, так это фраза, цитирую:
Неопределенность или NaN (от not a number) – это представление, придуманное для того, чтобы арифметическая операция могла всегда вернуть какое-то не бессмысленное значение. В IEEE754 NaN представлен как число, в котором E=Emax+1, а мантисса не нулевая. Любая операция с NaN возвращает NaN. При желании в мантиссу можно записывать информацию, которую программа сможет интерпретировать. Стандартом это не оговорено и мантисса чаще всего игнорируется.
Что NaN-ов вообще-то много я знал, но что разные NaN-ы можно использовать для передачи каких-то подробностей -- это свежая идея. Нет, конечно, это не для использования в каждодневном программировании, но если есть какая-нибудь часто вызываемая функция, которая возвращает NaN как индикатор "не получилось", то ведь можно вместе с ним передавать, например, конкретную причину. Хотя будет ли это быстрее, чем бросать в таких ситуациях исключение специального типа, с нужной информацией -- вопрос. Нужно потестировать
21 декабря 2010 г.
MySQL HandlerSocket
HandlerSocket -- это расширение (плагин) для MySQL, позволяющий делать простые CRUD запросы непосредственно к движку хранения данных MySQL, обходя слой SQL. По словам автора, производительность такого решения в случае, когда данные БД влезают в память выше, чем производительность memcached. При том, что мы сохраняем возможность работать с теми же данными через SQL.
Здесь краткое введение в тему.
А здесь -- драйвер для java. Осталось только найти повод его где-нибудь попользовать
Здесь краткое введение в тему.
А здесь -- драйвер для java. Осталось только найти повод его где-нибудь попользовать
11 октября 2010 г.
Range check elimination
Узнал приятную новость -- оказывается в OpenJDK JIT умеет делать (пока что простейшие) array range check elimination (пруф). Другими словами -- в простых циклах по массивам вида
если компилятор может доказать, что счетчик цикла не выходит за границы массива -- runtime проверки индекса при доступе к элементам массива будут убраны. А это означает, что скорость такого доступа уже точно ничем дополнительным, по сравнению с С, не ограничена
Пока я, правда, не понял, используется ли это в какой-нибудь release версии JDK.
for(int i=0;i<arr.length;i++){
arr[i] = ...;
}
если компилятор может доказать, что счетчик цикла не выходит за границы массива -- runtime проверки индекса при доступе к элементам массива будут убраны. А это означает, что скорость такого доступа уже точно ничем дополнительным, по сравнению с С, не ограничена
Пока я, правда, не понял, используется ли это в какой-нибудь release версии JDK.
28 сентября 2010 г.
Импорт классов из default package
C удивлением обнаружил, что, оказывается, классы из дефолтного пакета (которые в корне иерархии) нельзя импортировать и использовать в классах из любых других пакетов! Т.е. использовать можно, но только через reflection -- Class.forName(".."), etc. Более того, оказывается когда-то в java это было разрешено -- специальной конструкцией
import Unfinished; (а я даже не знал, что такая есть...). О, сколько нам открытий чудных...
15 сентября 2010 г.
Развернутый связный список
Стыдно признаться, но я никогда еще в своей практике не использовал LinkedList. Не находилось оказии -- всегда оказывалось, что ArrayList либо в принципе подходит лучше, либо алгоритм можно так перестроить, что будет подходить лучше, либо в принципе он хуже, но на потребных размерах выигрывает. Последовательный доступ, большие накладные расходы памяти на хранение указателей в узлах, недружественность к кэшу и векторным инструкциям -- на мой взгляд, этого достаточно, чтобы 10 раз подумать, прежде чем его использовать. Тем не менее, никуда не деться -- вставка в случайное место для ArrayList дороже, чем для Linked уже начиная где-то с 500-1000 элементов (ну еще есть многопоточные приложения, где недружественность к кэшу становится преимуществом -- меньше конкуренция разных вычислительных ядер за строки кэша).
Не далее как вчера я обдумывал эту мысль, и пришел к выводу, что если бы мне нужен был быстрый список без (быстрого) случайного доступа но со всеми остальными плюшками, я бы попробовал сделать что-то вроде смеси array и linked -- узлы с массивами по нескольку элементов, так, чтобы узел вместе со всей служебной информацией влезал, скажем, в cache line. Получаем сразу и меньшие накладные расходы памяти -- одна пара указателей не на один, а сразу на несколько элементов. И лучшую локальность данных, и поле применимости для векторых инструкций. Все плюшки, кроме быстрого случайного доступа.
А сегодня обнаруживаю, что идею украли прямо из головы. И даже обозвать уже успели, и в википедии записали. Называется развернутый связный список (unrolled linked list). Неплохая статья на MSDN по этой структуре данных. Автор провел небольшое исследование производительности, и нашел, что развернутый список обходится (последовательно) примерно в 2.5 раза медленнее массива (обычный связный -- в 12 раз медленнее). На мой взгляд -- вполне разумный компромисс.
Еще вчера же, когда я дочитывал про B-trees, мне так же пришло в голову, что обычные бинарные диревья в нынешних условиях многоуровневых кэшей и векторных инструкций тоже очень не в тему. Всякие TreeMap разумнее было бы делать на базе B-trees, нежели на основе красно-черных бинарных деревьев. Ведь в конце-концов B-trees и были придуманы для ситуаций, когда операция сравнения элементов гораздо (на порядки) дешевле операции загрузки очередной страницы дерева. Некогда имелась в виду загрузка с диска/ленты, но нынче в роли "медленного хранилища" вполне подходит основная оперативная память. При разнице в скоростях доступа к кэшу и оперативке в несколько порядков -- куда уж медленнее. Вместо того, чтобы делать одно сравнение, и переходить к следующему узлу -- с высокой вероятностью кэш-промаха -- было бы оптимальнее сделать десяток-другой сравнений сразу.
Не далее как вчера я обдумывал эту мысль, и пришел к выводу, что если бы мне нужен был быстрый список без (быстрого) случайного доступа но со всеми остальными плюшками, я бы попробовал сделать что-то вроде смеси array и linked -- узлы с массивами по нескольку элементов, так, чтобы узел вместе со всей служебной информацией влезал, скажем, в cache line. Получаем сразу и меньшие накладные расходы памяти -- одна пара указателей не на один, а сразу на несколько элементов. И лучшую локальность данных, и поле применимости для векторых инструкций. Все плюшки, кроме быстрого случайного доступа.
А сегодня обнаруживаю, что идею украли прямо из головы. И даже обозвать уже успели, и в википедии записали. Называется развернутый связный список (unrolled linked list). Неплохая статья на MSDN по этой структуре данных. Автор провел небольшое исследование производительности, и нашел, что развернутый список обходится (последовательно) примерно в 2.5 раза медленнее массива (обычный связный -- в 12 раз медленнее). На мой взгляд -- вполне разумный компромисс.
Еще вчера же, когда я дочитывал про B-trees, мне так же пришло в голову, что обычные бинарные диревья в нынешних условиях многоуровневых кэшей и векторных инструкций тоже очень не в тему. Всякие TreeMap разумнее было бы делать на базе B-trees, нежели на основе красно-черных бинарных деревьев. Ведь в конце-концов B-trees и были придуманы для ситуаций, когда операция сравнения элементов гораздо (на порядки) дешевле операции загрузки очередной страницы дерева. Некогда имелась в виду загрузка с диска/ленты, но нынче в роли "медленного хранилища" вполне подходит основная оперативная память. При разнице в скоростях доступа к кэшу и оперативке в несколько порядков -- куда уж медленнее. Вместо того, чтобы делать одно сравнение, и переходить к следующему узлу -- с высокой вероятностью кэш-промаха -- было бы оптимальнее сделать десяток-другой сравнений сразу.
5 сентября 2010 г.
Потестировал на днях свою реализацию lock-free BufferedQueue. Неожиданно, но версия с блокировками всухую обходит CAS. Пока не могу понять, в чем дело -- грешу на ConcurrentLinkedQueue
Оказывается, с атомиками все тоже не так-то просто. Они, конечно, дешевле блокировок, но создают ничуть не меньший траффик на межпроцессорной (межядерной) шине. В определенных условиях это может сильно ухудшать производительность.
Оказывается, с атомиками все тоже не так-то просто. Они, конечно, дешевле блокировок, но создают ничуть не меньший траффик на межпроцессорной (межядерной) шине. В определенных условиях это может сильно ухудшать производительность.
1 сентября 2010 г.
Shared exceptions
Доктор Хейнс Кабуц в очередной рассылке пишет про интересную вещь -- оказывается, если в коде часто выбрасываются RuntimeException типа NPE, или ArrayIndexOutOfBoundsException, то JIT в серверном режиме их оптимизирует -- начиная с какого-то момента он перестанет создавать новый экземпляр исключения на каждый случай, а начнет каждый раз бросать один и тот же экземпляр, с пустым stack trace! Я припоминаю, что в самом деле видел такие исключения без стека вызовов -- но как-то не подумал, с чем это может быть связано, списал на баг протоколирования. Оказывается эта оптимизация выполняется аж с 2002 года -- хотя я до сих пор нигде не встречал ее описания.
Подписаться на:
Сообщения (Atom)