De la nécessité d’adopter les opérations atomiques C11 ?

50
1
mar.
2018
Linux

Jonathan Corbet, fondateur de LWN et contributeur au noyau Linux, a publié en juin 2016 un article important sur l’apport de la dernière version du langage C dans les recherches d’optimisation du noyau. En voici une traduction.

N. D. M. : Les articles publiés sur LWN le sont généralement sous licence Creative Commons Attribution-ShareAlike 4.0 (CC BY-SA 4.0)

Un programme typique écrit en C consiste en un nombre déterminé d’opérations organisées dans un ordre spécifique. Au‐delà de la sphère d’influence du programmeur, toutefois, le compilateur comme le processeur sont susceptibles de modifier l’ordonnancement des opérations afin d’optimiser le temps d’exécution du programme. Si, dans le cadre d’un fil d’exécution unique, réordonnancer les opérations sans pour autant casser le programme reste une tâche relativement simple, tel n’est plus le cas lorsque plusieurs fils d’exécution se partagent un même espace mémoire. Dans ce dernier cas, les programmeurs en sont souvent réduits à définir explicitement les besoins d’ordonnancement.

Pour répondre à cette problématique, un certain nombre de barrières mémoire et d’opérations atomiques ont été mises au point dans le noyau afin de préserver l’ordre des accès mémoire lorsque c’est nécessaire, avec un minimum d’impact en termes de performances. La version C11 du langage C tente de répondre à cette même problématique avec son propre système de barrières. Ce qui incite à se poser la question : le noyau devrait‐il abandonner ses propres opérations au profit de celles définies par le standard C11 ?

Cette question a été soulevée pour la dernière fois en 2014 ; voir l’article LWN à ce sujet pour une meilleure compréhension de la toile de fond : comment les opérations atomiques de C11 fonctionnent et comment les accès mémoire concurrents peuvent mal tourner faute de contrôle suffisant sur l’ordonnancement des opérations. Dorénavant, la prise en charge des opérations atomiques de C11 par les compilateurs s’est améliorée et David Howells a mis au point une implémentation complète des opérations atomiques du noyau (x86) à partir de celles de C11. Cette implémentation est somme toute assez simple, comme l’illustrent par exemple les fonctions atomic_read() ci‐dessous :

    static __always_inline int __atomic_read(const atomic_t *v, int memorder)
    {
    return __atomic_load_n(&v->counter, memorder);
    }
    #define atomic_read(v)      (__atomic_read((v), __ATOMIC_RELAXED))
    #define atomic_read_acquire(v)  (__atomic_read((v), __ATOMIC_ACQUIRE))

Ces correctifs de David prouvent clairement que la conversion est possible. Cependant, la vraie question est celle de sa pertinence : comme peut‐on s’en douter, il y a des arguments pour et d’autres contre.

La bascule vers les opérations atomiques de C11 devrait en théorie permettre au noyau de s’affranchir de nombreuses portions de code délicates, spécifiques à l’architecture, pour tirer avantage d’un code équivalent, intégré au compilateur, que les programmes concurrents, en espace utilisateur, utiliseront également. L’usage des opérations atomiques de C11 offre au compilateur une meilleure visibilité sur ce que réalise effectivement le code, ouvrant ainsi la voie à de plus grandes possibilités d’optimisation et permettant l’usage d’instructions autrement difficiles à invoquer depuis du code assembleur. Le compilateur peut en outre sélectionner une instruction adaptée à la taille de l’opérande : ce qui aiderait à éliminer le temps de compilation conséquent induit par les multiples instructions switch actuellement présentes dans les fichiers d’en‐tête du noyau.

Les optimisations possibles ne sont pas encore complètement implémentées avec les compilateurs actuels, mais le potentiel est là pour permettre, à terme, aux compilateurs de produire du code encore plus efficace que du code assembleur, si optimisé soit‐il. Comme l’a dit Paul McKenney :

Je suis d’accord qu’il risque d’être bien difficile aux mécanismes internes de C11 de surpasser du code assembleur bien ajusté. Mais il ne devrait pas se passer trop longtemps avant que l’on voie les compilateurs générer un code plus performant que de l’assembleur « standard ». Et il se pourrait bien qu’à terme les compilateurs surpassent même de l’assembleur optimisé dans certains cas parmi les plus complexes, comme les boucles cmpxchg [N. D. T. : cmpxchg : instruction Intel compare and exchange — comparer et échanger].

Il y a aussi un aspect bénéfique de permettre au compilateur d’isoler certaines barrières spécifiques hors des opérations atomiques, pour des gains de performance, chose irréalisable dans le cas d’opérations codées directement en assembleur.

Il y a aussi bien sûr des inconvénients à faire cette bascule. L’un d’entre eux est que les opérations atomiques de C11 ne sont pas toujours bien implémentées dans les compilateurs, sauf pour les plus récents. En effet, David a indiqué « [qu’]il faudra faire avec une génération de code loin d’être optimale avec gcc, avant la version 7.1 » — version qui ne devrait pas être distribuée avant au moins un an. Et, comme on pouvait s’y attendre, le projet s’accompagne de multiples bogues ; s’ils ont été dûment rapportés et corrigés, il est fort probable que d’autres soient encore à venir. Sur le long terme, l’usage des opérations atomiques de C11 dans le noyau devrait certainement induire une meilleure implémentation du compilateur, mais y parvenir ne se fera pas sans douleur.

Si un noyau construit pour un système multiprocesseur venait à fonctionner sur une machine monoprocesseur, alors il corrigerait son code pour éliminer les inutiles instructions de synchronisation. En utilisant les opérations atomiques de C11, cette correction n’est plus applicable : impossible de localiser ces instructions, la moindre modification par le compilateur provoquerait une confusion énorme. Les systèmes monoprocesseurs se font certes de plus en plus rares et sans doute des noyaux spécifiques ont déjà été construits pour la plupart d’entre eux, mais il n’en reste pas moins préférable d’éviter de rendre ces systèmes encore plus lents.

Cependant, l’écueil le plus potentiellement difficile à surmonter est dû au fait que le modèle de mémoire implémenté dans C11 n’est pas tout‐à‐fait conforme à celui du noyau. Le premier repose sur une sémantique acquérir/relâcher — des barrières unidirectionnelles, décrites dans l’article de 2014 et celui‐ci. La majeure partie du noyau fait au contraire usage de barrières charger/enregistrer, plus strictes et bidirectionnelles. Une écriture en mémoire avec la sémantique relâcher ne se finalisera qu’une fois que toutes les opérations préalables de lecture ou d’écriture sont visibles du système, mais permet à d’autres opérations, logiquement faites après l’écriture, d’être réorganisées de façon à advenir avant cette même écriture. Au lieu de quoi la sémantique enregistrer met en œuvre un strict ordonnancement des autres opérations d’écriture de chaque côté de la barrière.

Une option serait d’affaiblir le modèle mémoire du noyau, de façon que les architectures reposant sur la sémantique acquérir/relâcher puissent bénéficier du gain de performances associé. Mais l’on peut s’attendre à voir un tel changement s’accompagner de son lot de bogues, bien subtils et difficiles à traquer. Cela mérite donc prudence et attention. Cela dit, David précise que l’architecture PowerPC semble déjà fonctionner avec un modèle plus faible, signe qu’il pourrait n’y avoir que peu de sources de problèmes traînant dans le noyau.

Comme l’a signalé Will Deacon, les opérations atomiques de C11 pèchent par manque d’implémentation des opérations sur les consommations des ressources (consume load), qui constituent une grande part du mécanisme RCU (read‐copy‐update — lecture‐copie‐mise à jour), entre autres. Une consommation de ressources pourrait toujours être remplacée avec la sémantique acquérir, mais au prix de performances amoindries. Plus généralement, Will s’inquiète de ce que le modèle C11 est très mal adapté à l’architecture ARM, et que la bascule aurait conséquemment des chances de résulter en une combinaison maladroite d’opérations spécifiques à C11 et au noyau, reconnaissant pour autant qu’une implémentation générique basée sur C11 et ses opérations atomiques serait fort utile aux développeurs qui portent le noyau sur de nouvelles architectures.

À ce stade, les discussions sur le sujet ont été bien moins animées que deux ans auparavant : peut‐être les développeurs se sont‐ils résignés à l’idée que ce changement est inéluctable, même s’il semble encore prématuré. Et, en effet, il y aurait des avantages certains à ce changement, tant côté compilateur que noyau. Mais, quant à savoir si ces avantages justifient le coût de la mise en œuvre, cela reste sujet à caution.

  • # Français

    Posté par . Évalué à 1 (+1/-1).

    La bascule vers les opérations atomiques de C11 devrait en théorie permettre au noyau de s’affranchir de nombreuses portions de code délicates, spécifiques à l’architecture, pour tirer avantage d’un code équivalent, intégré au compilateur, que les programmes concurrents, en espace utilisateur, utiliseront de même.

    Ce n'est pas plutôt "utiliseront d'eux-mêmes" ?

    • [^] # Re: Français

      Posté par . Évalué à 4 (+3/-0). Dernière modification le 01/03/18 à 17:30.

      les opérations atomiques de C11 pêchent par manque d’implémentation des opérations

      Comme elles n'ont pas d'implémentation des opérations, les opérations atomiques vont à la pêche au thon et à la morue ? ;)

      "pécher par", de "pécher", qui a deux sens : "commettre une faute contre la loi divine" ou "faillir, manquer". Source

      EDIT : mis à part ce que j'ai relevé, je trouve que la qualité de la traduction en tant que telle est excellente, bravo !

    • [^] # Re: Français

      Posté par . Évalué à 2 (+0/-0).

      Bah, non, c’est « de même » dans le sens « également, aussi, itou ».

      • [^] # Re: Français

        Posté par . Évalué à 2 (+0/-0).

        Cependant, l’écueil le plus potentiellement difficile à surmonter est dû au fait que le modèle de mémoire implémenté dans C11 n’est pas tout‐à‐fait conforme à celui du noyau.

        Cependant, l’écueil potentiellement le plus difficile à surmonter est dû au fait que le modèle de mémoire implémenté dans C11 n’est pas tout‐à‐fait conforme à celui du noyau.

  • # Réordonnancement étrange...

    Posté par . Évalué à 2 (+0/-0).

    La majeure partie du noyau fait au contraire usage de barrières charger/enregistrer, plus strictes et bidirectionnelles. Une écriture en mémoire avec la sémantique relâcher ne se finalisera qu’une fois que toutes les opérations préalables de lecture ou d’écriture sont visibles du système, mais permet à d’autres opérations, logiquement faites après l’écriture, d’être réorganisées de façon à advenir avant cette même écriture.

    Dans quel cas un tel réordonnancement se justifie-t-il ?

    • [^] # Re: Réordonnancement étrange...

      Posté par . Évalué à 4 (+1/-0).

      Cela se justifie par les performances, regrouper des opérations prends moins de temps que de les fragmenter (Lecture/écriture depuis les write cache).

      "La première sécurité est la liberté"

    • [^] # Re: Réordonnancement étrange...

      Posté par (page perso) . Évalué à 6 (+4/-0).

      Dans quel cas un tel réordonnancement se justifie-t-il ?

      Le ré-ordonnancement est une optimisation importante du compilateur. Un truc important est de générer du code qui minimise les dépendances immédiates entre deux instructions. Par exemple (si R0 et R1 sont des registres) :

      charger 12 dans R0
      charger 42 dans R1
      utiliser R0
      utiliser R1
      

      Ici l'instruction « charger 42 dans R1 » peut s'exécuter alors que « charger 12 dans R0 » n'est pas terminée (exécution pipelinée). Par contre, si on avait écrit :

      charger 12 dans R0
      utiliser R0
      charger 42 dans R1
      utiliser R1
      

      alors le processeur serait obligé d'attendre la fin des instructions « charger » avant les instructions « utiliser » correspondantes. Les performances seraient moins bonnes pour le même comportement.

      • [^] # Re: Réordonnancement étrange...

        Posté par (page perso) . Évalué à 3 (+1/-0).

        alors le processeur serait obligé d'attendre la fin des instructions « charger » avant les instructions « utiliser » correspondantes.

        Non, les processeurs font plein d'opérations en parallèle et ré-ordonne les instructions pour pouvoir les exécuter plus vite. (parfois même de manière spéculative)

        En fait c'est le contraire: On utilise les opération atomique pour dire au compilateur d'introduire des barrières dans le code pour que le processeur ne ré-ordonne pas ces opérations.

        • [^] # Re: Réordonnancement étrange...

          Posté par (page perso) . Évalué à 3 (+1/-0).

          Non, les processeurs font plein d'opérations en parallèle et ré-ordonne les instructions pour pouvoir les exécuter plus vite.

          Bien sûr, mais le processeur ne peut pas exécuter une opération (par exemple "ADD x, y") quand il n'a pas les données correspondantes (x et y). On peut essayer de spéculer, mais sur un truc aussi bête qu'une addition, on ne va pas spéculer les 2^{32} additions possibles s'il manque un opérande … Techniquement, le ré-ordonnancement peut éviter les bulles dans le pipeline.

          Bien sûr, tout dépend de l'architecture cible. Tous les processeurs ne réordonnent pas les instructions. Les processeurs Intel le font très bien sur mon exemple donc le compilateur x86 n'a pas besoin de se soucier de ce cas, mais tous les processeurs ne sont pas out-of-order comme ça il y a des tas d'architectures où c'est au compilateur de faire ce boulot.

          En fait c'est le contraire: On utilise les opération atomique pour dire au compilateur d'introduire des barrières dans le code pour que le processeur ne ré-ordonne pas ces opérations.

          Euh, pas compris le contraire de quoi. On dit la même chose là ;-).

          • [^] # Re: Réordonnancement étrange...

            Posté par (page perso) . Évalué à 2 (+0/-0).

            Bien sûr, mais le processeur ne peut pas exécuter une opération (par exemple "ADD x, y") quand il n'a pas les données correspondantes (x et y)

            Tout ne peux pas être éxécuter dans n'importe quel ordre. Je réagissait au fait que tu disait que « Le ré-ordonnancement est une optimisation importante du compilateur », alors que dans le contexte du message auquel tu réponds, ce n'est pas le compilateur, mais le CPU qui ré-ordonne.

            le contraire de quoi

            Le contraire du fait que les compilateurs doivent ordonnés les instructions dans le bon sans pour aider le CPU. (Mais c'est vrai que le compilateur à quand même encore des possibilité d'optimisations.)

            • [^] # Re: Réordonnancement étrange...

              Posté par (page perso) . Évalué à 2 (+0/-0).

              dans le contexte du message auquel tu réponds, ce n'est pas le compilateur, mais le CPU

              Bah non justement. C'est le couple (compilateur, processeur), et deux peuvent réordonner. Si ce n'était qu'un problème de CPU, la gestion des atomics à l'ancienne à coups de bibliothèque suffirait. La nécessité d'introduire ces opérations dans le langage, c'est pour donner la visibilité au compilateur sur ces opérations et permettre non-seulement les barrières mémoire, mais aussi les barrières de compilation.

              Par exemple, sur x86, le modèle mémoire est assez fort pour que la plupart des opérations atomiques puissent être compilées par un bête mov (regarde le code généré par un acquire ou un release si tu n'es pas convaincu. Perso je n'y croyais pas avant d'avoir vérifié ;-) ). La différence entre une opération atomique et une non-atomique est justement la barrière de compilation, pas la barrière mémoire qui n'est pas utile dans ce cas.

              • [^] # Re: Réordonnancement étrange...

                Posté par (page perso) . Évalué à 2 (+0/-0).

                Permet moi d'être en désacord sur les détails.

                Si ce n'était qu'un problème de CPU, la gestion des atomics à l'ancienne à coups de bibliothèque suffirait.

                Bah non justement, un appel à une fonction d'une bibliothèque est déjà une barrière complète pour le compilateur. Mais pas pour le CPU.

                Par contre, si ce n'était qu'un problème de ré-ordonnancement par le compilateur, la gestion à coup de volatile suffirait.

                • [^] # Re: Réordonnancement étrange...

                  Posté par (page perso) . Évalué à 2 (+0/-0).

                  un appel à une fonction d'une bibliothèque est déjà une barrière complète pour le compilateur. Mais pas pour le CPU.

                  La bibliothèque peut très bien insérer les barrières à coups de __asm(). C'est ce que tout le monde faisait avant C/C++11.

                  Par contre, si ce n'était qu'un problème de ré-ordonnancement par le compilateur, la gestion à coup de volatile suffirait.

                  Seulement si on est prêt à ruiner les perfs du programme. Cf. par exemple :

                  https://github.com/torvalds/linux/blob/master/Documentation/process/volatile-considered-harmful.rst

                  Les opérations atomiques permettent des barrières beaucoup plus fines (release, acquire, sequential consistency), donc beaucoup plus de contrôle sur les optimisations.

        • [^] # Re: Réordonnancement étrange...

          Posté par . Évalué à 3 (+0/-0).

          Les dépendances read-after-write sont importantes surtout sur les "cpu simples", mais avec les monstres que sont les X86, la taille de la fenêtre d'observation permet d'aller aux instructions suivantes.

          Le regroupement des load&store peut potentiellement avoir beaucoup d'impact de performance, car le cpu ne peut pas faire un store et un load en parallèle, il est obliger de vérifier qu'il n'est pas entrain de relire ce qu'il vient d'écrire.

          "La première sécurité est la liberté"

Envoyer un commentaire

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.