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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Я не согласен с пользователем 237815. синхронизированное ключевое слово не требует таких больших накладных расходов, как когда-то, но по сравнению с алгоритмом без блокировки оно имеет значительный объем накладных расходов, связанных с ним по сравнению с одним CAS.

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

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

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

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

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

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