Что делает `std :: kill_dependency` и зачем мне его использовать?

Question

Я читал о новой модели памяти C ++ 11 и наткнулся на функцию std::kill_dependency (& sect; 29.3 / 14-15). Я изо всех сил пытаюсь понять, почему я когда-либо хотел бы использовать это.

Я нашел пример в предложении N2664 , но это не сильно помогло.

Он начинается с показа кода без std::kill_dependency. Здесь первая строка переносит зависимость во вторую, которая переносит зависимость в операцию индексирования, а затем переносит зависимость в функцию do_something_with.

r1 = x.load(memory_order_consume);
r2 = r1->index;
do_something_with(a[r2]);

Есть еще один пример, который использует std::kill_dependency для разрыва зависимости между второй строкой и индексированием.

r1 = x.load(memory_order_consume);
r2 = r1->index;
do_something_with(a[std::kill_dependency(r2)]);

Насколько я могу судить, это означает, что индексация и вызов do_something_with не упорядочены по зависимости перед второй строкой. Согласно N2664:

Это позволяет компилятору переупорядочить вызов на do_something_with, например, путем выполнения спекулятивных оптимизаций, которые предсказывают значение a[r2].

Чтобы позвонить на do_something_with, необходимо ввести значение a[r2]. Если гипотетически компилятор «знает», что массив заполнен нулями, он может оптимизировать этот вызов до do_something_with(0); и переупорядочить этот вызов относительно двух других инструкций, как ему будет угодно. Это может привести к любому из:

// 1
r1 = x.load(memory_order_consume);
r2 = r1->index;
do_something_with(0);
// 2
r1 = x.load(memory_order_consume);
do_something_with(0);
r2 = r1->index;
// 3
do_something_with(0);
r1 = x.load(memory_order_consume);
r2 = r1->index;

Правильно ли мое понимание?

Если do_something_with синхронизируется с другим потоком каким-либо другим способом, что это означает в отношении порядка вызова x.load и этого другого потока?

Предполагая, что мое понимание правильное, меня все еще беспокоит одна вещь: когда я пишу код, какие причины побуждают меня выбрать уничтожение зависимости?

Answer 1

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

int t;
volatile int a, b;

t = *x;
a = t;
b = t;

Соответствующий компилятор может преобразовать это в:

a = *x;
b = *x;

Таким образом, a может не равняться b.Это также может сделать:

t2 = *x;
// use t2 somewhere
// later
t = *x;
a = t2;
b = t;

Используя load(memory_order_consume), мы требуем, чтобы использование загружаемого значения не перемещалось до точки использования.Другими словами,

t = x.load(memory_order_consume);
a = t;
b = t;
assert(a == b); // always true

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

r1 = x.load(memory_order_consume);
r2 = r1->index;
do_something_with(a[std::kill_dependency(r2)]);

Это указывает компилятору, что ему разрешено эффективно делать это:

predicted_r2 = x->index; // unordered load
r1 = x; // ordered load
r2 = r1->index;
do_something_with(a[predicted_r2]); // may be faster than waiting for r2's value to be available

Или даже это:

predicted_r2 = x->index; // unordered load
predicted_a  = a[predicted_r2]; // get the CPU loading it early on
r1 = x; // ordered load
r2 = r1->index; // ordered load
do_something_with(predicted_a);

Если компилятор знает, что do_something_with не изменит результат загрузки для r1 или r2, он может даже поднять его до конца:

do_something_with(a[x->index]); // completely unordered
r1 = x; // ordered
r2 = r1->index; // ordered

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

Answer 2

В дополнение к другому ответу, я укажу, что Скотт Мейерс, один из решительных лидеров в сообществе C ++, довольно сильно разбил memory_order_consume. Он в основном сказал, что считает, что в стандарте нет места. Он сказал, что есть два случая, когда memory_order_consume имеет какой-либо эффект:

• Экзотические архитектуры, предназначенные для поддержки более 1024 машин с общей памятью.
• The DEC Alpha

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

Конкретная оптимизация заключается в том, что эти процессоры позволяют разыменовывать поле до фактического получения адреса этого поля (т. Е. Он может искать x-> y, ДО того, как он даже ищет x, используя предсказанное значение x). Затем он возвращается и определяет, было ли значение x ожидаемым. В случае успеха это сэкономило время. При неудаче он должен вернуться назад и снова получить x-> y.

Memory_order_consume сообщает компилятору / архитектуре, что эти операции должны выполняться по порядку. Тем не менее, в наиболее полезном случае каждый захочет сделать (x-> y.z), где z не меняется. memory_order_consume заставит компилятор держать x y и z в порядке. kill_dependency (x-> y) .z сообщает компилятору / архитектуре, что он может возобновить выполнение таких гнусных переупорядочений.

99,999% разработчиков, вероятно, никогда не будут работать на платформе, где эта функция требуется (или имеет какой-либо эффект).

Answer 3

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

Теперь предположим, что читатель читает указатель, читает новые данные, возвращается позже и снова читает указатель, обнаруживая, что указатель не изменился. Аппаратное обеспечение не может сказать, что указатель больше не обновлялся, поэтому по семантике consume он не может использовать кэшированную копию данных, но должен снова прочитать ее из памяти. (Или, если подумать иначе, аппаратное обеспечение и компилятор не могут спекулятивно переместить чтение данных до чтения указателя.)

Здесь kill_dependency приходит на помощь. Оборачивая указатель в kill_dependency, вы создаете значение, которое больше не будет распространять зависимость, позволяя доступам через указатель использовать кэшированную копию новых данных.

Answer 4

Я предполагаю, что она включает эту оптимизацию.

r1 = x.load(memory_order_consume);
do_something_with(a[r1->index]);