Если операция RMW ничего не меняет, можно ли ее оптимизировать для всех порядков памяти? - PullRequest
1 голос
/ 02 ноября 2019

В модели памяти C / C ++ может ли компилятор просто объединить, а затем удалить избыточные / NOP атомарные операции модификации, такие как:

x++,
x--;

или даже просто

x+=0; // return value is ignored

Для атомарного скаляра x?

Имеет ли это значение для последовательной согласованности или просто для более слабых порядков памяти?

(Примечание: для более слабых порядков памяти, которые все еще что-то делают; для расслабленных нетреальный вопрос здесь. ВНОВЬ РЕДАКТИРОВАТЬ: Нет, на самом деле нет серьезного вопроса в этом особом случае. См. мой собственный ответ. Даже расслабленный очищается для удаления.)

РЕДАКТИРОВАТЬ:

Вопросне о генерации кода для определенного доступа: если бы я хотел видеть два lock add, сгенерированных на Intel для первого примера, я бы сделал x volatile.

Вопрос в том, являются ли эти инструкции C / C ++иметь какое-либо влияние: может ли компилятор просто отфильтровать и удалить эти nul-операции (которые не являются операциями с ослабленным порядком) как своего рода преобразование источника в источник? (или преобразование абстрактного дерева в абстрактное дерево, возможно в компиляторе "front end")

РЕДАКТИРОВАТЬ 2:

Краткое изложение гипотез:

  • notвсе операции ослаблены
  • ничего не изменчиво
  • атомарные объекты действительно потенциально доступны для нескольких функций и потоков (без автоматического атомарного объекта, адрес которого не является общим)

Необязательная гипотеза:

Если вы хотите, вы можете предположить, что адрес атома так не взят, что все доступы по имени, и что все доступы имеют свойство:

  1. То, что доступ к этой переменной нигде не имеет ослабленного элемента загрузки / хранения: все операции загрузки должны быть получены, а все хранилища должны иметь освобождение (поэтому все RMW должны быть по крайней мере acq_rel).

  2. Или, что для тех обращений, которые ослаблены, код доступа не считывает значение для какой-либо иной цели, кроме его изменения: ослабленный RMW не сохраняет значение в дальнейшем (и непроверить значение, чтобы решить, что делать дальше). Другими словами, нет данных или управляющей зависимости от значения атомного объекта , если только загрузка не имеет значения .

  3. или что все обращения к атомарному элементу являются последовательнымипоследовательны.

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

Примечание: доступ не считается "полностью расслабленным", даже если онвыполняется с использованием более слабого порядка памяти, , когда код гарантирует, что наблюдатели имеют одинаковую видимость памяти , поэтому это считается действительным для (1) и (2):

atomic_thread_fence(std::memory_order_release);
x.store(1,std::memory_order_relaxed);

каквидимость памяти, по крайней мере, так же хороша, как и для x.store(1,std::memory_order_release);

. Это считается действительным для (1) и (2):

int v = x.load(std::memory_order_relaxed);
atomic_thread_fence(std::memory_order_acquire);

по той же причине.

Это глупо, тривиально допустимо для (2) (i - это просто int)

i=x.load(std::memory_order_relaxed),i=0; // useless

, так как информация из расслабленной операции не сохранялась.

Этодействителен для (2):

(void)x.fetch_add(1, std::memory_order_relaxed);

Это недействительно для (2):

if (x.load(std::memory_order_relaxed))
  f();
else
  g();

, поскольку последующее решение было основано на расслабленной нагрузке, равно как и

i += x.fetch_add(1, std::memory_order_release);

Примечание: (2) охватывает одно из наиболее распространенных применений атомарного, поточно-ориентированного счетчика ссылок. (ИСПРАВЛЕНИЕ: неясно, что все поточно-безопасные счетчики технически соответствуют описанию, поскольку приобретение может быть выполнено только после 0 декремента, а затем было принято решение на основе счетчика> 0 без приобретения; решение не делать что-то, кромееще ...)

Ответы [ 3 ]

3 голосов
/ 02 ноября 2019

Нет, определенно не совсем. Это, по крайней мере, барьер памяти в потоке для более сильных порядков памяти.


Для mo_relaxed атомов, да, я думаю, что теоретически он может быть полностью оптимизирован, как если бы он не былтам в источнике. Это эквивалентно тому, что поток просто не является частью последовательности выпуска, частью которой он мог быть.

Если вы использовали результат fetch_add(0, mo_relaxed), то я думаю, что сворачивать их вместе и просто выполнять загрузкувместо RMW 0 может быть не совсем эквивалентным. Барьеры в этой нити, окружающие расслабленный RMW, все еще влияют на все операции, включая порядок расслабленной операции по отношению к. неатомные операции. С нагрузкой + хранилище , связанными вместе как атомарный RMW , вещи, которые заказывают хранилища, могли бы заказать атомарный RMW, если бы они не заказывали чистый груз.

Но я не думаю, чтолюбой порядок в C ++ выглядит следующим образом: mo_release хранит порядок более ранних загрузок и сохраняет, а atomic_thread_fence(mo_release) напоминает барьер asm StoreStore + LoadStore. ( Зависание на заборах ). Так что да, учитывая, что любой порядок, наложенный на C ++, будет также применяться к расслабленной нагрузке в равной степени к расслабленному RMW, я думаю, int tmp = shared.fetch_add(0, mo_relaxed) можно было бы оптимизировать только под нагрузку.


( Inпрактические компиляторы вообще не оптимизируют атомики, в основном трактуя их как volatile atomic, даже для mo_relaxed. Почему компиляторы не объединяют избыточные записи std :: atomic? и http://wg21.link/n4455 + http://wg21.link/p0062. Слишком сложно / не существует механизма, позволяющего компиляторам знать, когда не к.)

Но да, стандарт ISO C ++ на бумаге не даетгарантировать, что другие потоки действительно могут наблюдать любое заданное промежуточное состояние.

Мысленный эксперимент: рассмотрим реализацию C ++ в одноядерной кооперативной многозадачной системе . Он реализует std::thread, вставляя вызовы yield там, где это необходимо, чтобы избежать взаимоблокировок, но не между каждой инструкцией. Ничто в стандарте не требует выхода между num++ и num--, чтобы позволить другим потокам наблюдать это состояние.

Правило «как будто» в основном позволяет компилятору выбирать допустимый / возможный порядок и принимать решение при компиляции. время это то, что происходит каждый раз.

На практике это может создать проблемы справедливости, если разблокировка / повторная блокировка фактически не дает другим потокам возможность взять блокировку, если -- / ++ объединены вместев просто барьер памяти без модификации атомного объекта! Это, помимо прочего, объясняет, почему компиляторы не оптимизируют.


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

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

Рассмотрим последовательность:

// broken code where optimization could fix it
    memcpy(buf, stuff, sizeof(buf));

    done.store(1, mo_relaxed);       // relaxed: can reorder with memcpy
    done.fetch_add(-1, mo_relaxed);
    done.fetch_add(+1, mo_release);  // release-store publishes the result

Это может оптимизировать до done.store(1, mo_release);, что правильно публикует 1 в другом потоке без риска того, что 1 будет виден слишком рано, до обновленных значений buf.

Но это также могло бы оптимизировать только отмену пары RMW в ограждение после расслабленного магазина, который все еще будет сломан. (И не ошибка оптимизации.)

// still broken
    memcpy(buf, stuff, sizeof(buf));

    done.store(1, mo_relaxed);       // relaxed: can reorder with memcpy
    atomic_thread_fence(mo_release);

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


Увеличение и уменьшение seq_cst все еще создает своего рода барьер памяти. Если бы они не были оптимизированы, более ранние хранилища не могли бы чередоваться с более поздними загрузками. Чтобы сохранить это, компиляция для x86, вероятно, все равно должна будет генерировать mfence.

Конечно, очевидной вещью будет lock add [x], 0, который на самом деле делает фиктивный RMW общего объекта, который мы сделали x++ / x-- вкл. Но я думаю одного барьера памяти, не связанного с доступом к этому фактическому объекту или строке кэша, достаточно.

И, конечно, он должен действовать как барьер памяти времени компиляции,блокирование переупорядочения во время компиляции неатомарного и атомарного доступа к нему.

Для acq_rel или более слабого fetch_add(0) или отмены последовательности, барьер памяти во время выполнения может возникнуть бесплатно на x86, только нужно ограничить компиляциюпорядок времени.

См. также раздел моего ответа по Может ли num ++ быть атомарным для 'int num'? , а также в комментариях к ответу Ричарда Ходжеса. (Но обратите внимание, что некоторые из этих обсуждений смущены рассуждениями о том, когда между ++ и -- происходят изменения в других объектах. Конечно, все упорядочения операций этого потока, подразумеваемые атомами, должны быть сохранены.)


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

1 голос
/ 02 ноября 2019

Модель памяти C ++ обеспечивает четыре требования согласованности для всех атомарных обращений к одному и тому же атомарному объекту. Эти требования применяются независимо от порядка памяти. Как указано в ненормативной нотации:

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

Добавлено выделение.

Учитывая, что обе операции происходят с одной и той же атомарной переменной, и первая определенно происходит раньше второй (из-за того, что Если вы установили последовательность до it), переупорядочивание этих операций невозможно. Опять же, даже если используются операции relaxed.

Если эта пара операций была удалена компилятором, это гарантировало бы, что никакие другие потоки никогда не увидят увеличенное значение. Поэтому теперь возникает вопрос, потребует ли стандарт, чтобы какой-то другой поток мог видеть увеличенное значение.

Это не так. Без какого-либо способа что-то гарантированно «произойдет после» приращения и «произойдет до» приращения, нет никакой гарантии, что любая операция в любом другом потоке непременно увидит увеличенное значение.

Это оставляет один вопрос: всегда ли вторая операция отменяет первую? То есть отменяет ли декремент приращение? Это зависит от рассматриваемого скалярного типа. ++ и - определены только для указателей и целочисленных специализаций atomic. Поэтому нам нужно только рассмотреть их.

Для указателей декремент отменяет приращение. Причина в том, что единственный способ увеличения + уменьшения указателя не привел бы к тому же указателю на тот же объект, если бы приращение указателя было само UB. То есть, если указатель недействителен, равен NULL или является указателем конца-конца на объект / массив. Но компиляторы не должны учитывать UB-случаи, поскольку ... они не определены. Во всех случаях, когда приращение равно допустимо , уменьшение указателя также должно быть допустимым (или UB, возможно, из-за того, что кто-то освобождает память или иным образом делает указатель недействительным, но опять же, компилятору не нужноcare).

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

То есть целые числа со знаком. C ++ обычно делает целочисленное переполнение со знаком в UB. К счастью, это не относится к атомной математике;стандарт явно говорит :

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

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

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

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

0 голосов
/ 15 ноября 2019

В модели памяти C / C ++ может ли компилятор просто объединить и затем удалить избыточные / NOP атомарные операции модификации,

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

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

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

Нет. Даже это неправильно : для даже непринужденных операций безусловное удаление не является допустимым преобразованием (хотя в большинстве практических случаев это, безусловно, допустимо, но в большинстве случаев правильное по-прежнему неверно, и «верно» в> 99% практических случаях"не имеет ничего общего с вопросом):

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

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

Но очень проблематичное стандартное определение «зависания» описывает не выполнение программы, а отдельный поток: поток застревает, если не будет выполнять побочный эффект, который потенциально может повлиять на наблюдаемые побочные эффекты, а именно:

  1. явно не наблюдается (нет ввода-вывода)
  2. нет действий, которые могут взаимодействовать с другим потоком

Стандартное определение 2. чрезвычайно велико и упрощенно, все операции на устройстве связи между потокамиce count: любая атомарная операция, любое действие на любом мьютексе. Полный текст требования (соответствующая часть выделена жирным шрифтом):

[intro.progress]

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

  • завершить,
  • сделать вызов функции ввода-вывода библиотеки,
  • выполнить доступ через энергозависимое значение glvalue или
  • выполнить операцию синхронизации или атомарную операцию .

[ Примечание: Это предназначено для того, чтобы разрешить преобразования компилятора, такие как удаление пустых циклов, даже если завершение не может быть доказано. - примечание конца ]

Это определение даже не указывает:

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

Это означает, что все эти глупостиколичество операций:

  • для заборов :

    • , выполняющих забор захвата (даже если за ним нет атомарной операции) в потоке, которыйхотя бы один раз сделал атомарное хранилище, может синхронизироваться с другим ограждением или атомарной операцией
  • для мьютексов :

    • блокировканедавно созданная, явно бесполезная функция private mutex;
    • блокировка мьютекса, чтобы просто разблокировать его, ничего не делая с заблокированным мьютексом;
  • для atomics :

    • чтение атомной переменной, объявленной как квалифицированная const (не константная ссылка на неконстантную атомную);
    • чтениеатомарное, игнорирующее значение, даже с упрощенным упорядочением памяти;
    • установка неконстантного квалифицированного атома в его собственное неизменное значение (установка переменной в ноль, когда ничто во всей программе не устанавливает его в ненулевое значение)даже при расслабленном порядке ;;
    • выполнение операций с локальной атомарной переменной, недоступной другим потокам;
  • для операций с потоками:

    • создание потока (который может ничего не делать) и присоединение к нему, по-видимому, создают операцию синхронизации (NOP).

Это означает не рано, локальнопреобразование программного кода , которое не оставляет следов преобразования на более поздние фазы компилятора и удаляет даже самый глупый и бесполезный примитив между потоками , абсолютно безоговорочно допустимо согласноg к стандартному , так как он может удалить последнюю потенциально полезную (но фактически бесполезную) операцию в цикле (цикл не должен быть записан for или while, этолюбая циклическая конструкция, напримерa backward goto).

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

Это похоже на дефект.

Значимое требование должно быть основано:

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

Я не предлагаю замену прямо сейчас, так как остальная часть спецификации потока не 'мне даже ясно.

...