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.

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

  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. Так, записываем: время на вопросы уменьшить до крайности :)

    ОтветитьУдалить