Почему этот код работает * медленнее * с несколькими потоками, даже на многоядерном компьютере?

Question

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

Сначала посмотрите на код:

class ThreadSafeStack
  def initialize
    @s,@m = [],Mutex.new
  end
  def push(value)
    @m.synchronize { @s.push(value) }
  end
  def pop
    @m.synchronize { @s.pop }
  end
  def peek
    @m.synchronize { @s.last }
  end
end

Полный сценарий тестирования находится на https://github.com/alexdowad/showcase/blob/master/ruby-threads/concurrent_stack.rb. По сути, явыполнить миллион нажатий, миллион просмотров и миллион всплывающих сообщений, разделенных между 1, 5 или 25 потоками (работающими параллельно).

Результаты работы 4-ядерного Mac Pro с JRuby 1.6.5.1:

Testing ThreadSafeStack with 1 thread, iterating 1000000x each
  1.575000   0.000000   1.575000 (  1.575000)
Testing ThreadSafeStack with 5 threads, iterating 200000x each
  4.838000   0.000000   4.838000 (  4.838000)
Testing ThreadSafeStack with 25 threads, iterating 40000x each
 11.409000   0.000000  11.409000 ( 11.409000)

Что дает ???

РЕДАКТИРОВАТЬ : еще одна информация, которая может иметь отношение к делу - этот тест действительно работает быстреес несколькими потоками , когда Я использую стек без блокировки (реализовано с помощью операций сравнения и замены).

Answer 1

Потому что ... вы синхронизируете?

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

Изменить, чтобы добавить из комментариев ниже, потому что это .. стоит добавить:

Блокировка дорогая. У вас есть X потоков, которые сейчас борются за один и тот же ресурс. Я не знаком с внутренностями ruby, чтобы точно сказать вам, как они это реализуют, но по крайней мере в * nix это должен быть довольно простой путь к pthread_mutex. Необслуживаемая блокировка может быть обработана в пользовательском пространстве, но для принудительной блокировки требуется вызов в ядро; это дорого и почему это намного медленнее, не говоря уже о том, что каждый раз, когда поток уступает ожиданию блокировки, более чем вероятно, что вы делаете переключение контекста, что также дорого.

Answer 2

Я рекомендую вам просмотреть слайды Скотта Мейера Кэши ЦП и почему вы заботитесь . Особый интерес для вас представляет слайд 8, на котором показано, как наивному подходу добавления многопоточности к алгоритму на самом деле требуется 16 физических потоков ЦП, чтобы соответствовать производительности одного потока , а 2 потока примерно вдвое медленнее , чем один поток (очень похоже на ваш эксперимент). Херб Саттер также имеет множество статей и семинаров, посвященных этой теме, и Поваренная книга по оптимизации программного обеспечения - превосходная книга по этой теме. И, конечно же, есть Искусство многопроцессорного программирования . Обратите внимание, что Ничего Я упоминал выше, что-то связано с Ruby. Это не случайно, тема / проблема является фундаментальной и происходит от оборудования .

В результате получается, что даже если ваши мьютексы легковесны и реализованы только в пространстве пользователя (без поездки в землю ядра), вы работаете с алгоритмом когерентности кэша ЦП . Каждый раз, когда вы обнаруживаете, что просматриваете код, который в параллельной среде изменяет общее состояние примерно так же часто, как и его чтение (подсказка: ваша защита стека Mutex равна точно такого общего состояния, а также самого стека) вы должны ожидать довольно ужасную производительность, гораздо медленнее, чем один поток. В основном все ваши обращения к такому общему состоянию должны обслуживаться из основного ОЗУ, а не из кеша, а это примерно в 100 раз медленнее. Один поток заплатит этот штраф только при первом доступе, все последующие доступы будут из кэша L1 / L2.

Вот почему серьезное многопоточное приложение

• не делить состояние между потоками
• использовать конструкции без блокировки

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

Answer 3

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

Answer 4

Вы тестируете ThreadSafeStack, который синхронизирован, поэтому не может быть одновременных операций и разницы нет.Добавьте накладные расходы на синхронизацию, и это станет медленнее.