Введение в lock-free программирование

[robert_ayrapetyan]

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

[marshinov]

Задач, требующих прям lock-free вроде-бы нет, но для себя интересно. Буду рад, если продолжите писать.

[DistortNeo]

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

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

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

[Borz]

разве асинхронный код не является одним из вариантов lock-free? или при этом у вас всё равно остаются блокировки?

[DistortNeo]

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

[aamonster]

Насколько я знаю, есть две основные ситуации, где это нужно:

1. Нужно гарантировать минимальную задержку выполнения для худшего случая. Пусть даже ценой ухудшения среднего быстродействия.
2. Высокая загрузка системы (ну, просто при высокой загрузке мы стабильно попадаем в тот самый "худший случай").

[robert_ayrapetyan]

Есть ли какие-то цифры и факты на эту тему?
Просто гуглеж на тему «lock free vs mutex» выдает какие-то пространные рассуждения на тему быстродействия, аналогично без конкретных замеров…

[khim]

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

Поищите какой-нибудь конкретный алгоритм для конкретного случая — получите конкретные цифры. Примерно такие.

[23derevo]

1. вы путаете lock-free и wait-free

2. Если ресурс contended (за него борятся N >> 1 потоков одновременно), то N-1 из N потоков в CAS Loop уйдут на второй круг. Прирост производительности может быть если ресурс — не contended.

3. С блокировками много проблем в плане надежности.

[claygod]

вы путаете lock-free и wait-free

Кстати да, и про wait-free очень бы хотелось почитать толковую статью,
может когда-нибудь и на Хабре что-то на эту тему появится.

[jetcar]

по мне так lock плох только в одном случае, когда 2 паралельных треда друг дружку залочат изза того что где-то чтото не учёл, ну и если работаешь с чем-то внешним что работает только с локами, в остальных случаях локи надёжнее и проще разобраться если чтото пойдёт не так, ну и зачастую быстрее

[khim]

локи надёжнее и проще разобраться если чтото пойдёт не так, ну и зачастую быстрее

Так не бывает, извините. Чтобы было надёжнее, проще и быстрее — так бывает только в сказках. Локи надёжнее, но, разумеется, ни разу не быстрее если у вас реально есть одновременный доступ к одной и той же структуре данных.

[23derevo]

Сценарий, в которых lock-free алгоритмы в случае «одновременного доступа» скажем 5-10 потоков к ресурсу будут быстрее алгоритма с блокировками, еще поискать нужно. Я этим занимался в свое время довольно серьезно, и результаты были такими, что часто заранее и не угадаешь, что быстрее.

[claygod]

часто заранее и не угадаешь, что быстрее

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

[23derevo]

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

[claygod]

Спасибо за формулирование правила. А как вы Вы определяете «высокий-низкий»?

[23derevo]

10 — высокий, 1 — низкий. Точка равеновесия будет посредине, ищется экспериментальным путем. Предсказать заранее трудно