Pourquoi les compilateurs ne fusionnent-ils pas les écritures std::atomiques redondantes ?

Question

Je me demande pourquoi aucun compilateur n'est prêt à fusionner des écritures consécutives de la même valeur dans une seule variable atomique, par exemple :

#include <atomic>
std::atomic<int> y(0);
void f() {
  auto order = std::memory_order_relaxed;
  y.store(1, order);
  y.store(1, order);
  y.store(1, order);
}

Chaque compilateur que j'ai essayé émettra l'écriture ci-dessus trois fois. Quel observateur légitime et sans compétition pourrait voir une différence entre le code ci-dessus et une version optimisée avec une seule écriture (c'est-à-dire que la règle "as-if" ne s'applique pas) ?

Si la variable avait été volatile, alors évidemment aucune optimisation n'est applicable. Qu'est-ce qui l'empêche dans mon cas ?

Voici le code dans explorateur de compilateur .

Answer 1

Les normes C++11 / C++14 comme écrit permettent aux trois magasins d'être repliés/coalisés en un seul magasin de la valeur finale. Même dans un cas comme celui-ci :

  y.store(1, order);
  y.store(2, order);
  y.store(3, order); // inlining + constant-folding could produce this in real code

La norme ne no garantir qu'un observateur tournant sur y (avec une charge atomique ou un CAS) verra jamais y == 2 . Un programme qui dépendrait de cela aurait un bogue de course de données, mais seulement le type de course de données le plus courant, et non le type de course de données du C++ Undefined Behaviour. (Il s'agit d'un comportement indéfini uniquement avec les variables non atomiques). Un programme qui s'attend à parfois voir qu'il n'est même pas nécessairement bogué. (Voir ci-dessous au sujet des barres de progression).

Tout ordre qui est possible sur la machine abstraite C++ peut être choisi (au moment de la compilation) comme l'ordre qui va toujours se produire . C'est la règle du "si" en action. Dans ce cas, c'est comme si les trois stockages se sont produits dos à dos dans l'ordre global, sans qu'aucun chargement ou stockage d'autres threads ne se produise entre les y=1 y y=3 .

Il ne dépend pas de l'architecture ou du matériel cible, tout comme l'a fait l'agent de sécurité. réorganisation au moment de la compilation d'opérations atomiques relaxées sont autorisées même en ciblant le x86 fortement ordonné. Le compilateur n'a pas à préserver tout ce que l'on pourrait attendre en pensant au matériel pour lequel on compile, donc on a besoin de barrières. Les barrières peuvent être compilées en instructions asm zéro.

---

Alors pourquoi les compilateurs ne font-ils pas cette optimisation ?

Il s'agit d'un problème de qualité d'implémentation, qui peut modifier les performances et le comportement observés sur le matériel réel.

Le cas le plus évident où cela pose problème est celui de la barre de progression. . Si l'on sort les magasins d'une boucle (qui ne contient aucune autre opération atomique) et qu'on les replie tous en un seul, la barre de progression restera à 0 et atteindra 100 % à la fin.

Il n'y a pas de C++11 std::atomic moyen de arrêter Ainsi, pour l'instant, les compilateurs choisissent simplement de ne jamais fusionner plusieurs opérations atomiques en une seule. (Les coalescer toutes en une seule opération ne change pas leur ordre les unes par rapport aux autres).

Les rédacteurs de compilateurs ont remarqué à juste titre que les programmeurs s'attendent à ce qu'un stockage atomique se produise effectivement en mémoire chaque fois que la source fait y.store() . (Voir la plupart des autres réponses à cette question, qui affirment que les magasins doivent se produire séparément en raison des lecteurs possibles qui attendent de voir une valeur intermédiaire) ; c'est-à-dire qu'il viole la règle du le principe de la moindre surprise .

Toutefois, il existe des cas où elle serait très utile, par exemple pour éviter les inutiles shared_ptr réf compte inc/déc dans une boucle.

Il est évident que toute réorganisation ou fusion ne doit pas violer d'autres règles d'ordonnancement. Par exemple, num++; num--; devrait toujours être une barrière complète au réordonnancement à l'exécution et à la compilation, même s'il ne touche plus la mémoire à l'adresse num .

---

Des discussions sont en cours pour étendre le std::atomic API donner aux programmeurs le contrôle de ces optimisations, ce qui permettra aux compilateurs d'optimiser lorsque cela est utile, ce qui peut arriver même dans un code soigneusement écrit qui n'est pas intentionnellement inefficace. Quelques exemples de cas utiles pour l'optimisation sont mentionnés dans les liens suivants de discussion / proposition de groupe de travail :

• http://wg21.link/n4455 : N4455 Aucun compilateur sensé n'optimiserait les Atomics
• http://wg21.link/p0062 : WG21/P0062R1 : Quand les compilateurs doivent-ils optimiser les atomiques ?

Voir également la discussion sur ce même sujet dans la réponse de Richard Hodges à la question suivante Est-ce que num++ peut être atomique pour 'int num' ? (voir les commentaires). Voir aussi la dernière section de ma réponse à la même question, où j'argumente plus en détail que cette optimisation est autorisée. (Je serai bref ici, car les liens du groupe de travail C++ reconnaissent déjà que la norme actuelle telle qu'elle est écrite l'autorise, et que les compilateurs actuels ne l'optimisent tout simplement pas exprès).

---

Dans le cadre de la norme actuelle, volatile atomic<int> y serait un moyen de s'assurer que les magasins qui s'y trouvent ne sont pas autorisés à être optimisés. (Comme Herb Sutter fait remarquer dans une réponse SO , volatile y atomic partagent déjà certaines exigences, mais elles sont différentes). Voir aussi std::memory_order La relation de l'entreprise avec volatile sur cppreference.

Accès à volatile ne sont pas autorisés à être optimisés (parce qu'ils pourraient être des registres d'entrée-sortie mappés en mémoire, par exemple).

Utilisation de volatile atomic<T> résout en grande partie le problème de la barre de progression, mais c'est plutôt laid et pourrait sembler idiot dans quelques années si/quand le C++ décide d'une syntaxe différente pour contrôler l'optimisation afin que les compilateurs puissent commencer à le faire en pratique.

Je pense que nous pouvons être sûrs que les compilateurs ne commenceront pas à faire cette optimisation tant qu'il n'y aura pas un moyen de la contrôler. Espérons qu'il s'agira d'une sorte d'option de participation (comme une option d'achat). memory_order_release_coalesce ) qui ne change pas le comportement du code C++11/14 existant lorsqu'il est compilé en C++quelque chose. Mais cela pourrait être comme la proposition dans wg21/p0062 : marquer les cas de non-optimisation avec [[brittle_atomic]] .

wg21/p0062 avertisse que même si volatile atomic ne résout pas tout, et décourage son utilisation à cette fin . Il donne cet exemple :

if(x) {
    foo();
    y.store(0);
} else {
    bar();
    y.store(0);  // release a lock before a long-running loop
    for() {...} // loop contains no atomics or volatiles
}
// A compiler can merge the stores into a y.store(0) here.

Même avec volatile atomic<int> y un compilateur est autorisé à évincer le y.store() de la if/else et de ne le faire qu'une seule fois, parce qu'il s'agit toujours de faire exactement un stockage avec la même valeur. (Ce qui serait après la longue boucle dans la branche else). Surtout si le stockage est seulement relaxed o release au lieu de seq_cst .

volatile arrête le coalescencement discuté dans la question, mais cela souligne que d'autres optimisations sur les atomic<> peut également être problématique pour les performances réelles.

---

Parmi les autres raisons de ne pas optimiser, citons : personne n'a écrit le code compliqué qui permettrait au compilateur d'effectuer ces optimisations en toute sécurité (sans jamais se tromper). Ce n'est pas suffisant, car N4455 dit que LLVM implémente déjà ou pourrait facilement implémenter plusieurs des optimisations qu'il a mentionnées.

La raison de la confusion pour les programmeurs est certainement plausible, cependant. Le code sans verrou est déjà assez difficile à écrire correctement en premier lieu.

Ne soyez pas désinvolte dans votre utilisation des armes atomiques : elles ne sont pas bon marché et n'optimisent pas beaucoup (actuellement pas du tout). Il n'est pas toujours facile d'éviter les opérations atomiques redondantes avec std::shared_ptr<T> cependant, puisqu'il n'existe pas de version non-atomique de cette dernière (bien que une des réponses ici offre un moyen simple de définir un shared_ptr_unsynchronized<T> pour gcc).

Answer 2

Vous faites référence à l'élimination des dépôts morts.

Il n'est pas interdit d'éliminer un magasin mort atomique mais il est plus difficile de prouver qu'un magasin atomique peut être qualifié comme tel.

Les optimisations traditionnelles du compilateur, telles que l'élimination des magasins morts, peuvent être effectuées sur les opérations atomiques, même celles qui sont cohérentes sur le plan séquentiel.
Les optimiseurs doivent faire attention à ne pas faire cela à travers synchronisation parce qu'un autre fil d'exécution peut observer ou modifier la mémoire, ce qui signifie que les optimisations traditionnelles doivent tenir compte d'un plus grand nombre d'instructions intermédiaires qu'elles ne le feraient habituellement en considérant les optimisations des opérations atomiques.
Dans le cas de l'élimination des magasins morts, il ne suffit pas de prouver qu'un magasin atomique post-domine et aliène un autre magasin pour éliminer ce dernier.

de N4455 Aucun compilateur sensé n'optimiserait les Atomics

Le problème de la DSE atomique, dans le cas général, est qu'elle implique la recherche de points de synchronisation, ce terme désignant, selon ma compréhension, les points du code où il y a se passe avant relation entre une instruction sur un thread A et une instruction sur un autre fil B.

Considérons ce code exécuté par un thread A :

y.store(1, std::memory_order_seq_cst);
y.store(2, std::memory_order_seq_cst);
y.store(3, std::memory_order_seq_cst);

Peut-il être optimisé comme y.store(3, std::memory_order_seq_cst) ?

Si un fil B attend de voir y = 2 (par exemple avec un CAS), il ne l'observera jamais si le code est optimisé.

Cependant, d'après ce que j'ai compris, le fait d'avoir un bouclage B et un CASsing sur y = 2 est une course aux données car il n'y a pas d'ordre total entre les instructions des deux threads.
Une exécution où les instructions de A sont exécutées avant la boucle de B est observable (c'est-à-dire permise) et le compilateur peut donc optimiser pour y.store(3, std::memory_order_seq_cst) .

Si les threads A et B sont synchronisés, d'une manière ou d'une autre, entre les magasins du thread A, l'optimisation ne serait pas autorisée (un ordre partiel serait induit, ce qui pourrait conduire à ce que B observe potentiellement y = 2 ).

Prouver qu'une telle synchronisation n'existe pas est difficile car cela implique de considérer un champ d'application plus large et de prendre en compte toutes les particularités d'une architecture.

D'après ce que j'ai compris, en raison de l'ancienneté relativement faible des opérations atomiques et de la difficulté de raisonner sur l'ordonnancement de la mémoire, la visibilité et la synchronisation, les compilateurs n'effectuent pas toutes les optimisations possibles sur les atomiques jusqu'à ce qu'un cadre plus robuste pour détecter et comprendre les conditions nécessaires soit construit.

Je crois que votre exemple est une simplification du thread de comptage donné plus haut, car il n'a pas d'autre thread ni de point de synchronisation, pour ce que je vois, je suppose que le compilateur aurait pu optimiser les trois stores.

Answer 3

Pendant que vous changez la valeur d'un atomique dans un thread, un autre thread peut le vérifier et effectuer une opération basée sur la valeur de l'atomique. L'exemple que vous avez donné est si spécifique que les développeurs de compilateurs ne voient pas l'intérêt de l'optimiser. Cependant, si un thread fixe, par exemple, des valeurs consécutives pour un atomique : 0 , 1 , 2 etc., l'autre thread peut mettre quelque chose dans les emplacements indiqués par la valeur de l'atomique.

Answer 4

NB : J'allais commenter ceci mais c'est un peu trop verbeux.

Un fait intéressant est que ce comportement n'est pas, en termes de C++, une course aux données.

La note 21 de la p.14 est intéressante : http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3690.pdf (c'est moi qui souligne) :

L'exécution d'un programme contient une course de données si elle contient deux actions conflictuelles dans des threads différents, au moins deux fois par jour. dont l'un n'est non atomique

Voir aussi p.11 note 5 :

Les opérations atomiques "relaxées" ne sont pas des opérations de synchronisation même si même si, comme les opérations de synchronisation, elles ne peuvent pas contribuer aux courses de données.

Ainsi, une action conflictuelle sur un atome n'est jamais une course aux données - au sens de la norme C++.

Ces opérations sont toutes atomiques (et spécifiquement relaxées) mais pas de course aux données ici les amis !

Je suis d'accord qu'il n'y a pas de différence fiable/prévisible entre ces deux-là sur n'importe quelle plateforme (raisonnable) :

include <atomic>
std::atomic<int> y(0);
void f() {
  auto order = std::memory_order_relaxed;
  y.store(1, order);
  y.store(1, order);
  y.store(1, order);
}

et

include <atomic>
std::atomic<int> y(0);
void f() {
  auto order = std::memory_order_relaxed;
  y.store(1, order);
}

Mais dans le cadre de la définition du modèle de mémoire C++, ce n'est pas une course aux données.

Je ne comprends pas facilement pourquoi cette définition est fournie, mais elle donne au développeur quelques cartes pour s'engager dans une communication désordonnée entre des fils dont il sait (sur sa plateforme) qu'ils fonctionneront statistiquement.

Par exemple, le fait de définir une valeur 3 fois puis de la relire montrera un certain degré de contention pour cet emplacement. Ces approches ne sont pas déterministes, mais de nombreux algorithmes concurrents efficaces ne sont pas déterministes. Par exemple, un temps d'arrêt try_lock_until() est toujours une condition de course mais reste une technique utile.

Il semble que la norme C++ vous offre des certitudes en matière de "courses de données", tout en autorisant certains jeux avec les conditions de course, qui sont, en dernière analyse, des choses différentes.

En bref, la norme semble spécifier que lorsque d'autres threads peuvent voir l'effet de "martelage" d'une valeur définie 3 fois, les autres threads doivent être en mesure de voir cet effet (même si parfois ils ne le voient pas !). C'est le cas sur la quasi-totalité des plates-formes modernes, où les autres threads peuvent, dans certaines circonstances, voir le martèlement.

Answer 5

En bref, parce que la norme (par exemple les paragaraphes autour et en dessous de 20 en [intro.multithread] ) ne le permet pas.

Il existe des garanties "happens-before" qui doivent être remplies et qui, entre autres, excluent les écritures de réordonnancement ou de coalescence (le paragraphe 19 le dit même explicitement à propos du réordonnancement).

Si votre thread écrit trois valeurs en mémoire (disons 1, 2 et 3) l'une après l'autre, un autre thread peut lire la valeur. Si, par exemple, votre thread est interrompu (ou même s'il s'exécute simultanément) et qu'un autre thread également écrit à cet emplacement, le thread observateur doit voir les opérations dans l'ordre exact où elles se produisent (soit par ordonnancement, soit par coïncidence, soit pour une raison quelconque). C'est une garantie.

Comment cela est-il possible si vous ne faites que la moitié des écritures (ou même une seule) ? Ce n'est pas possible.

Et si votre thread écrit plutôt 1 -1 -1 mais qu'un autre écrit sporadiquement 2 ou 3 ? Et si un troisième thread observe l'emplacement et attend une valeur particulière qui n'apparaît jamais parce qu'elle est optimisée ?

Il est impossible d'offrir les garanties données si les stockages (et les chargements aussi) ne sont pas effectués comme demandé. Tous, et dans le même ordre.