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

Ответ 1

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

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

Самый простой вопрос:

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

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

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

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

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

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

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

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

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

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

Почему MFENCE происходит после записи в 'a not before.

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

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

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

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

ARM32 asm для 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], но в загрузках и магазинах всегда есть операнд регистров, а операнд памяти - второй. Это действительно странно, если вы привыкли к x86, где операнд памяти может быть источником или dest для большинства не-векторных инструкций. Загрузка мгновенных констант также требует много инструкций, поскольку фиксированная длина инструкции оставляет место для 16b полезной нагрузки для movw (перемещение слова)/movt (перемещение вверх).

Отпустить/получить

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

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

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

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

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

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

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

В вашем случае вам нужен только ваш продюсер, чтобы убедиться, что магазины становятся глобально видимыми в правильном порядке, т.е. бар StoreStore перед хранилищем до a. 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 standalone fence путают повторное использование имен "приобретать" и "выпускать" для забора StoreStore и LoadLoad, которые заказывают все магазины ( или все нагрузки) по крайней мере в желаемом направлении. На практике они обычно выдают HW-инструкции, которые являются барьерами StoreStore или LoadLoad с двух сторон. Этот документ является предложением о том, что стало настоящим стандартом. Вы можете видеть, как memory_order_release сопоставляется с #LoadStore | #StoreStore на SPARC RMO, который, как я полагаю, был включен частично из-за того, что он имеет все типы барьеров отдельно. (hmm, веб-страница cppref упоминает только магазины заказов, а не компонент LoadStore. Это не стандарт С++, хотя, возможно, полный стандарт говорит больше.)

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

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

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

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

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

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

ссылки:

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

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

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

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

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

• Ограничения зависимости: http://www.mjmwired.net/kernel/Documentation/memory-barriers.txt#592

• Doug Lea говорит, что для x86 требуется только LFENCE для данных, которые были написаны с потоковой записью вроде 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 (и С++) не имеет, но все остальное делает). Верните несколько сообщений из этого, чтобы увидеть забавные оскорбления Линуса Торвальдса, прежде чем он перешел к объяснению более подробных/технических причин его аргументов.