Que fait `std::kill_dependency`, et pourquoi voudrais-je l'utiliser ?

Question

J'ai lu des articles sur le nouveau modèle de mémoire C++11 et je suis tombé sur l'article std::kill_dependency (§29.3/14-15). J'ai du mal à comprendre pourquoi je voudrais l'utiliser.

J'ai trouvé un exemple dans le Proposition N2664 mais ça n'a pas beaucoup aidé.

Il commence par montrer le code sans std::kill_dependency . Ici, la première ligne transporte une dépendance dans la seconde, qui transporte une dépendance dans l'opération d'indexation, puis transporte une dépendance dans l'opération d'indexation. do_something_with fonction.

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

Il existe un autre exemple qui utilise std::kill_dependency pour rompre la dépendance entre la deuxième ligne et l'indexation.

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

Pour autant que je puisse dire, cela signifie que l'indexation et l'appel à do_something_with ne sont pas ordonnées en fonction de la dépendance avant la deuxième ligne. Selon N2664 :

Cela permet au compilateur de réordonner l'appel à do_something_with par exemple, en effectuant des optimisations spéculatives qui prévoient la valeur de a[r2] .

Afin d'effectuer l'appel à do_something_with la valeur a[r2] est nécessaire. Si, hypothétiquement, le compilateur "sait" que le tableau est rempli de zéros, il peut optimiser cet appel à do_something_with(0); et réorganiser cet appel par rapport aux deux autres instructions comme bon lui semble. Il peut produire n'importe lequel de :

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

Ma compréhension est-elle correcte ?

Si do_something_with se synchronise avec un autre thread par un autre moyen, qu'est-ce que cela signifie en ce qui concerne l'ordre des x.load appel et cet autre fil ?

En supposant que ma compréhension soit correcte, il reste une chose qui me chiffonne : lorsque j'écris du code, quelles raisons me conduiraient à choisir de tuer une dépendance ?

Answer 1

L'objectif de memory_order_consume est de s'assurer que le compilateur n'effectue pas certaines optimisations malheureuses qui pourraient casser les algorithmes lockless. Par exemple, considérez ce code :

int t;
volatile int a, b;

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

Un compilateur conforme peut transformer ceci en :

a = *x;
b = *x;

Ainsi, a peut ne pas être égal à b. Il peut aussi l'être :

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

En utilisant load(memory_order_consume) nous exigeons que les utilisations de la valeur chargée ne soient pas déplacées avant le point d'utilisation. En d'autres termes,

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

Le document standard envisage le cas où l'on ne souhaite ordonner que certains champs d'une structure. L'exemple est le suivant :

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

Cela indique au compilateur qu'il est autorisé à faire cela :

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

Ou même ça :

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

Si le compilateur sait que do_something_with ne changera pas le résultat des charges pour r1 ou r2, alors il peut même le faire monter à fond :

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

Cela permet au compilateur d'avoir un peu plus de liberté dans son optimisation.

Answer 2

En plus de l'autre réponse, je soulignerai que Scott Meyers, l'un des leaders définitifs de la communauté C++, a assez fortement critiqué memory_order_consume. Il a essentiellement dit qu'il pensait qu'elle n'avait pas sa place dans la norme. Il a dit qu'il y a deux cas où memory_order_consume a un effet quelconque :

• Architectures exotiques conçues pour supporter des machines à mémoire partagée de 1024+ cœurs.
• Le DEC Alpha

Oui, une fois de plus, le DEC Alpha est entré dans l'infamie en utilisant une optimisation qui n'a été vue dans aucune autre puce jusqu'à de nombreuses années plus tard sur des machines absurdement spécialisées.

L'optimisation particulière est que ces processeurs permettent de déréférencer un champ avant d'obtenir réellement l'adresse de ce champ (c'est-à-dire qu'il peut chercher x->y AVANT même de chercher x, en utilisant une valeur prédite de x). Il revient ensuite en arrière et détermine si x était la valeur qu'il attendait. En cas de succès, elle a gagné du temps. En cas d'échec, elle doit retourner chercher x->y à nouveau.

Memory_order_consume indique au compilateur/architecture que ces opérations doivent se produire dans l'ordre. Cependant, dans le cas le plus utile, on finira par vouloir faire (x->y.z), où z ne change pas. memory_order_consume forcerait le compilateur à garder x y et z dans l'ordre. kill_dependency(x->y).z dit au compilateur/architecture qu'il peut recommencer à faire de tels réarrangements infâmes.

99,999 % des développeurs ne travailleront probablement jamais sur une plate-forme où cette fonctionnalité est requise (ou a un quelconque effet).

Answer 3

Le cas habituel d'utilisation de kill_dependency résulte de ce qui suit. Supposons que vous vouliez faire des mises à jour atomiques d'une structure de données partagée non triviale. Une façon typique de le faire est de créer de façon non atomique de nouvelles données et de faire basculer de façon atomique un pointeur de la structure de données vers les nouvelles données. Une fois que vous avez fait cela, vous n'allez pas modifier les nouvelles données jusqu'à ce que vous ayez basculé le pointeur de la structure de données vers quelque chose d'autre (et attendu que tous les lecteurs aient quitté les lieux). Ce paradigme est largement utilisé, par exemple read-copy-update dans le noyau Linux.

Supposons maintenant que le lecteur lise le pointeur, lise les nouvelles données et revienne plus tard pour relire le pointeur et constater qu'il n'a pas changé. Le matériel ne peut pas dire que le pointeur n'a pas été mis à jour à nouveau, donc en consume sémantique, il ne peut pas utiliser une copie en cache des données mais doit les relire depuis la mémoire. (Ou pour le voir d'une autre manière, le matériel et le compilateur ne peuvent pas spéculer pour déplacer la lecture des données avant la lecture du pointeur).

C'est là que kill_dependency vient à la rescousse. En enveloppant le pointeur dans un kill_dependency vous créez une valeur qui ne propagera plus la dépendance, permettant aux accès par le biais du pointeur d'utiliser la copie en cache des nouvelles données.

Answer 4

Je pense qu'il permet cette optimisation.

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