Ссылка на 4 возможных реализации seq_cst на x86_64: http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html

И первая картинка там не release, а relaxed для c.store():

Anatoly MoskovskyВася УткинА раз компилятор оставляет возможность таких переупорядочиваний процессору, значит и сам компилятор может делать эти же переупорядочивания.

Ну, я бы остерегся делать какие-либо выводы на основе реализации компиляторов.
Не говоря уже о том что отсутствие упорядочивания от компилятора не означает что процессор может переупорядочивать . Вполне возможно и другая причина - компилятор знает что проц. не будет переупорядочивать и поэтому не делает барьер.

Касательно вообще поднятого мной вопроса, то по всей видимости порядок гарантируется только среди доступов с seq_cst , а все что без него может передвигаться.
В этом случае непонятно как все работает ))
Все вот эти примеры с машинным кодом не слишком проясняют.
Позже еще почитаю и поэкспериментирую.
То что процессор точно может переупорядочивать - это я доказал.
Какой код генерирует GCC/Clang/MSVC/icc - можете посмотреть, а то что x86_64 может менять местами Store-Load без MFENCE между ними - это документация: Intel® 64 and IA-32 Architectures
автор8.2.3.4 Loads May Be Reordered with Earlier Stores to Different Locations

Ну а строго - именно так и написано в стандарте, но как я понял его никто не понимает, кроме тех кто писал

khizmaxВася Уткин,
Я согласен с вами, что указание порядка прямо с атомарной инструкцией, как это задано в C++11, может дать некие преимущества компилятору при оптимизации.
Правда, вот этот пример на PowerPC, про store/store reordering,

Вася Уткин* PowerPC - может переупорядочить Store-Store т.к. между ними нет sync:

меня несколько смущает: вроде бы общепринято, что для spin-lock достаточно acquire/release семантики: acquire RMW - вход в критическую секцию, release store - выход. Положим, что spin-lock защищает секцию, в которой мы только что-то сохраняем:
Из вашего примера, где используется даже более сильный seq_cst store, получается, что на PowerPC (а раз это компилятор "пошалил", то можно полагать, - на любой архитектуре) все store (обычные, не atomic), могут просочиться вниз, за критическую секцию спин-лока?.. Или я чего-то не понял?..
Да, не поняли, но я описал очень строго.
1. Могут быть переупорядочены: store(seq), store(relaxed)
2. Не могут быть переупорядочены: store(relaxed), store(seq)
3. Компилятор не шалил, а выполнил строго то что описано в стандарте C++11 и мануалах PowerPC.
4. Не смотря на это, никакие инструкции Store или Load не могут выйти за пределы критической секции (пункт 2). Но множество Store могут войти в критическую секцию, если это выгодно процессору или компилятору (пункт 1).
5. Из пункт 4 - множество критических секций могут быть слиты в одну (acq - acquire, rel - release):
* было: load1(acq), code1, store1(rel), load2(acq), code2, store2(rel), load3(acq), code3, store3(rel)
* стало: load1(acq), load2(acq), load3(acq), code1, code2, code3, store1(rel), store2(rel), store3(rel)

Ещё раз схема - справедливость которой я утверждаю, такое переупорядочивание строго позволено стандартом C++11 и оно очень сильно оптимизирует программу.
1. Т.к. a.store(seq) расположен до c.store(relaxed), то они могут поменяться местами.
2. Если бы c.store(relaxed) стоял до a.store(seq), как это расположено в критической секции - то они не могли бы поменяться местами - sync стоит прям перед a.store(seq) : https://godbolt.org/g/BTQBr8


Ещё раз внимательнее посмотрите картинки со стрелочками - такое переупорядочивание не нарушает критические секции, но позволяет их очень сильно оптимизировать:


khizmaxОбщее замечание: мне кажется, мы, по сути, говорим об одном и том же, только вы защищаете подход C++11, а я вижу в нем недостатки для практической работы. Большинство рассуждений сразу скатываются в atomic load/store с двумя, максимум тремя переменными. Алгоритмы lock-free структур данных работают часто с бОльшим числом атомарных переменных и не только с load/store, но и RMW (обычно CAS). Анализ правильности расстановки memory order в таких случаях весьма затруднен. Нужны инструменты (вы ведь, надеюсь, не полагаетесь только на аналитическое доказательство, что ваша программа не имеет утечек памяти, а применяете ещё и инструменты для поиска утечек, - asan и подобное). Да, C++11 допускает барьеры, не привязанные к переменным, - atomic_thread_fence, - но, например, TSan не инструментирует atomic_thread_fence, то есть просто не замечает его. Других удобных инструментов среди свободных я не знаю :-(
Я соглашусь с тем, что atomic_thread_fence дает меньше простора компилятору для оптимзации, - но разве это плохо?.. Особенно в такой тонкой области, как memory ordering...
Да, я говорю о плюсах именно стандарта C++11, но не о плюсах его реализации в компиляторах, утилитах и (может быть удивитесь) в процессорах.
В современных компиляторах icc/clang, утилитах из Intel Cluster Studio и процессорах ARM v8 с этим более менее нормально.
Например, в относительно новом ARM v8 исходили именно из модели памяти стандарта C++11 - атомарные операции совмещены с барьерами памяти:
* store(seq), load(seq) не генерируют барьер dmb ish на новых ARM v8: https://godbolt.org/g/J0u2LU
* Но store(seq), load(seq) генерируют барьер bl на старых ARM: https://godbolt.org/g/ekowgC

А если писать store(relaxed), fence(seq), load(relaxed) то даже новому процессору ARM v8 придется генерировать dmb ish: https://godbolt.org/g/Aow2MB

Поправил ссылку и dmb ish, вместо bl __sync_synchronize:
автор* Но store(seq), load(seq) генерируют барьер dmb ish на старых ARM: https://godbolt.org/g/V06gfN

khizmaxБольшинство рассуждений сразу скатываются в atomic load/store с двумя, максимум тремя переменными. Алгоритмы lock-free структур данных работают часто с бОльшим числом атомарных переменных и не только с load/store, но и RMW (обычно CAS). Анализ правильности расстановки memory order в таких случаях весьма затруднен.
Я могу объяснить и на больших алгоритмах, со множеством RMW, там гораздо больше оптимизаций возможно. Но смысл? Если у одних из лучших разработчиков даже после детального доказательства вызывают вопросы примеры из 3-х переменных :)

khizmaxЯ соглашусь с тем, что atomic_thread_fence дает меньше простора компилятору для оптимзации, - но разве это плохо?.. Особенно в такой тонкой области, как memory ordering...
Это плохо из-за значительной потери производительности - доказал выше.
И плохо из-за меньшей надежности программы:
* барьеры неправильно совмещенные с неправильными операциями выдают ошибки компиляции: http://melpon.org/wandbox/permlink/HHalUgvmUAUxoaGH
* барьеры реализованные отдельно от операций как ни ставь не выдадут ошибки компиляции: http://melpon.org/wandbox/permlink/TxpwSSGWpnLqw5LY

Но вы правы, что большинство утилит и компиляторов пока работают с C++11 не так хорошо, да и процессоров чьим архитектурам больше 8 лет - не заточены под него :)
Со временем они дотянут до C++11.
Однако я не защищаю C++11, я считаю что будущее за Hardware Transactional Memory и Best practicies из GPU (CUDA/HIP). Рано или поздно CPU дорастут по ширине SIMD и количеству ALU до GPU.

Anatoly MoskovskyВася Уткинтакое переупорядочивание не нарушает критические секции, но позволяет их очень сильно оптимизировать
Любой вход /выход чтения/записи в /из критической секции - это нарушение семантики критической секции.
Поэтому я пока не верю, вышеприведенным картинкам. А вот многолетней практике спинлоков в SMP - верю ))
Но к сожалению, у меня нет времени сейчас вникать в это и разбираться.
Выделенное - абсолютно не верно, это азы многопоточного программирования. Ну дело ваше не верить стандарту C++11, ассемблеру генерируемому компиляторами gcc/clang/icc/msvc и документации Intel IA64, кто не разобрался - тому остается только верить во что-то

khizmaxвроде бы общепринято, что для spin-lock достаточно acquire/release семантики: acquire RMW - вход в критическую секцию, release store - выход. Положим, что spin-lock защищает секцию, в которой мы только что-то сохраняем:


Anatoly MoskovskyВася Уткинтакое переупорядочивание не нарушает критические секции, но позволяет их очень сильно оптимизировать
Любой вход /выход чтения/записи в /из критической секции - это нарушение семантики критической секции.
Поэтому я пока не верю, вышеприведенным картинкам. А вот многолетней практике спинлоков в SMP - верю ))
Но к сожалению, у меня нет времени сейчас вникать в это и разбираться.

Anatoly MoskovskyСтранно, я всегда думал что через load/store совмещенный с seq_cst компилятору нельзя двигать операции в обе стороны (так же как и через release/acquire в одну сторону ), иначе например мьютекс не будет работать.
Я же вижу вы сами все прекрасно знаете :)
Т.е. для spin-lock достаточно acquire/release, к тому же через release/acquire нельзя двигать операции в одну сторону, тогда у меня вопрос к вам, в какую одну сторону нельзя двигать операции: 1.наружу или 2.внутрь крит секции? :)

khizmaxВася Уткин,
Я вижу, что вы очень хорошо понимаете memory ordering C++11. К сожалению, о себе я такого сказать не могу, - у меня типичный пример "бумажных знаний", когда вроде что-то знаешь, а применить на практике не можешь, либо можешь, но с большими сомнениями.
Красиво затролили :)

khizmaxВася УткинМогут быть переупорядочены: store(seq), store(relaxed)
Для меня это тоже было неожиданно - переупорядочение через seq_cst. Перечитал первоисточники, - вроде все верно, действительно могут. Хм...
Заметьте, ключевое слово здесь - "вроде", то есть я так до конца и не уверен, правильно ли я понял стандарт. Отсюда я делаю выводы:
либо я плохо понимаю английский

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

либо я полный нуб (этого тоже исключать нельзя)

Судя по тому, что я наблюдаю в инете и при личном общении, - скорее всего пункт 2.

Возможно даже разработчики компиляторов не сразу поняли стандарт, судя по несуразным багам в некоторых компиляторах, в примерах из 1 операции: https://connect.microsoft.com/VisualStudio/feedback/details/770885

khizmaxВася УткинЯ могу объяснить и на больших алгоритмах, со множеством RMW, там гораздо больше оптимизаций возможно. Но смысл? Если у одних из лучших разработчиков даже после детального доказательства вызывают вопросы примеры из 3-х переменных :)

В связи с этим у меня к вам предложение, даже два, на выбор:

1. Сложные вещи должны быть понятными. Мне кажется, что стандарту в части atomic и memory ordering не хватает некоего handbook, "memory ordering для чайников", где вполне понятным языком, но с точным доказательством со ссылками на пункты стандарта (назовем их аксиомами) был бы разбор типичных (и нетипичных) случаев переупорядочения. Причем ссылок на конкретные архитектуры в качестве доказательства быть не должно, - такие ссылки допустимы только как иллюстрации, - так как стандарт все же не привязан к конкретной архитектуре, поэтому следует ожидать, что компилятор может применять одни и те же оптимизации для любой архитектуры (понимаю, что это предположение спорно, но все же). Результатом такой работы могла бы быть статья/цикл статей, например, на хабре или где угодно, - думаю, было бы весьма интересно.

2. Мой шкурный интерес: провести code review в части memory ordering (но и в любой другой части тоже, если есть желание) библиотеки libcds . Я догадываюсь (точнее - знаю), что там багов в части memory order может быть много, об этом мне постоянно говорит TSan, но интерпретировать его ворнинги я часто не в состоянии, а не верить автору TSan я тоже не осмеливаюсь.
1. Может быть.
2. Вот тут боюсь или я рихнусь пока составлю схемы, или люди которые это будут читать Или просто скажут - не верю.


По поводу статей - на примере того же изменения порядка (store(relaxed) <--> load(seq)):

1.1. Например, в стандарте C++11 § 29.3 (3): http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/n4606.pdf
Есть такая фраза: There shall be a single total order S on all memory_order_seq_cst operations , consistent with the “happens before”...
- Т.е. чтобы доказать, что у seq_cst-операций есть единый порядок - достаточно привести эту цитату.
- Но чтобы доказать, что что у любых других операций нет единого порядка с seq_cst-операциями, надо доказать, что такого нигде в стандарте не написано:)

1.2. С другой стороны, если по логике :
- Чтобы доказать что чего-то никогда не бывает - надо привести строгую цитату
- Чтобы доказать что что-то хотябы иногда может быть - достаточно показать хотябы один случай

Т.е. для memory_order по логике:
- Чтобы доказать то, чего никогда не может быть (не может быть переупорядочивания seq-операций) - надо привести цитату со строгой гарантией - для этого достаточно привести эту цитату: There shall be a single total order S on all memory_order_seq_cst operations , consistent with the “happens before”...
- А чтобы доказать то, что не обязательно, но в принципе может быть (store(relaxed) <--> load(seq)) - достаточно привести хотя бы один пример показывающий его существование.

Но вы пишите: "Причем ссылок на конкретные архитектуры в качестве доказательства быть не должно"
Тогда остается только доказать, что нигде в стандарте не написано "у любых не-seq-операций есть единый порядкок с seq_cst-операциями" - как это сделать? :)

А вы вообще не думали libcds в boost продвинуть, или хотябы какие-то части libcds в стандарт?

Anatoly MoskovskyВася Уткинв какую одну сторону нельзя двигать операции: 1.наружу или 2.внутрь крит секции? :)
Наружу точно нельзя. А внутрь двигать это хамство - программисту лучше знать что должно быть внутри секции ))

Обкладывайте критическую секцию снаружи std::atomic_thread_fence(std::memory_order_seq_cst); https://godbolt.org/g/CT89i5
ни одна муха не пролетит в неё, и увидите по изменению производительности - кому лучше знать :)