27 марта 2012 г.

...и вновь продолжается бой

Я тут в процессе подготовки к докладу -- прорабатываю тему Disruptor-а. И вот любопытные вещи обнаруживаются. Вот оказывается, что чтобы скакнуть почти вдвое от производительности ABQ нет необходимости реализовывать сразу хитрую очередь из Art of MP. Достаточно убрать из ABQ Condition-ы. Да, вполне можно оставить ReentrantLock, просто вместо ожидания на Condition notEmpty/notFull сделать spin-wait:

private final T[] items;
    /** items index for next take, poll or remove */
    private int takeIndex = 0;
    /** items index for next put, offer, or add. */
    private int putIndex = 0;
    /** Number of items in the queue */
    private int count = 0;

    private final ReentrantLock lock = new ReentrantLock();

    @SuppressWarnings( "unchecked" )
    public ABQConditionFreeQueue( final int size ) {
        this.items = ( T[] ) new Object[size];
    }

    private int inc( int i ) {
        return ( ++i == items.length ) ? 0 : i;
    }

    @Override
    public void enqueue( final T item ) throws InterruptedException {
        for ( int i = 0; ; i++ ) {
            if ( count < items.length
                    && tryAcquireLock() ) {
                try {
                    if ( count < items.length ) {
                        items[putIndex] = item;
                        putIndex = inc( putIndex );
                        ++count;
                        return;
                    }
                } finally {
                    releaseLock();
                }
            }
            backoff();
        }
    }

    @Override
    public T dequeue() throws InterruptedException {
        for ( int i = 0; ; i++ ) {
            if ( count > 0 && tryAcquireLock() ) {
                try {
                    if ( count > 0 ) {
                        final T item = items[takeIndex];
                        items[takeIndex] = null;
                        takeIndex = inc( takeIndex );
                        --count;
                        return item;
                    }
                } finally {
                    releaseLock();
                }
            }
            backoff();
        }
    }

    private void backoff() throws InterruptedException {
        Thread.yield();
    }

    private void releaseLock() {
        lock.unlock();
    }

    private boolean tryAcquireLock() throws InterruptedException {
        return lock.tryLock();
    }
Большая часть кода взята из ABQ, если что. Причем без backoff() эта штука обходит ABQ вдвое, а с задержкой через Thread.yield() -- почти вчетверо. Простота залог успеха. А я в прошлый заход сразу полез в дебри CAS-free.

10 комментариев:

  1. Не могу не поёрничать, что именно это я сразу про disruptor vs. ABQ и говорил: http://cheremin.blogspot.com/2011/09/disruptor-1.html

    ОтветитьУдалить
  2. Не, ты говорил -- насколько я тебя понял -- как раз про другое. Ты катил бочку на ReentrantLock, который там один (и потому contended), и который паркуется при первом же неудачном CAS-e. А это вовсе не важно -- я ж пишу, RL можно оставить, нехай он себе паркуется. Тормозят Condition-ы. Если оставить RL, но вместо ожидания на Condition сделать активное ожидание на условии -- пропускная способность сильно растет.

    ОтветитьУдалить
  3. Руслан, а к какому докладу-то ты готовишься? Где тебя можно будет послушать? Как доклад будет называться?

    ОтветитьУдалить
  4. А, да. На JavaOne я буду докладываться, 18 числа. Расчленяя Disruptor называется доклад. Вроде, в 16 часов

    ОтветитьУдалить
  5. Круто, молодца! Надо будет тебе каверзный вопрос какой-нибудь подготовить :)

    ОтветитьУдалить
  6. Так, записываем: время на вопросы уменьшить до крайности :)

    ОтветитьУдалить
  7. Руслан, конечно, хоть статье 5 лет, но у меня возник вопрос на этом моменте "Причем без backoff() эта штука обходит ABQ вдвое".

    А корректно ли убирать backoff()? В вашем коде я просто убрал backoff() в dequeue и тест ниже завис(тестировал через jcstress).

    @JCStressTest(Mode.Termination)
    @Outcome(id = "TERMINATED", expect = Expect.ACCEPTABLE, desc = "Gracefully finished.")
    @Outcome(id = "STALE", expect = Expect.ACCEPTABLE_INTERESTING, desc = "Test hung up.")
    @State
    public static class ABQConditionFreeQueueTest {

    ABQConditionFreeQueue queue = new ABQConditionFreeQueue<>(1);

    @Actor
    void actor1() throws InterruptedException {
    queue.dequeue();
    }

    @Signal
    public void signal() throws InterruptedException {
    queue.enqueue(1);
    }

    }

    Я попробовал объяснить поведение следующим образом. Представим такое выполнение:

    Thread B кладет в очередь, то есть выполняет следующие действия
    count < items.length && tryAcquireLock()
    if ( count < items.length ){
    ...
    ++count;
    ...
    finally {
    releaseLock();
    }

    Thread A вечно читает count > 0. Процесс не доходит до tryAcquireLock() из-за short-circut evaluation


    Thread B(здесь я пропустил некоторые операции)
    load(count, 0) --hb--> load(items.length, threhshold) --hb-->lock(v) --hb--> load(count, 0) --hb--> load(items.length, threhshold)
    --hb--> write(count, 1)--hb--> unlock(v)

    Thread A
    load(count, 0)

    И я не вижу как даже через so можно связать выполнение Thread B с Thread A, соответственно, выполнение, когда Thread A видит только count == 0, возможно.

    Может на слайдах, где Вы этот код, другая версия(они уже давно не доступны) или я где-то ошибся?

    ОтветитьУдалить
    Ответы
    1. 0. Все примеры кода в рамках того исследования -- это эксперименты. Вовсе не все они строго корректны -- я об этом, кажется, упоминал в докладе. Эти промежуточные варианты сфокусированы на том, чтобы посмотреть на конкретный эффект.

      1. Thread.yield() не может влиять на корректность кода, потому что у Thread.yield() нет никакой особой семантики в JMM. Он не SA, и не образует ни с кем ребер hb.

      2. Этот код написан спекулятивно: внешние проверки в цикле с count не защищены локом, поэтому теоретически JIT может их вынести за цикл. Вполне вероятно, что в новых версиях он стал делать это более агрессивно -- я встречал некоторое количество обсуждений на похожую тему в c-i. Кроме того и сам лок может быть уязвим к простаиванию (starvation): если один поток захватывает его слишком часто, то другой может его вообще не получить. То есть да, этот код не гарантирует прогресса (liveness).

      Удалить
  8. Ссылка на доклад протухла, а в интернете так и не нашел, поэтому и задал вопрос.

    Самое забавное, что именно в варианте, где есть Thread.yield() вечного цикла не наблюдал на x86 процессоре, несмотря на отсутствие ребер hb. Я не знаю, чем это объяснить. Это меня и смутило, думал на слайдах информации больше.

    На других архитектурах видимо проблема будет более нагляднее.

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

      Я бы не ожидал, что на других архитектурах проблема будет более наглядна: скорее всего дело в том, что jit выносит чтение count за цикл. Если это так, то вряд ли это зависит от железа.

      Лучше попробуйте более старые версии явы.

      Удалить