Реалистичны ли данные о производительности стека без блокировки на http://tinyurl.com/pzpyvb9?

В конце http://blog.memsql.com/common-pitfalls-in-writing-lock-free-algorithms/, Дэвид Столп показывает данные о производительности стека без блокировки, показывающие, что версия без блокировки работает медленнее, чем последовательная версия, защищенная мьютексом, даже при увеличении конкуренции. Результаты интересные, но меня беспокоят две вещи:

  • В лучшем случае «общая пропускная способность» снижается, а затем выравнивается по мере увеличения количества потоков. Не должна ли общая пропускная способность увеличиваться по мере увеличения количества потоков?
  • На итоговой диаграмме значения производительности для 1 потока варьируются примерно от 35 до 55 млн. Это кажется ужасно широким диапазоном для 1 потока (где не может быть никаких разногласий).

Я пытался найти способ связаться с автором по поводу этих проблем, но безуспешно, поэтому я обращаюсь к сообществу SO, чтобы узнать, кажутся ли результаты реалистичными. Они?


c++ multithreading performance benchmarking lock-free
person KnowItAllWannabe    schedule 03.10.2013    source источник
comment
Как я вижу, версия с мьютексом самая медленная.   -  person GJ.    schedule 03.10.2013
comment
@GJ: Насколько я могу судить, версия на основе мьютекса по существу имеет ту же (медленную) скорость, что и наивная версия без блокировки (согласно окончательной диаграмме). Однако это могло бы быть немного медленнее, вы правы. Но это не влияет на мои вопросы о пропускной способности по мере увеличения количества потоков или о широком диапазоне значений пропускной способности для одного потока.   -  person KnowItAllWannabe    schedule 04.10.2013

Ответы (2)


arrow_upward
1
arrow_downward

В лучшем случае «общая пропускная способность» снижается, а затем выравнивается по мере увеличения количества потоков. Не должна ли общая пропускная способность увеличиваться по мере увеличения количества потоков?

Это нормально! Стек только один! Узким местом является синхронизация памяти между потоками, а не выполнение кода. Таким образом, если больше потоков заполняет стек, должно возникнуть больше конфликтов памяти (возникают условия гонки), поэтому пропускная способность снижается.

На итоговой диаграмме значения производительности для 1 потока варьируются примерно от 35 до 55 млн. Это кажется ужасно широким диапазоном для 1 потока (где не может быть никаких разногласий).

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

Если вы проверите код, то увидите, что версия SpinLock очень проста и может быть быстрее, чем LockFree, потому что она сделана с помощью атомарной функции test_and_set, которая обычно быстрее, чем атомарная функция CAS (сравнение и обмен), которая используется в версии LockFree.

ИЗМЕНИТЬ:

В версии LockFree используется cmpxchg16b, который является 16-байтным CAS, в SpinLock используется только 8-байтовая функция test_and_set (реализованная с помощью cmpxchg8b), так что разница в скорости существует!

person GJ.    schedule 03.10.2013
comment
Если тестовый код выполнял некоторую работу между операциями со стеком (например, выполнял некоторую работу по подготовке объекта для стека, затем помещал его в стек; после извлечения элемента выполнял некоторую работу над ним), мы ожидали бы, что пропускная способность будет увеличиваться по мере увеличения числа потоков увеличилось, не так ли? Кроме того, я правильно понимаю, что вы загрузили код теста и взглянули на него? - person KnowItAllWannabe; 04.10.2013
comment
@KnowItAllWannabe: проверьте код, как создан стек потокобезопасных программ для LockFree и SpinLock. В версии LockFree используется cmpxchg16b, который составляет 16 байт CAS, в SpinLock используется только 8 байт CAS cmpxchg8b, так что разница в скорости существует! - person GJ.; 04.10.2013
comment
Я отмечаю это как принятый ответ, потому что он пришел первым. Ответ Дэвида Хаммена ниже по сути такой же, хотя его легче читать. - person KnowItAllWannabe; 05.10.2013

arrow_upward
1
arrow_downward

В лучшем случае «общая пропускная способность» снижается, а затем выравнивается по мере увеличения количества потоков. Не должна ли общая пропускная способность увеличиваться по мере увеличения количества потоков?

Не обязательно и точно не в этом случае. Многопоточность выгодна, если потоки выполнения могут выполняться одновременно. Лучше сделать приложение однопоточным, если потоки никогда не могут выполняться одновременно или если почти все выполнение связано с конкуренцией за один единственный ресурс.

Этот тест был разработан таким образом, чтобы потоки не могли выполняться одновременно. Почти весь код борется за один ресурс — стек. Этот номинально плохой дизайн был намеренно использован здесь, чтобы проверить накладные расходы различных схем параллельного выполнения и проверить, насколько хорошо различные схемы справляются с конфликтами.

На итоговой диаграмме значения производительности для 1 потока варьируются примерно от 35 до 55 млн. Это кажется ужасно широким диапазоном для 1 потока (где не может быть никаких разногласий).

Даже без конкуренции блокировка и разблокировка мьютекса сопряжены со значительными накладными расходами. При сравнении и обмене накладных расходов намного меньше, а при тестировании и установке еще меньше. Эти чистые накладные расходы — это то, что тестируется, когда есть только один поток выполнения.

person David Hammen    schedule 04.10.2013