Масштабируемость и ограничения SpinLock

Я написал простую программу для проверки пропускной способности блокировки CLH. У меня есть код, как описано в книге "Искусство многоядерного программирования". Затем я запустил счетчик изменяющегося количества потоков на 10 секунд и определил counter/10.0 как пропускную способность.

Мой вопрос заключается в том, находятся ли результаты, которые я получил, в пределах логического диапазона и что может быть причиной того, что они такие, какие они есть. Я спрашиваю, потому что падение пропускной способности для блокировки CLH происходит очень быстро. Это результаты для блокировки cLH, где слева указано количество потоков, а справа — пропускная способность (размер счетчика, до которого каждый поток увеличивает его один раз в критической секции, защищенной блокировкой CLH, разделенный на 10).

CLH 1 2.89563825E7 2 1.33501436E7 4 5675832.3 8 15868.9 16 11114.4 32 68.4

Как вы видите, выпадение безумно и заставляет меня думать, что я мог что-то испортить.

Это мой код для блокировки CLH (так же, как в вышеупомянутой книге):

static class CLHLock implements Lock {
    AtomicReference<QNode> tail;
    ThreadLocal<QNode> myNode, myPred;

    public CLHLock() {
        tail = new AtomicReference<QNode>(new QNode());

        this.myNode = new ThreadLocal<QNode>() {
            protected QNode initialValue() {
                return new QNode();
            }
        };

        this.myPred = new ThreadLocal<QNode>() {
            protected QNode initialValue() {
                return null;
            }
        };
    }

    public void lock() {
        QNode qnode = this.myNode.get();
        qnode.locked.set(true);        

        QNode pred = this.tail.getAndSet(qnode);
        myPred.set(pred);           
        while (pred.locked.get()) {}      
    }

    public void unlock() {
        QNode qnode = this.myNode.get(); 
        qnode.locked.set(false);       
        this.myNode.set(this.myPred.get());   
    }

    static class QNode {  
        public AtomicBoolean locked = new AtomicBoolean(false);
    }
}

Запуск состоит из основного потока, ожидающего 10 секунд, в то время как другие пытаются заблокировать, увеличить, а затем разблокировать, пока изменчивое логическое значение не сообщит им, что время истекло.


person TheFooBarWay    schedule 11.05.2016    source источник
comment
По моему опыту, большая часть деградации вызвана перегрузкой процессора. while (pred.locked.get()) {} мог бы быть более общительным с while (pred.locked.get()) {Thread.yield();}. Может без разницы, так что только комментировать.   -  person OldCurmudgeon    schedule 11.05.2016


Ответы (1)


О реализации блокировки CLH

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

О результатах сравнительного анализа

Судить о правильности некоторого кода на основании тестов его производительности — задача, требующая не меньше знаний, чем судить о правильности некоторого кода на основе тестов его корректности.

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

Вот спекулятивное объяснение ваших результатов, которое может быть неверным, но вполне правдоподобным:

  • С 1 потоком ваш код выполняется очень быстро, потому что практически нет конкуренции за блокировку и нет перегрузки кеша. Вы, вероятно, выиграете от успешного прогнозирования ветвлений и раннего запуска JIT без последующей деоптимизации.
  • С 2 и 4 потоками вы получаете некоторое снижение пропускной способности. Это не так уж плохо, потому что у вас все еще есть аппаратные потоки, но теперь вы испытываете некоторую перегрузку кеша (возможно, даже ложное совместное использование), некоторый когерентный трафик и, возможно, некоторое неверное предсказание ветвления (из-за общей инфраструктуры вашего теста). Хотя вы не получаете увеличения пропускной способности от параллельного выполнения, вы все равно в порядке.
  • С 8 и 16 потоками вы превысили пределы доступных аппаратных потоков на вашем компьютере. Вы начинаете сталкиваться с эффектами планирования ОС, гораздо более значительным переполнением кеша, а также значительными конфликтами в вашем коде.
  • С 32 потоками вы выходите за пределы некоторых быстрых аппаратных механизмов кэширования (кэш L1, TLB) и переходите на следующий самый быстрый механизм. Для этого необязательно превышать ограничение на размер кэша, вы также можете превысить ограничение на ассоциативность.
person Dimitar Dimitrov    schedule 11.05.2016