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

Стандарты 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 ++. (Это UB только с неатомарными переменными). Программа, которая ожидает иногда увидеть это, вовсе не обязательно содержит ошибки. (См. Ниже re: индикаторы выполнения.)

Любой порядок, который возможен на абстрактной машине C ++, может быть выбран (во время компиляции) в качестве порядка, который будет всегда. Это правило «как если бы» в действии. В этом случае это как если бы все три хранилища произошли друг за другом в глобальном порядке, без загрузки или сохранения из других потоков между y=1 и y=3.

Это не зависит от целевой архитектуры или оборудования; точно так же, как переупорядочение во время компиляции расслабленных атомарных операций разрешено, даже если ориентированный на строго упорядоченный x86. Компилятор не должен сохранять ничего, что вы могли бы ожидать, думая об оборудовании, для которого вы компилируете, поэтому вам нужны барьеры. Барьеры могут компилироваться в нулевые инструкции asm.

Так почему компиляторы не делают эту оптимизацию?

Это проблема качества реализации, которая может изменить наблюдаемую производительность / поведение на реальном оборудовании.

Самый очевидный случай, когда это проблема, - это индикатор выполнения. Выведение хранилищ из цикла (который не содержит других атомарных операций) и сворачивание их всех в один приведет к тому, что индикатор выполнения останется на 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 Ни один нормальный компилятор не оптимизирует атомику
• http://wg21.link/p0062: WG21 / P0062R1: Когда компиляторам следует оптимизировать атомикс?

См. Также обсуждение этой же темы в ответе Ричарда Ходжеса на Может ли 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), которая не изменит поведение существующего кода C ++ 11/14, когда он скомпилирован как C ++. Но это может быть похоже на предложение в wg21 / p0062: tag not-optimize case with [[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).

Вы имеете в виду устранение мертвых запасов.

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

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

^{из N4455 Никакой разумный компилятор не оптимизирует атомику}

Проблема атомарной 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 и CASing на y = 2 - это гонка данных, поскольку нет полного порядка между инструкциями двух потоков.
Выполнение, при котором инструкции A выполняются до того, как цикл B становится наблюдаемым (т. Е. разрешено) и, таким образом, компилятор может оптимизировать до y.store(3, std::memory_order_seq_cst).

Если потоки A и B каким-то образом синхронизируются между хранилищами в потоке A, тогда оптимизация не будет разрешена (будет индуцирован частичный порядок, что, возможно, приведет к тому, что B потенциально будет наблюдать y = 2).

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

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

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

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

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 раза, другие потоки должны иметь возможность видеть этот эффект (даже если они иногда не могут!). Это тот случай, когда практически все современные платформы, которые другие потоки могут при некоторых обстоятельствах столкнуться с проблемой.

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

Существуют гарантии «случилось раньше», которые должны быть выполнены и которые, среди прочего, исключают переупорядочивание или объединение операций записи (в параграфе 19 это прямо говорится даже о переупорядочении).

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

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

Что, если ваш поток вместо этого записывает 1 -1 -1, а другой спорадически записывает 2 или 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;
}

[РЕДАКТИРОВАТЬ] Сначала я не утверждал, что 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 делать это иначе.