Подтвердить что ты не робот

Как "приобретать" и "потреблять" порядки памяти различаются, а когда "потреблять" предпочтительнее?

Стандарт С++ 11 определяет модель памяти (1.7, 1.10), которая содержит порядки памяти, которые, грубо говоря, "последовательно последовательны", "приобретают", "потребляют", "освобождают" и "расслабляют", Точно так же программа правильна, только если она без гонок, что происходит, если все действия можно поместить в каком-то порядке, в котором происходит одно действие - до другого. Способ, которым выполняется действие X, - до действия Y заключается в том, что либо X секвенирован до Y (внутри одного потока), либо X межпоточно-происходит-до Y. Последнее условие дается, среди прочего, при

  • X синхронизируется с Y или
  • X упорядочен по закону до Y.

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

Итак, какова цель понятия "порядок зависимостей"? Какое преимущество оно обеспечивает в сравнении с более упорядоченным - до/синхронизация - с упорядочением? Поскольку правила для этого более строгие, я предполагаю, что их можно реализовать более эффективно.

Можете ли вы привести пример программы, в которой переход от выпуска/приобретения к выпуску/потреблению является правильным и обеспечивает нетривиальное преимущество? А когда std::kill_dependency обеспечит улучшение? Высокоуровневые аргументы были бы хороши, но бонусные очки за аппаратные отличия.

4b9b3361

ОТВЕТЫ

Ответ 1

упорядочение зависимостей данных было введено N2492 со следующим обоснованием:

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

  • доступ для чтения к редко написанным параллельным структурам данных.

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

  • публикация-подписка семантика для публикации с указателем

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

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

акцент мой

представлен мотивирующий пример использования rcu_dereference() из ядра Linux

Ответ 2

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

Ключевой пример использования заключается в том, чтобы писатель последовательно структурировал структуру данных, а затем разворачивал общий указатель на новую структуру (используя атомы release или acq_rel). Читатель использует load-consumume для чтения указателя и разыгрывает его, чтобы добраться до структуры данных. Разница создает зависимость данных, поэтому читателю гарантированно будет видеть инициализированные данные.

std::atomic<int *> foo {nullptr};
std::atomic<int> bar;

void thread1()
{
    bar = 7;
    int * x = new int {51};
    foo.store(x, std::memory_order_release);
}

void thread2()
{
    int *y = foo.load(std::memory_order_consume)
    if (y)
    {
        assert(*y == 51); //succeeds
        // assert(bar == 7); //undefined behavior - could race with the store to bar 
        // assert(kill_dependency(*y) + bar == 58) // undefined behavior (same reason)
        assert(*y + bar == 58); // succeeds - evaluation of bar pulled into the dependency 
    }
}

Есть две причины для обеспечения потребления нагрузки. Основная причина в том, что нагрузки ARM и Power гарантированы, но требуют дополнительного ограждения, чтобы превратить их в приобретение. (На x86 все нагрузки приобретаются, поэтому потребление не обеспечивает прямого преимущества производительности при наивной компиляции.) Вторая причина заключается в том, что компилятор может перемещать более поздние операции без зависимости от данных до потребления, чего он не может сделать для приобретения. (Включение таких оптимизаций является большой причиной для построения всего этого порядка памяти в языке.)

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

Обратите внимание, что использование потребляемых результатов приводит к отношениям, которые уже не являются транзитивными (хотя он по-прежнему гарантированно ацикличен). Например, хранилище до bar происходит перед хранилищем до foo, которое происходит до разыменования y, которое происходит до чтения bar (в заявленном утверждении), но хранилище до bar не выполняется перед чтением bar. Это приводит к более сложному определению того, что происходит раньше, но вы можете себе представить, как он работает (начните с sequenced-before, затем распространяйте через любое количество связей release-потребляете-dataDependency или release-приобретаете-sequencedBefore)

Ответ 3

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

http://preshing.com/20140709/the-purpose-of-memory_order_consume-in-cpp11/

Он показывает конкретный пример С++ с соответствующим эталонным кодом сборки для трех разных архитектур. По сравнению с memory_order_acquire, memory_order_consume потенциально предлагает 3-кратное ускорение PowerPC, ускорение 1.6x на ARM и незначительное ускорение на x86, которое в любом случае имеет сильную согласованность. Ловушка заключается в том, что с того момента, когда он написал это, только GCC на самом деле обрабатывал семантику, по-другому, от приобретения и, вероятно, из-за ошибки. Тем не менее, это демонстрирует, что ускорение доступно, если авторы компилятора могут понять, как воспользоваться им.

Ответ 4

Я хотел бы записать частичный вывод, хотя это не настоящий ответ и не означает, что не будет большой щедрости для правильного ответа.

Посмотрев на 1.10 на некоторое время, и в частности очень полезную заметку в пункте 11, я думаю, что это не так сложно. Большая разница между синхронизацией-с (далее: s/w) и зависимостью-упорядоченной-предшествующей (добой) заключается в том, что связь между событиями может быть установлена ​​путем конкатенации секвенированных ранее (s/b) и s/w произвольно, но не так для dob. Обратите внимание, что одно из определений для inter-thread происходит раньше:

A синхронизируется с X и X секвенируется до B

Но аналогичная инструкция для A является упорядоченной по заказу до того, как X отсутствует!

Итак, с release/приобретать (т.е. s/w) мы можем упорядочить произвольные события:

A1    s/b    B1                                            Thread 1
                   s/w
                          C1    s/b    D1                  Thread 2

Но теперь рассмотрим произвольную последовательность событий, подобных этой:

A2    s/b    B2                                            Thread 1
                   dob
                          C2    s/b    D2                  Thread 2

В этой последовательности все еще верно, что A2 происходит до C2 (потому что A2 - это s/b B2 и B2 inter-thread происходит до C2 из-за dob; но мы можем утверждать, что вы никогда не можете сказать!). Однако это не правда, что A2 происходит до D2. События A2 и D2 не упорядочены по отношению друг к другу, , если фактически не выполняется, что C2 несет зависимость от D2. Это более строгое требование, и отсутствие этого требования A2 -to- D2 не может быть заказано "через" пару для выпуска/потребления.

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

Кроме того, обратите внимание, что упорядочение восстанавливается, если мы добавляем последнюю более сильную пару release/получение:

A2    s/b    B2                                                         Th 1
                   dob
                          C2    s/b    D2                               Th 2
                                             s/w
                                                    E2    s/b    F2     Th 3

Теперь, по котируемому правилу, D2 inter-thread происходит до F2, и поэтому так делают C2 и B2, и поэтому A2 происходит до F2. Но учтите, что до сих пор нет порядка между A2 и D2 — упорядочение происходит только между A2 и более поздними событиями.

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

Может быть, вот пример, который имеет смысл?

std::atomic<int> foo(0);

int x = 0;

void thread1()
{
    x = 51;
    foo.store(10, std::memory_order_release);
}

void thread2()
{
    if (foo.load(std::memory_order_acquire) == 10)
    {
        assert(x == 51);
    }
}

Как написано, код без гонок, и утверждение будет выполняться, потому что пара release/приобретает пару для хранения x = 51 до загрузки в этом утверждении. Однако, изменив "приобретать" на "потребление", это уже не будет истинным, и программа будет иметь гонку данных на X, поскольку x = 51 не несет никакой зависимости в хранилище до foo. Точка оптимизации состоит в том, что этот магазин можно свободно переупорядочить, не заботясь о том, что делает foo, потому что нет зависимости.