Почему компиляторы не объединяют избыточные записи std::atomic?
Мне интересно, почему ни один компилятор не готов объединить последовательные записи одного и того же значения в одну атомарную переменную, например:
#include <atomic>
std::atomic<int> y(0);
void f() {
auto order = std::memory_order_relaxed;
y.store(1, order);
y.store(1, order);
y.store(1, order);
}
Каждый компилятор, который я пробовал, выдаст вышеописанную запись три раза. Какой законный наблюдатель, не участвующий в гонке, может увидеть разницу между приведенным выше кодом и оптимизированной версией с помощью одной записи (т.е. не применяется правило "как если")?
Если переменная была изменчивой, то, очевидно, оптимизация не применима. Что мешает этому в моем случае?
Вот код в проводнике компилятора.
9 ответов
Написанные стандарты C++11 / C++14 позволяют объединять / объединять три хранилища в одно хранилище конечного значения. Даже в таком случае:
y.store(1, order);
y.store(2, order);
y.store(3, order); // inlining + constant-folding could produce this in real code
Стандарт не гарантирует, что наблюдатель вращается на y (с атомной нагрузкой или CAS) когда-нибудь увидят y == 2, У программы, которая зависела от этого, была бы ошибка гонок данных, но только гонка садовых разновидностей, а не гонка данных C++ Undefined Behavior. (Это UB только с неатомарными переменными). Программа, которая ожидает его иногда увидеть, не обязательно даже глючит. (См. Ниже re: индикаторы выполнения.)
Любой порядок, который возможен на абстрактной машине C++, может быть выбран (во время компиляции) как порядок, который всегда будет происходить. Это как будто правило в действии. В этом случае создается впечатление, что все три хранилища происходили последовательно в глобальном порядке, без каких-либо загрузок или хранилищ из других потоков, происходящих между y=1 а также y=3,
Это не зависит от целевой архитектуры или оборудования; точно так же, как во время компиляции переупорядочение расслабленных атомарных операций допускается даже при нацеливании на строго упорядоченный x86. Компилятору не нужно сохранять то, что вы можете ожидать от размышлений об оборудовании, для которого вы собираете, поэтому вам нужны барьеры. Барьеры могут компилироваться в инструкции без нуля.
Так почему же компиляторы не делают эту оптимизацию?
Это проблема качества реализации, и она может изменить наблюдаемую производительность / поведение на реальном оборудовании.
Наиболее очевидный случай, когда это проблема, - индикатор выполнения. Вытягивание хранилищ из цикла (который не содержит других атомарных операций) и объединение их всех в одно приведет к тому, что индикатор выполнения останется равным 0, а затем достигнет 100% в конце.
Там нет C++ 11 std::atomic способ помешать им делать это в тех случаях, когда вы этого не хотите, поэтому на данный момент компиляторы просто выбирают никогда не объединять несколько атомарных операций в одну. (Объединение их всех в одну операцию не меняет их порядок относительно друг друга.)
Авторы компиляторов правильно заметили, что программисты ожидают, что атомное хранилище будет происходить с памятью каждый раз, когда источник делает y.store(), (См. Большинство других ответов на этот вопрос, в которых утверждается, что магазины должны происходить отдельно, потому что возможные читатели ожидают увидеть промежуточное значение.) Т.е. это нарушает принцип наименьшего удивления.
Однако есть случаи, когда это было бы очень полезно, например, избегать бесполезного shared_ptr ref count inc / dec в цикле.
Очевидно, что любое изменение порядка или объединение не может нарушать любые другие правила заказа. Например, num++; num--; все равно должен быть полный барьер для времени выполнения и переупорядочения во время компиляции, даже если он больше не касается памяти в num,
В настоящее время обсуждается вопрос о продлении std::atomic API, чтобы дать программистам контроль над такими оптимизациями, после чего компиляторы смогут оптимизировать, когда это полезно, что может случиться даже в тщательно написанном коде, который не является преднамеренно неэффективным. Некоторые примеры полезных случаев для оптимизации упомянуты в следующих ссылках обсуждения / предложения рабочей группы:
- http://wg21.link/n4455: N4455 Никакой здравомыслящий компилятор не будет оптимизировать Atomics
- http://wg21.link/p0062: WG21 / P0062R1: Когда компиляторы должны оптимизировать атомарность?
См. Также обсуждение этой же темы в ответе Ричарда Ходжеса " Может ли num++ быть атомарным для" int num "? (см. комментарии). Смотрите также последний раздел моего ответа на тот же вопрос, где я более подробно утверждаю, что эта оптимизация разрешена. (Оставим это коротким здесь, потому что эти ссылки рабочей группы C++ уже признают, что текущий стандарт, как написано, действительно позволяет это, и что текущие компиляторы просто не оптимизируются специально.)
В рамках действующего стандарта, volatile atomic<int> y было бы одним из способов гарантировать, что магазины к нему не могут быть оптимизированы. (Как указывает Херб Саттер в SO ответе, volatile а также atomic уже разделяют некоторые требования, но они разные). Смотрите также std::memory_order отношения с volatile по ссылке.
Доступ к volatile объекты не могут быть оптимизированы (потому что они могут быть, например, отображаемыми в регистры ввода-вывода).
Не меняй все свои atomic переменные к volatile atomic еще; комитет по стандартам может выбрать что-то еще (так как volatile atomic уродливо, и злоупотребляет значением volatile). Я думаю, мы можем быть уверены, что компиляторы не начнут выполнять эту оптимизацию, пока не найдется способ ее контролировать. Надеюсь, это будет некое согласие (например, memory_order_release_coalesce) это не меняет поведение существующего кода C++11/14 при компиляции в C++. Но это может быть похоже на предложение в wg21/p0062, чтобы пометить случаи неоптимизации с помощью [[brittle_atomic]],
wg21 / p0062 предупреждает, что даже volatile atomic не решает все, и препятствует его использованию для этой цели. Это дает этот пример:
if(x) {
foo();
y.store(0);
} else {
bar();
y.store(0); // release a lock before a long-running loop
for() {...} // loop contains no atomics or volatiles
}
// A compiler can merge the stores into a y.store(0) here.
Даже с volatile atomic<int> y компилятору разрешено потопить y.store() вне if/else и просто сделайте это один раз, потому что он все еще делает ровно 1 магазин с тем же значением. (Что будет после длинного цикла в ветви else).
volatile останавливает объединение, обсуждаемое в вопросе, но это указывает на то, что другие оптимизации на atomic<> также может быть проблематичным для реальной производительности.
Другие причины неоптимизации включают в себя: никто не написал сложный код, который позволил бы компилятору безопасно выполнять эти оптимизации (никогда не ошибаясь). Этого недостаточно, потому что N4455 говорит, что LLVM уже реализует или может легко реализовать некоторые из упомянутых оптимизаций.
Впрочем, причина заблуждения для программистов вполне вероятна. Код без блокировки достаточно сложен, чтобы правильно писать в первую очередь.
Не будьте внимательны при использовании атомного оружия: оно не дешевое и не оптимизирует много (в настоящее время совсем нет). Не всегда легко легко избежать избыточных атомарных операций с std::shared_ptr<T> тем не менее, поскольку нет неатомарной версии этого (хотя один из ответов здесь дает простой способ определить shared_ptr_unsynchronized<T> для gcc).
Вы имеете в виду устранение мертвых магазинов.
Не запрещается уничтожать атомный мертвый склад, но труднее доказать, что атомный склад квалифицируется как таковой.
Традиционные оптимизации компилятора, такие как устранение мертвого хранилища, могут выполняться на элементарных операциях, даже последовательно согласованных.
Оптимизаторы должны быть осторожны, чтобы не делать этого в точках синхронизации, потому что другой поток выполнения может наблюдать или изменять память, что означает, что традиционные оптимизации должны учитывать больше промежуточных инструкций, чем обычно при рассмотрении оптимизаций для атомарных операций.
В случае удаления мертвого хранилища недостаточно доказать, что атомарный магазин пост-доминирует и создает псевдоним другого для устранения другого хранилища.от N4455 нет нормального компилятора, который бы оптимизировал Atomics
Проблема атомарного DSE, в общем случае, заключается в том, что он включает в себя поиск точек синхронизации, в моем понимании этот термин означает точки в коде, где есть связь между инструкцией в потоке A и инструкцией в другом потоке B.,
Рассмотрим этот код, выполняемый потоком A:
y.store(1, std::memory_order_seq_cst);
y.store(2, std::memory_order_seq_cst);
y.store(3, std::memory_order_seq_cst);
Можно ли это оптимизировать как y.store(3, std::memory_order_seq_cst)?
Если поток B ждет, чтобы увидеть y = 2 (например, с CAS), он никогда не будет наблюдать это, если код будет оптимизирован.
Тем не менее, в моем понимании, имея цикл B и CASsing на y = 2 является гонкой данных, поскольку между инструкциями двух потоков нет полного порядка.
Выполнение, при котором инструкции A выполняются до того, как цикл B становится видимым (то есть разрешенным), и, таким образом, компилятор может оптимизировать y.store(3, std::memory_order_seq_cst),
Если потоки A и B синхронизируются каким-либо образом между хранилищами в потоке A, тогда оптимизация не будет разрешена (будет вызван частичный порядок, что может привести к потенциальному наблюдению B). y = 2).
Доказать, что такой синхронизации не существует, сложно, так как для этого требуется рассмотреть более широкую область и учесть все особенности архитектуры.
Насколько я понимаю, из-за относительно небольшого возраста атомарных операций и сложности рассуждений об упорядочении памяти, видимости и синхронизации, компиляторы не выполняют всех возможных оптимизаций по атомарности, пока не появится более надежная структура для обнаружения и понимания необходимых условия построены.
Я полагаю, что ваш пример - это упрощение подсчитываемого потока, приведенного выше, так как у него нет другого потока или точки синхронизации, поскольку, как я вижу, компилятор мог оптимизировать три хранилища.
Пока вы меняете значение атома в одном потоке, другой поток может проверять его и выполнять операцию на основе значения атома. Приведенный вами пример настолько специфичен, что разработчики компиляторов не видят в нем смысла оптимизировать. Однако, если один поток устанавливает, например, последовательные значения для атомарного: 0, 1, 2и т. д., другой поток может помещать что-то в слоты, указанные значением атома.
Короче говоря, потому что стандарт (например, парагарафы вокруг и ниже 20 в [intro.multithread]) запрещает это.
Существуют гарантии "до того", которые должны быть выполнены и которые, помимо прочего, исключают переупорядочение или объединение записей (пункт 19 даже прямо говорит о переупорядочении).
Если ваш поток записывает три значения в память (скажем, 1, 2 и 3) одно за другим, другой поток может прочитать значение. Если, например, ваш поток прерывается (или даже если он работает одновременно), и другой поток также записывает данные в это местоположение, тогда наблюдающий поток должен видеть операции в том же порядке, в каком они происходят (либо по расписанию, либо по совпадению, либо по любой причине). Это гарантия.
Как это возможно, если вы делаете только половину записи (или даже только одну)? Это не так.
Что, если ваш поток вместо этого записывает 1 -1 -1, а другой случайным образом записывает 2 или 3? Что, если третий поток наблюдает за местоположением и ожидает определенного значения, которое просто не появляется, потому что оно оптимизировано?
Невозможно предоставить гарантии, которые предоставляются, если магазины (и грузы тоже) не выполняются в соответствии с требованиями. Все они и в том же порядке.
NB: Я собирался это прокомментировать, но это слишком многословно.
Один интересный факт заключается в том, что это поведение не в терминах C++ - гонка данных.
Интересна заметка 21 на стр.14: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3690.pdf (мой акцент):
Выполнение программы содержит гонку данных, если она содержит два конфликтующих действия в разных потоках, по крайней мере одно из которых не является атомарным
Также на с.11 примечание 5:
"Расслабленные" атомарные операции не являются операциями синхронизации, хотя, подобно операциям синхронизации, они не могут способствовать гонкам данных.
Таким образом, конфликтующие действия на атомарном уровне никогда не являются гонкой данных - с точки зрения стандарта C++.
Все эти операции являются атомарными (и особенно расслабленными), но здесь нет гонок за данными!
Я согласен, что нет никакой надежной / предсказуемой разницы между этими двумя на любой (разумной) платформе:
include <atomic>
std::atomic<int> y(0);
void f() {
auto order = std::memory_order_relaxed;
y.store(1, order);
y.store(1, order);
y.store(1, order);
}
а также
include <atomic>
std::atomic<int> y(0);
void f() {
auto order = std::memory_order_relaxed;
y.store(1, order);
}
Но в рамках определения модели памяти C++ это не гонка данных.
Я не могу легко понять, почему это определение предоставлено, но оно дает разработчику несколько карт для случайной связи между потоками, которые, как они могут знать (на их платформе), будут статистически работать.
Например, если установить значение 3 раза, а затем прочитать его, будет показана некоторая степень конкуренции за это местоположение. Такие подходы не являются детерминированными, но многие эффективные параллельные алгоритмы не являются детерминированными. Например, тайм-аут try_lock_until() это всегда условие гонки, но остается полезной техникой.
То, что кажется стандартом C++, дает вам уверенность в отношении "гонок данных", но разрешает некоторые забавные игры с условиями гонки, которые в конечном счете представляют собой разные вещи.
Короче говоря, в стандарте указывается, что в тех случаях, когда другие потоки могут видеть эффект "забивания" значения, установленного 3 раза, другие потоки должны иметь возможность видеть этот эффект (даже если иногда это не так!). Это тот случай, когда почти все современные платформы, которые другие потоки могут при некоторых обстоятельствах увидеть, как это происходит.
Практический вариант использования шаблона, если поток делает что-то важное между обновлениями, которое не зависит от или не изменяет y, может быть: * Поток 2 читает значение y чтобы проверить, насколько прогресс проделан Темой 1.
Таким образом, возможно, поток 1 должен загрузить файл конфигурации как шаг 1, поместить его проанализированное содержимое в структуру данных как шаг 2 и отобразить главное окно как шаг 3, в то время как поток 2 ожидает завершения шага 2, чтобы он мог выполнить другую задачу параллельно, которая зависит от структуры данных. (Конечно, этот пример требует семантики получения / выпуска, а не упрощенного порядка.)
Я уверен, что соответствующая реализация позволяет потоку 1 не обновлять y на любом промежуточном этапе - хотя я не изучал языковой стандарт, я был бы шокирован, если бы он не поддерживал оборудование, на котором опрашивается другой поток y может никогда не увидеть значение 2.
Тем не менее, это гипотетический случай, когда можно было бы оптимизировать обновления статуса. Может быть, разработчик компилятора придет сюда и скажет, почему этот компилятор решил не делать этого, но одна из возможных причин - позволить вам выстрелить себе в ногу или, по крайней мере, поразить себя пальцем ноги.
Давайте пройдемся немного дальше от патологического случая, когда три магазина находятся рядом друг с другом. Давайте предположим, что между магазинами делается какая-то нетривиальная работа, и что такая работа не предполагает y вообще (так что анализ путей данных может определить, что три хранилища фактически избыточны, по крайней мере, в этом потоке), и сам по себе не создает никаких барьеров памяти (так что что-то еще не заставляет хранилища быть видимыми для других потоки). Теперь вполне возможно, что другие потоки имеют возможность выполнять работу между магазинами, и, возможно, эти другие потоки манипулируют y и что у этого потока есть какая-то причина, чтобы сбросить его на 1 (2-е хранилище). Если бы первые два магазина были отброшены, это изменило бы поведение.
Автор компилятора не может просто выполнить оптимизацию. Они также должны убедить себя в том, что оптимизация действительна в ситуациях, когда разработчик компиляции намеревается применить ее, что она не будет применяться в ситуациях, когда она недопустима, что она не нарушает код, который фактически нарушен, но " работает "на других реализациях. Это, вероятно, больше работы, чем сама оптимизация.
С другой стороны, я мог бы представить, что на практике (то есть в программах, которые должны выполнять работу, а не в тестах), эта оптимизация очень мало сэкономит во времени выполнения.
Таким образом, автор компилятора посмотрит на стоимость, затем посмотрит на выгоду и риски, и, вероятно, примет решение против этого.
Поскольку ожидается, что переменные, содержащиеся в объекте std::atomic, будут доступны из нескольких потоков, следует ожидать, что они ведут себя как минимум, как если бы они были объявлены с ключевым словом volatile.
Это была стандартная и рекомендуемая практика до того, как в процессорных архитектурах появились строки кэша и т. Д.
[EDIT2] Можно утверждать, что std::atomic<> являются volatile переменные многоядерного возраста. Как определено в C/C++, volatile достаточно только для синхронизации атомарных чтений из одного потока с ISR, модифицирующей переменную (которая в этом случае фактически является атомарной записью, как видно из основного потока).
Я лично рад, что ни один компилятор не оптимизировал бы записи в атомарную переменную. Если запись оптимизирована, как вы можете гарантировать, что каждая из этих записей потенциально будет видна читателям в других потоках? Не забывайте, что это также часть контракта std::atomic<>.
Рассмотрим этот фрагмент кода, где компилятор сильно повлияет на результат.
#include <atomic>
#include <thread>
static const int N{ 1000000 };
std::atomic<int> flag{1};
std::atomic<bool> do_run { true };
void write_1()
{
while (do_run.load())
{
flag = 1; flag = 1; flag = 1; flag = 1;
flag = 1; flag = 1; flag = 1; flag = 1;
flag = 1; flag = 1; flag = 1; flag = 1;
flag = 1; flag = 1; flag = 1; flag = 1;
}
}
void write_0()
{
while (do_run.load())
{
flag = -1; flag = -1; flag = -1; flag = -1;
}
}
int main(int argc, char** argv)
{
int counter{};
std::thread t0(&write_0);
std::thread t1(&write_1);
for (int i = 0; i < N; ++i)
{
counter += flag;
std::this_thread::yield();
}
do_run = false;
t0.join();
t1.join();
return counter;
}
[EDIT] Сначала я не продвигался, что volatile был центральным в реализации атомики, но...
Так как, казалось, были сомнения относительно того, volatile имел какое-то отношение к атомам, я исследовал этот вопрос. Вот атомная реализация от VS2017 stl. Как я и предполагал, ключевое слово volatile есть везде.
// from file atomic, line 264...
// TEMPLATE CLASS _Atomic_impl
template<unsigned _Bytes>
struct _Atomic_impl
{ // struct for managing locks around operations on atomic types
typedef _Uint1_t _My_int; // "1 byte" means "no alignment required"
constexpr _Atomic_impl() _NOEXCEPT
: _My_flag(0)
{ // default constructor
}
bool _Is_lock_free() const volatile
{ // operations that use locks are not lock-free
return (false);
}
void _Store(void *_Tgt, const void *_Src, memory_order _Order) volatile
{ // lock and store
_Atomic_copy(&_My_flag, _Bytes, _Tgt, _Src, _Order);
}
void _Load(void *_Tgt, const void *_Src,
memory_order _Order) const volatile
{ // lock and load
_Atomic_copy(&_My_flag, _Bytes, _Tgt, _Src, _Order);
}
void _Exchange(void *_Left, void *_Right, memory_order _Order) volatile
{ // lock and exchange
_Atomic_exchange(&_My_flag, _Bytes, _Left, _Right, _Order);
}
bool _Compare_exchange_weak(
void *_Tgt, void *_Exp, const void *_Value,
memory_order _Order1, memory_order _Order2) volatile
{ // lock and compare/exchange
return (_Atomic_compare_exchange_weak(
&_My_flag, _Bytes, _Tgt, _Exp, _Value, _Order1, _Order2));
}
bool _Compare_exchange_strong(
void *_Tgt, void *_Exp, const void *_Value,
memory_order _Order1, memory_order _Order2) volatile
{ // lock and compare/exchange
return (_Atomic_compare_exchange_strong(
&_My_flag, _Bytes, _Tgt, _Exp, _Value, _Order1, _Order2));
}
private:
mutable _Atomic_flag_t _My_flag;
};
Все специализации в MS stl используют volatile для ключевых функций.
Вот объявление одной из таких ключевых функций:
inline int _Atomic_compare_exchange_strong_8(volatile _Uint8_t *_Tgt, _Uint8_t *_Exp, _Uint8_t _Value, memory_order _Order1, memory_order _Order2)
Вы заметите необходимые volatile uint8_t* содержит значение, содержащееся в std::atomic. Этот шаблон можно наблюдать во всей реализации MS std::atomic<>. У команды gcc и любого другого поставщика stl нет причин делать это иначе.