В каких случаях структуры данных без блокировок работают быстрее, чем основанные на блокировках?

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

• Конкуренция должна быть высокой
• Ядер ЦП должно быть достаточно, чтобы вращающийся поток мог работать непрерывно (в идеале должен быть закреплен на собственном ядре)

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

это зависит от вероятности столкновения.

если коллизия очень вероятна, оптимальным решением является мьютекс. Например: 2 потока постоянно помещают данные в конец контейнера. С блокировкой свободы только 1 поток будет успешным. Другой должен будет повторить попытку. В этом случае блокировка и ожидание были бы лучше.

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

Другая проблема со свободой от блокировок — спин-блокировки (интенсивное использование памяти), общая производительность атомарных переменных и некоторые ограничения на переменные.

Например, если у вас есть ограничение x == y, которое должно быть истинным, вы не можете использовать атомарные переменные для x и y, потому что вы не можете изменить обе переменные одновременно, в то время как lock() удовлетворит ограничение

Конструкция мьютекса очень редко, если вообще когда-либо, превосходит беззамковую. Итак, следующий вопрос: зачем кому-то использовать мьютекс, а не беззамковую конструкцию?

Проблема в том, что конструкции без замков могут быть сложными и требуют значительного объема проектирования, чтобы быть надежными; в то время как мьютекс довольно тривиален (в сравнении), а при отладке может быть еще сложнее. По этой причине люди, как правило, предпочитают сначала использовать мьютексы, а затем мигрировать на блокировку позже, как только будет доказано, что конкуренция является узким местом.

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