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

Question

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

GCC компилирует это:

#include <atomic>
std::atomic<int> a; 
int b(0);

void func()
{
  b = 2; 
  a = 1;
}

к этому:

func():
    mov DWORD PTR b[rip], 2
    mov DWORD PTR a[rip], 1
    mfence
    ret

Итак, чтобы уточнить вещи для меня:

Любой другой поток, читающий 'a' как 1, гарантированно читает 'b' как 2.
Почему MFENCE происходит после записи в "а", а не раньше.
Гарантируется ли запись в 'a' атомарной (в узком смысле, не в языке C++) операции, и применима ли она ко всем процессорам Intel? Я предполагаю, что из этого выходного кода.

Также clang (v3.5.1 -O3) делает это:

mov dword ptr [rip + b], 2
mov eax, 1
xchg    dword ptr [rip + a], eax
ret

Что кажется более простым для моего маленького ума, но почему другой подход, в чем преимущество каждого?

12

c++ assembly x86 compiler-construction

Источник

user3818191 03 сен '15 в 20:30

1 ответ

Решение

Другие вопросы по тегам c++ assembly x86 compiler-construction

user224132 04 сен '15 в 09:20 2015-09-04 09:20 · Accepted Answer · 2015-09-04 09:20

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

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

Сначала простой вопрос:

Гарантируется, что запись в 'a' будет атомарной?

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

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

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

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

Любой другой поток, читающий 'a' как 1, гарантированно читает 'b' как 2.

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

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

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

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

Почему MFENCE происходит после записи в "а", а не раньше.

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

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

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

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

Выпуск / Приобретение

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

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

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

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

Совместно используемая хэш-таблица, защищенная блокировкой чтения / записи (например), требует для получения блокировки атомарной операции чтения-изменения-записи-записи-загрузки / выпуска-хранения. x86 lock xadd является полным барьером (включая StoreLoad), но ARM64 имеет версию load-receive /store-release версии load-connected /store-conditional для выполнения атомарных операций чтения-изменения-записи. Насколько я понимаю, это устраняет необходимость в барьере 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 не являются операциями и неявны в каждой операции памяти. Вы можете сделать свой код более эффективным на слабо упорядоченных ISA, используя a.load(std::memory_order_acquire),

Обратите внимание, что функции автономного ограждения std::atomic сбивают с толку повторное использование имен "acqu" и "release" для ограждений StoreStore и LoadLoad, которые упорядочивают все хранилища (или все загрузки) по крайней мере в желаемом направлении. На практике они обычно испускают инструкции HW, которые являются двусторонними барьерами StoreStore или LoadLoad. Этот документ является предложением о том, что стало текущим стандартом. Вы можете увидеть, как memory_order_release отображается на #LoadStore | #StoreStore на SPARC RMO, который, как я предполагаю, был включен частично, потому что он имеет все типы барьеров отдельно. (Хм, на веб-странице 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 кодируйте экспериментально, потому что современные компиляторы дают вам более сильный порядок, чем запросы кода.

В любом случае, действительно сложно проверить что-либо из этого экспериментально, потому что это чувствительно ко времени. Кроме того, если компилятор не переупорядочивает операции (потому что вы не указали этого не делать), потоки производителя-потребителя никогда не будут иметь проблем с 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 в C++11 (уже связанное выше) охватывает именно этот случай использования флага для передачи неатомарной полезной нагрузки между потоками.
Для чего предназначены барьеры StoreLoad (x86 mfence): рабочий пример программы, демонстрирующий необходимость: http://preshing.com/20120515/memory-reordering-caught-in-the-act/
Барьеры зависимости от данных (только Alpha нуждается в явных барьерах этого типа, но C++ потенциально нуждается в них для предотвращения спекулятивных нагрузок компилятора): http://www.mjmwired.net/kernel/Documentation/memory-barriers.txt
Барьеры зависимости от контроля: http://www.mjmwired.net/kernel/Documentation/memory-barriers.txt
Даг Ли говорит, что 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 (и C++) этого нет, но все остальное есть). Вернитесь на несколько постов, чтобы увидеть забавные оскорбления Линуса Торвальдса, прежде чем он объяснит более подробные / технические причины своих аргументов.