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