29 ноября 2011 г.

Puzzler из concurrency-interest

Замечательную штуку вчера продемонстрировал Hans Boehm в листе рассылки concurrency-interest (любопытно, что тема началась с запроса на легализацию разных трюков с s.m.Unsafe -- дискуссии concurrency-interest частенько очень сильно плутают). Ханс писал про опасность методов типа lock.tryLock() -- в смысле сложности их правильного понимания. Вот, например, код:

//Thread 1:
x = 17;
l.lock();

//Thread 2:
while ( l.tryLock() ) {
    l.unlock();
}
... x ...  // какое значение у x в этой точке?

Чтобы ответить на вопрос, обязан ли x быть равным 17 в конце второго потока надо ответить на вопрос "есть ли здесь data race?"

С одной стороны, с точки зрения "универсального" определения программа считается data race free если для всех sequentally consistent трасс над ней отсутствует конкурентный доступ к данным. В данном случае, кажется, это выполняется -- во всех SC трассах сначала в x пишется 17, и только потом x читается -- поэтому кажется, что код data race free, а значит после цикла во втором потоке x должен быть равен 17.

С другой стороны, JMM определяет data race free несколько иначе -- все конкурирующие доступы к данным должны быть упорядочены через happens-before. Поскольку между потоком 1 и 2 нет никаких ребер HB, то доступы к x на запись и на чтение в разных потоках не упорядочены через HB, и, следовательно, они образуют гонку -- а значит, значение x после цикла во втором потоке не определено.



Найти правильную точку зрения сравнительно просто -- достаточно вспомнить, что критические секции (и вообще, и в java в частности) имеют семантику "можно войти, нельзя выйти" (roach motel semantics) -- код может вноситься внутрь секции, но не может выноситься из нее. Это значит, что x=17 и l.lock() в потоке 1 могут быть переупорядочены -- присвоение может быть внесено в критическую секцию. Это сразу дает право сказать, что здесь таки есть гонка, и значение x во втором потоке действительно не определено.

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

А ошибка в рассуждениях в том, что, когда мы придумываем SC трассы над кодом, мы делаем два неявных предположения о том, что такое лок. Первое из них -- что лок неявно содержит некое состояние -- каким потоком он сейчас захвачен. Это состояние меняется вызовами lock()/unlock(), а так же запрашивается, и, возможно, меняется вызовом tryLock(). И это предположение верно -- у лока действительно есть это внутреннее состояние.

Но есть еще и второе предположение -- что изменения этого состояния методами lock()/unlock()/tryLock() -- имеют семантику volatile store/load. И вот это уже не верно. В соответствии со спецификацией, lock()/tryLock() имеют (==обязаны иметь) только семантику acquire, а unlock() -- только семантику release. А это значит, что мы не все трассы рассмотрели.

Путаницы добавляет тот факт, что на реализация блокировок обычно делается через CAS, а CAS на x86 имеет семантику full fence. То есть на x86 для любой реализации монитора (из мне известных) lock() будет иметь семантику full fence просто в силу того, что аппаратная модель памяти соответствующего процессора более слабых барьеров не предусматривает. И код Ханса будет скорее всего работать корректно (==не будет содержать гонок). Но это особенности именно аппаратной модели памяти конкретного процессора. Скажем, на пресловутых Azul-ах есть CAS без семантики барьера, и есть односторонние барьеры. И там вполне можно реализовать (правда, не на уровне java, а разве что на уровне интринсиков JIT-а) монитор, у которого lock() будет иметь честную семантику только acqiure.

Собственно, если я правильно понял Ханса, он и обращает внимание на то, что с введением методов типа tryLock() монитор становится легко принять за этакую неявную volatile переменную -- что не соответствует реальной семантике операций с мониторами.

28 ноября 2011 г.

В продолжение темы: глубже в synchronized vs ReentrantLock

После провокационной статьи Мартина у нас с Алексеем Шипилевым и Артемом состоялась любопытная переписка. Результаты ее более полно описал Артем, в своей статье.

Для меня там была одна важная, но неожиданная деталь. С предыдущей своей попытки разобраться в различиях synchronized и RL блокировок у меня создалось ощущение, что они во многом схожи. То есть synchronized имеет иерархию biased->thin(spin)->fat (строго говоря, скорее thin->(biased|fat) ), а RL имеет иерархию spin->park (с опциональным "выхватыванием" (barging). Это значит (как мне казалось), что оба типа блокировок почти идентичны на уровнях thin-fat. Я видел synchronized lock как (thin+fat) реализованный на уровне JVM + biasing, а ReentrantLock -- как (thin+fat) реализованный на уровне java + barging. При этом (thin+fat) часть у них очень близка (так мне казалось).

Оказывается, что это неправда. Действительно, и у synchronized и у RL есть части thin (CAS-based), и fat (OS-level parking). Но они сильно отличаются по политикам перехода между этими двумя режимами. А именно:

ReentrantLock на каждую попытку захвата монитора сначала пытается захватить монитор быстрым CAS-ом, и, в случае неуспеха этого благого начинания -- паркуется. То есть, по-сути, у RL нет "состояния" thin/fat -- он всегда является их суперпозицией.

synchronized же имеет явное поле (часть markword, вроде бы) "текущий тип блокировки" -- со значениями biased/thin/fat. И у него есть определенные правила перехода между этими типами. В частности, лок стартует в состоянии thin. Если привязка блокировок включена, то, по истечении определенного времени (biasing delay) если лок все время захватывается одним потоком -- он становится biased. Если лок захватывается разными потоками, но остается при этом uncontended (т.е. в каждый момент времени им владеет только один поток) - лок остается в состоянии thin. Если же случается столкновение потоков на блокировке, то лок "надувается" (inflate) -- переходит в состояние fat.

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

Вторая тонкость состоит в том, что "надувшийся" (fat) монитор -- это еще не kernel-space lock. Это свой собственный, JVM-ный, библиотечный лок, который сначала немного спиннится в user-space, и только потом, если спиннингом разрулить contention не удалось -- все-таки идет на поклон к батькеOS thread scheduler-у, прося разрулить ситуевину.

И когда говорят об адаптивном спиннинге в приложении к synchronized мониторам -- имеют в виду именно этот спиннинг внутри "надувшегося" монитора -- последний шанс разрулиться перед прыжком в омут с головойkernel space.

Если посмотреть на эту картину, то получается, что с точки зрения алгоритмов, у RL перед synchronized нет ни одного преимущества -- все, что умеет делать RL умеет и synchronized, но synchronized умеет делать и больше. Но при этом RL проще -- что может оказаться критичным, например, если наш конкретный use case этих сложностей не требует, а попадает на область применимости простейшего uncontended CAS lock-а -- RL может выиграть, например, за счет более простого memory layout-а.

То есть если мы пишем некий компонент, который хотим сделать просто потоковобезопасным (thread-safe) -- то есть мы допускаем его использование в многопоточном окружении, но не рассчитываем на особо большую нагрузку -- то пользуем synchronized и не парим себе мозг. synchronized наиболее адаптивен -- может сам приспособиться к различным профилям нагрузки. Плюс к тому, biased locking + поддержка со стороны JIT-а (выбрасывание блокировок по результатам escape analysis, эскалация блокировок, и прочая белая магия) делает synchronized исключительно эффективным в тех случаях, когда конкретный объект используется в однопоточном сценарии.

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

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

P.S. Алексей -- спасибо за терпеливые разъяснения :)

Снова о biased locking

Очередной виток истории начался с провокационного поста Мартина Томпсона (это автор Disruptor-а, если чё) -- и его продолжения, написанного после того, как Мартину указали на некоторые мелкие недостатки его бенчмарков :)

Во-первых, поднятый Мартином вопрос "есть ли сейчас смысл в привязанных блокировках" породил переписку Дэйва Дайса с Клиффом Кликом. В этой переписке довольно отчетливо высказана интересная мысль -- что привязанные блокировки скорее всего скоро отойдут в прошлое. Почему? Потому что это, по меткому выражению Клиффа "software solution to a hardware problem (expensive CAS)".

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

Сейчас же Клифф хвастается тем, что на Azul-ах uncontended {CAS + full_fence} (обычный CAS у них не имеет семантики барьера) выполняется за 5-6 тиков. На текущих Nehalem-ах локальный CAS требует 10-15 тиков (против мифических >100, с которых все когда-то начиналось) -- и есть шанс, что будет оптимизироваться дальше. В таких условиях Клифф пишет, что в версиях jdk для Azul они уже отказались вовсе от biased locking -- нет смысла, обычный CAS-lock выигрывает у любой реализации biasing. Для версии своего jdk под x86 они все еще используют biased locks (правда, какую-то свою реализацию -- не такую, как у Sun/Oracle JDK) -- но видимо, это вопрос времени.

С другой же стороны, обновленные бенчи Мартина показывают, что пока что, на Nehalem-ах, с использованием стандартного Oracle JDK, biased locks обходят RL/synchronized где-то в 10 раз. Хотя к бенчам Мартина я теперь отношусь как-то с осторожностью :(

24 ноября 2011 г.

Хорошая архитектура...

...позволяет откладывать принятие ключевых решений. Хорошая архитектура максимизирует количество непринятых решений. (с) Боб Мартин

Прочитал сегодня на хабрахабре, и просто поразился -- насколько это соответствует моему собственному ощущению. Огромное спасибо Бобу, и автору статьи за вербализацию.

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

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). Вот и получается фигня всякая...

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

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

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Мб, проценты -- среднее значение стандартного отклонения):
ABQ: (2.6-2.8 ± 7%)
Optimized SESDQueue: (17-19 ± 20%)
Disruptor:(30-75 ± 30%)
*106ops/sec

Заходим с хвоста

После долгих раздумий я решил зайти с обратной стороны. Основные конкурентные операции в реализации очереди это 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%)
*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, и разброс в этих результатах может быть гораздо выше -- кроме того на персональной машине гораздо сложнее обеспечить должную изоляцию).