Привет,
я тот самый дядька, который гонит пургу на стендапах :-) Не мог пройти мимо

NekZНапример, что не нужно математически доказывать корректность алгоритма -- нужно его обложить кучей грубых и нагрузочных тестов в продакшне. Типа "ну а мне-то чо, что доказано? Главное чтобы работало стабильно"


Это довольно серьезный вопрос. Дело в том, что описание и доказательство работоспособности алгоритма обычно дается в независимом от языка реализации виде и поэтому - в предположении sequential consistent модели памяти. Думаю, SQ - это не то, что Вы хотели бы видеть у себя в программе. Работ, посвященных анализу конкурентных алгоритмов именно в модели памяти C++, немного (справедливости ради надо сказать, что их появляется все больше), и в основном они касаются простейших алгоритмов с двумя - тремя атомарными переменными. В случае алгоритмов с бОльшим числом взаимодействующих атомарных переменных анализ весьма затруднен. Инструментов для анализа довольно мало (я имею в виду открытых, open source) - кроме Thread Sanitizer, пожалуй, ничего и нет. Выхлоп, который дает TSan, довольно часто ставит меня в тупик...

Есть ещё relacy Дмитрию Вьюкова, - пожалуй, наиболее продвинутый (по заложенной идее) на сегодня инструмент, жаль, что он не доведен до конца (хотелось бы инструментации кода в стиле санитайзеров).

Вообще, я скажу крамольную вещь, - модель памяти C++ так, как она описана в стандарте, нежизнеспособна. Это набор аксиом, весьма слабо коррелирующих с реальным положением дел в hardware. Это мое сугубое ИМХО, но оно косвенно подтверждается, например, нежеланием разработчиков Linux переходить на модель памяти C++11 (как Вы помните, модель памяти C++11 также распространяется на C11), и это нежелание они (Linux developers) весьма неплохо аргументируют.

NekZИли его подход к проектированию кода -- прямо на стэндапе показывал как подпирает свой код костылями (ещё и в виде макросов)
Видимо, на одном из выступлений я забыл произнести сакральную фразу про то, что "lock-free алгоритмы настолько многословны, что не вмещаются на страницу презентации, поэтому здесь я нагадил применил макросы". Я тоже не любитель макромагии, подтверждением чему может быть исходный код libcds в первозданном, так сказать, виде.
Ну и насчет костылей. Вы не поверите, пока не прочтете первоисточники, - половина lock-free кода - это именно костыли. Костыли для того, чтобы любое промежуточное состояние контейнера в процессе вставки/удаления элемента было персистентным. Поэтому я предпочитаю термин "трюки" ;-) Костыль - это кеши процессора.

Да, ссылки есть, например, одно из последних: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0124r1.html
Вообще, у Paul McKenney много об этом.
Но разговор идет не о том, что лучше/хуже, а о том, что они (модели памяти) различны. Ядро Линукса использует более "старую" модель (read/write barriers), которая возникла как раз из железа и зачастую более понятна в применении.

CEMbа можно небольшой экскурс по теме, как оно устроено, и почему оно плохо?

уфф, вкратце так и не опишешь... Это тема для хорошего застолья с пивом на весь вечер. Ниже - мое ИМХО.
Я впервые услышал и увлекся lock-free структурами данных в 2006 году, то есть почти одновременно с началом дискуссии об atomic в C++11. Тогда (где-то 2008-2010 года) было несколько подходов к atomic и несколько жарких дискуссий в политкорректной форме, все документы есть на wg21 . Победил Hans Boehm и его подход.
Так как в то время C++11 ещё не было, приходилось писать свои atomic-велосипеды и, соотвественно, изучать модели памяти различных архитектур (честно скажу - от тех времен в голове мало что осталось). Причем весьма полезной была инсайдерская инфа от разработчиков того или иного процессора с различных форумов.

В стандарте модель памяти C++11 описана в терминах ячеек памяти, и memory order применяется тоже к ячейкам памяти. То есть если есть два различных адреса A и B, то, по стандарту, memory ordering, примененный к A и к B, никак не связаны. Отсюда вытекают некоторые подозрительные вещи: например, чтобы удовлетворить стандарту, предлагается вводить ненужные атомарные переменные с довольно тяжелыми операциями atomic fetch_add и memory_order_acq_rel ( вот разбор схемы Hazard Pointer в терминах C++11 memory model). Но реально memory order - это барьеры, на всех современных архитектурах они не применяются с конкретным адресам памяти, - они глобальны. На ассемблере барьер - это отдельная инструкция .
Часто возражают - а вот Intel Itanium, у него load/store с явным указанием acq/rel-семантики в одной инструкции, то есть тут барьер явно привязан к конкретному адресу, что и постулирует стандарт. Но если почитать спеку Intel Itanium по его модели памяти, то там часто путаница - в одном месте cказано, что memory ordering применяется к адресу, в другом - про адреса вообще ни слова. И самое главное - по инфе от разработчиков Итаниума, внутри все эти acq/rel-полубарьеры для load/store - это обычный mfence, то есть полный барьер, не связанный с адресом!
А теперь немного конспирологии ;-) Родителем memory model C++11 является, насколько я понимаю, Hans Boehm, - умный мужик ученый (любимое число - 42 ;), который на момент разработки стандарта работал... в лабораториях HP ! А кто такая HP? Это главный пропагандист архитектуры Itanium. А у Itanium load/store с явным указанием семантики acq/rel, - то, что мы сегодня видим в atomic load/store C++11.

Что ещё мне не нравится в стандарте - то, что memory order явно связан с потоками (threads). Да, несомненно, модель памяти предназначена именно для multithread. Но попытка каким-то образом связать load.acq одного потока с store.rel другого - это запутывание читателя! Один поток никак не может влиять на видимость значений в другом; часто пишут "поток A записал в M значение 42, но поток B не увидит 42 в M, пока/если..." и т.д. Все это чушь полная! Вернее, это производное рассуждение от истинной проблемы. Видимостью мы управлять вообще не можем. У современных процессоров кеши когерентные, так что "A записал, а B не увидел" - с точки зрения кеша такого быть не может. Но вот порядок/order , в котором B увидит то, что записал A, может быть другим. И виноват в этом не кеш, а небольшой костыль в виде store buffer между каждым ядром процессора и L1 кешем. Порядком мы управлять можем - это называется memory fence/barrier. И это отдельная инструкция, а не довесок/флаг в виде memory order к atomic load/store.

У меня большое подозрение, что C++11 memory model писалась исключительно для реализации spin lock. Но в конкурентных контейнерах применяются такие изощренные схемы, которым существующий memory ordering мал. Например, частый трюк при построении алгоритма конкурентного self-balanced дерева: операция поиска find() - неблокируемая, операции insert/erase - применяется fine grained locks на уровне узлов. То есть это схема single producer (только один поток может делать вращения) - multiple consumer (много потоков могут ходить по дереву, в том числе и по тем ветвям, которые в данный момент вращаются). При вращениях, особенно двойных, очень важен порядок, в котором указатели на узлы дерева (они, конечно же, atomic) модифицируются, иначе find()-потоки залезут не туда. Вопрос: какой тут должен быть memory ordering для чтения и записи node ptr?.. По сути, здесь достаточно store/store барьера во вращениях между каждым изменением указателя на узлы, то есть только в producer'е, чтобы задать порядок, в котором consumer'ы должны увидеть модифицируемые узлы поддерева. Как выразить это в C++11 memory model?..

NekZ,

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

Вася Уткин, я ждал этого вопроса, про оптимизации компилятора ;-) Вы уже все сами ответили - да, барьеры также являются и барьерами компилятора. Полагаю, C++11 memory model для компиляторов был головной болью, ибо запрещал практически все оптимизации (речь, конечно, об atomic), - все они рассчитаны на один поток. Например, GCC, объявив GCC-4.8 "C++11 ready", только к GCC-6 восстановил большую часть оптимизаций (это мое наблюдение и найденные обмолвки/слухи/тесты в инете, пруфа не дам).
Но почему они (барьеры) должны быть обязательно прикреплены к atomic load/store/RMW?..
load(acquire) - это

load x
membar LoadLoad | LoadStore

store( release ) - это

membar LoadStore | StoreStore
store x

Вот вам явные (полу)барьеры с relaxed load/store. Они же - барьеры компилятора (они же - ассемблер Sparc; пожалуй, у Sparc была наиболее прямая memory model, без излишеств, но которая позволяла всё).
Это та модель, которая применялась до C++11, которая применяется сейчас в ядре Linux и которая прямо вытекает из железа.
И здесь барьеры не привязаны к ячейкам памяти, которые читаются/пишутся. Это просто явное указание упорядочения load/store.
Именно это я и "имел в виду под выделенным" - барьер не привязан явно к адресу. Если вы внимательно прочтете ту ссылку, которую я давал, не весь документ, а часть про Hazard Pointer, - увидите: там ради удовлетворения стандарта (которого на момент написания ещё не было, но он активно обсуждался) вводится ненужная для HP атомарная переменная, через которую синхронизируются потоки с помощью RMW. И все потому, что в HP atomic.load(A, acquire) и тут же atomic.store(B, release) - два разных адреса, а два разных адреса по C++11 не синхронизируются.

В общем, чем больше я работаю с atomic/memory ordering, - тем больше у меня вопросов. Maybe, это потому, что в свое время я начитался запрещенной литературы мануалов по различным архитектурам (кстати, могу сказать, - по большей части многотомное и бесполезное чтиво, только запутывает, начинаешь с подозрением относится даже к регистровым операциям).
Мне все больше кажется, что C++11 memory model - это лишь первая итерация, ещё далекая до идеала. И я рад, что нашлись линуксоиды-ядерщики, которые задают комитету похожие вопросы, - значит, дискуссия продолжится и решение будет найдено.