Que signifie «arrive avant»?

9

L'expression «survient avant» est utilisée plusieurs fois dans le projet de norme C ++.

Par exemple: Résiliation [basic.start.term] / 5

Si l'achèvement de l'initialisation d'un objet avec une durée de stockage statique se produit fortement avant un appel à std :: atexit (voir, [support.start.term]), l'appel à la fonction est passé à std :: atexit est séquencé avant l'appel au destructeur de l'objet. Si un appel à std :: atexit se produit fortement avant la fin de l'initialisation d'un objet avec une durée de stockage statique, l'appel au destructeur de l'objet est séquencé avant l'appel à la fonction passé à std :: atexit . Si un appel à std :: atexit se produit fortement avant un autre appel à std :: atexit, l'appel à la fonction passé au deuxième appel std :: atexit est séquencé avant l'appel à la fonction passé au premier appel std :: atexit.

Et défini dans les courses de données [intro.races] / 12

Une évaluation A se produit fortement avant une évaluation D si, soit

(12.1) A est séquencé avant D, ou

(12.2) A se synchronise avec D, et A et D sont des opérations atomiques séquentiellement cohérentes ([atomics.order]), ou

(12.3) il existe des évaluations B et C telles que A est séquencé avant B, B se produit simplement avant C, et C est séquencé avant D, ou

(12.4) il y a une évaluation B telle que A se produit fortement avant B, et B se produit fortement avant D.

[Remarque: officieusement, si A se produit fortement avant B, alors A semble être évalué avant B dans tous les contextes. Se produit fortement avant d'exclure les opérations de consommation. - note de fin]

Pourquoi «cela se produit-il avant» a été introduit? Intuitivement, quelle est sa différence et sa relation avec "qui se passe avant"?

Que signifie «A semble être évalué avant B dans tous les contextes» dans la note?

(Remarque: la motivation de cette question sont les commentaires de Peter Cordes sous cette réponse .)

Projet de devis standard supplémentaire (merci à Peter Cordes)

Ordre et cohérence [atomics.order] / 4

Il existe un seul ordre total S sur toutes les opérations memory_order :: seq_cst, y compris les clôtures, qui satisfait les contraintes suivantes. Premièrement, si A et B sont des opérations memory_order :: seq_cst et A se produit fortement avant B, alors A précède B dans S. Deuxièmement, pour chaque paire d'opérations atomiques A et B sur un objet M, où A est ordonné par cohérence avant B, les quatre conditions suivantes doivent être remplies par S:

(4.1) si A et B sont tous deux des opérations memory_order :: seq_cst, alors A précède B dans S; et

(4.2) si A est une opération memory_order :: seq_cst et B se produit avant une clôture memory_order :: seq_cst Y, alors A précède Y dans S; et

(4.3) si une clôture memory_order :: seq_cst X se produit avant que A et B ne soient une opération memory_order :: seq_cst, alors X précède B dans S; et

(4.4) si une barrière memory_order :: seq_cst X se produit avant A et B se produit avant une barrière memory_order :: seq_cst Y, alors X précède Y dans S.

curiousguy
la source
1
Le projet de norme actuel fait également référence à "A arrive fortement avant B" comme condition d'une règle s'appliquant seq_cst, dans Atomics 31.4 Ordre et cohérence: 4 . Ce n'est pas dans la norme C ++ 17 n4659 , où 32.4 - 3 définit l'existence d'un seul ordre total d'opérations seq_cst cohérent avec l'ordre «se produit avant» et les ordres de modification pour tous les emplacements affectés ; le «fortement» a été ajouté dans un projet ultérieur.
Peter Cordes
2
@PeterCordes Je pense que le commentaire excluant la consommation, déclarant que c'est HB «dans tous les contextes» / «fort» et parler d'appels aux pointeurs de fonction est quelque chose d'un cadeau mort. Si un programme multithread appelle atexit()dans un thread et exit()dans un autre, il ne suffit pas que les initialiseurs portent uniquement une dépendance basée sur la consommation uniquement parce que les résultats diffèrent de if a exit()été invoqué par le même thread. Une de mes réponses les plus anciennes concernait cette différence.
Iwillnotexist Idonotexist
@IwillnotexistIdonotexist Pouvez-vous même quitter un programme MT? N'est-ce pas fondamentalement une idée cassée?
curiousguy
1
@curiousguy C'est le but de exit(). N'importe quel thread peut tuer l'intégralité du programme en quittant, ou le thread principal peut quitter en return-ing. Cela entraîne l'appel des atexit()gestionnaires et la mort de tous les threads quoi qu'ils fassent.
Iwillnotexist Idonotexist

Réponses:

5

Pourquoi «cela se produit-il avant» a été introduit? Intuitivement, quelle est sa différence et sa relation avec "qui se passe avant"?

Préparez-vous aussi pour "arrive simplement avant"! Jetez un œil à cet instantané actuel de cppref https://en.cppreference.com/w/cpp/atomic/memory_order

entrez la description de l'image ici

Il semble que "se produit simplement avant" soit ajouté en C ++ 20.

Se produit simplement avant

Indépendamment des threads, l'évaluation A se produit simplement avant l'évaluation B si l'une des conditions suivantes est vraie:

1) A est séquencé avant B

2) A se synchronise avec B

3) A se produit simplement avant X, et X se produit simplement avant B

Remarque: sans les opérations de consommation, les relations se produit simplement avant et se produisent avant sont les mêmes.

Donc, Simply-HB et HB sont les mêmes, sauf pour la façon dont ils gèrent les opérations de consommation. Voir HB

Se produit avant

Indépendamment des threads, l'évaluation A se produit avant l'évaluation B si l'une des conditions suivantes est vraie:

1) A est séquencé avant B

2) Un inter-thread se produit avant B

L'implémentation est nécessaire pour garantir que la relation qui se produit avant est acyclique, en introduisant une synchronisation supplémentaire si nécessaire (elle ne peut être nécessaire que si une opération de consommation est impliquée, voir Batty et al)

En quoi diffèrent-ils en matière de consommation? Voir Inter-Thread-HB

Inter-thread se produit avant

Entre les threads, l'évaluation A inter-thread se produit avant l'évaluation B si l'une des conditions suivantes est vraie

1) A se synchronise avec B

2) A est ordonné par dépendance avant B

3) ...

...

Une opération dont la dépendance est ordonnée (c'est-à-dire qui utilise la libération / la consommation) est HB mais pas nécessairement Simply-HB.

Consommer est plus détendu qu'acquérir, donc si je comprends bien, HB est plus détendu que Simply-HB.

Se produit fortement avant

Indépendamment des threads, l'évaluation A se produit fortement avant l'évaluation B si l'une des conditions suivantes est vraie:

1) A est séquencé avant B

2) A se synchronise avec B, et A et B sont des opérations atomiques séquentiellement cohérentes

3) A est séquencé avant X, X se produit simplement avant Y et Y est séquencé avant B

4) A se produit fortement - avant X, et X se produit fortement - avant B

Remarque: de manière informelle, si A se produit fortement avant B, alors A semble être évalué avant B dans tous les contextes.

Remarque: se produit fortement-avant exclut les opérations de consommation.

Une opération de libération / consommation ne peut donc pas être Strongly-HB.

La version / acquisition peut être HB et Simply-HB (car la version / acquisition se synchronise avec) mais n'est pas nécessairement Strongly-HB. Parce que Strongly-HB dit spécifiquement que A doit se synchroniser avec B ET être une opération séquentielle cohérente.

                            Is happens-before guaranteed?

                        HB             Simply-HB          Strongly-HB

relaxed                 no                 no                 no
release/consume        yes                 no                 no      
release/acquire        yes                yes                 no
S.C.                   yes                yes                yes

Que signifie «A semble être évalué avant B dans tous les contextes» dans la note?

Tous les contextes: tous les threads / tous les CPU voient (ou "finiront par s'entendre") le même ordre. C'est la garantie d'une cohérence séquentielle - un ordre global de modification totale de toutes les variables. Les chaînes d'acquisition / libération garantissent uniquement l'ordre de modification perçu pour les threads participant à la chaîne. Les threads en dehors de la chaîne sont théoriquement autorisés à voir un ordre différent.

Je ne sais pas pourquoi Strongly-HB et Simply-HB ont été introduits. Peut-être pour aider à clarifier comment fonctionner autour de consommer? Strongly-HB a de belles propriétés - si un thread observe A se produit fortement avant B, il sait que tous les threads observeront la même chose.

L'histoire de consommer:

Paul E. McKenney est responsable de consommer dans les standards C et C ++. Consume garantit un ordre entre l'affectation du pointeur et la mémoire vers laquelle il pointe. Il a été inventé à cause du DEC Alpha. Le DEC Alpha pouvait déréférencer spéculativement un pointeur, il avait donc également une barrière de mémoire pour empêcher cela. Le DEC Alpha n'est plus fabriqué et aucun processeur n'a aujourd'hui ce comportement. Consommer est destiné à être très détendu.

Humphrey Winnebago
la source
1
Bon chagrin. Je regrette presque d'avoir posé cette question. Je veux revenir à la résolution des problèmes C ++ simples comme les règles d'invalidation de l'itérateur, la recherche de nom dépendante de l'argument, les opérateurs de conversion définis par l'utilisateur du modèle, la déduction des arguments de modèle, lorsque la recherche de nom apparaît dans une classe de base dans un membre d'un modèle, et lorsque vous peut se convertir en une base virtuelle au début de la construction d'un objet.
curiousguy
Re: consommer. Affirmez-vous que le sort de la commande de consommer est lié au sort de DEC Alpha et n'a aucune valeur en dehors de cet arc particulier?
curiousguy
1
C'est une bonne question. En y regardant de plus près, il semble que la consommation puisse théoriquement améliorer les performances des arches faiblement ordonnées comme ARM et PowerPC. Donnez-moi un peu plus de temps pour l'examiner.
Humphrey Winnebago
1
Je dirais que consommer existe à cause de tous les ISA faiblement ordonnés autres que Alpha. Dans Alpha asm, les seules options sont détendues et acquièrent (et seq-cst), pas l'ordre de dépendance. mo_consumeest destiné à tirer parti de l'ordre de dépendance des données sur les CPU réels et à formaliser le fait que le compilateur ne peut pas rompre la dépendance aux données via la prédiction de branche. Par exemple, int *p = load(); tmp = *p;le compilateur pourrait interrompre l'introduction if(p==known_address) tmp = *known_address; else tmp=*p;s'il avait des raisons de s'attendre à ce qu'une certaine valeur de pointeur soit commune. C'est légal pour se détendre mais pas consommer.
Peter Cordes
@PeterCordes à droite ... les arches avec un ordre faible doivent émettre une barrière de mémoire pour acquérir, mais (théoriquement) pas pour consommer. On dirait que vous pensez que si l'Alpha n'avait jamais existé, nous aurions quand même consommé? En outre, vous dites essentiellement que consommer est une barrière de compilation sophistiquée (ou "standard").
Humphrey Winnebago