Поскольку в комментариях ответ нашли аж несколько раз, то сознаюсь — да, идея в том, что второй процессор это не только дополнительные 600 баксов стоимости и 70Вт энергопотребления, но еще и лишние 32Кб L1 кэша данных (а в Sandy Bridge так и лишние 256Кб L2, потому что там L2 тоже на каждое ядро). Так что, хотя в общем случае логично ожидать, что однопроцессорная версия будет быстрее (потому что не надо тратиться на синхронизацию), но если задача достаточно memory intensive (т.е. мы упираемся в скорость доступа к данным), причем фазы P1 и P2 оперируют разными данными, то в двухпроцессорном варианте данные фазы 1 будут горячими в кэше CPU1, а данные фазы 2 горячими в кэше CPU2. Получим эффективный размер L1 в 64Кб. И эффект от такого "увеличения" кэша может оказаться доминирующим, и оправдать даже расходы на синхронизацию.
Показаны сообщения с ярлыком benchmarking. Показать все сообщения
Показаны сообщения с ярлыком benchmarking. Показать все сообщения
4 февраля 2013 г.
28 января 2013 г.
А что мы измеряем, когда измеряем "производительность CAS-а"?
Очередная статья Мартина — продолжение одного из его уже довольно старых экспериментов. Там у него получилось, что простейший бенчмарк скорости выполнения
intcementAndGet (==lock xadd) показывает лучшие результаты на процессорах архитектуры Nehalem, нежели на процессорах более свежей (и, вообще говоря, почти везде более производительной) архитектуры Sandy Bridge. Бенчмарк был совершенно тривиальный — сколько-то потоков, тупо делающих __sync_add_and_fetch() одному счетчику — поэтому результаты, конечно, выглядели странно. И вот, больше чем через год, наконец-то странность объяснилась, и объяснение очень интересное — я не могу удержаться, и не разобрать его.18 октября 2012 г.
Off-heap: троллинг 70-го уровня
Последнее время я часто сталкиваюсь с идеей off-heap storage в java. Это когда
DirectByteBuffer/Unsafe используют для организации данных вне java heap. Предположительно, это должно радикально снизить нагрузку на GC, да и, в некоторых случаях, сам доступ к данным ускорить. Сам я к этой идее относился довольно скептически: на мой взгляд у нее довольно узкая область применимости, и усилиями разработчиков JVM она становится с каждым годом еще уже. Мне кажется, многие, кто смотрит в сторону off-heap просто еще не разобрались толком, что можно делать на чистой java. Но пока это были все теоретические предположения — с Unsafe я проводил лишь один небольшой эксперимент, и, хоть предположения он, косвенно, и подтвердил, но одного эксперимента для выводов явно недостаточно. А сделать серьезный бенчмарк как-то было лениво. 22 апреля 2012 г.
Код бенчмарков
Отдельные люди на JavaOne после доклада просили выложить код бенчмарков. Вот, код здесь.
Ногами прошу не бить :)
Ногами прошу не бить :)
21 апреля 2012 г.
...расследования
Я уже писал, что мне наконец-таки пришла в голову мысль, почему у Disruptor в бенчмарках такой большой статистический разброс. Еще точнее -- это не статистический гауссовский шум, а совершенно отчетливо различные режимы работы -- вот только не было понятно, откуда там внутри, где все просто, берутся еще какие-то режимы. Так вот, разгадка этого явления мне явилась в 5 утра в прошлую среду, во время подготовки слайдов к докладу. В честь такого счастья мне показалось честным рассказать про разгадку сначала на докладе, а уж потом здесь :)
В общем, одна картинка -- стоит тысячи слов. А уж знали бы вы, чего мне стоило выдрать эту картинку из своей презентации! ГуглоДокументы так просто контент не отдают:)
Идея простая. Поскольку бенчмарки у меня без нагрузки, то скорость перемещения курсоров издателя/подписчика определяется, в основном, внутренней механикой. А она у издателя и подписчика почти идентична. Поэтому двигаться они будут примерно с одиноковой скоростью. А значит в установившимся режиме они будут находиться на каком-то более-менее фиксированном растоянии друг от друга. Ну, разумеется, как-то колебаясь вокруг этого среднего расстояния.
Так вот, если это среднее расстояние таково, что записываемые издателем сообщения находятся на другом кэш-лайне, чем читаемые подписчиком -- то все шоколадно, контроллер памяти работает в приемлемом режиме. А вот если расстояние окажется слишком маленьким -- издатель и подписчик будут работать в пределах одного кэш-лайна. А значит -- контроллер памяти будет играть в пинг-понг: издатель будет для записи требовать кэшлайн в в своем кэше в состоянии M, а читатель -- в своем, в состоянии S. Да, это типичный пример false sharing.
Какое расстояние будет в установившемся режиме -- это, как я понимаю, в значительной степени случайность. Как там в переходном режиме система поколбасится -- так и будет. Спонтанное нарушение симметрии, одним словом :) Вот и получается несколько режимов функционирования с разной пропускной способностью -- в зависимости от случайного gap-а между курсорами, сложившегося в переходном процессе.
Отсюда же понятно, почему отключение бэтчинга для подписчика ускоряет систему в ненагруженном режиме -- бэтчинг это оптимизация, слегка ускоряющая подписчика. А значит он будет с большей вероятностью догонять издателя, и постоянно тыкаться в его спину. А это, как мы уже поняли, не эффективно.
Интересная штука -- когда курсоры идут плотно друг к другу пропускная способность падает. А вот время ответа (latency) -- скорее всего тоже будет падать. Я его не измерял, но кажется очевидным, что чем меньше расстояние между первым и последним курсором в цепочке -- тем быстрее конкретное сообщение будет полностью обработано. А это значит, что бэтчинг здесь это такой размен throughput<->latency. Можно чуть поднять throughput, но ценой увеличения времени обработки одного сообщения. Можно чуть уменьшить время ответа -- но ценой падения и пропускной способности (==менее эффективного использования шины interconnect-а).
И смотрите, как любопытно выходит (дальше мои довольно умозрительные рассуждения): почти наверняка замедление работы в subscriber-batching будет проявляться только в ненагруженном режиме. В нагруженном режиме скорость движения курсоров определяется не их механикой, а нагрузкой -- курсоры двигаются настолько быстро, насколько обработчик успевает делать свою работу. А это значит, что система будет самоподстраивающейся: если нагрузки немного, и обработчики успевают все перемолоть быстро -- они догонят издателя, и будут идти за ним ноздря в ноздрю, уменьшая время ответа. Как только нагрузка вырастает, обработчики начинают не справляться с работой так быстро -- и отстают от издателя. А это сразу дает им чуть-чуть продохнуть за счет более эффективного бэтчинга (больше сообщений за раз) и за счет большего КПД использования interconnect-а. Все это, разумеется, в некоторых, небольших, пределах -- серьезное изменение нагрузки так не скомпенсируешь. Можно даже примерно прикинуть, насколько небольших: худший режим с бэтчингом у нас 15 000 пакетов/мс (~70 нс/пакет), лучший без бэтчинга 35 000 (~30нс/пакет). Разница в 40 нс -- это и есть оценка того, сколько может нам сэкономить сам Disruptor за счет автоматического перехода между режимами.
UPD: Как мне тонко намекнули в комментариях, я забыл важную часть -- гипотеза-то ценна не сама по себе, а тем, что она имеет экспериментальные подтверждения! А именно: если причина ухудшения пропускной способности при включении бэтчинга и нестабильности работы -- действительно такая, как я предположил, то должна быть корреляция между средним расстоянием между курсорами (а схеме это обозначено как gap), и пропускной способностью в конкретном эксперименте. Это можно проверить, и я это проверил. Результат -- вот он (по X -- gap, по Y -- throughput):
По-моему, все очень наглядно. Скачок производительности происходит как раз в области gap=2.5-3.0 Это отлично коррелирует с тем фактом, что размер сообщений у меня примерно 24 байта, т.е. их на 64-байтный кэшлайн умещается как раз чуть меньше 3 штук.
UPD#2: По многочисленным просьбам трудящихся числом 2 -- бенчмарки с пэддингом сообщений. Без batching 19 789 (+/- 483), с batching 20 488 (+/- 1 277).
В общем, одна картинка -- стоит тысячи слов. А уж знали бы вы, чего мне стоило выдрать эту картинку из своей презентации! ГуглоДокументы так просто контент не отдают:)
Идея простая. Поскольку бенчмарки у меня без нагрузки, то скорость перемещения курсоров издателя/подписчика определяется, в основном, внутренней механикой. А она у издателя и подписчика почти идентична. Поэтому двигаться они будут примерно с одиноковой скоростью. А значит в установившимся режиме они будут находиться на каком-то более-менее фиксированном растоянии друг от друга. Ну, разумеется, как-то колебаясь вокруг этого среднего расстояния.
Так вот, если это среднее расстояние таково, что записываемые издателем сообщения находятся на другом кэш-лайне, чем читаемые подписчиком -- то все шоколадно, контроллер памяти работает в приемлемом режиме. А вот если расстояние окажется слишком маленьким -- издатель и подписчик будут работать в пределах одного кэш-лайна. А значит -- контроллер памяти будет играть в пинг-понг: издатель будет для записи требовать кэшлайн в в своем кэше в состоянии M, а читатель -- в своем, в состоянии S. Да, это типичный пример false sharing.
Какое расстояние будет в установившемся режиме -- это, как я понимаю, в значительной степени случайность. Как там в переходном режиме система поколбасится -- так и будет. Спонтанное нарушение симметрии, одним словом :) Вот и получается несколько режимов функционирования с разной пропускной способностью -- в зависимости от случайного gap-а между курсорами, сложившегося в переходном процессе.
Отсюда же понятно, почему отключение бэтчинга для подписчика ускоряет систему в ненагруженном режиме -- бэтчинг это оптимизация, слегка ускоряющая подписчика. А значит он будет с большей вероятностью догонять издателя, и постоянно тыкаться в его спину. А это, как мы уже поняли, не эффективно.
Интересная штука -- когда курсоры идут плотно друг к другу пропускная способность падает. А вот время ответа (latency) -- скорее всего тоже будет падать. Я его не измерял, но кажется очевидным, что чем меньше расстояние между первым и последним курсором в цепочке -- тем быстрее конкретное сообщение будет полностью обработано. А это значит, что бэтчинг здесь это такой размен throughput<->latency. Можно чуть поднять throughput, но ценой увеличения времени обработки одного сообщения. Можно чуть уменьшить время ответа -- но ценой падения и пропускной способности (==менее эффективного использования шины interconnect-а).
И смотрите, как любопытно выходит (дальше мои довольно умозрительные рассуждения): почти наверняка замедление работы в subscriber-batching будет проявляться только в ненагруженном режиме. В нагруженном режиме скорость движения курсоров определяется не их механикой, а нагрузкой -- курсоры двигаются настолько быстро, насколько обработчик успевает делать свою работу. А это значит, что система будет самоподстраивающейся: если нагрузки немного, и обработчики успевают все перемолоть быстро -- они догонят издателя, и будут идти за ним ноздря в ноздрю, уменьшая время ответа. Как только нагрузка вырастает, обработчики начинают не справляться с работой так быстро -- и отстают от издателя. А это сразу дает им чуть-чуть продохнуть за счет более эффективного бэтчинга (больше сообщений за раз) и за счет большего КПД использования interconnect-а. Все это, разумеется, в некоторых, небольших, пределах -- серьезное изменение нагрузки так не скомпенсируешь. Можно даже примерно прикинуть, насколько небольших: худший режим с бэтчингом у нас 15 000 пакетов/мс (~70 нс/пакет), лучший без бэтчинга 35 000 (~30нс/пакет). Разница в 40 нс -- это и есть оценка того, сколько может нам сэкономить сам Disruptor за счет автоматического перехода между режимами.
UPD: Как мне тонко намекнули в комментариях, я забыл важную часть -- гипотеза-то ценна не сама по себе, а тем, что она имеет экспериментальные подтверждения! А именно: если причина ухудшения пропускной способности при включении бэтчинга и нестабильности работы -- действительно такая, как я предположил, то должна быть корреляция между средним расстоянием между курсорами (а схеме это обозначено как gap), и пропускной способностью в конкретном эксперименте. Это можно проверить, и я это проверил. Результат -- вот он (по X -- gap, по Y -- throughput):
По-моему, все очень наглядно. Скачок производительности происходит как раз в области gap=2.5-3.0 Это отлично коррелирует с тем фактом, что размер сообщений у меня примерно 24 байта, т.е. их на 64-байтный кэшлайн умещается как раз чуть меньше 3 штук.
UPD#2: По многочисленным просьбам трудящихся числом 2 -- бенчмарки с пэддингом сообщений. Без batching 19 789 (+/- 483), с batching 20 488 (+/- 1 277).
1 апреля 2012 г.
Скандалы, интриги...
Дошли руки посмотреть на бенчмарки самого Disruptor-а -- у него их есть немного. Сколько я помню, они сравнивали Disruptor vs ArrayBlockingQueue. Но в последних версиях в бенчмарках используются уже LinkedBlockingQueue -- якобы, они быстрее.
Интрига в том, что в их бенчмарках это действительно так -- LBQ стабильно лучше ABQ. Но в моих бенчмарках ситуация ровно обратная -- ABQ стабильно лучше. И я не могу найти причин, почему это так.
UPD: Оказывается, что LBQ быстрее на моем ноуте (Core i7 2GHz), а вот ABQ быстрее на сервере (Xeon E5620 2.4GHz). Подозрение мое падает даже не на то, что это разные модели, а больше на то, что сервер, кажется, ccNUMA, а ноут SMP. Хотя внятно объяснить, как это связано я пока не могу
Интрига в том, что в их бенчмарках это действительно так -- LBQ стабильно лучше ABQ. Но в моих бенчмарках ситуация ровно обратная -- ABQ стабильно лучше. И я не могу найти причин, почему это так.
UPD: Оказывается, что LBQ быстрее на моем ноуте (Core i7 2GHz), а вот ABQ быстрее на сервере (Xeon E5620 2.4GHz). Подозрение мое падает даже не на то, что это разные модели, а больше на то, что сервер, кажется, ccNUMA, а ноут SMP. Хотя внятно объяснить, как это связано я пока не могу
15 февраля 2012 г.
Arrays.sort() через Unsafe
Наблюдая за тем, как Даг Ли в последних версиях FJ активно использует Unsafe для доступа к массивам, мне пришел в голову вопрос: а что будет, если взять реализацию Arrays.sort(), и переписать ее через Unsafe[.arrayBaseOffset(), .arrayIndexScale(), .putXXX(), .getXXX()]? Казалось бы, таким образом можно избавиться от range checks. Да, JIT умеет их и сам убирать -- но лишь тогда, когда может доказать, что конкретный сценарий доступа к массиву эти самые границы гарантированно не нарушает. В сортировке доступ к массиву идет довольно причудливым паттерном, и кажется, что JIT-у вряд ли по силам доказать отсутствие необходимости проверки границ.
Я не поленился -- переписал Arrays.sort(long[]) на прямой доступ. UnsafeArraysSorter.java (у меня все еще 1.6, так что тимсорта не ждите). Прогнал тесты -- и вот фиг вам. Классическая реализация стабильно немного быстрее (+2-3% -- разброс результатов здесь маленький, так что даже такая мелочь вполне заметна).
Сижу теперь, и думаю -- да как же это? Либо JIT в целом умнее, чем я думал, либо он что-то особенное знает об Arrays.sort() :) Второй вариант мне кажется вероятнее.А власти-то -- скрывают!
Я не поленился -- переписал Arrays.sort(long[]) на прямой доступ. UnsafeArraysSorter.java (у меня все еще 1.6, так что тимсорта не ждите). Прогнал тесты -- и вот фиг вам. Классическая реализация стабильно немного быстрее (+2-3% -- разброс результатов здесь маленький, так что даже такая мелочь вполне заметна).
Сижу теперь, и думаю -- да как же это? Либо JIT в целом умнее, чем я думал, либо он что-то особенное знает об Arrays.sort() :) Второй вариант мне кажется вероятнее.
12 января 2012 г.
Disruptor #3.2: Эксперименты с производительностью -- update
Последняя серия экспериментов закончилась на том, что между самой оптимизированной реализацией очереди и Disruptor-ом все еще оставалось порядка 10% разницы (27 против 30*10^6 сообщений/сек на моем сервере). По косвенным данным, оставшиеся 10% можно было списать на записи ссылок в массив -- в очереди это делается при каждом enqueue, Д же заполняет массив только однажды (Тут надо заметить, что в моем бенче этот эффект так заметен, потому что я тестирую холостой ход -- полезная нагрузка, передаваемая в сообщении у меня всего 1 long. В реальной жизни полезная нагрузка будет побольше, так что одна дополнительная операция записи ссылки потеряется за несколькими операциями записи полей сообщения -- инфа 100%). Еще я грешил на false sharing by card marking -- поскольку ячейки массива идут подряд, их dirty flags должны быть тоже рядом, и должны обновляться при каждой перезаписи. Из этого я сделал вывод, что в 1.7 с +UseCondCardMark все будет шоколадно -- но это фиг проверишь, потому что 1.7 ставить я все еще не готов.
По зрелому размышлению я пришел к выводу, что card marking здесь не при делах. У меня же ссылки в массив пишутся только одним потоком -- который выполняет enqueue. Вот если бы я на dequeue очищал ссылку в null (как, собственно, стоило бы делать в production-ready коде) -- тогда другое дело. Но же я выкинул очистку на одной из первых оптимизаций -- так что у меня по любому single writer получается.
А вот как проверить, что сама запись ссылки порождает 10% оверхеда -- мне пришло в голову вчера. Все довольно просто: у меня же очереди используют пул сообщений (чтобы не плодить лишнюю аллокацию). Пул, естественно, имеет тот же размер, что и очередь (зачем ему больше?), поэтому после первого же прохода все элементы во внутреннем буфере очереди фиксированы -- на следующих проходах они перезаписываются поверх себя же. Достаточно вместо set сделать там test-and-set -- и можно будет проверять.
Эксперименты были запущены, и -- бинго! -- наконец-то мы совершенно догнали Д :) 30*10^6 msg/sec. Предположение о том, что во всем (в оставшихся 10%) виновата запись ссылки в буфер таким образом, похоже, оправдывается. Процесс разборки магии Д на компоненты на этом можно считать закрытым.
Единственное, что остается для меня все еще не понятным -- это нестабильность результатов. Типичные результаты запуска выглядят так:
Turn # 1 takes 67058 ms; 7456232 ops/sec
Turn # 2 takes 15854 ms; 31537782 ops/sec
Turn # 3 takes 16058 ms; 31137128 ops/sec
Turn # 4 takes 16201 ms; 30862292 ops/sec
Turn # 5 takes 16111 ms; 31034697 ops/sec
Turn # 6 takes 15794 ms; 31657591 ops/sec
Turn # 7 takes 60603 ms; 8250417 ops/sec
Это совершенно не похоже на нормальное распределение вокруг среднего :) Ощущение, что система может функционировать в одном из 2 режимов -- либо все хорошо, либо случается какое-то гавно.ЖопойИнтуитивно я ощущаю, что это тот же случай, что и у Питера -- где-то тут недостаточно полей (padding), из-за чего при неудачной дефрагментации после GC внезапно возникает false sharing. Но вот где именно я пока понять не могу. Вроде бы все важные переменные у меня обложены полями по самые гланды...
По зрелому размышлению я пришел к выводу, что card marking здесь не при делах. У меня же ссылки в массив пишутся только одним потоком -- который выполняет enqueue. Вот если бы я на dequeue очищал ссылку в null (как, собственно, стоило бы делать в production-ready коде) -- тогда другое дело. Но же я выкинул очистку на одной из первых оптимизаций -- так что у меня по любому single writer получается.
А вот как проверить, что сама запись ссылки порождает 10% оверхеда -- мне пришло в голову вчера. Все довольно просто: у меня же очереди используют пул сообщений (чтобы не плодить лишнюю аллокацию). Пул, естественно, имеет тот же размер, что и очередь (зачем ему больше?), поэтому после первого же прохода все элементы во внутреннем буфере очереди фиксированы -- на следующих проходах они перезаписываются поверх себя же. Достаточно вместо set сделать там test-and-set -- и можно будет проверять.
Эксперименты были запущены, и -- бинго! -- наконец-то мы совершенно догнали Д :) 30*10^6 msg/sec. Предположение о том, что во всем (в оставшихся 10%) виновата запись ссылки в буфер таким образом, похоже, оправдывается. Процесс разборки магии Д на компоненты на этом можно считать закрытым.
Единственное, что остается для меня все еще не понятным -- это нестабильность результатов. Типичные результаты запуска выглядят так:
Turn # 1 takes 67058 ms; 7456232 ops/sec
Turn # 2 takes 15854 ms; 31537782 ops/sec
Turn # 3 takes 16058 ms; 31137128 ops/sec
Turn # 4 takes 16201 ms; 30862292 ops/sec
Turn # 5 takes 16111 ms; 31034697 ops/sec
Turn # 6 takes 15794 ms; 31657591 ops/sec
Turn # 7 takes 60603 ms; 8250417 ops/sec
Это совершенно не похоже на нормальное распределение вокруг среднего :) Ощущение, что система может функционировать в одном из 2 режимов -- либо все хорошо, либо случается какое-то гавно.
9 ноября 2011 г.
Задачка с stack overflow
Ways to improve performance consistency -- некий Peter Lawrey -- довольно продвинутый чувак, если судить по его блогу -- написал message-passing штукакенцию, отдаленно напоминающую дизруптор -- в том смысле, что используется что-то вроде массива как носитель, и потоки передают друг другу сообщения, извещая друг друга мембарами. Правда, в качестве массива он использует ByteBuffer.allocateDirect(). Смысл этого для меня пока не очень понятен, но такова уж его идея.
Проблема у мужика в том, что результаты бенчмарков у него скачут примерно вдвое-втрое. И он спрашивает сообщество "WTF, gays?".
Причем его более тщательные исследования намекают, что скачки производительности происходят после срабатывания GC. Это как бы намекает, что дело тут в memory layout-е, который может меняться после дефрагментации памяти в ходе сборки мусора.
С одной стороны, ситуация похожа на ту, что я наблюдал в своих экспериментах. С другой -- в его коде пишутся не ссылки, а просто числа (ByteBuffer только их и принимает) -- а для long[] в качестве носителя у меня результаты вполне себе повторяемые, скачков в разы там нет. Это несколько удивляет.
Моя текущая версия происходящего состоит в том, что Питер использует для привязки к ядрам taskset. Но taskset привязывает процесс целиком. Это значит, что никак не фиксируется, как раскиданы по ядрам потоки внутри процесса. GC запускается, скорее всего, в отдельном потоке -- и создает нифиговую пиковую нагрузку -- при этом в момент его запуска собственно бенчмаркирующие потоки приостановлены (stop-the-world). Очень логично, что в этот момент ОС решедулит потоки, так, что ничего не делающие потоки скидываются на одно ядро, а потоку GC, аццки вкалывающему, выделяется ядро в безраздельное пользование. Соответственно, после того, как сборщик мусора успокоился, ОС почему-то не возвращает потоки назад, на отдельные ядра. Тут возникает вопрос "почему", но мне кажется, что это сценарий реалистичный -- обычно такие важные алгоритмы пишутся довольно консервативно, в духе "нет веских причин -- ничего не трогай". Т.е. если нет веских причин, перебрасывать потоки между ядрами шедулер не будет -- противное может привести к тому, что в каких-то ситуациях ему придется постоянно перекидывать потоки, что, понятно, хреново.
Жду от мужика отзыва -- мои сервера сейчас слишком заняты, чтобы я себе мог позволить погонять бенчмарки самому.
UPD: Питер отписался по результатам. Мое предположение оказалось неверным -- потоки не решедулятся (UPD2: на самом деле, они как раз решедулятся -- но это не оказывает существенного влияния на производительность). Причина оказалась (по его словам) в том, что буфер и счетчики в определенных случаях оказывались лежащими последовательно в памяти. Поскольку паддинг у его счетчиков сделан только после используемого поля value, то буфер, идущий в памяти перед счетчиками может легко заползти на их строку (я писал про такой сценарий в статье про false sharing). Вот и получается фигня всякая...
Проблема у мужика в том, что результаты бенчмарков у него скачут примерно вдвое-втрое. И он спрашивает сообщество "WTF, gays?".
Причем его более тщательные исследования намекают, что скачки производительности происходят после срабатывания GC. Это как бы намекает, что дело тут в memory layout-е, который может меняться после дефрагментации памяти в ходе сборки мусора.
С одной стороны, ситуация похожа на ту, что я наблюдал в своих экспериментах. С другой -- в его коде пишутся не ссылки, а просто числа (ByteBuffer только их и принимает) -- а для long[] в качестве носителя у меня результаты вполне себе повторяемые, скачков в разы там нет. Это несколько удивляет.
Моя текущая версия происходящего состоит в том, что Питер использует для привязки к ядрам taskset. Но taskset привязывает процесс целиком. Это значит, что никак не фиксируется, как раскиданы по ядрам потоки внутри процесса. GC запускается, скорее всего, в отдельном потоке -- и создает нифиговую пиковую нагрузку -- при этом в момент его запуска собственно бенчмаркирующие потоки приостановлены (stop-the-world). Очень логично, что в этот момент ОС решедулит потоки, так, что ничего не делающие потоки скидываются на одно ядро, а потоку GC, аццки вкалывающему, выделяется ядро в безраздельное пользование. Соответственно, после того, как сборщик мусора успокоился, ОС почему-то не возвращает потоки назад, на отдельные ядра. Тут возникает вопрос "почему", но мне кажется, что это сценарий реалистичный -- обычно такие важные алгоритмы пишутся довольно консервативно, в духе "нет веских причин -- ничего не трогай". Т.е. если нет веских причин, перебрасывать потоки между ядрами шедулер не будет -- противное может привести к тому, что в каких-то ситуациях ему придется постоянно перекидывать потоки, что, понятно, хреново.
Жду от мужика отзыва -- мои сервера сейчас слишком заняты, чтобы я себе мог позволить погонять бенчмарки самому.
UPD: Питер отписался по результатам. Мое предположение оказалось неверным -- потоки не решедулятся (UPD2: на самом деле, они как раз решедулятся -- но это не оказывает существенного влияния на производительность). Причина оказалась (по его словам) в том, что буфер и счетчики в определенных случаях оказывались лежащими последовательно в памяти. Поскольку паддинг у его счетчиков сделан только после используемого поля value, то буфер, идущий в памяти перед счетчиками может легко заползти на их строку (я писал про такой сценарий в статье про false sharing). Вот и получается фигня всякая...
3 ноября 2011 г.
Disruptor #3.1.4.1: Эксперименты с производительностью -- анализ
Что можно сказать по поводу результатов экспериментов? Картина получается довольно непростая. Первый вопрос: какой из результатов Disruptor брать за основной -- при разнице в 3 раза между производительностью на малых и больших размерах буфера. Мое мнение, что за основу стоит брать именно 30 миллионов ops/sec, которые он выдает на большом буфере. 75 миллионов на малом буфере с батчингом кажутся мне артефактом "холостого хода". Другими словами, я почти уверен, что если начать использовать более-менее тяжелые объекты событий, и более-менее тяжелые обработчики, то этот результат радикально изменится. На это намекает и гиганский разброс результатов различных экспериментов, и то, что LMAX в реальном своем продакшене сообщает о размере очереди в 2М, и то, что при увеличении размера буфера результаты с батчингом и без него сходятся к одному значению пропускной способности в "жалкие" 30 миллионов операций.
Но если принять за рабочую гипотезу, что реперная точка Disruptor -- 30 миллионов оп/сек, то получается, что потестировать эффект от батчинга у меня толком не получилось -- разница между Д с батчингом и без него становится артефактом эксперимента на холостом ходу. Это не очень-то и удивительно -- батчинг, предположительно, должен сглаживать неравномерности во входном потоке данных, но ведь у нас-то входной поток искусственный, и никаких заметных неравномерностей не содержит, негде батчингу развернуться. Но дело в том, что батчинг -- это принципиальное отличие Disruptor-а от очередей -- отличие в интерфейсе/контракте, а не в реализации (для того, чтобы допустить пакетную обработку в очереди потребуется изменить ее интерфейс). И именно это принципиальное отличие надежно оценить и не удалось. Пичалька...
Тем не менее, если мы принимаем производительность Д за 30 млн. оп/сек, то самая базовая, "тупая" реализация single enq single deq queue может дать нам примерно треть от этой производительности. Применяя к этой тупой реализации последовательно: 1) пул для уменьшения аллокации объектов 2) оптимизацию spin-loop-ов 3) volatile write -> lazySet 4) остаток от деления -> битовая маска -- мы получаем ускорение чуть больше чем вдвое -- т.е. 2/3 от производительности Д, причем вклад от этих трех оптимизаций сравним.
Строго говоря, эти оптимизации не вполне независимы -- то есть, применив их в другой последовательности мы скорее всего получим другие цифры для эффекта каждой из них. Поэтому оценивать их вклад точнее, чем по порядку величины смысла я не вижу.
Ближе подойти к Д мне не удалось (я не готов ставить пока не особо стабильный jdk1.7 с его -XX:+UseCondCardMark на рабочий сервер), но косвенные эксперименты с заменой ссылок на long показывают, что очень вероятно, что еще 1/3 производительности теряется на false sharing by card marking.
И если это так, то самым "доходным" решением в дизайне Д признается идея применить заранее заполненный буфер. Поскольку это сразу позволило им и избежать аллокации объектов-событий, и нагрузки на GC для их сборки, и избежать false sharing при модификации ссылок. В сумме это дает почти половину разницы в производительности между Д и самой тупой реализацией SESDQueue. Остальные тонкости -- в том числе padding (на который любит напирать Мартин в своем блоге), и кэширование условий в spin-loop-ах, и lazySet (о которых он не упоминает:) ) -- на фоне этого выглядят довольно бледно.
Очень впечатляет рывок, который получается заменой Object[] -> long[] -- более чем втрое подскакивает производительность. Выглядит это так, что запись ссылочных полей стоит весьма недешево, по крайней мере в многопоточном окружении.
Вот такая получилась загогулина. Напоминаю только, что все это про холостой ход -- под нагрузкой результаты могут сильно отличаться, и ключевые факторы в производительности могут стать другими.
Но если принять за рабочую гипотезу, что реперная точка Disruptor -- 30 миллионов оп/сек, то получается, что потестировать эффект от батчинга у меня толком не получилось -- разница между Д с батчингом и без него становится артефактом эксперимента на холостом ходу. Это не очень-то и удивительно -- батчинг, предположительно, должен сглаживать неравномерности во входном потоке данных, но ведь у нас-то входной поток искусственный, и никаких заметных неравномерностей не содержит, негде батчингу развернуться. Но дело в том, что батчинг -- это принципиальное отличие Disruptor-а от очередей -- отличие в интерфейсе/контракте, а не в реализации (для того, чтобы допустить пакетную обработку в очереди потребуется изменить ее интерфейс). И именно это принципиальное отличие надежно оценить и не удалось. Пичалька...
Тем не менее, если мы принимаем производительность Д за 30 млн. оп/сек, то самая базовая, "тупая" реализация single enq single deq queue может дать нам примерно треть от этой производительности. Применяя к этой тупой реализации последовательно: 1) пул для уменьшения аллокации объектов 2) оптимизацию spin-loop-ов 3) volatile write -> lazySet 4) остаток от деления -> битовая маска -- мы получаем ускорение чуть больше чем вдвое -- т.е. 2/3 от производительности Д, причем вклад от этих трех оптимизаций сравним.
Строго говоря, эти оптимизации не вполне независимы -- то есть, применив их в другой последовательности мы скорее всего получим другие цифры для эффекта каждой из них. Поэтому оценивать их вклад точнее, чем по порядку величины смысла я не вижу.
Ближе подойти к Д мне не удалось (я не готов ставить пока не особо стабильный jdk1.7 с его -XX:+UseCondCardMark на рабочий сервер), но косвенные эксперименты с заменой ссылок на long показывают, что очень вероятно, что еще 1/3 производительности теряется на false sharing by card marking.
И если это так, то самым "доходным" решением в дизайне Д признается идея применить заранее заполненный буфер. Поскольку это сразу позволило им и избежать аллокации объектов-событий, и нагрузки на GC для их сборки, и избежать false sharing при модификации ссылок. В сумме это дает почти половину разницы в производительности между Д и самой тупой реализацией SESDQueue. Остальные тонкости -- в том числе padding (на который любит напирать Мартин в своем блоге), и кэширование условий в spin-loop-ах, и lazySet (о которых он не упоминает:) ) -- на фоне этого выглядят довольно бледно.
Очень впечатляет рывок, который получается заменой Object[] -> long[] -- более чем втрое подскакивает производительность. Выглядит это так, что запись ссылочных полей стоит весьма недешево, по крайней мере в многопоточном окружении.
Вот такая получилась загогулина. Напоминаю только, что все это про холостой ход -- под нагрузкой результаты могут сильно отличаться, и ключевые факторы в производительности могут стать другими.
2 ноября 2011 г.
Disruptor #3.1.4: Эксперименты с производительностью (продолжение)
Я расчитывал написать продолжение предыдущей статьи уже через пару дней, но эксперименты затянулись...
В предыдущий заход я остановился на том, что оптимизированная single enqueuer single dequeuer очередь на холостом ходу обходит j.u.c.ABQ примерно в 5 раз -- и во столько же раз ее обходит disruptor. Поскольку я не верю в черную магию (тем более -- чужую), приходится ковырять дальше.
Во-первых, по совету мастеров я начал использовать taskset для привязки потоков к ядрам. Потом я еще немного подумал, и решил напрямую звать sched_setaffinity() через JNA для конкретных потоков. Плюс nice -20 чтобы уменьшить шанс вмешательства всяких фоновых процессов -- это несколько уменьшило дрожание и чуть улучшило результаты. Во-вторых я сделал несколько экспериментов на нашем рабочем сервере -- который (Xeon E5620, 2.40GHz)x8, Java: 1.6.0_18, Sun Microsystems Inc, Runtime: 1.6.0_18-b18, VM: 16.0-b13, OS: Linux 2.6.32
Обновленные результаты предыдущих серий такие (указан диапазон для различных значений размера буфера: 1024б-2Мб, проценты -- среднее значение стандартного отклонения):
*106ops/sec
Эта штука работает в разы быстрее: (142-157± 10%)*106 -- более того, она примерно в два раза быстрее disruptor-а. Ну наконец-то, чудес, похоже, и правда не случается -- мы теперь можем сказать,где собака порыласьчто разница в производительности где-то здесь:
Кто бы мог подумать? -- а я еще сомневался, стоит ли экономить на такой мелочи как деление. Посыпаю голову пеплом.
Похоже, мы зажали disruptor в вилку, и очень похоже, что предположение о GC write barrier действительно оправдывается.
*106ops/sec
Интересно отметить как зависит производительность от размера буфера. Disruptor (+batching) очень сильно замедляется при увеличении буфера -- примерно в 3 раза при переходе от 1024 до 2Мб. Очереди же замедляются существенно меньше -- на 15-20% всего.
Так же меня все еще не удовлетворяет стабильность результатов -- между различными запусками результаты зачастую отличаются в разы. Привязка к ядрам и повышение приоритета процесса где-то раза в полтора уменьшили этот разброс, но он все равно остается очень большим -- стандартное отклонение для некоторых экспериментов (тут особо выделяется как раз Д) достигает 35%, а амплитуда разброса значений -- 45%. Причем заметно, что повторы внутри одного запуска (одной JVM) имеют значительно меньший разброс. Напрашивается вывод, что это не случайная, а систематическая погрешность, каким-то образом зависящая от момента запуска JVM. Но у меня пока кончились идеи "что еще можно сделать, чтобы уменьшить влияние внешних факторов". Мартин что-то еще писал про перенаправление прерываний -- чтобы они не посылались тем ядрам, на которых сидят бенчмарки...
Продолжение (окончание, надеюсь) -- в следующих сериях
P.S. Нужно сказать, что Алексей Шипилев проводил эти тесты на своем оборудовании, и (на JDK1.7, -XX:+UseCondCardMark ) получил у самой оптимизированной из реализаций очередей (с маской вместо остатка от деления, с lazySet, с большим padding-ом в 128 байт, но без оптимизации spin-wait) результаты практически не отличимые от Disruptor. Я у себя не могу повторить его результаты -- на рабочий сервер ставить экспериментальный пакет OpenJDK1.7 я не готов, а порт для мака на моем ноутбуке дает результаты заметно хуже (но надо помнить, что у меня на маке нет taskset, и разброс в этих результатах может быть гораздо выше -- кроме того на персональной машине гораздо сложнее обеспечить должную изоляцию).
В предыдущий заход я остановился на том, что оптимизированная single enqueuer single dequeuer очередь на холостом ходу обходит j.u.c.ABQ примерно в 5 раз -- и во столько же раз ее обходит disruptor. Поскольку я не верю в черную магию (тем более -- чужую), приходится ковырять дальше.
Во-первых, по совету мастеров я начал использовать taskset для привязки потоков к ядрам. Потом я еще немного подумал, и решил напрямую звать sched_setaffinity() через JNA для конкретных потоков. Плюс nice -20 чтобы уменьшить шанс вмешательства всяких фоновых процессов -- это несколько уменьшило дрожание и чуть улучшило результаты. Во-вторых я сделал несколько экспериментов на нашем рабочем сервере -- который (Xeon E5620, 2.40GHz)x8, Java: 1.6.0_18, Sun Microsystems Inc, Runtime: 1.6.0_18-b18, VM: 16.0-b13, OS: Linux 2.6.32
Обновленные результаты предыдущих серий такие (указан диапазон для различных значений размера буфера: 1024б-2Мб, проценты -- среднее значение стандартного отклонения):
| ABQ: | (2.6-2.8 ± 7%) |
| Optimized SESDQueue: | (17-19 ± 20%) |
| Disruptor: | (30-75 ± 30%) |
Заходим с хвоста
После долгих раздумий я решил зайти с обратной стороны. Основные конкурентные операции в реализации очереди это volatile read/write указателей на голову/хвост очереди. Можно попробовать убрать вообще всю работу с массивом -- размещение/удаление оттуда элементов -- и оставить только механику передвижения курсоров:public class SESDSequencer {
//======================================================
private static final AtomicLongFieldUpdater<SESDSequencer> tailUpdater = AtomicLongFieldUpdater.newUpdater( SESDSequencer.class, "tailCursor" );
private static final AtomicLongFieldUpdater<SESDSequencer> headUpdater = AtomicLongFieldUpdater.newUpdater( SESDSequencer.class, "headCursor" );
//======================================================
private final int length;
private volatile long headCursor = 0;
private volatile long p11, p12, p13, p14, p15, p16, p17, p18 = 7;
private volatile long tailCursor = 0;
private volatile long p21, p22, p23, p24, p25, p26, p27, p28 = 8;
private long lastHeadObserved = 0;
private volatile long p31, p32, p33, p34, p35, p36, p37, p38 = 9;
private long lastTailObserved = 0;
public long sumPaddingToPreventOptimisation() {
return p11 + p12 + p13 + p14 + p15 + p16 + p17 + p18
+ p21 + p22 + p23 + p24 + p25 + p26 + p27 + p28
+ p31 + p32 + p33 + p34 + p35 + p36 + p37 + p38;
}
public SESDSequencer( final int length ) {
checkArgument( length > 0, "length(%s) must be >0", length );
this.length = length;
sumPaddingToPreventOptimisation();
}
private long nextTail() {
final long tail = tailCursor;
waitWhileNotFull( tail );
return tail + 1;
}
private long nextHead() {
final long head = headCursor;
waitWhileNotEmpty( head );
return head + 1;
}
private void publishTail( final long newTail ) {
tailUpdater.lazySet( this, newTail );
}
private void publishHead( final long newHead ) {
headUpdater.lazySet( this, newHead );
}
private void waitWhileNotFull( final long tail ) {
//spin-wait: "while not full"
final long target = tail - length;
while ( target == lastHeadObserved ) {
lastHeadObserved = headCursor;
}
}
private void waitWhileNotEmpty( final long head ) {
//spin-wait: "while not empty"
while ( head == lastTailObserved ) {
lastTailObserved = tailCursor;
}
}
public void moveHead() {
final long newTail = nextTail();
publishTail( newTail );
}
public void moveTail() {
final long newHead = nextHead();
publishHead( newHead );
}
}
Эта штука работает в разы быстрее: (142-157± 10%)*106 -- более того, она примерно в два раза быстрее disruptor-а. Ну наконец-то, чудес, похоже, и правда не случается -- мы теперь можем сказать,
public void enqueue( final T item ) {
final long newTail = nextTail();
//это те 2 строчки, что отличают
//SESDSequencer.moveTail() от SESDQueue.enqueue():
final int index = index( newTail - 1 );
elements[index] = item;
publishTail( newTail );
}
public T dequeue() {
final long newHead = nextHead();
//а это -- те 2 строчки, что отличают
//SESDSequencer.moveHead() от SESDQueue.dequeue():
final int index = index( newHead - 1 );
final T item = elements[index];
publishHead( newHead );
return item;
}
Битовые маски
Дальнейшие поиски внутри указанных 4-х строчек приводят к неожиданному результату: замена вычисления индекса через остаток от деления ( sequence % length) на использование битовой маски ( sequence & (length-1) -- соответственно, ограничивая размер буфера степенью двойки) дает около 25% прироста производительности: (19-27± 20%)*106ops/sec.Кто бы мог подумать? -- а я еще сомневался, стоит ли экономить на такой мелочи как деление. Посыпаю голову пеплом.
GC write barrier
Следующая идея состоит в том, чтобы проверить гипотезу о влиянии GC write barrier-а при записи ссылки. С этой целью я сделал реализацию очереди, которая хранит не ссылки на объекты (LongValueEntry) а просто long -- соответственно, внутри у нее не Object[], а long[]. Результат: (107-114± 10%)*106ops/sec.Похоже, мы зажали disruptor в вилку, и очень похоже, что предположение о GC write barrier действительно оправдывается.
Деоптимизируем Disruptor
Еще одна идея возникла уже со стороны Disruptor-а -- почему бы не отключить в нем batching? Это несложно: нужно скопировать com.lmax.disruptor.BatchEventProcessor и заменить буквально одну строчку в методе run():final long availableSequence = sequenceBarrier.waitFor(nextSequence);
while (nextSequence <= availableSequence)
{
event = ringBuffer.get(nextSequence);
eventHandler.onEvent(event, nextSequence, nextSequence == availableSequence);
nextSequence++;
}
//вот эту строку надо внести в цикл выше ^^
sequence.set(nextSequence - 1L);
Результат интересный -- на малых размерах очереди (1024-32K) Disruptor без batching сильно тормозится: 28 вместо 70 миллионов ops/sec. На больших же размерах очереди (256К-2М) разница практически отсутствует (особенно учитывая немалую статистическую погрешность примерно в 20%). Можно сформулировать иначе -- Д без батчинга почти не зависит от размера буфера, в то время как с батчингом он сильно (почти в 3 раза) ускоряется на коротких буферах. Пока мне не приходит в голову внятное объяснение этого феномена. Можно заметить, что у Xeon E5620 кэш L1=64K, то есть малые буфера в него полностью влезают, а большие -- полностью не влезают. Этот факт явно что-то символизирует, но вот что именно -- пока не соображуВыводы
Что у меня пока получается в итоге:| ABQ: | (2.6-2.8 ± 7%) |
| SESDQueue(+lazySet, +spinning): | (17-19 ± 20%) |
| .............+bitmask: | (19-27 ± 20%) |
| Disruptor (+batching): | (30-75 ± 30%) |
| Disruptor (-batching): | (26-30 ± 20%) |
| LongQueue: | (107-114 ± 25%) |
| Sequencer: | (143-157± 15%) |
Интересно отметить как зависит производительность от размера буфера. Disruptor (+batching) очень сильно замедляется при увеличении буфера -- примерно в 3 раза при переходе от 1024 до 2Мб. Очереди же замедляются существенно меньше -- на 15-20% всего.
Так же меня все еще не удовлетворяет стабильность результатов -- между различными запусками результаты зачастую отличаются в разы. Привязка к ядрам и повышение приоритета процесса где-то раза в полтора уменьшили этот разброс, но он все равно остается очень большим -- стандартное отклонение для некоторых экспериментов (тут особо выделяется как раз Д) достигает 35%, а амплитуда разброса значений -- 45%. Причем заметно, что повторы внутри одного запуска (одной JVM) имеют значительно меньший разброс. Напрашивается вывод, что это не случайная, а систематическая погрешность, каким-то образом зависящая от момента запуска JVM. Но у меня пока кончились идеи "что еще можно сделать, чтобы уменьшить влияние внешних факторов". Мартин что-то еще писал про перенаправление прерываний -- чтобы они не посылались тем ядрам, на которых сидят бенчмарки...
Продолжение (окончание, надеюсь) -- в следующих сериях
P.S. Нужно сказать, что Алексей Шипилев проводил эти тесты на своем оборудовании, и (на JDK1.7, -XX:+UseCondCardMark ) получил у самой оптимизированной из реализаций очередей (с маской вместо остатка от деления, с lazySet, с большим padding-ом в 128 байт, но без оптимизации spin-wait) результаты практически не отличимые от Disruptor. Я у себя не могу повторить его результаты -- на рабочий сервер ставить экспериментальный пакет OpenJDK1.7 я не готов, а порт для мака на моем ноутбуке дает результаты заметно хуже (но надо помнить, что у меня на маке нет taskset, и разброс в этих результатах может быть гораздо выше -- кроме того на персональной машине гораздо сложнее обеспечить должную изоляцию).
24 октября 2011 г.
taskset для бенчмарков
Экспериментировал с бенчмарками с привязыванием потоков к ядрам через taskset. И вот не дает мне покоя мысль: ведь если я привяжу процесс, тестирующий какой-то двухпоточный код к двум конкретным ядрам (taskset -c 1,2 mvn exec:java ...) то с одной стороны мои потоки не будут кочевать по другим ядрам. А с другой -- у JVM кроме моих 2 потоков еще дюжина фоновых запущена, не считая GC -- и они ведь все тоже будут за эти два ядра конкурировать. Хотя у меня еще 16 ядер свободны... Это не считая того, что никто не помешает ведь моим двум потокам периодически просто меняться ядрами :)
Похоже, все-таки надо искать способ назначать thread affinity mask изнутри, для конкретных потоков. Где-то в сети я видел код, делающий это через JNA довольно компактно.
UPD:Бросил все, и написал свою собственную утилиту, с преферансом и куртизанками: ThreadAffinity.java. Утилита использует JNA, работает только на linux -- винды у меня сейчас банально нет под рукой, а на MacOS найти нужный системный вызов мне пока не удалось.
Похоже, все-таки надо искать способ назначать thread affinity mask изнутри, для конкретных потоков. Где-то в сети я видел код, делающий это через JNA довольно компактно.
UPD:Бросил все, и написал свою собственную утилиту, с преферансом и куртизанками: ThreadAffinity.java. Утилита использует JNA, работает только на linux -- винды у меня сейчас банально нет под рукой, а на MacOS найти нужный системный вызов мне пока не удалось.
11 октября 2011 г.
LMAX Disruptor #3.1: эксперименты с производительностью
Разбирательства с lazySet и прочими тонкостями моделей памяти несколько отвлекли меня от продолжения вивисекции disruptor-а. А ведь сам пристальный интерес к lazySet у меня возник как раз после того, как бенчмарки показали, что если заменить его на обычный .set() -- пропускная способность падает почти вдвое. Так что пока суд да дело -- я напишу об этих самых бенчмарках.
Сначала про задумку. Задумка возникла еще во время первого знакомства с disruptor-ом, и укрепилась в ходе дискуссии с Алексеем о его мнимых и реальных достоинствах. Дело в том, что бенчмарки disruptor-а, которые приводят разработчики, сравнивают его с j.u.c.ArrayBlockingQueue. Это достаточно справедливо в том смысле, что ABQ наиболее подходящий готовый компонент из стандартной библиотеки, которым воспользуется обычный разработчик, буде ему понадобится сконструировать конвейерную многопоточную обработку сообщений. Но ABQ это вовсе не самая производительная (ни в плане пропускной способности, ни в плане задержек) реализация конкурентной очереди. Это достаточно простая и надежная реализация, с приемлемой производительностью -- именно поэтому (как я полагаю) она и является частью стандартной библиотеки. И если уж ставить вопрос "disruptor vs queues" -- как его пытаются поставить разработчики, то надо сравнивать disruptor c сопоставимыми по степени оптимизированности реализациями очередей. Которых -- увы -- в стандартной поставке JDK нет. Но это всего лишь означает, что их надо написать :)
Таким образом и возникла идея этого теста. Вместо тестирования "disruptor vs queues" в благоприятных для него условиях попробуем тестировать в неблагоприятных. Возьмем disruptor в простейшей топологии A->B (один поток -- поставщик, один поток -- обработчик-потребитель). Возьмем простейшую реализацию single enqueuer single dequeuer очереди на основе массива (собственно, это будет очень близко к реализации самого disruptor-а -- по-сути, он и есть такая очередь, только на стероидах). Будем постепенно вносить в эту очередь различные оптимизации, или/и будем постепенно "убирать" различные оптимизации из disruptor-а. Поскольку эти две структуры данных весьма близки изначально, то на каком-то этапе они станут почти неразличимы, и производительность должна оказаться равной. То есть на выходе у нас получится последовательность шагов, каждый из которых на сколько-то улучшает очередь/ухудшает disruptor -- так, что они в конце-концов становятся неразличимы. И можно будет смотреть, какие факторы собственно являются в дизайне disruptor-а ключевыми для производительности, а какие -- второстепенными.
Дисклаймер: я провожу тесты без нагрузки. То есть измеряю пропускную способность в сферическом случае в вакууме -- она может коррелировать с производительностью в боевых условиях, а может и не коррелировать. Меня здесь интересуют именно накладные расходы на холостом ходу -- "стоимость" работы внутренней механики. Просто хотя бы потому, что рабочий ход мне не на чем исследовать -- нет конкретного примера.
Один поток пишет в "очередь" 300 миллионов записей (для начала -- LongValueEntry), другой поток их из "очереди" вытаскивает. Время выполнения определяется по моменту вытаскивания последней записи из "очереди".
Цикл выполняется 5 раз подряд в одном запуске -- 1-2 раз обычно выбрасывается, чтобы не учитывать разогрев JVM. Запусков обычно 2-3 -- сколько достаточно для более-менее уверенной статистики.
В бенчмарках присутствует так же ArrayBlockingQueue -- в качестве реперной точки.
Код здесь.
Система: MBP, i7 2GHz, MacOS X 10.6.8,
JDK 1.6.0_26-b03-377, "-da -server -Xmx512m -Xms512"
Емкость очереди -- 1024 элемента.
Базовые результаты (ops/sec == количество сообщений, прошедших "очередь" за секунду).
Нифиговое такое различие, а? Меня, правда, немного напрягает, что разница в скорости между ABQ и Disruptor составляет 25 раз, вместо 5-6 в их собственных тестах...
Ок, начинаем оптимизацию. Шаг №1: первое, что приходит в голову -- аллокация. Disruptor использует однажды преаллоцированные объекты, обе наши очереди -- создают 300 миллионов временных объектов. Проверим какое влияние это оказывает -- сделаем пул объектов. Задача упрощается тем, что пул имеет заранее известную емкость (==емкости очереди), плюс он не должен быть потоковобезопасным, потому что мы знаем, что у нас только один поток-производитель:
Различие не то, чтобы особо радикальное, но процентов 15 наша SESD очередь выиграла.
Шаг №2 -- добавляем padding, чтобы избежать false sharing:
Шаг №3 -- оптимизируем spin-loop-ы. Опять же, подглядывая в код disruptor-а можно заметить такой прием:
Результат: (12.9+/-0.1)e6 (== +20%).
Шаг №3 -- используем lazySet. Опять же подсмотренно в классе Sequence из disruptor -- похоже, что операции обновления курсоров здесь не требуют всей строгости семантики volatile store -- достаточно LoadStore+StoreStore барьеров перед ними -- то есть гарантии, что все, что произошло до обновления курсора в program order будет видимо остальным потокам до того, как станет видимым это обновление. Для этого не нужно volatile store, достаточно lazySet:
Результат: (13.9+/-0.1)e6 (== +10%).
В общем-то, прямолинейные оптимизации закончились -- а мы все еще отстаем от disruptor в 5 раз. Продолжение -- в следующих сериях :)
Сначала про задумку. Задумка возникла еще во время первого знакомства с disruptor-ом, и укрепилась в ходе дискуссии с Алексеем о его мнимых и реальных достоинствах. Дело в том, что бенчмарки disruptor-а, которые приводят разработчики, сравнивают его с j.u.c.ArrayBlockingQueue. Это достаточно справедливо в том смысле, что ABQ наиболее подходящий готовый компонент из стандартной библиотеки, которым воспользуется обычный разработчик, буде ему понадобится сконструировать конвейерную многопоточную обработку сообщений. Но ABQ это вовсе не самая производительная (ни в плане пропускной способности, ни в плане задержек) реализация конкурентной очереди. Это достаточно простая и надежная реализация, с приемлемой производительностью -- именно поэтому (как я полагаю) она и является частью стандартной библиотеки. И если уж ставить вопрос "disruptor vs queues" -- как его пытаются поставить разработчики, то надо сравнивать disruptor c сопоставимыми по степени оптимизированности реализациями очередей. Которых -- увы -- в стандартной поставке JDK нет. Но это всего лишь означает, что их надо написать :)
Таким образом и возникла идея этого теста. Вместо тестирования "disruptor vs queues" в благоприятных для него условиях попробуем тестировать в неблагоприятных. Возьмем disruptor в простейшей топологии A->B (один поток -- поставщик, один поток -- обработчик-потребитель). Возьмем простейшую реализацию single enqueuer single dequeuer очереди на основе массива (собственно, это будет очень близко к реализации самого disruptor-а -- по-сути, он и есть такая очередь, только на стероидах). Будем постепенно вносить в эту очередь различные оптимизации, или/и будем постепенно "убирать" различные оптимизации из disruptor-а. Поскольку эти две структуры данных весьма близки изначально, то на каком-то этапе они станут почти неразличимы, и производительность должна оказаться равной. То есть на выходе у нас получится последовательность шагов, каждый из которых на сколько-то улучшает очередь/ухудшает disruptor -- так, что они в конце-концов становятся неразличимы. И можно будет смотреть, какие факторы собственно являются в дизайне disruptor-а ключевыми для производительности, а какие -- второстепенными.
Дисклаймер: я провожу тесты без нагрузки. То есть измеряю пропускную способность в сферическом случае в вакууме -- она может коррелировать с производительностью в боевых условиях, а может и не коррелировать. Меня здесь интересуют именно накладные расходы на холостом ходу -- "стоимость" работы внутренней механики. Просто хотя бы потому, что рабочий ход мне не на чем исследовать -- нет конкретного примера.
Single Enqueuer, Single Dequeuer Queue
Итак, откуда начинаем плясать: вот так выглядит single enqueuer single dequeuer array-based queue:public class SESDQueue<T> {
private final int length;
private volatile long headCursor = 0;
private volatile long tailCursor = 0;
private final T[] elements;
/* Elements range: [headCursor, tailCursor)
*
* (tailCursor - headCursor) == elements count
*
* 0 <= (tailCursor - headCursor) <= length => state invariant
*
* tailCursor - headCursor == length => queue is full
* tailCursor - headCursor == 0 => queue is empty
*
* (headCursor % length ) is the index of first item in queue
* (tailCursor % length ) is the index of _cell_ for _next last item_
*/
public SESDQueue( final int length ) {
checkArgument( length > 0, "length(%s) must be >0", length );
this.length = length;
elements = ( T[] ) new Object[length];
}
private long nextTail() {
final long tail = tailCursor;
waitWhileNotFull( tail );
assert ( tail == tailCursor ) : "tail=" + tail + " <> tailCursor=" + tailCursor + " -- seems like multi-threaded enqueue() detected!";
return tail + 1;
}
private long nextHead() {
final long head = headCursor;
waitWhileNotEmpty( head );
assert ( head == headCursor ) : "head=" + head + " <> headCursor=" + headCursor + " -- seems like multi-threaded dequeue() detected!";
return head + 1;
}
private void publishTail( final long newTail ) {
assert ( newTail >= headCursor ) : "newTail(" + newTail + ") < headCursor(" + headCursor + ")";
tailCursor = newTail;
}
private void publishHead( final long newHead ) {
assert ( newHead <= tailCursor ) : "newHead(" + newHead + ") > tailCursor(" + tailCursor + ")";
headCursor = newHead;
}
private void waitWhileNotFull( final long tail ) {
//spin-wait: "while not full"
while ( tail == headCursor + length ) {
}
}
private void waitWhileNotEmpty( final long head ) {
//spin-wait: "while not empty"
while ( head == tailCursor ) {
}
}
public void enqueue( final T item ) {
final long newTail = nextTail();
final int index = ( int ) ( ( newTail - 1 ) % length );
elements[index] = item;
publishTail( newTail );
}
public T dequeue() {
final long newHead = nextHead();
final int index = ( int ) ( ( newHead - 1 ) % length );
final T item = elements[index];
elements[index] = null;//for GC
publishHead( newHead );
return item;
}
public int size() {
return ( int ) ( tailCursor - headCursor );
}
}
В ней нет ни одного CAS, только volatile load/stores - это ее плюс. Писать/читать ее может только по одному потоку -- это ее минус, в данном случае несущественный, так как disruptor тоже в своем наилучшем варианте single publishing, и принципиально single subsriber.Схема бенчей
Один поток пишет в "очередь" 300 миллионов записей (для начала -- LongValueEntry), другой поток их из "очереди" вытаскивает. Время выполнения определяется по моменту вытаскивания последней записи из "очереди".
Цикл выполняется 5 раз подряд в одном запуске -- 1-2 раз обычно выбрасывается, чтобы не учитывать разогрев JVM. Запусков обычно 2-3 -- сколько достаточно для более-менее уверенной статистики.
В бенчмарках присутствует так же ArrayBlockingQueue -- в качестве реперной точки.
Код здесь.
Поехали...
Система: MBP, i7 2GHz, MacOS X 10.6.8,
JDK 1.6.0_26-b03-377, "-da -server -Xmx512m -Xms512"
Емкость очереди -- 1024 элемента.
Базовые результаты (ops/sec == количество сообщений, прошедших "очередь" за секунду).
| ABQ | SESD | Disruptor |
|---|---|---|
| (2.65+/-0.05)e6 | (9.0+/-0.3)e6 | (65+/-3)e6 |
Нифиговое такое различие, а? Меня, правда, немного напрягает, что разница в скорости между ABQ и Disruptor составляет 25 раз, вместо 5-6 в их собственных тестах...
Ок, начинаем оптимизацию. Шаг №1: первое, что приходит в голову -- аллокация. Disruptor использует однажды преаллоцированные объекты, обе наши очереди -- создают 300 миллионов временных объектов. Проверим какое влияние это оказывает -- сделаем пул объектов. Задача упрощается тем, что пул имеет заранее известную емкость (==емкости очереди), плюс он не должен быть потоковобезопасным, потому что мы знаем, что у нас только один поток-производитель:
class EventPool<T> implements EventFactory<T> {
private final EventFactory<T> factory;
private final Object[] items;
private int counter = 0;
private EventPool( final int size,
final EventFactory<T> factory ) {
this.factory = factory;
this.items = new Object[size];
for ( int i = 0; i < items.length; i++ ) {
items[i] = factory.newInstance();
}
}
@Override
@SuppressWarnings( "unchecked" )
public T newInstance() {
try {
return ( T ) items[counter];
} finally {
counter = ( counter + 1 ) % items.length;
}
}
}
| ABQ | SESD | Disruptor |
|---|---|---|
| (2.70+/-0.04)e6 | (10.7+/-0.4)e6 | (65+/-3)e6 |
Различие не то, чтобы особо радикальное, но процентов 15 наша SESD очередь выиграла.
Шаг №2 -- добавляем padding, чтобы избежать false sharing:
private volatile long headCursor = 0;
public volatile long p11, p12, p13, p14, p15, p16, p17, p18 = 7;
private volatile long tailCursor = 0;
public volatile long p21, p22, p23, p24, p25, p26, p27, p28 = 8;
public long sumPaddingToPreventOptimisation() {
return p11 + p12 + p13 + p14 + p15 + p16 + p17 + p18
+ p21 + p22 + p23 + p24 + p25 + p26 + p27 + p28;
}
результат SESDQueue: (10.8+/-0.2)e6 -- какие-то крохи, даже говорить стыдно. Даже как-то странно...Шаг №3 -- оптимизируем spin-loop-ы. Опять же, подглядывая в код disruptor-а можно заметить такой прием:
private void waitWhileNotEmpty( final long head ) {
//spin-wait: "while not empty"
while ( head == tailCursor ) {
}
}
Зачем нам здесь каждый раз читать tailCursor (volatile load), когда единожды обнаружив, что он на сколько-то больше head мы можем просто запомнить его текущее значение в локальной для потока переменной, и пересчитывать ее значение только когда head будет снова ему равно://тут опять же будет padding...
private long lastTailObserved = 0;
//и тут --- тоже...
private void waitWhileNotEmpty( final long head ) {
while ( head == lastTailObserved ) {
lastTailObserved = tailCursor;
}
}
Результат: (12.9+/-0.1)e6 (== +20%).
Шаг №3 -- используем lazySet. Опять же подсмотренно в классе Sequence из disruptor -- похоже, что операции обновления курсоров здесь не требуют всей строгости семантики volatile store -- достаточно LoadStore+StoreStore барьеров перед ними -- то есть гарантии, что все, что произошло до обновления курсора в program order будет видимо остальным потокам до того, как станет видимым это обновление. Для этого не нужно volatile store, достаточно lazySet:
Результат: (13.9+/-0.1)e6 (== +10%).
В общем-то, прямолинейные оптимизации закончились -- а мы все еще отстаем от disruptor в 5 раз. Продолжение -- в следующих сериях :)
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 немного просел.
Проверим -- введем поля:
Остается неразгаданной ситуация с jdk-exclusive. Во-первых производительность продолжает сильно деградировать -- примерно в 3.5 раза с 1 до 8 потоков. Причины этого поведения мне пока непонятны. Плюс здесь еще самый большой статистический разброс результатов: относительная погрешность достигает 50%, отдельные измерения с одинаковыми параметрами дают, в разных заходах, результаты, различающиеся раза в 3. В раздумьях.
P.S. Код здесь
Гоняю я их в многопоточном варианте -- ибо у нас-то симулятор далеко не однопоточный. Стандартный генератор, поскольку он 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. Код здесь
21 июня 2011 г.
Про бенчмаркинг высококонкурентного кода
Великолепная статья Дэвида -- про одну из характерных ошибок при бенчмаркинге high-concurrent приложений.
Допустим, у нас есть код, который плохо масштабируется. Проще говоря, если построить график в осях "пропускная способность (Y) -- количество worker-ов (Х)", то график будет выпуклым вверх: сначала пропускная способность будет расти, потом достигнет максимума, и начнет убывать. Обычная причина состоит в том, что накладные расходы на взаимодействие между worker-ами начинают доминировать, и съедают весь потенциальный прирост производительности.
Часто оказывается, что ситуацию можно "улучшить" если некоторым способом ограничить степень конкурентности -- например, введя задержки (back-offs). "Улучшить" в том смысле, что производительность, разумеется, все равно не будет далее расти с ростом количества worker-ов, но, по крайней мере, она не будет и падать -- вместо кривой с максимумом и дальнейшим падением мы получим кривую, выходящую на асимптоту.
Допустим теперь, что мы пока еще не сделали эту "оптимизацию", и работаем со своим кодом в той области высокой конкуренции, где его производительность уже деградирует (т.е. меньше максимума). Мы пытаемся его оптимизировать, используя стандартный цикл измерение-анализ-модификация. Тогда легко может оказаться, что какая-нибудь модификация, замедляющая выполнение кода сработает как неявная задержка (back-off), "улучшающая" его конкурентные свойства. "Улучшающая", повторяю, в том лишь смысле, что она перемещает начало деградации на более высокие уровни конкурентности, чем нам сейчас доступны. Платой за это является то, что при меньшей конкурентности производительность будет хуже.
Введение явных задержек, вместо неявной деоптимизации, разумеется лучше -- хотя бы в том смысле, что мы осознаем, что эти задержки полезны только при высокой конкуренции, и можем включать их только при превышении определенного уровня конкурентности -- не оказывая тем самым эффекта на скорость выполнения кода в низкоконкурентном случае.
Похожий эффект может возникать при профилировании -- код, выполняющий измерения (инкрементируемые счетчики, вызываемые callback-и...) так же может выступать в роли источника неявных задержек, улучшающих производительность в области где она начинает падать. Получается "гейзенбаг" в бенчмаркинге: производительность улучшается, когда за системой начинают наблюдать :)
Этот эффект нужно иметь ввиду при бенчмаркинге конкурентных приложений. Хорошей практикой будет проверять эффект каждого изменения в максимально широком диапазоне конкурентности, а не только для пиковых значений.
Допустим, у нас есть код, который плохо масштабируется. Проще говоря, если построить график в осях "пропускная способность (Y) -- количество worker-ов (Х)", то график будет выпуклым вверх: сначала пропускная способность будет расти, потом достигнет максимума, и начнет убывать. Обычная причина состоит в том, что накладные расходы на взаимодействие между worker-ами начинают доминировать, и съедают весь потенциальный прирост производительности.
Часто оказывается, что ситуацию можно "улучшить" если некоторым способом ограничить степень конкурентности -- например, введя задержки (back-offs). "Улучшить" в том смысле, что производительность, разумеется, все равно не будет далее расти с ростом количества worker-ов, но, по крайней мере, она не будет и падать -- вместо кривой с максимумом и дальнейшим падением мы получим кривую, выходящую на асимптоту.
Допустим теперь, что мы пока еще не сделали эту "оптимизацию", и работаем со своим кодом в той области высокой конкуренции, где его производительность уже деградирует (т.е. меньше максимума). Мы пытаемся его оптимизировать, используя стандартный цикл измерение-анализ-модификация. Тогда легко может оказаться, что какая-нибудь модификация, замедляющая выполнение кода сработает как неявная задержка (back-off), "улучшающая" его конкурентные свойства. "Улучшающая", повторяю, в том лишь смысле, что она перемещает начало деградации на более высокие уровни конкурентности, чем нам сейчас доступны. Платой за это является то, что при меньшей конкурентности производительность будет хуже.
Введение явных задержек, вместо неявной деоптимизации, разумеется лучше -- хотя бы в том смысле, что мы осознаем, что эти задержки полезны только при высокой конкуренции, и можем включать их только при превышении определенного уровня конкурентности -- не оказывая тем самым эффекта на скорость выполнения кода в низкоконкурентном случае.
Похожий эффект может возникать при профилировании -- код, выполняющий измерения (инкрементируемые счетчики, вызываемые callback-и...) так же может выступать в роли источника неявных задержек, улучшающих производительность в области где она начинает падать. Получается "гейзенбаг" в бенчмаркинге: производительность улучшается, когда за системой начинают наблюдать :)
Этот эффект нужно иметь ввиду при бенчмаркинге конкурентных приложений. Хорошей практикой будет проверять эффект каждого изменения в максимально широком диапазоне конкурентности, а не только для пиковых значений.
27 августа 2010 г.
Immutable vs Mutable объекты
Когда я узнал, что final поля "гарантированно видимы любому потоку" после завершения инициализации, я подумал, что ведь это чего-то да стоит. В том смысле, что создание immutable объекта с final полями должно быть дороже (как минимум, в многопоточном окружении, чтобы JIT не смог это оптимизировать). Т.е. как минимум нужен же мембар по завершении конструктора. Сегодня попытался это проверить -- объявил два идентичных класса, у одного из которых все поля final, и создавал их в 150 потоков параллельно. Черта с два -- одинаково. Даже наоборот, есть слабое преимущество у immutable класса, но я бы не назвал его статистически значимым -- где-то 0.5%, слишком мало, чтобы принимать во внимание в случае микробенчмарка.
P.S. Постфактум это становится довольно очевидным. Семантика final полей обеспечивается StoreStore барьером между инициализацией полей и публикацией ссылки на созданный объект:
Но на x86, где я тестировал, StoreStore барьер не нужен -- тамошняя "железная" модель памяти (TSO -- total store order) достаточно строгая сама по себе.
Более того, по словам DL в его кулинарной книге StoreStore барьеры, даже если они и требуются на какой-то архитектуре, обычно одни из самых дешевых. Так что, с высокой степенью вероятности, их влияние на производительность даже там, где они есть (и требуются) будет теряться на фоне, например, затрат на выделение памяти
P.S. Постфактум это становится довольно очевидным. Семантика final полей обеспечивается StoreStore барьером между инициализацией полей и публикацией ссылки на созданный объект:
localRef = alloc(...); localRef.field1 = ...; localRef.field2 = ...; .... StoreStore; globallyAvailableRef = localRef;
Но на x86, где я тестировал, StoreStore барьер не нужен -- тамошняя "железная" модель памяти (TSO -- total store order) достаточно строгая сама по себе.
Более того, по словам DL в его кулинарной книге StoreStore барьеры, даже если они и требуются на какой-то архитектуре, обычно одни из самых дешевых. Так что, с высокой степенью вероятности, их влияние на производительность даже там, где они есть (и требуются) будет теряться на фоне, например, затрат на выделение памяти
Производительность
Тестировал, ради интереса, пиковую производительность разных методов доступа к разделяемому состоянию в многопоточном окружении. Участники соревнования -- sunchronized, ReentrantLock, AtomicInteger, volatile+AtomicIntegerFieldUpdater.
Результаты, в целом, предсказуемы -- атомики в 2-3 раза быстрее блокировок. Две интересные вещи:
ReentrantLock опять обогнал synchronized! Заметно -- на четверть почти. Как-то я уже обнаруживал этот феномен. До сих пор не могу понять, в чем здесь цимус -- Сановцы забили на оптимизацию "старого" способа синхронизации? -- но на ус придется намотать :)
AtomicInteger немного обогнал volatile+AtomicIntegerFieldUpdater. Чуть-чуть -- процентов на 5 в среднем. Не то, чтобы неожиданно -- накладные расходы на reflection-based доступ -- но все же приятно видеть их вживую в цифрах. Разница есть, она измерима, но по величине явно не критична. Т.е. на AtomicIntegerFieldUpdater можно закладываться как на альтернативу AtomicInteger.
Результаты, в целом, предсказуемы -- атомики в 2-3 раза быстрее блокировок. Две интересные вещи:
ReentrantLock опять обогнал synchronized! Заметно -- на четверть почти. Как-то я уже обнаруживал этот феномен. До сих пор не могу понять, в чем здесь цимус -- Сановцы забили на оптимизацию "старого" способа синхронизации? -- но на ус придется намотать :)
AtomicInteger немного обогнал volatile+AtomicIntegerFieldUpdater. Чуть-чуть -- процентов на 5 в среднем. Не то, чтобы неожиданно -- накладные расходы на reflection-based доступ -- но все же приятно видеть их вживую в цифрах. Разница есть, она измерима, но по величине явно не критична. Т.е. на AtomicIntegerFieldUpdater можно закладываться как на альтернативу AtomicInteger.
14 августа 2009 г.
Решил перед уходом в отпуск протестировать "потолок" скорости расчета, на который можно рассчитывать в джаве. Для примера взял простейшую систему из N материальных точек (без столкновений, без вращений), в однородном поле тяжести. Все координаты развернул в линейные массивы double[], и реализовал стандартный Рунге-Кутты 4-го порядка. Итог: real-time (т.е. когда симуляционное время не отстает от реального) считается примерно 4500 объектов (jre1.6.0_14, -server -XX:+DoEscapeAnalysis, P4 3.2Ггц).
Для сравнения: когда у нас еще не было вращения и столкновений, в real-time обсчитывалось примерно 500 объектов. Т.е. я оцениваю так, что потенциал чисто низкоуровневых оптимизаций (развернуть структуры данных, улучшить cache-locality, b т.п.) у нас еще где-то на 300-500% прироста.
В качестве ориентировки переписал (матерясь -- забыл уже все) код на С++, запустил из под Visual Studio. Включил все оптимизации, которые нашел (__inline, глобальную оптимизацию, оптимизацию скорости, SSE2). Результат (примерный) -- процентов на 5-9% быстрее, чем в джаве
Для сравнения: когда у нас еще не было вращения и столкновений, в real-time обсчитывалось примерно 500 объектов. Т.е. я оцениваю так, что потенциал чисто низкоуровневых оптимизаций (развернуть структуры данных, улучшить cache-locality, b т.п.) у нас еще где-то на 300-500% прироста.
В качестве ориентировки переписал (матерясь -- забыл уже все) код на С++, запустил из под Visual Studio. Включил все оптимизации, которые нашел (__inline, глобальную оптимизацию, оптимизацию скорости, SSE2). Результат (примерный) -- процентов на 5-9% быстрее, чем в джаве
7 августа 2009 г.
тригонометрия
Тригонометрические функции в джаве довольно медленные. 1000 проходов по 100000 вычислений синусов на моей машине (P4, 3.2ГГц) выполняется за 8 секунд. Простейшая аппроксимация Тейлора с пятым порядком включительно выполняется в 10 раз быстрее, при этом дает 9-10 верных знаков на интервале (-0.1, 1). И, насколько я помню, аппроксимация Тейлора еще не лучшая для этой цели. Так что если вам нужна быстрая тригонометрия для небольших углов -- добро пожаловать назад в 80-90-е,
16 июля 2009 г.
Float vs Double
Тестировал производительность плавающей запятой в java. Обычно я везде использую double, но пока изучал jbullet заметил, что там вся арифметика на float-ах, и мне стало интересно.
тестировал под 1.6.0_14, с опциями -server -XX:+DoEscapeAnalysis -Xmx300m -Xms300m
В итоге, получается, что сложение/умножение примерно в два раза медленнее для double, деление -- примерно на 30%, сравнение мало отличается. Буду теперь для операций, не требующих особой точности, активно использовать float.
- import junit.framework.TestCase;
-
- public class FloatVsDoublePerfomance extends TestCase {
- private static final int[] SIZES = new int[]{ 1000, 10000, 100000, 300000 };
- private static final int ITER = 10000;
-
- public void test() {
- for ( int i = 0; i < SIZES.length; i++ ) {
- final int size = SIZES[i];
-
- _testFloat( size );
- System.gc();
- System.gc();
-
- _testDouble( size );
- System.gc();
- System.gc();
- }
- }
-
- private static void _testFloat( final int size ) {
- final float[] arr = createFloatArray( size );
-
- System.out.printf( "float[%d * %d]\n", size, ITER );
- //warm-up -- cache load, etc
- testFloatCompare( arr );
-
-
- long startedAt = System.currentTimeMillis();
- //compare
- for ( int i = 0; i < ITER; i++ ) {
- testFloatCompare( arr );
- }
- System.out.printf( "\tcompare: %d ms\n", ( System.currentTimeMillis() - startedAt ) );
-
- //summ
- startedAt = System.currentTimeMillis();
- for ( int i = 0; i < ITER; i++ ) {
- testFloatSumm( arr );
- }
- System.out.printf( "\tsum: %d ms\n", ( System.currentTimeMillis() - startedAt ) );
-
- //mul
- startedAt = System.currentTimeMillis();
- for ( int i = 0; i < ITER; i++ ) {
- testFloatMul( arr );
- }
- System.out.printf( "\tmul: %d ms\n", ( System.currentTimeMillis() - startedAt ) );
-
- //div
- startedAt = System.currentTimeMillis();
- for ( int i = 0; i < ITER; i++ ) {
- testFloatDiv( arr );
- }
- System.out.printf( "\tdiv: %d ms\n", ( System.currentTimeMillis() - startedAt ) );
- }
-
- private static void _testDouble( final int size ) {
- final double[] arr = createDoubleArray( size );
-
- System.out.printf( "double[%d * %d]\n", size, ITER );
- //warm-up -- cache load, etc
- testDoubleCompare( arr );
-
-
- long startedAt = System.currentTimeMillis();
- //compare
- for ( int i = 0; i < ITER; i++ ) {
- testDoubleCompare( arr );
- }
- System.out.printf( "\tcompare: %d ms\n", ( System.currentTimeMillis() - startedAt ) );
-
- //summ
- startedAt = System.currentTimeMillis();
- for ( int i = 0; i < ITER; i++ ) {
- testDoubleSumm( arr );
- }
- System.out.printf( "\tsum: %d ms\n", ( System.currentTimeMillis() - startedAt ) );
-
- //mul
- startedAt = System.currentTimeMillis();
- for ( int i = 0; i < ITER; i++ ) {
- testDoubleMul( arr );
- }
- System.out.printf( "\tmul: %d ms\n", ( System.currentTimeMillis() - startedAt ) );
-
- //div
- startedAt = System.currentTimeMillis();
- for ( int i = 0; i < ITER; i++ ) {
- testDoubleDiv( arr );
- }
- System.out.printf( "\tdiv: %d ms\n", ( System.currentTimeMillis() - startedAt ) );
- }
-
- private static float[] createFloatArray( final int size ) {
- final float[] arr = new float[size];
- for ( int i = 0; i < arr.length; i++ ) {
- arr[i] = ( float )( Math.random() * 100 );
- }
- return arr;
- }
-
- private static void testFloatDiv( final float[] arr ) {
- for ( int i = 0; i < arr.length; i++ ) {
- arr[i] = arr[i] / arr[i];
- }
- }
-
- private static void testFloatMul( final float[] arr ) {
- for ( int i = 0; i < arr.length; i++ ) {
- arr[i] = arr[i] * arr[i];
- }
- }
-
- private static void testFloatSumm( final float[] arr ) {
- for ( int i = 0; i < arr.length; i++ ) {
- arr[i] = arr[i] + arr[i];
- }
- }
-
- private static void testFloatCompare( final float[] arr ) {
- int _ = 0;
- for ( int i = 0; i < arr.length; i++ ) {
- if ( arr[i] < 50 ) {
- _++;//просто чтобы компилятор не выкинул сравнение
- }
- }
- }
-
-
- private static double[] createDoubleArray( final int size ) {
- final double[] arr = new double[size];
- for ( int i = 0; i < arr.length; i++ ) {
- arr[i] = Math.random() * 100;
- }
- return arr;
- }
-
- private static void testDoubleDiv( final double[] arr ) {
- for ( int i = 0; i < arr.length; i++ ) {
- arr[i] = arr[i] / arr[i];
- }
- }
-
- private static void testDoubleMul( final double[] arr ) {
- for ( int i = 0; i < arr.length; i++ ) {
- arr[i] = arr[i] * arr[i];
- }
- }
-
- private static void testDoubleSumm( final double[] arr ) {
- for ( int i = 0; i < arr.length; i++ ) {
- arr[i] = arr[i] + arr[i];
- }
- }
-
- private static void testDoubleCompare( final double[] arr ) {
- int _ = 0;
- for ( int i = 0; i < arr.length; i++ ) {
- if ( arr[i] < 50 ) {
- _++;//просто чтобы компилятор не выкинул сравнение
- }
- }
- }
- }
* This source code was highlighted with Source Code Highlighter.тестировал под 1.6.0_14, с опциями -server -XX:+DoEscapeAnalysis -Xmx300m -Xms300m
В итоге, получается, что сложение/умножение примерно в два раза медленнее для double, деление -- примерно на 30%, сравнение мало отличается. Буду теперь для операций, не требующих особой точности, активно использовать float.
Подписаться на:
Сообщения (Atom)