Атомные операции, std :: atomic и упорядочение записи

Я поместил ваш пример в проводник компилятора Godbolt и добавил некоторые функции для чтения, увеличения или объединения ( a+=b ) двух атомных переменных. Я также использовал a.store(1, memory_order_release); вместо a = 1; чтобы не получать больше заказов, чем нужно, так что это просто простой магазин на x86.

См. Ниже (надеюсь, правильные) объяснения. Обновление : у меня была семантика «выпуска», запутанная только с барьером StoreStore. Я думаю, что исправил все ошибки, но, возможно, оставил их.

---

Первый вопрос:

Является ли запись «а» гарантированной атомарной?

Да, любой stream, читающий a , получит либо старое, либо новое значение, а не какое-то наполовину написанное значение. Это происходит бесплатно на x86 и большинстве других архитектур с любым выровненным типом, который вписывается в регистр. (например, не int64_t на 32 бит). Таким образом, во многих системах это происходит так же, как и для b , как большинство компиляторов будет генерировать код.

Существуют некоторые типы хранилищ, которые не могут быть атомарными на x86, включая неодинаковые магазины, которые пересекают границу строки кэша. Но std::atomic конечно, гарантирует любое выравнивание.

Операции чтения-изменения-записи – это то, где это становится интересным. 1000 оценок a+=3 выполняемых в нескольких streamах одновременно, всегда будут давать a += 3000 . Вы потенциально получите меньше, если a не было атомарным.

Удовлетворительный факт: подписанные атомные типы гарантируют двойное дополнение дополнений, в отличие от обычных подписанных типов. C и C ++ все еще цепляются за идею оставить недопустимое недопустимое целочисленное переполнение в других случаях. Некоторые процессоры не имеют арифметического сдвига вправо, поэтому оставляя правый сдвиг отрицательных чисел неопределенным, имеет какой-то смысл, но в остальном он просто чувствует, как смешно обруч перепрыгивает теперь, когда все процессоры используют дополнение 2 и 8-битные байты.

---

Является ли какой-либо другой stream, читающий «a», как 1, гарантированно читает «b» как 2.

Да, из-за гарантий, предоставляемых std::atomic .

Теперь мы попадаем в модель памяти языка и аппаратное обеспечение, на котором оно работает.

C11 и C ++ 11 имеют очень слабую модель упорядочения памяти, что означает, что компилятору разрешено изменять порядок операций с памятью, если вы не скажете об этом. (источник: слабые и сильные модели памяти Джеффа Прешинга ). Даже если x86 является вашей целевой машиной, вы должны остановить компилятор от повторного заказа магазинов во время компиляции . (например, обычно вы хотите, чтобы компилятор вытащил a = 1 из цикла, который также записывается в b ).

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

---

Почему MFENCE происходит после того, как пишут «a» раньше.

Хранилища StoreStore – это no-op с сильной моделью памяти x86, поэтому компилятор просто должен поставить хранилище в b до того, как хранилище будет реализовано для упорядочения исходного кода.

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

x86 может повторно заказать магазины после загрузки. На практике происходит то, что исполнение вне порядка видит независимую нагрузку в streamе команд и выполняет ее перед магазином, который все еще ожидает, когда данные будут готовы. В любом случае, последовательная согласованность запрещает это, поэтому gcc использует MFENCE , который является полным барьером, включая StoreLoad ( единственный вид x86 не имеет свободного LFENCE/SFENCE . ( LFENCE/SFENCE применимы только для слабо упорядоченных операций, таких как movnt .))

Другой способ выразить это так, как используют документы C ++: последовательная согласованность гарантирует, что все streamи будут видеть все изменения в том же порядке. MFENCE после каждого атомного хранилища гарантирует, что этот stream видит магазины из других streamов. В противном случае наши грузы будут видеть наши магазины, прежде чем грузы других streamов будут видеть наши магазины . Барьер StoreLoad (MFENCE) задерживает наши нагрузки до тех пор, пока магазины, которые должны произойти в первую очередь.

ARM32 asm для b=2; a=1; b=2; a=1; является:

 # get pointers and constants into registers str r1, [r3] # store b=2 dmb sy # Data Memory Barrier: full memory barrier to order the stores. # I think just a StoreStore barrier here (dmb st) would be sufficient, but gcc doesn't do that. Maybe later versions have that optimization, or maybe I'm wrong. str r2, [r3, #4] # store a=1 (a is 4 bytes after b) dmb sy # full memory barrier to order this store wrt. all following loads and stores. 

Я не знаю ARM asm, но до сих пор я понял, что обычно это op dest, src1 [,src2] , но op dest, src1 [,src2] загружаются и сохраняются операнды регистров, а операнд памяти – второй. Это действительно странно, если вы привыкли к x86, где операнд памяти может быть источником или dest для большинства не-векторных инструкций. Загрузка мгновенных констант также требует больших инструкций, поскольку фиксированная длина инструкции оставляет место для 16b полезной нагрузки для movw (move word) / movt (move top).

---

Освободить / Приобрести

release и acquire имен для односторонних барьеров памяти происходит из замков:

• Один stream изменяет общую структуру данных, а затем освобождает блокировку. Разблокировка должна быть глобально видимой после всех нагрузок / хранилищ данных, которые она защищает. (StoreStore + LoadStore)
• Другой stream получает блокировку (чтение или RMW с хранилищем-релизом) и должен делать все нагрузки / хранилища в общую структуру данных после того, как приобретаемое становится глобально видимым. (LoadLoad + LoadStore)

Обратите внимание, что std: atomic использует эти имена даже для автономных ограждений, которые немного отличаются от операций загрузки или хранения. (См. Atom_thread_fence, ниже).

Освобождение / приобретение семантики сильнее, чем требует производитель-потребитель. Для этого требуется одноразовый StoreStore (производитель) и однонаправленный LoadLoad (потребитель) без заказа LoadStore.

Общая hash-таблица, защищенная блокировкой чтения / записи (например), требует операции атомарного считывания-записи-записи-освобождения-хранения-освобождения-хранилища для получения блокировки. x86 lock xadd является полным барьером (включая StoreLoad), но ARM64 имеет версию load-getting / store-release с привязкой к загрузке / хранилище для выполнения атомарного чтения-модификации-записи. Насколько я понимаю, это позволяет избежать барьера StoreLoad даже для блокировки.

---

Использование более слабого, но все еще достаточного порядка

Записывает в std::atomic типы упорядочиваются по отношению к любому другому доступу к памяти в исходном коде (как загрузких, так и хранилищах) по умолчанию. Вы можете контролировать, какой порядок наложен на std::memory_order .

В вашем случае вам нужен только ваш продюсер, чтобы убедиться, что магазины становятся глобально видимыми в правильном порядке, т.е. бар StoreStore перед магазином. store(memory_order_release) включает это и многое другое. std::atomic_thread_fence(memory_order_release) – это всего лишь односторонний бар StoreStore для всех магазинов. x86 делает StoreStore бесплатно, поэтому все, что нужно сделать компилятору, это поместить магазины в исходный порядок.

Выпуск вместо seq_cst будет большим выигрышем в производительности, особенно. на таких архитектурах, как x86, где выпуск дешевый / бесплатный. Это еще более справедливо, если распространенный случай без конкуренции.

Чтение атомных переменных также накладывает полную последовательную согласованность нагрузки по отношению ко всем другим нагрузкам и магазинам. На x86 это бесплатно. Потенциалы LoadLoad и LoadStore не являются операционными и неявными в каждой памяти op. Вы можете сделать свой код более эффективным для слабо упорядоченных ISA, используя a.load(std::memory_order_acquire) .

Обратите внимание, что std :: atomic автономные функции забора путают повторное использование имен «приобретать» и «выпускать» для ограждений StoreStore и LoadLoad, которые заказывают все магазины (или все грузы) по крайней мере в нужном направлении . На практике они обычно выдают HW-инструкции, которые являются барьерами StoreStore или LoadLoad с двух сторон. Этот документ является предложением о том, что стало настоящим стандартом. Вы можете видеть, как memory_order_release сопоставляется с #LoadStore | #StoreStore #LoadStore | #StoreStore на SPARC RMO, который, я полагаю, был включен частично из-за того, что он имеет все типы барьеров отдельно. (hmm, веб-страница cppref упоминает только магазины заказов, а не компонент LoadStore. Однако это не стандарт C ++, поэтому, возможно, полный стандарт говорит больше.)

---

memory_order_consume недостаточно силен для этого прецедента. В этом сообщении рассказывается о вашем случае использования флага, чтобы указать, что другие данные готовы, и говорит о memory_order_consume .

consume было бы достаточно, если бы ваш флаг был указателем на b или даже указателем на структуру или массив. Тем не менее, ни один компилятор не знает, как выполнять отслеживание зависимостей, чтобы убедиться, что он помещает вещь в правильном порядке в asm, поэтому текущие реализации всегда обрабатывают consume как acquire . Это слишком плохо, потому что каждая архитектура, кроме DEC alpha (и программной модели C ++ 11), предоставляет этот заказ бесплатно. По словам Линуса Торвальдса, только несколько аппаратных реализаций Alpha действительно могут иметь такое переупорядочение, поэтому дорогостоящие барьерные инструкции, необходимые повсюду, были чистым недостатком для большинства Alphas.

Производителю еще нужно использовать семантику release (бар StoreStore), чтобы убедиться, что новая полезная нагрузка видна при обновлении указателя.

Неплохая идея написать код, используя consume , если вы уверены, что понимаете последствия и не зависите от того, что consume , не гарантирует. В будущем, когда компиляторы умнее, ваш код будет компилироваться без барьерных инструкций даже на ARM / PPC. Фактическое перемещение данных должно происходить между кешами на разных процессорах, но на слабых моделях модели памяти вы можете избежать ожиданий видимости любых несвязанных записей (например, буферов с нуля в производителю).

Просто имейте в виду, что вы действительно не можете проверить код memory_order_consume экспериментально , потому что текущие компиляторы дают вам более сильный порядок, чем запросы кода.

В любом случае, действительно сложно проверить любой из этих экспериментов, потому что он чувствителен к времени. Кроме того, если компилятор не переупорядочивает операции (потому что вам не удалось сказать это не так), streamи производителей-потребителей никогда не будут иметь проблемы на x86. Вам нужно будет протестировать на ARM или PowerPC или что-то еще, чтобы попытаться найти проблемы с упорядочением на практике.

---

Рекомендации:

• https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67458 : Я сообщил об ошибке gcc, которую я нашел с b=2; a.store(1, MO_release); b=3; b=2; a.store(1, MO_release); b=3; производя a=1;b=3 на x86, а не b=3; a=1; b=3; a=1;

• https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67461 : Я также сообщил о том, что ARM gcc использует два dmb sy в строке для a=1; a=1; a=1; a=1; , и x86 gcc, возможно, может работать с меньшим количеством операций mfence. Я не уверен, что требуется mfence между каждым хранилищем, чтобы защитить обработчик сигналов от ошибочных предположений или если это просто недостающая оптимизация.

• objective memory_order_consume в C ++ 11 (уже связанная выше) охватывает именно этот случай использования флага для передачи неатомной полезной нагрузки между streamами.

• Какие барьеры StoreLoad (x86 mfence) предназначены для: рабочей примерной программы, которая демонстрирует необходимость: http://preshing.com/20120515/memory-reordering-caught-in-the-act/

• Барьеры, связанные с зависимостью данных (только Alpha нуждается в явных барьерах этого типа, но C ++ потенциально нуждается в них, чтобы компилятор не выполнял спекулятивные нагрузки): http://www.mjmwired.net/kernel/Documentation/memory-barriers.txt#360

• Контрольные барьеры зависимости: http://www.mjmwired.net/kernel/Documentation/memory-barriers.txt#592

• Дуг Ли говорит, что для x86 требуется только LFENCE для данных, которые были написаны с «streamовой» movntdqa например movntdqa или movnti . (NT = невременное). Помимо обхода кеша, x86 NT загружает / сохраняет слабо упорядоченную семантику.

• http://preshing.com/20120913/acquire-and-release-semantics/

• http://preshing.com/20120612/an-introduction-to-lock-free-programming/ (указывает на книги и другие материалы, которые он рекомендует).

• Интересная тема на realworldtech о том, лучше ли существуют барьеры во всем мире или сильные модели памяти, в том числе и то, что зависимость данных почти свободна от HW, поэтому глупо пропустить ее и поставить большую нагрузку на программное обеспечение. (Вещь Alpha (и C ++) не имеет, но все остальное делает). Верните несколько сообщений из этого, чтобы увидеть забавные оскорбления Линуса Торвальдса, прежде чем он перешел к объяснению более подробных / технических причин его аргументов.