Почему компиляторы не объединяют избыточные std:: atomic write?

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

#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);
}

Каждый компилятор, который я пробовал, выдает вышеприведенную запись три раза. Какой законный, независимый от гонки наблюдатель мог видеть разницу между приведенным выше кодом и оптимизированной версией с одной записью (т.е. Не применяется правило "как-если" )?

Если переменная была изменчивой, то, очевидно, оптимизация не применима. Что мешает этому в моем случае?

Вот код в проводник компилятора.

Ответ 1

Написанные стандарты 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 inc/dec в цикле.

Очевидно, что любое изменение порядка или объединение не может нарушать любые другие правила заказа. Например, num++; num--; num++; num--; все равно должен быть полный барьер для времени выполнения и переупорядочения во время компиляции, даже если он больше не затрагивает память при num.

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

http://wg21.link/n4455: N4455 Никакой здравомыслящий компилятор не будет оптимизировать Atomics
http://wg21.link/p0062: WG21/P0062R1: Когда компиляторы должны оптимизировать атомарность?

См. Также обсуждение этой же темы в ответе Ричарда Ходжеса на Can num++ быть атомарным для "int num"? (см. комментарии). Смотрите также последний раздел моего ответа на тот же вопрос, где я более подробно утверждаю, что эта оптимизация разрешена. (Оставим это коротким здесь, потому что эти ссылки рабочей группы C++ уже признают, что текущий стандарт, как написано, позволяет это, и что текущие компиляторы просто не оптимизируют специально.)

В текущем стандарте volatile atomic<int> y будет одним из способов гарантировать, что хранилища для него не будут оптимизированы. (Как указывает Херб Саттер в SO-ответе, volatile и atomic уже разделяют некоторые требования, но они разные). Смотрите также связь std::memory_order с volatile по cppreference.

Доступ к volatile объектам не может быть оптимизирован (например, это могут быть регистры ввода-вывода с отображением в памяти).

Использование volatile atomic<T> основном решает проблему с индикатором выполнения, но это отчасти уродливо и может выглядеть глупо через несколько лет, если/когда C++ решит использовать другой синтаксис для управления оптимизацией, чтобы компиляторы могли начать делать это на практике.

Я думаю, мы можем быть уверены, что компиляторы не начнут выполнять эту оптимизацию, пока не найдется способ ее контролировать. Надеемся, что это будет своего рода memory_order_release_coalesce (например, 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). Особенно, если магазин только relaxed или release вместо seq_cst.

volatile останавливает объединение, обсуждаемое в этом вопросе, но это указывает на то, что другие оптимизации atomic<> также могут создавать проблемы для реальной производительности.

Другие причины неоптимизации включают: никто не написал сложный код, который позволил бы компилятору безопасно выполнять эти оптимизации (даже не ошибаясь). Этого недостаточно, потому что N4455 говорит, что LLVM уже реализует или может легко реализовать некоторые из упомянутых оптимизаций.

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

Не будьте внимательны при использовании атомного оружия: оно не дешевое и не оптимизирует много (в настоящее время совсем нет). Однако не всегда легко легко избежать избыточных атомарных операций с std::shared_ptr<T>, поскольку не существует неатомарной версии (хотя один из ответов здесь дает простой способ определить shared_ptr_unsynchronized<T> для gcc).

Ответ 2

Вы имеете в виду уничтожение мертвых магазинов.

Не исключено уничтожение атомного мертвого хранилища, но сложнее доказать, что атомный магазин квалифицируется как таковой.

Традиционные оптимизации компилятора, такие как уничтожение мертвого хранилища, могут выполняться на атомных операциях, даже последовательно согласованных.
Оптимизаторы должны быть осторожны, чтобы не делать этого в точках синхронизации, потому что другой поток выполнения может наблюдать или изменять память, а это означает, что традиционная оптимизация должна учитывать более сложные команды, чем обычно при рассмотрении оптимизации для атомных операций. В случае уничтожения мертвого магазина недостаточно доказать, что атомный магазин после доминирования и псевдонимов другой, чтобы исключить другой магазин.

^{from N4455 No Sane Compiler оптимизирует 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).

Доказательство того, что такой синхронизации не существует, связано с рассмотрением более широкой области и с учетом всех особенностей архитектуры.

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

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

Ответ 3

Пока вы изменяете значение атома в одном потоке, некоторые другие потоки могут проверять его и выполнять операцию, основанную на значении атома. Пример, который вы дали, настолько специфичен, что разработчики компилятора не считают его оптимальным. Однако, если один поток задает, например. последовательные значения для атома: 0, 1, 2 и т.д., другой поток может помещать что-то в слоты, обозначенные значением атома.

Ответ 4

Короче, потому что стандарт (например, парагарафы вокруг и ниже 20 в [intro.multithread]) запрещает это.

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

Если ваш поток записывает три значения в память (скажем, 1, 2 и 3) один за другим, другой поток может считывать значение. Если, например, ваш поток прерывается (или даже если он выполняется одновременно), и другой поток также записывает в это место, то наблюдательный поток должен видеть операции в точно таком же порядке, как они происходят (либо путем планирования, либо совпадения, либо по какой-либо причине). Это гарантия.

Как это возможно, если вы делаете только половину записи (или даже только одну)? Это не так.

Что делать, если ваш поток вместо этого выписывает 1 -1 -1, а другой один спорадически выписывает 2 или 3? Что делать, если третий поток наблюдает за местоположением и ждет определенного значения, которое просто не появляется, потому что оно оптимизировано?

Невозможно предоставить гарантии, которые предоставляются, если магазины (и нагрузки тоже) не выполняются по запросу. Все они и в том же порядке.

Ответ 5

NB: Я собирался прокомментировать это, но это немного слишком многословно.

Интересным фактом является то, что это поведение не в терминах расы данных С++.

Замечание 21 на стр. 14 интересно: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3690.pdf (мой акцент):

Выполнение программы содержит гонку данных, если она содержит два конфликтующие действия в разных потоках, по крайней мере , один из которых не атомный

Также на стр. 11 примечание 5:

"Расслабленные" атомные операции не являются операциями синхронизации даже хотя, как и операции синхронизации, они не могут расы данных.

Таким образом, конфликтное действие на атомаре никогда не является расой данных - в терминах стандарта С++.

Все эти операции являются атомарными (и, в частности, расслабленными), но здесь нет данных.

Я не согласен с надежной/предсказуемой разницей между этими двумя на любой (разумной) платформе:

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);
}

Но в определении, представленном моделью памяти С++, это не гонка данных.

Я не могу легко понять, почему это определение предоставлено, но оно дает разработчику несколько карт для участия в беспорядочной связи между потоками, которые они могут знать (на их платформе) будет статистически работать.

Например, установив значение 3 раза, а затем прочитав его, будет отображаться определенная степень конкуренции для этого местоположения. Такие подходы не детерминированы, но многие эффективные параллельные алгоритмы не детерминированы. Например, тайм-аут try_lock_until() всегда является условием гонки, но остается полезной техникой.

То, что кажется стандартом С++, дает вам определенность вокруг "гонок данных", но разрешает некоторые забавные и-игры с условиями гонки, которые в конечном итоге анализируют разные вещи.

Вкратце стандарт указывает, что если другие потоки могут видеть эффект "забивания" значения, установленного 3 раза, другие потоки должны иметь возможность видеть этот эффект (даже если они иногда могут и не быть!). Это случай, когда практически все современные платформы, которые другие потоки могут при некоторых обстоятельствах видеть, забивают.

Ответ 6

Практический пример использования шаблона, если поток делает что-то важное между обновлениями, не зависящими от или изменениями y, может быть: * Thread 2 считывает значение y, чтобы проверить, насколько прогресс Thread 1 сделал.

Итак, возможно, что Thread 1 должен загрузить файл конфигурации в качестве шага 1, поместить его проанализированное содержимое в структуру данных в качестве шага 2 и отобразить главное окно в качестве шага 3, в то время как Thread 2 ждет на шаге 2 для завершения поэтому он может выполнять другую задачу параллельно, что зависит от структуры данных. (Конечно, этот пример требует семантики получения/выпуска, а не расслабленного упорядочения.)

Im довольно уверен, что соответствующая реализация позволяет Thread 1 не обновлять y на любом промежуточном этапе - в то время как я havent по сравнению с языковым стандартом, я был бы шокирован, если он не поддерживает аппаратное обеспечение, на котором другой опрос потока y может никогда не увидеть значение 2.

Тем не менее, это гипотетический экземпляр, где может быть пессимально оптимизировать обновления статуса. Может быть, разработчик компилятора придет сюда и скажет, почему этот компилятор решил не делать этого, но одна из возможных причин - позволить вам застрелить себя в ноге или по крайней мере окунуться в носок.

Ответ 7

Пройдите немного дальше от патологического случая, когда три магазина находятся рядом друг с другом. Предположим, что существует некоторая нетривиальная работа между хранилищами, и что такая работа вообще не включает y (так что анализ пути данных может определить, что три магазина на самом деле избыточны, по крайней мере, внутри этого потока), и сам не вводит никаких барьеров памяти (так что что-то еще не заставляет магазины быть видимыми для других потоков). Теперь вполне возможно, что другие потоки имеют возможность выполнять работу между хранилищами, и, возможно, эти другие потоки управляют y и что этот поток имеет некоторые причины, чтобы потребовать reset его до 1 (второй магазин). Если первые два магазина были сброшены, это изменит поведение.

Ответ 8

Писатель компилятора не может просто выполнить оптимизацию. Они также должны убедить себя, что оптимизация действительна в ситуациях, когда автор компилятора намеревается применить ее, что она не будет применяться в ситуациях, когда она недействительна, что она не нарушает код, который на самом деле сломан, но "работает" на других реализациях. Это, вероятно, больше работы, чем сама оптимизация.

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

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

Ответ 9

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

Это была стандартная и рекомендуемая практика до того, как в архитектуре ЦП были введены строки кэша и т.д.

[EDIT2] Можно утверждать, что std:: atomic < > являются переменными volatile многоядерного возраста. Как определено в 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 сделать это по-другому.