Comprendre std::atomic::compare_exchange_weak() en C++11

Question

bool compare_exchange_weak (T& expected, T val, ..);

compare_exchange_weak() est l'une des primitives de comparaison-échanges fournies en C++11. Elle est faible dans le sens où il renvoie false même si la valeur de l'objet est égale à expected . Ceci est dû à défaillance intempestive sur certaines plateformes où une séquence d'instructions (au lieu d'une seule comme sur x86) est utilisée pour l'implémenter. Sur ces plates-formes, le changement de contexte, le rechargement de la même adresse (ou ligne de cache) par un autre thread, etc. peuvent faire échouer la primitive. Il s'agit de spurious car ce n'est pas la valeur de l'objet (pas égal à expected ) qui fait échouer l'opération. Il s'agit plutôt d'un problème de timing.

Mais ce qui m'intrigue, c'est ce qui est dit dans la norme C++11 (ISO/IEC 14882),

29.6.5 .. Une conséquence de l'échec fallacieux est que presque toutes les utilisations de la méthode faible de faible se feront dans une boucle.

Pourquoi faut-il que ce soit dans une boucle en presque toutes les utilisations ? Est-ce que cela signifie que nous allons faire une boucle lorsqu'il échoue à cause de fausses défaillances ? Si c'est le cas, pourquoi nous donnons-nous la peine d'utiliser compare_exchange_weak() et écrire la boucle nous-mêmes ? Nous pouvons simplement utiliser compare_exchange_strong() ce qui, je pense, devrait nous débarrasser des faux échecs. Quels sont les cas d'utilisation courants de compare_exchange_weak() ?

Une autre question connexe. Dans son livre "C++ Concurrency In Action" Anthony dit,

//Because compare_exchange_weak() can fail spuriously, it must typically
//be used in a loop:

bool expected=false;
extern atomic<bool> b; // set somewhere else
while(!b.compare_exchange_weak(expected,true) && !expected);

//In this case, you keep looping as long as expected is still false,
//indicating that the compare_exchange_weak() call failed spuriously.

Pourquoi est-ce que !expected dans la condition de la boucle ? Est-il là pour éviter que tous les threads ne meurent de faim et ne progressent pas pendant un certain temps ?

Une dernière question

Sur les plates-formes où il n'existe pas d'instruction CAS matérielle unique, les versions faible et forte sont implémentées en utilisant LL/SC (comme ARM, PowerPC, etc.). Y a-t-il donc une différence entre les deux boucles suivantes ? Pourquoi, si c'est le cas ? (Pour moi, elles devraient avoir des performances similaires).

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_weak(..))
{ .. }

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_strong(..)) 
{ .. }

Je suis venu avec cette dernière question, vous avez tous mentionné qu'il peut y avoir une différence de performance à l'intérieur d'une boucle. C'est également mentionné par la norme C++11 (ISO/IEC 14882) :

Quand une comparaison et un échange sont dans une boucle, la version faible produira meilleures performances sur certaines plateformes.

Mais comme analysé ci-dessus, deux versions dans une boucle devraient donner des performances identiques/similaires. Quelle est la chose qui me manque ?

Answer 1

Pourquoi faire un échange en boucle ?

En général, vous voulez que votre travail soit terminé avant de passer à autre chose, donc vous mettez compare_exchange_weak dans une boucle de sorte qu'il essaie d'échanger jusqu'à ce qu'il réussisse (c'est-à-dire qu'il retourne true ).

Notez qu'également compare_exchange_strong est souvent utilisé dans une boucle. Elle n'échoue pas en raison d'une défaillance intempestive, mais elle échoue en raison d'écritures concurrentes.

Pourquoi utiliser weak au lieu de strong ?

C'est assez simple : les défaillances intempestives ne sont pas fréquentes et ne représentent donc pas un gros problème de performance. En revanche, tolérer un tel échec permet une mise en œuvre beaucoup plus efficace de la fonction weak (par rapport à la version strong ) sur certaines plateformes : strong doit toujours vérifier l'absence d'erreur et la masquer. Cette opération est coûteuse.

Ainsi, weak est utilisé car il est beaucoup plus rapide que strong sur certaines plateformes

Quand devez-vous utiliser weak et quand strong ?

El référence indique quand utiliser weak et quand utiliser strong :

Lorsqu'une comparaison et un échange sont dans une boucle, la version faible donnera meilleures performances sur certaines plateformes. Lorsqu'une comparaison et échange faible nécessite une boucle et qu'une version forte n'en nécessite pas, la version forte est préférable.

La réponse semble donc être assez simple à retenir : si vous devez introduire une boucle uniquement à cause d'une défaillance parasite, ne le faites pas ; utilisez strong . Si vous avez une boucle de toute façon, alors utilisez weak .

Pourquoi est-ce que !expected dans l'exemple

Cela dépend de la situation et de la sémantique souhaitée, mais en général, ce n'est pas nécessaire pour l'exactitude. L'omettre donnerait une sémantique très similaire. Seulement dans le cas où un autre thread pourrait réinitialiser la valeur de false la sémantique pourrait être légèrement différente (mais je ne peux pas trouver un exemple significatif où vous voudriez cela). Voir Commentaire de Tony D. pour une explication détaillée.

Il s'agit simplement d'une voie rapide lorsque un autre le fil écrit true : Alors le nous abandonnons au lieu d'essayer d'écrire true encore.

Concernant votre dernière question

Mais comme analysé ci-dessus, deux versions dans une boucle devraient donner des performances identiques/similaires. Quelle est la chose qui me manque ?

Desde Wikipedia :

Les implémentations réelles de LL/SC ne réussissent pas toujours s'il n'y a pas de mises à jour simultanées de l'emplacement mémoire en question. Tout événement exceptionnel exceptionnels entre les deux opérations, tels qu'un changement de contexte, une autre contexte, un autre lien de chargement, ou même (sur de nombreuses plates-formes) une autre opération de chargement ou de stockage, fera en sorte que le conditionnel de stockage se perdra. entraînera l'échec du stockage conditionnel. Les anciennes versions de anciennes échoueront si des mises à jour sont diffusées sur le bus mémoire. bus mémoire.

Ainsi, LL/SC échouera faussement lors d'un changement de contexte, par exemple. Maintenant, la version forte apporterait sa "propre petite boucle" pour détecter ce faux échec et le masquer en réessayant. Notez que cette propre boucle est aussi plus compliquée qu'une boucle CAS habituelle, puisqu'elle doit distinguer entre l'échec fallacieux (et le masquer) et l'échec dû à un accès concurrent (qui résulte en un retour avec la valeur false ). La version faible n'a pas de boucle propre.

Puisque vous fournissez une boucle explicite dans les deux exemples, il n'est tout simplement pas nécessaire d'avoir la petite boucle pour la version forte. Par conséquent, dans l'exemple avec la strong la vérification de l'échec est faite deux fois ; une fois par compare_exchange_strong (ce qui est plus compliqué puisqu'il doit distinguer l'échec fallacieux et les accès simultanés) et une fois par votre boucle. Cette vérification coûteuse est inutile et la raison pour laquelle weak sera plus rapide ici.

Notez aussi que votre argument (LL/SC) est juste un possibilité de mettre cela en œuvre. Il existe d'autres plateformes qui ont des jeux d'instructions encore différents. De plus (et plus important), notez que std::atomic doit soutenir toutes les opérations pour tous les types de données possibles Ainsi, même si vous déclarez une structure de dix millions d'octets, vous pouvez utiliser la fonction compare_exchange sur ce sujet. Même sur un processeur qui dispose de CAS, vous ne pouvez pas CASer dix millions d'octets, le compilateur générera donc d'autres instructions (probablement l'acquisition d'un verrou, suivie d'une comparaison et d'un échange non atomiques, suivis d'une libération du verrou). Maintenant, pensez au nombre de choses qui peuvent se produire pendant l'échange de dix millions d'octets. Ainsi, alors qu'une erreur parasite peut être très rare pour des échanges de 8 octets, elle pourrait être plus fréquente dans ce cas.

Donc, en résumé, le C++ vous donne deux sémantiques, une sémantique "best effort" ( weak ) et un "Je vais le faire pour sûr, peu importe combien de mauvaises choses pourraient se produire entre-temps" ( strong ). La façon dont ils sont implémentés sur différents types de données et plates-formes est un sujet totalement différent. Ne liez pas votre modèle mental à l'implémentation sur votre plate-forme spécifique ; la bibliothèque standard est conçue pour fonctionner avec plus d'architectures que vous ne le pensez. La seule conclusion générale que nous pouvons tirer est qu'il est généralement plus difficile de garantir le succès (et donc d'exiger un travail supplémentaire) que de simplement essayer et de laisser une marge de manœuvre pour un éventuel échec.

Answer 2

J'essaie de répondre à cette question moi-même, après avoir parcouru diverses ressources en ligne (par ex, celui-ci y celui-ci ), la norme C++11, ainsi que les réponses données ici.

Les questions connexes sont fusionnées (par exemple, " pourquoi !attendu ? " est fusionné avec "pourquoi mettre compare_exchange_weak() dans une boucle ? ") et les réponses sont données en conséquence.

---

Pourquoi compare_exchange_weak() doit-il être dans une boucle dans presque toutes les utilisations ?

Modèle typique A

Vous devez réaliser une mise à jour atomique basée sur la valeur de la variable atomique. Un échec indique que la variable n'est pas mise à jour avec la valeur souhaitée et que nous voulons réessayer. Notez que nous ne nous soucions pas vraiment de savoir s'il échoue en raison d'une écriture simultanée ou d'un échec fallacieux. Mais nous nous soucions que c'est nous qui font ce changement.

expected = current.load();
do desired = function(expected);
while (!current.compare_exchange_weak(expected, desired));

Un exemple concret est l'ajout simultané par plusieurs threads d'un élément à une liste singulièrement liée. Chaque thread charge d'abord le pointeur de tête, alloue un nouveau nœud et ajoute la tête à ce nouveau nœud. Enfin, il essaie d'échanger le nouveau nœud avec la tête.

Un autre exemple consiste à mettre en œuvre un mutex en utilisant std::atomic<bool> . Un seul thread au maximum peut entrer dans la section critique à la fois, en fonction du thread qui a défini en premier la section critique. current a true et sortir de la boucle.

Modèle typique B

Il s'agit en fait du modèle mentionné dans le livre d'Anthony. Contrairement au modèle A, vous voulez que la variable atomique soit mise à jour une fois, mais vous ne vous souciez pas de savoir qui le fait. Tant qu'il n'est pas mis à jour, vous réessayez. Ceci est typiquement utilisé avec des variables booléennes. Par exemple, vous devez implémenter un déclencheur pour qu'une machine à états passe à l'action. Le thread qui déclenche le déclencheur est indépendant.

expected = false;
// !expected: if expected is set to true by another thread, it's done!
// Otherwise, it fails spuriously and we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

Notez que nous ne pouvons généralement pas utiliser ce modèle pour implémenter un mutex. Sinon, plusieurs threads peuvent se trouver à l'intérieur de la section critique en même temps.

Cela dit, il devrait être rare d'utiliser compare_exchange_weak() en dehors d'une boucle. Au contraire, il y a des cas où la version forte est utilisée. Par exemple,

bool criticalSection_tryEnter(lock)
{
  bool flag = false;
  return lock.compare_exchange_strong(flag, true);
}

compare_exchange_weak n'est pas approprié ici parce que lorsqu'il revient à cause d'un échec fallacieux, il est probable que personne n'occupe encore la section critique.

Starving Thread ?

Un point qui mérite d'être mentionné est ce qui se passe si les échecs fallacieux continuent à se produire, ce qui affame le fil de discussion ? Théoriquement, cela pourrait se produire sur des plateformes où compare_exchange_XXX() est implémenté comme une séquence d'instructions (par exemple, LL/SC). Des accès fréquents à la même ligne de cache entre LL et SC produiront des défaillances parasites continues. Un exemple plus réaliste est dû à un ordonnancement stupide où tous les threads concurrents sont entrelacés de la manière suivante.

Time
 |  thread 1 (LL)
 |  thread 2 (LL)
 |  thread 1 (compare, SC), fails spuriously due to thread 2's LL
 |  thread 1 (LL)
 |  thread 2 (compare, SC), fails spuriously due to thread 1's LL
 |  thread 2 (LL)
 v  ..

Cela peut-il arriver ?

Heureusement, ce ne sera pas toujours le cas, grâce aux exigences du C++11 :

Les implémentations doivent garantir que les opérations de comparaison et d'échange faibles ne renvoient pas systématiquement false, sauf si l'objet atomique a une valeur différente de celle attendue ou qu'il y ait des modifications modifications simultanées de l'objet atomique.

Pourquoi prendre la peine d'utiliser compare_exchange_weak() et d'écrire la boucle nous-mêmes ? Nous pouvons simplement utiliser compare_exchange_strong().

Ça dépend.

Cas 1 : Quand les deux doivent être utilisés à l'intérieur d'une boucle. C++11 dit :

Lorsqu'une comparaison et échange est dans une boucle, la version faible donnera meilleures performances sur certaines plateformes.

Sur x86 (au moins actuellement. Peut-être qu'un jour, un schéma similaire à celui de LL/SC sera utilisé pour améliorer les performances lorsque davantage de cœurs seront introduits), les versions faible et forte sont essentiellement les mêmes car elles se résument toutes deux à une seule instruction. cmpxchg . Sur certaines autres plateformes où compare_exchange_XXX() n'est pas mis en œuvre atomiquement (ce qui signifie ici qu'il n'existe pas de primitive matérielle unique), la version faible à l'intérieur de la boucle peut gagner la bataille parce que la version forte devra gérer les faux échecs et réessayer en conséquence.

Mais,

rarement, on peut préférer compare_exchange_strong() sur compare_exchange_weak() même dans une boucle. Par exemple, lorsqu'il y a beaucoup de choses à faire entre le chargement d'une variable atomique et l'échange d'une nouvelle valeur calculée (cf. function() ci-dessus). Si la variable atomique elle-même ne change pas fréquemment, nous n'avons pas besoin de répéter le calcul coûteux pour chaque échec fallacieux. Au lieu de cela, nous pouvons espérer que compare_exchange_strong() "absorber" de tels échecs et nous ne répétons le calcul que lorsqu'il échoue en raison d'un véritable changement de valeur.

Cas 2 : Lorsque seulement compare_exchange_weak() doivent être utilisés à l'intérieur d'une boucle. C++11 dit aussi :

Lorsqu'une comparaison et un échange faibles nécessitent une boucle et qu'une comparaison et un échange forts n'en ont pas besoin. ne le ferait pas, la comparaison forte est préférable.

C'est typiquement le cas lorsque vous bouclez juste pour éliminer les échecs parasites de la version faible. Vous réessayez jusqu'à ce que l'échange soit réussi ou échoue à cause d'une écriture concurrente.

expected = false;
// !expected: if it fails spuriously, we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

Au mieux, c'est réinventer les roues et faire la même chose que compare_exchange_strong() . Pire ? Cette approche ne permet pas de tirer pleinement parti des machines qui fournissent des comparaisons et des échanges non fallacieux dans le matériel. .

Enfin, si vous bouclez pour d'autres choses (par exemple, voir le "schéma type A" ci-dessus), il y a de fortes chances que compare_exchange_strong() doit également être placé dans une boucle, ce qui nous ramène au cas précédent.

Answer 3

Pourquoi faut-il que ce soit dans une boucle en presque toutes les utilisations ?

Parce que si vous ne bouclez pas et qu'elle échoue de manière fallacieuse, votre programme n'a rien fait d'utile - vous n'avez pas mis à jour l'objet atomique et vous ne savez pas quelle est sa valeur actuelle (Correction : voir le commentaire de Cameron ci-dessous). Si l'appel ne fait rien d'utile, quel est l'intérêt de le faire ?

Cela signifie-t-il que nous ferons une boucle lorsqu'il échouera à cause de fausses défaillances ?

Oui.

Si c'est le cas, pourquoi se donner la peine d'utiliser compare_exchange_weak() et écrire la boucle nous-mêmes ? Nous pouvons simplement utiliser compare_exchange_strong() qui, je pense, devrait nous débarrasser des échecs intempestifs. Quels sont les cas d'utilisation courants de compare_exchange_weak() ?

Sur certaines architectures compare_exchange_weak est plus efficace, et les échecs intempestifs devraient être assez rares, il est donc possible d'écrire des algorithmes plus efficaces en utilisant la forme faible et une boucle.

En général, il est probablement préférable d'utiliser la version forte si votre algorithme n'a pas besoin de boucler, car vous n'avez pas à vous soucier des échecs intempestifs. S'il a besoin de boucler même pour la version forte (et de nombreux algorithmes ont besoin de boucler de toute façon), alors l'utilisation de la forme faible peut être plus efficace sur certaines plateformes.

Pourquoi est-ce que !expected dans la condition de la boucle ?

La valeur aurait pu être fixée à true par un autre fil, donc vous ne voulez pas continuer à tourner en boucle pour essayer de le régler.

Editar:

Mais comme analysé ci-dessus, deux versions dans une boucle devraient donner des performances identiques/similaires. Quelle est la chose qui me manque ?

Il est évident que sur les plates-formes où les défaillances intempestives sont possibles, l'implémentation de la fonction compare_exchange_strong doit être plus complexe, afin de vérifier l'absence d'erreur et de réessayer.

La forme faible ne renvoie qu'en cas de faux échec, elle ne réessaie pas.

Answer 4

D'accord, donc j'ai besoin d'une fonction qui effectue un décalage atomique vers la gauche. Mon processeur n'a pas d'opération native pour cela, et la bibliothèque standard n'a pas de fonction pour cela, donc il semble que je doive écrire la mienne. C'est parti :

void atomicLeftShift(std::atomic<int>* var, int shiftBy)
{
    do {
        int oldVal = std::atomic_load(var);
        int newVal = oldVal << shiftBy;
    } while(!std::compare_exchange_weak(oldVal, newVal));
}

Il y a deux raisons pour lesquelles cette boucle peut être exécutée plus d'une fois.

1. Quelqu'un d'autre a changé la variable pendant que je faisais mon changement de vitesse à gauche. Les résultats de mon calcul ne doivent pas être appliqués à la variable atomique, car cela effacerait effectivement l'écriture de cette personne.
2. Mon processeur a roté et le CAS a faussement échoué.

Honnêtement, je ne me soucie pas duquel. Le changement de vitesse à gauche est assez rapide pour que je puisse le refaire, même si l'échec était faux.

Qu'est-ce que moins rapide, cependant, est le code supplémentaire que le CAS fort doit envelopper autour du CAS faible afin d'être fort. Ce code ne fait pas grand-chose quand le CAS faible réussit... mais quand il échoue, le CAS fort doit faire un travail de détective pour déterminer si c'était le cas 1 ou le cas 2. Ce travail de détection prend la forme d'une deuxième boucle, effectivement à l'intérieur de ma propre boucle. Deux boucles imbriquées. Imaginez que votre professeur d'algorithmique vous regarde fixement.

Et comme je l'ai déjà dit, je me moque du résultat de ce travail de détective ! Dans tous les cas, je vais devoir refaire le CAS. Ainsi, l'utilisation d'un CAS fort ne m'apporte précisément rien, et me fait perdre une quantité faible mais mesurable d'efficacité.

En d'autres termes, le CAS faible est utilisé pour mettre en œuvre des opérations de mise à jour atomique. Le CAS fort est utilisé lorsque vous vous souciez du résultat du CAS.

Answer 5

Je pense que la plupart des réponses ci-dessus abordent la question des "défaillances intempestives" comme une sorte de problème, un compromis entre performance et correction.

On peut voir que la version faible est plus rapide la plupart du temps, mais en cas d'échec fallacieux, elle devient plus lente. Et la version forte est une version qui n'a aucune possibilité d'échec fallacieux, mais elle est presque toujours plus lente.

Pour moi, la principale différence réside dans la façon dont ces deux versions traitent le problème de l'ABA :

La version faible ne réussira que si personne n'a touché la ligne de cache entre le chargement et le stockage, donc elle détectera à 100% le problème ABA.

La version forte n'échouera que si la comparaison échoue, elle ne détectera donc pas le problème ABA sans mesures supplémentaires.

Donc, en théorie, si vous utilisez la version faible sur une architecture faiblement ordonnée, vous n'avez pas besoin du mécanisme de détection ABA et l'implémentation sera beaucoup plus simple, donnant de meilleures performances.

Mais, sur x86 (architecture à ordre fort), la version faible et la version forte sont les mêmes, et elles souffrent toutes deux du problème ABA.

Ainsi, si vous écrivez un algorithme entièrement multiplateforme, vous devez de toute façon résoudre le problème de l'ABA. Il n'y a donc aucun avantage en termes de performances à utiliser la version faible, mais il y a une pénalité en termes de performances pour la gestion des échecs intempestifs.

En conclusion - pour des raisons de portabilité et de performance, la version forte est toujours une option meilleure ou égale.

La version faible ne peut être une meilleure option que si elle vous permet de sauter complètement les contre-mesures ABA ou si votre algorithme ne se soucie pas de l'ABA.