В каких случаях лучше использовать lockfree структуры данных, а когда на мютексах?

Question

[Trrrrr]

Необходимо реализовать multiple writer single reader queue.
Сразу нагугилось boost::lockfree::queue. Мне для этого никогда не приходилось использовать lockfree алгоритмы. Вот стало интересно в каких случаях предпочтительнее их использовать.

Answer 1

[degs]

Это сильно зависит от задачи, в общем случае lockfree алгоритмы позволяют передавать сообщения без блокировки читающего/пишущих потоков и получить задержку < 1 мкс на сообщение. Если у вас именно такие технические требования, то boost::lockfree вероятно единственный портабельный вариант.
Однако, если вас интересует скорость передачи (а не задержка в терминах мкс/на сообщение), то обычная блокирующая очередь ничем не уступит по параметру собщений/сек.
Еще один вариант применения - если вам нужно как можно быстрее освободить пишущий поток (типичный пример - логгер), тогда неблокирующая очередь - самый оптимальный алгоритм.
Обратите также внимание на то что boost::lockfree, как и все другие реализации, не предоставляет способа синхронизации читающего потока, то есть он будет непрерывно работать тратя ресурсы CPU. Если же вы искуственно его синхронизуете, например на мьютексе, то lockfree очередь выродится до обычной блокирующей. Еще из недостатков, существующая имплементация жестко ограничивает типы данных в очереди, простые данные с побитовым копированием и без конструктора, это очень ограничивает варианты дизайна.
Моя рекомендация - если у вас нет очень жестких специфических требований на пердачу данных, используйте обычную очередь.

Comments

[Trrrrr]

Да я так и сделал, решил что обычная реализация будет проще/понятнее для будущей отладки. Но вот насчет типов данных в очереди проблем как раз я бы не увидел. У меня были бы умные указатели на обьекты.

[degs]

@Trrrrr: Умные указатели не пойдут, вот кусочек из документации:

template class queue;
Requirements:
T must have a copy constructor
T must have a trivial assignment operator
T must have a trivial destructor

Если строго следовать букве, это значит что T должен простой побитово копируемой структурой с пустым деструктором. Похоже авторы вложили всю ментальную мощь в сам алгоритм и полностью забыли про всяческий полиморфизм, которым так славен был ранний boost.
Как пример, автор boost::log на вопрос, почему они не используют boost::lockfree, уклончиво ответил что в нем слишком много конструктивных ограничений и им пришлось написать свою неблокируюшую очередь. Тревожный звоночек для boost я бы сказал.

[Trrrrr]

@degs: ну обычные указатели в любом случае смогу хранить. Так что я пока что проблем не вижу в ограничении все равно.

Answer 2

[AxisPod]

На деле всё очень сложно и часто без 2х реализаций сказать очень сложно. На жесткой гонке lock-free могут очень плохо себя показать, т.к. будут постоянно болтаться во внутренних циклах, пытаться записать данные, при этом другие потоки будут влезать и мешаться. Опять же всё зависит от того как использовать. Например вряд ли будет выгодным вытаскивание из одной очереди 5-10 элементов на одно действие, т.к. будет в лучшем случае 10-20 lock-free операций со сбросом кэша, тут выгоднее даже будет spinlock mutex.

Answer 3

[Сергей Протько]

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

Так же при большом количестве потоков и высоком уровне конкуренси lock-free предпочтительнее.

Comments

[AxisPod]

На деле вы не совсем правильно выразились, стоит использовать если потоков много, но при этом не высока гонка на lock-free алгоритмах, если же нагрузка на lock-free алгоритмы будет высока, то гонка съест всё преимущество.

[Сергей Протько]

@AxisPod: ну как... если у нас есть 4 потока, которые пишут в буфер результат каких-то вычислений и 1 пото которые эти результаты считает и что-то делаешь с этим дальше... скажем вычисления длятся 100 микросекунд, запись в буфер - 1 микросекунду, переключение контекста - 100 микросекунд... чтение из буфера - так же 1 микросекунду или итого меньше. Так у нас 4 потока за 100 микросекунд посчитают свои результаты и потратят ~4 микросекунды на то что бы записать все в буфер. Причем поток-читатель может обратиться к разделяемому ресурсу, залочиться, и это приведет к каким-то микролагам...

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

Немного сумбурно вышло...

[AxisPod]

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