Здравствуйте, rm822, Вы писали:

R>Я буду исходить из реальных задач.
R>Ну например — есть у меня какой-то кусок работы, который я решил распараллелить с помощью OMP. Пусть у меня в нем есть vector в который я запихиваю элементы, в последовательной версии он был один, а в параллельной есть выбор
R>-я могу оставить его и сделать синхронизацию через criticalsection. Я знаю что один Interlocked займет тиков 70, ну плюс еще затраты на мутекс — пускай 200 тиков = 270 тиков из которых 70 не параллелятся
R>-могу присобачить lockfree контейнер (предположим что они у вас хорошего качества). Overhead на их использование неизвестен и неизвестно какая часть не распараллеливается в принципе
R>-могу использовать отдельные вектора и получить overhead только на слиянии. Конечно этим шагом я снижу распараллеливаемость, но эти затраты легко померять

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

И чего тут не хватает? Твоего представления о lock-free алгоритмах?
Если серьёзно, то во-первых никто и не говорит, что какое-то решение подходит для всех проблем. Т.е. постановка не понятна, ты взял какую-то конкретную проблему, и что дальше? Даже если бы ты однозначно заключил, что lock-free алгоритм для неё полностью не подходит, это бы практически ничего не говорило о применимости lock-free алгоритмов. Как говорится — "в Англии есть как минимум одна овца, белая как минимум с одного бока"
Во-вторых, lock-free алгоритм, который содержит 1 атомарную RMW инструкцию на операцию практически всего лучше аналогичного mutex-based алгоритма, т.к. спин-мьютекс всегда содержит эту же самую 1 атомарную RMW инструкцию, а не спин мьютекс будет содержать как минимум 2.
В-третьих, lock-free как таковой — это не о производительности

Автор: remark
Дата: 27.04.08

, и это не надо забывать. Lock-free — это только forward-progress и termination-safety. Наивное, но распространённое, мнение "что вот сейчас я добавлю lock-free, и всё станет быстро и масштабируемо" мягко говоря не верно. Это то же самое, что "вот сейчас я добавлю SSE оптимизации в мою пузырьковую сортировку, и она станет супер-быстрой".
А если делать упор на производительности и масштабируемости, то это несколько другая область алгоритмов, в целом они вполне могут и использовать мьютексы на каких-то путях, и обычно это затрагивает не просто какой-то компонент, а скорее симбиоз между всеми уровнями приложения, начиная с самых высоких, и до самых низких, где производительность и масштабируемость "подкрепляется" некоторыми "lock-free техниками" по необходимости.
Для конкретно твоего примера никакие специальные concurrent контейнеры не нужны, и третий вариант скорее всего самый лучший и намного лучший (тут можно обойтись вообще без мьютексов, достаточно pthread_create/pthread_join). Тем более, что фаза слияния тоже иногда распараллеливается (например, слияние в merge-sort).