Co robi 'STD::kill dependency' i dlaczego miałbym go używać?

Question

Co robi 'STD::kill dependency' i dlaczego miałbym go używać?

Czytałem o nowym modelu pamięci C++11 i natknąłem się na funkcję std::kill_dependency (§29.3/14-15). Ciężko mi zrozumieć, Dlaczego chciałbym go użyć.

Znalazłem przykład w propozycji n2664 ale to niewiele pomogło.

Zaczyna się od wyświetlenia kodu bez std::kill_dependency. W tym przypadku pierwsza linia przenosi zależność do drugiej, która przenosi zależność do operacji indeksowania, a następnie przenosi zależność do do_something_with funkcja.

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

Istnieje kolejny przykład, który używa std::kill_dependency do zerwania zależności między drugą linią a indeksowaniem.

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

Z tego, co wiem, oznacza to, że indeksowanie i wywołanie {[5] } nie są zależnościami uporządkowanymi przed drugą linią. Według N2664:

Pozwala to kompilatorowi zmienić kolejność wywołania na do_something_with, na przykład poprzez wykonywanie optymalizacji spekulacyjnych, które przewidują wartość a[r2].

W celu wykonaj wywołanie do_something_with potrzebna jest wartość a[r2]. Jeśli, hipotetycznie, kompilator "wie", że tablica jest wypełniona zerami, może zoptymalizować to wywołanie do do_something_with(0); I zmienić kolejność tego wywołania względem dwóch pozostałych instrukcji. Może produkować dowolne z:

// 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;

Czy moje rozumienie jest poprawne?

Jeśli do_something_with synchronizuje się z innym wątkiem za pomocą innych środków, co to oznacza w odniesieniu do kolejności wywołania x.load i tego drugiego wątek?

Zakładając, że moje niedomówienie jest poprawne, wciąż jest jedna rzecz, która mnie denerwuje: kiedy piszę kod, jakie powody skłoniłyby mnie do wybrania zabicia zależności?

53

c++c++11 multithreading memory-model

Author: R. Martinho Fernandes, 2011-08-22

Source

4 answers

Oprócz drugiej odpowiedzi, zwrócę uwagę, że Scott Meyers, jeden z definitywnych liderów w społeczności C++, dość mocno pobił memory_order_consume. W zasadzie powiedział, że uważa, że nie ma miejsca w standardzie. Powiedział, że są dwa przypadki, w których memory_order_consume ma jakikolwiek wpływ:

DEC Alpha

Tak, po raz kolejny DEC Alpha znajduje się w infamy za pomocą optymalizacji nie widzianej w żadnym innym chipie dopiero wiele lat później na absurdalnie wyspecjalizowanych maszynach.

Szczególna optymalizacja polega na tym, że procesory pozwalają na dereferencję pola przed rzeczywistym uzyskaniem adresu tego pola (tzn. może on wyszukać x->y, zanim nawet wyszukuje x, używając przewidywanej wartości x). Następnie wraca i określa, czy x było wartością oczekiwaną. Na sukces, to oszczędność czasu. Po niepowodzeniu musi wrócić i dostać x - > y jeszcze raz.

Memory_order_consume mówi kompilatorowi / architekturze, że te operacje muszą się odbywać w kolejności. Jednak w najbardziej użytecznym przypadku, jeden będzie chciał zrobić (x - > y.Z), gdzie z nie zmienia. memory_order_consume zmusi kompilator do utrzymywania x y i z w porządku. kill_dependency (x->y).z mówi kompilatorowi / architekturze, że może wznowić takie nikczemne zmiany kolejności.

99,999% programistów prawdopodobnie nigdy nie będzie pracować na platformie, na której ta funkcja jest wymagane (lub ma jakikolwiek wpływ w ogóle).

11

Author: Cort Ammon,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-09-03 05:51:43

Zwykły przypadek użycia kill_dependency wynika z następujących faktów. Załóżmy, że chcesz dokonać atomowych aktualizacji nietrywialnej współdzielonej struktury danych. Typowym sposobem na to jest nieatomiczne tworzenie nowych danych i atomiczne Przesuwanie wskaźnika ze struktury danych do nowych danych. Gdy to zrobisz, nie zmienisz nowych danych, dopóki nie przesuniesz WSKAŹNIKA z niego na coś innego(i nie poczekasz, aż wszyscy czytelnicy odejdą). Ten paradygmat jest szeroko stosowany, np. read-copy-update w jądro Linuksa.

Przypuśćmy, że czytnik odczytuje wskaźnik, odczytuje nowe dane, a potem wróci i ponownie odczyta wskaźnik, stwierdzając, że wskaźnik się nie zmienił. Sprzęt nie może stwierdzić, że wskaźnik nie został ponownie zaktualizowany, więc przez semantykę consume nie może użyć buforowanej kopii danych, ale musi odczytać je ponownie z pamięci. (Lub myśląc o tym w inny sposób, sprzęt i kompilator nie mogą spekulatywnie przesunąć odczytu danych przed odczytem wskaźnika.)

Tutaj kill_dependency przychodzi na ratunek. Owijając wskaźnik w kill_dependency, tworzysz wartość, która nie będzie już propagować zależności, umożliwiając dostęp za pośrednictwem wskaźnika korzystanie z buforowanej kopii nowych danych.

3

Author: user2949652,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-01-16 15:31:59

Wydaje mi się, że umożliwia to optymalizację.

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

0

Author: Daniel A. White,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-08-22 16:35:52

score 39 · Accepted Answer

Celem memory_order_consume jest upewnienie się, że kompilator nie wykonuje pewnych niefortunnych optymalizacji, które mogą złamać algorytmy bez blokady. Na przykład rozważ ten kod:

int t;
volatile int a, b;

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

Zgodny kompilator może przekształcić to w:

a = *x;
b = *x;

Zatem a nie może równać się b. może również:

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

Używając load(memory_order_consume), wymagamy, aby użycie ładowanej wartości nie było przenoszone przed punktem użycia. Innymi słowy,

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

Standardowy dokument rozważa przypadek, w którym możesz być zainteresowany tylko zamówieniem niektórych pól struktury. Przykład:

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

To instruuje kompilator, że jest dozwolone, skutecznie, zrobić to:

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

Albo nawet to:

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

Jeśli kompilator wie, że do_something_with nie zmieni wyniku obciążenia dla r1 lub r2, to może nawet podnieść go do góry:

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

Pozwala to kompilatorowi na nieco większą swobodę w jego optymalizacji.