Действительно ли алгоритмы без блокировки работают лучше, чем их аналоги с полной блокировкой?

Question

Раймонд Чен делает огромный серию на без блокировки алгоритмы ,Помимо простых случаев функций InterlockedXxx, кажется, что преобладающая модель со всеми из них состоит в том, что они реализуют свои собственные блокировки .Конечно, нет блокировок процессора, но концепция циклического повторения на каждом процессоре для обеспечения согласованности очень похожа на спин-блокировку.Будучи спин-блокировкой, они будут менее эффективными, чем обычные блокировки, которые поставляются с операционной системой, поскольку они не дают контроля над своими квантами, ожидая других потоков.Поэтому всякий раз, когда кто-то приходит ко мне и говорит «но мой алгоритм не блокируется», мой общий ответ «так»?

Мне любопытно - есть ли тесты , которые доступныпоказать алгоритмы без блокировки, чтобы иметь преимущество перед их аналогами с полной блокировкой?

Answer 1

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

Однако они, как правило, значительно улучшают общую пропускную способность алгоритма в целом перед лицом конфликтов. Задержка переключения потоков * Переключения контекста и , которые быстро, во многих потоках, значительно замедляют пропускную способность вашего приложения. Алгоритмы без блокировок эффективно реализуют свои собственные «блокировки», но они делают это таким образом, что предотвращают или уменьшают количество переключений контекста, поэтому они имеют тенденцию не выполнять свои блокирующие аналоги.

Как говорится, большая часть этого зависит от рассматриваемого алгоритма (и реализации). Например, у меня есть некоторые процедуры, которые мне удалось переключить на новые параллельные коллекции .NET 4 вместо использования предыдущих механизмов блокировки, и я измерил улучшения более чем на 30% в моей общей скорости алгоритма. При этом существует множество тестов, которые показывают снижение производительности при использовании некоторых из этих же коллекций по сравнению с базовой блокировкой. Как и во всех оптимизациях производительности - вы на самом деле не будете знать, пока вы не измерите .

Answer 2

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

Ни один из ответов здесь, кажется, на самом деле не кажетсяПолучите суть разницы между «безблокировочной» петлей CAS и мьютексом или спин-блокировкой.

Важным отличием является то, что алгоритмы без блокировки гарантированно добьются прогресса самостоятельно - без помощи других потоков.С блокировкой или спин-блокировкой любой плохой поток, который не может получить блокировку, полностью во власти потока, которому принадлежит блокировка.Плохой поток, который не может получить блокировку, ничего не может сделать, кроме wait (либо из-за занятого ожидания, либо из-за ожидания ОС).

С алгоритмами без блокировки, которые зацикливаются наCAS, каждый поток гарантированно делает успехи независимо от того, что делают другие конкурирующие потоки.Каждая нить, по сути, контролирует свою судьбу.Да, он все еще может повторяться много раз, но количество циклов ограничено числом конкурирующих потоков.Это не может бесконечно зацикливаться, по большей части.(На практике возможна активная блокировка из-за, например, петли LL / SC , которая продолжает сбой из-за ложного совместного использования) - но опять-таки поток может принять меры для решения этой проблемы -это не во власти другого потока, удерживающего блокировку.

Что касается производительности, это зависит.Я видел вопиющие примеры алгоритмов без блокировок, которые полностью уступали своим аналогам блокировки даже в условиях высокой конкуренции.На компьютере с архитектурой x86-64 под управлением Debian 7 я сравнил производительность между очередью C ++ Boost.Lockfree (на основе алгоритма Майкла / Скотта) и простым старым std::queue окружением с std::mutex.В условиях сильного конфликта потоков версия без блокировки была почти в два раза медленнее.

Так почему это так?Что ж, производительность алгоритмов без блокировки в конечном итоге сводится к деталям реализации.Как алгоритм избегает ABA?Как добиться безопасного восстановления памяти?Существует так много вариантов ... теговые указатели, восстановление на основе эпох, RCU / состояние покоя, указатели опасности, общий сбор мусора в рамках всего процесса и т. Д. Все эти стратегии влияют на производительность, а некоторые также накладывают ограничения на то, как ваше приложение в целомможет быть разработан.В целом, по моему опыту, подходы подсчета ссылок (или подходы с теговыми указателями), как правило, работают плохо.Но альтернативы могут быть гораздо более сложными для реализации и требуют гораздо больше инфраструктуры восстановления памяти, основанной на локальном потоке хранения или обобщенной сборке мусора.

Answer 3

Без блокировки не обязательно быстрее, но она может исключить возможность взаимоблокировки или прямой блокировки, так что вы можете гарантировать, что ваша программа всегда будет продвигаться к завершению. С блокировками трудно дать какую-либо такую ​​гарантию - слишком легко пропустить некоторую возможную последовательность выполнения, которая приводит к тупику.

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

Answer 4

В Windows на x64 простой (без объединяющего массива перед списком freelist) свободный список без блокировок примерно на порядок быстрее, чем freelist на основе мьютекса.

На моем ноутбуке (Core i5)для одного потока без блокировок я получаю около 31 млн. операций списка независимых пользователей в секунду, а для мьютекса - около 2,3 млн. операций в секунду.

Для двух потоков (на отдельных физических ядрах) с I без блокировки.получить около 12,4 млн. фриланс-операций на поток.С мьютексом я получаю около 80 ТЫСЯЧ операций в секунду.

Answer 5

Основное преимущество подлинно свободных от блокирования алгоритмов состоит в том, что они надежны, даже если задача становится отложенной (обратите внимание, что освобождение от блокировки является более жестким условием, чем «не использовать блокировки» (*)). Несмотря на то, что существуют преимущества в производительности, позволяющие избежать ненужной блокировки, наиболее эффективными структурами данных часто являются те, которые во многих случаях могут работать с блокировками, но могут использовать блокировки для минимизации перебоев.

(*) Я видел несколько попыток «заблокировать» очереди с несколькими производителями, когда производитель, который был задержан в неподходящее время, не позволил бы покупателям видеть какие-либо новые элементы, пока он не завершил свою работу); такие структуры данных не следует называть «без блокировки». Один производитель, который заблокирован, не будет блокировать других производителей, но может произвольно блокировать потребителей.

Answer 6

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

Возьмите два Java-класса, ConcurrentLinkedQueue и LinkedBlockingQueue. При умеренной конкуренции в реальном мире CLQ значительно превосходит LBQ. В условиях сильной конкуренции использование приостановившихся потоков позволит LBQ работать лучше.

Я не согласен с user237815. Синхронизированное ключевое слово не требует таких дополнительных затрат, как это было раньше, но по сравнению с алгоритмом без блокировки оно имеет достаточное количество служебных данных по сравнению с одним CAS.

Answer 7

Да, свобода блокировок гарантирует прогресс, но если вы вручную не прервите потоки, что возможно на некоторых платформах, или не выделите их в критическом разделе и не получите исключение из памяти, или что-нибудь еще глупое, вам это не нужно. Правильно реализованная спин-блокировка почти всегда превосходит безблокировочные подходы, если не работает одинаково, потому что обычно вы будете выполнять больше работы в первый раз или после неудачных попыток. Если вы продолжаете сокращать время и переполняете процессор с помощью сравнительных инструкций обмена и / или не возвращаетесь после некоторого периода, предоставляя временный интервал потока другим потокам (что дает возможность запланированному потоку пробудиться и снять блокировку), то код без блокировки может работать лучше , Кроме этого я не думаю, что это возможно. Я не заинтересован, и не был в сложных типах данных, где спин-блокировка не подходит, но все же я чувствую, что правильно спроектированные алгоритмы блокировки будут почти всегда лучше. хотя я могу ошибаться.

Answer 8

Без блокировки также имеет то преимущество, что не спит.В ядрах есть места, где вам не разрешено спать - в ядре Windows их много - и это сильно ограничивает вашу способность использовать структуры данных.

Answer 9

Недавно на JavaOne Russia Сотрудник Oracle (который специализируется на производительности и тестах Java) показал некоторые измерения операций в секунду при параллельном доступе к простому счетчику int с использованием CAS (без блокировки, высокий уровеньфактически спин-блокировка) и классические блокировки (java.util.concurrent.locks.ReentrantLock)

http://dl.dropbox.com/u/19116634/pics/lock-free-vs-locks.png // извините, я не могу вставить изображения

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

Answer 10

В Java, по крайней мере, блокировка сама по себе может быть очень быстрой.Синхронизированное ключевое слово не добавляет много накладных расходов.Вы можете сами протестировать его, просто вызвав синхронизированный метод в цикле.

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