Les coroutines en langage C (2000)
(chiark.greenend.org.uk)- Quand un code producteur et un code consommateur s’échangent des données, réécrire l’un des deux sous forme de fonction appelée tend à noyer la structure de l’algorithme d’origine dans des transitions d’état
- Le modèle de coroutine à la Knuth permet à deux routines de sauvegarder leur position d’exécution et de se passer le contrôle, mais dans la structure d’appel fondée sur la pile du C, il est difficile de l’implémenter directement de manière portable
- L’astuce centrale de cet article consiste à utiliser la syntaxe C qui autorise des
casedans un sous-bloc deswitch, ainsi que la macro__LINE__, pour créer une machine à états implicite qui réentre à l’endroit situé après unreturn - Les macros
crBegin,crReturn,crFinishpermettent de conserver la structure de boucle d’origine d’un décompresseur et d’un parseur, mais les variables locales à préserver doivent êtrestatic, et il ne faut pas placercrReturndans unswitchexplicite ni sur la même ligne qu’un autrecrReturn - Dans le code réel, une variante améliorée qui passe une structure de contexte est nécessaire à cause des contraintes de réentrance et de multithreading, et
coroutine.hfournit à la fois les macros simplesscret les macros réentrantesccr
Problème de structure lors de la connexion d’un producteur et d’un consommateur
- Dans les gros programmes, il est fréquent qu’un code produise des données pendant qu’un autre les consomme, et décider lequel doit être appelant et lequel doit être appelé complique la conception
- L’exemple se compose de deux petites routines
- Le code de décompression par longueur de répétition lit l’entrée avec
getchar()et produit les caractères un par un avecemit() - Le parseur lit les caractères avec
getchar()et traite les séquences continues de lettres commeWORD, les autres caractères commePUNCT
- Le code de décompression par longueur de répétition lit l’entrée avec
- Prises séparément, les deux routines sont naturelles, mais pour que la sortie
emit()du décompresseur alimente directement l’entréegetchar()du parseur, il faut une structure pour les relier - On peut aussi résoudre cela avec un tube entre deux processus ou deux threads
emit()du décompresseur écrit dans le tube, etgetchar()du parseur lit à l’autre extrémité- Cette méthode est simple et robuste, mais lourde et peu portable, et on ne souhaite souvent pas séparer des threads pour une tâche simple
Perte de lisibilité lors de la réécriture d’une fonction
- La solution traditionnelle consiste à réécrire une extrémité du canal de communication sous la forme d’une fonction appelable
- Si l’on transforme le décompresseur en fonction qui renvoie un caractère par appel, le parseur existant peut appeler
decompressor()à la place degetchar() - Inversement, si l’on transforme le parseur en fonction appelée à chaque réception d’un caractère, le code de décompression existant peut appeler
parser()à la place deemit() - Il n’est pas nécessaire de transformer les deux : un seul côté suffit pour établir la connexion, mais le code réécrit devient bien plus difficile à lire que l’original
- Dans le décompresseur et le parseur d’origine, le déroulement de l’algorithme apparaît naturellement dans les boucles
- Dans la version réécrite, tout dépend de variables d’état
staticet de transitionsswitch, ce qui rend le format compressé ou la grammaire du parseur difficiles à lire dans le code
- Le but est donc de relier les deux sans réécrire explicitement l’un d’eux comme une machine à états
Les coroutines à la Knuth et les limites du C
- La solution de coroutine de Donald Knuth abandonne la distinction entre appelant et appelé, et traite les deux processus comme des entités coopératives de même niveau
- Le mécanisme d’appel de ce modèle diffère d’un appel de fonction ordinaire
- La position d’exécution courante est sauvegardée ailleurs que sur la pile
- L’exécution saute vers la position que l’autre routine avait enregistrée lors de sa dernière suspension
- Quand le décompresseur émet un caractère, il sauvegarde son compteur ordinal puis passe à la position sauvegardée du parseur
- Quand le parseur a besoin du caractère suivant, il sauvegarde son propre compteur ordinal puis revient à la position sauvegardée du décompresseur
- Le contrôle fait des allers-retours entre les deux routines autant que nécessaire
- Cette approche est théoriquement élégante, mais en pratique elle n’est possible qu’en assembleur
- Un langage de haut niveau comme le C repose sur une structure fondée sur la pile : lorsqu’on transfère le contrôle entre fonctions, l’une doit être l’appelant et l’autre l’appelé
- En C portable, l’approche de coroutine pure est à peine plus pratique que la solution par tube Unix
Imiter un « return and continue » en C
- En C, le comportement nécessaire est qu’une fonction appelée fasse un
return, puis, à l’appel suivant, reprenne juste après cereturn - Par exemple, il serait idéal qu’une fonction de la forme
for (i = 0; i < 10; i++) return i;renvoie successivement de 0 à 9 lorsqu’elle est appelée 10 fois - La première implémentation utilise une variable d’état et
goto- On place un label au début de la fonction et après chaque
return - Une variable
state, préservée entre les appels, indique le label de reprise suivant - Au début de la fonction,
switch(state)saute vers le bon label - Juste avant le
return, on enregistre dansstatele label auquel revenir lors de l’appel suivant
- On place un label au début de la fonction et après chaque
- Cette méthode fonctionne, mais la gestion manuelle des labels est lourde en maintenance
- Chaque nouveau
returnimpose de créer un label et de l’ajouter auswitchinitial - Quand on supprime un
return, il faut aussi supprimer le label correspondant - Il faut sans cesse maintenir la cohérence entre le corps de la fonction et la liste du
switch
- Chaque nouveau
Une machine à états dissimulée avec le Duff’s device
- Le célèbre Duff’s device exploite une particularité de la syntaxe C : les instructions
cased’unswitchpeuvent apparaître dans ses sous-blocs - Appliquée à l’astuce des coroutines, cette propriété permet au
switch, au lieu de choisir quelgotoexécuter, de se comporter lui-même comme un saut de réentrée - La forme de base est la suivante
- Un
static int statemémorise le prochain point de reprise - La fonction commence par
switch(state) { case 0: ... } - Juste avant un
return, on stocke dansstatela valeur ducasesuivant - Juste après le
return, on place le labelcasecorrespondant
- Un
- En emballant cela dans des macros, on obtient une interface qui ressemble à des coroutines
crBeginmasquestatic int state=0; switch(state) { case 0:crReturnenregistrestate, renvoie la valeur, puis place un labelcaseau même endroitcrFinishferme le bloc ouvert
crReturnest encapsulé dansdo ... while(0), ce qui évite les problèmes de syntaxe quand on l’utilise entreifetelsesans accolades- Au départ, il faut fournir explicitement le numéro d’état, comme dans
crReturn(1, i), mais la macro__LINE__de l’ANSI C permet d’utiliser le numéro de ligne source courant comme valeur d’état - Après cette amélioration, on peut écrire simplement
crReturn(x), au prix d’une nouvelle règle : il ne faut jamais mettre deuxcrReturnsur la même ligne
Règles d’utilisation des macros et exemples
- Les coroutines fondées sur des macros reposent sur quelques règles
- Il faut entourer le corps de la fonction avec
crBeginetcrFinish - Toute variable locale qui doit survivre au-delà d’un
crReturndoit être déclaréestatic - Il ne faut jamais placer
crReturndans unswitchexplicite - Avec l’implémentation fondée sur
__LINE__, il ne faut jamais mettre deuxcrReturnsur la même ligne
- Il faut entourer le corps de la fonction avec
- Dans l’exemple du décompresseur, la structure de boucle d’origine est conservée et l’on remplace
emit(c)parcrReturn(c)au moment d’émettre un caractère - Dans l’exemple du parseur, lorsqu’un nouveau caractère est nécessaire,
crReturn()redonne la main à l’appelant, puis l’exécution reprend à l’appel suivant avec le nouveau caractère reçu dans le paramètrec - Le parseur subit une petite modification structurelle
- Comme le premier caractère est déjà présent dans
cà l’entrée de la fonction, lecrReturncorrespondant augetchar()du début de la boucle d’origine est déplacé à la fin de la boucle - On pourrait aussi décider que le parseur nécessite un appel d’initialisation
- Comme le premier caractère est déjà présent dans
- Il n’est pas nécessaire de convertir les deux routines aux macros de coroutine : on peut n’en convertir qu’une et laisser l’autre jouer le rôle d’appelant
- Au final, la combinaison de l’ANSI C, du préprocesseur et d’une syntaxe peu utilisée de
switchpermet de transférer des données entre producteur et consommateur sans réécriture explicite en machine à états
Conflit entre standards de codage et clarté algorithmique
- Cette technique viole sévèrement les standards de codage habituels
- Elle contient des accolades déséquilibrées dans les macros
- Elle utilise des
casedans des sous-blocs crReturnmasque à la foisswitch,returnetcasedans une seule macro
- Des macros qui dissimulent ainsi la structure syntaxique peuvent être vues, du point de vue des standards de codage, comme nuisibles à la clarté
- Cependant, une fonction réécrite en machine à états explicite se compose elle aussi de petits blocs
case STATEet de transitions d’état, sans structure visuelle très différente d’une fonction qui enchaîne des blocs à labelsgoto - Plus une fonction est longue, plus la réécriture en machine à états détériore la structure algorithmique d’origine
- Cette technique est donc un compromis : elle cache une partie de la structure syntaxique afin de mieux faire ressortir la structure de l’algorithme
Variante réentrante et code fourni
- L’implémentation jouet la plus simple dépend de variables
static, donc n’est ni réentrante ni adaptée au multithreading - Dans une application réelle, il faut pouvoir appeler la même fonction dans plusieurs contextes, chacun devant reprendre après son propre dernier
return - L’amélioration consiste à passer un pointeur vers une structure de contexte comme paramètre supplémentaire
- L’état local et la variable d’état de coroutine deviennent des membres de cette structure
- Les variables comme un compteur de boucle doivent alors être accédées via
ctx->iau lieu dei - Le code devient un peu plus laid, mais le problème de réentrance disparaît tout en conservant la structure générale de la routine
- En C++, on peut faire des coroutines sous forme de membres de classe et stocker dans la classe l’état correspondant aux variables locales, ce qui gère plus naturellement les questions de portée
- Le fichier
coroutine.hfourni implémente cette astuce de coroutine sous forme d’un ensemble de macros prédéfinies- Les macros préfixées par
scrutilisent des variablesstaticdans la version simple - Les macros préfixées par
ccrcorrespondent à la version avancée réentrante - La documentation détaillée se trouve dans les commentaires du fichier d’en-tête
- Les macros préfixées par
- Visual C++ 6 gère bizarrement la macro
__LINE__avec le réglage de debug par défaut « Program Database for Edit and Continue », et supporte donc mal cette astuce- Pour compiler un programme utilisant ces coroutines avec VC++ 6, il faut désactiver Edit and Continue
- Dans les paramètres du projet, onglet « C/C++ », catégorie « General », il faut choisir une option de « Debug info » autre que « Program Database for Edit and Continue »
- Le fichier d’en-tête est distribué sous licence MIT
Références associées et usage réel
- The Art of Computer Programming de Donald Knuth, volume 1, section 1.4.2, traite des coroutines sous leur forme pure
- Dans la discussion de Tom Duff sur le Duff’s device, certains éléments suggèrent qu’il a pu imaginer indépendamment une astuce de coroutine similaire, ce que Tom Duff a confirmé dans un commentaire de blog lors d’une mise à jour du 2005-03-07
- Le code du protocole SSH de PuTTY utilise réellement cette astuce de coroutine
- Le cas de PuTTY montre un niveau de bidouillage C particulièrement poussé, rare dans du code de production sérieux
1 commentaires
Avis sur Hacker News
Je suis revenu plusieurs fois sur cette page en essayant de réduire la complexité de l’API dans un projet C, et je trouve l’explication du flux de contrôle excellente.
Elle m’a aussi aidé à réfléchir plus clairement aux différences de lisibilité entre les approches, ainsi qu’à la sauvegarde de l’état dans et hors de la pile.
Ma conclusion actuelle est qu’il vaut mieux laisser aux utilisateurs de la bibliothèque le choix d’utiliser ou non les coroutines en C. Par exemple, Mongoose(https://github.com/cesanta/mongoose) gère l’asynchrone via des callbacks d’événements ; pour ce type de bibliothèque, il est bien plus agréable de l’envelopper avec les primitives de threads/tâches propres à chaque système, plutôt que d’essayer de la porter vers de mythiques coroutines C multiplateformes, ou pire, vers
std::thread.[1] https://www.chiark.greenend.org.uk/~sgtatham/putty/
[2] https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
Les coroutines sont un concept vraiment élégant, et les vidéos de la CppCon sur les coroutines C++, présentées surtout par des gens de chez Microsoft, sont particulièrement plaisantes à regarder. L’accroche « abstraction à coût négatif » est aussi assez bonne.
Il y a quelques années, des amis chez Meta ont commencé à utiliser les coroutines C++ et m’ont dit que cela avait finalement été une grosse erreur. Ils ont dû affronter des bugs d’implémentation dans les compilateurs, qui ont probablement été assez pénibles à traquer. Chez Google, on attend que les personnes compétentes qui intègrent correctement cela dans google3/ nous disent que l’on peut maintenant s’en servir.
Cet article explique, via le dispositif de Duff [1], une forme de
gotostructuré à base de macros comme stratégie d’implémentation des coroutines en C. Le point clé est que l’on peut placer des instructionscasepresque n’importe où dans un blocswitch; on enveloppe alors toute la fonction dans unswitch, on stocke dans une variablestaticle dernier point de retour de la coroutine, et on étiquette chaquecoReturnavec uncase.L’article de Sustrik sur les coroutines en C peut aussi être intéressant [2].
[1] https://en.wikipedia.org/wiki/Duff%27s_device
[2] https://250bpm.com/blog:48/index.html
co_yield,co_returnouco_awaitdisséminé un peu partout dans le code C++ a à la fois des avantages et des inconvénients.L’avantage par rapport à l’approche interne de google3, c’est qu’à la lecture du code, l’asynchronicité de chaque partie est explicite. Certains programmeurs chez Google ne connaissaient le modèle de threading qu’au niveau d’une branche, voire pas au-delà, et finissaient plus tard par créer de graves bugs.
L’inconvénient est plus simple : comme beaucoup de code « peut être asynchrone », avec le temps tout devient asynchrone simplement parce que les programmeurs écrivent dans ce mode. Le choix entre un spinlock et un mutex qui cède la main devrait dépendre de la taille de la section critique et de la situation de threading du moment, mais quand on cherche la lisibilité et la cohérence, tout le projet a facilement tendance à pencher d’un seul côté.
J’aimerais en savoir plus sur des implémentations de langages de threading qui ne prendraient pas l’un des deux côtés comme valeur par défaut, et qui optimiseraient davantage l’exécution suivante à partir du profil de l’exécution précédente, sans changement de code ni bug.
lc-addrlabels.h.J’ai aussi utilisé la fonctionnalité de labels locaux de GCC pour éviter complètement l’usage de
__LINE__, ce qui permettait même d’avoir plusieurscoReturnsur une même ligne.casepresque n’importe où dans un blocswitch, mais cette possibilité elle-même est presque certainement une fonctionnalité intentionnelle.Comme le dit aussi le bas de l’article, Duff a compris qu’on pouvait construire des coroutines par-dessus, mais il trouvait cette idée « dégoûtante ».
Si l’on considère le
switchdu C comme une sorte de pattern matching peu expressif, le « fallthrough » peut facilement ressembler à un bug, mais ce n’en est pas un. C’est de la même famille que legotocalculé de Fortran, en plus pratique, car les valeurs n’ont pas besoin d’être contiguës et il n’est pas nécessaire d’énumérer tous les labels en haut. En l’écrivant, je me dis que cela ressemble peut-être encore plus à unCOMEFROMcalculé.Dire qu’« aucun langage de haut niveau largement utilisé ne prend en charge les coroutines » pouvait être vrai en 2000, mais aujourd’hui de nombreux langages les prennent en charge, notamment C++20, Lua, Python, Ruby.
yieldexistait déjà à l’époque, ou qu’il est apparu peu après.La proposition d’amélioration à la fin de l’article — « ajouter un pointeur vers une structure de contexte comme argument supplémentaire de la fonction, et déclarer tout l’état local ainsi que les variables d’état de la coroutine comme membres de cette structure » — ressemble à une implémentation de closures. On dirait que l’appelé devient une lambda et utilise les variables externes/le contexte/l’état pour décider quoi faire ou avec quelles valeurs ; je me demande si je comprends bien.
L’approche avec
switchn’est pas rarissime, mais on utilise généralement un pointeur d’état passé à la fonction d’initialisation et à la fonction coroutine.J’ai souvent utilisé cette méthode dans des projets embarqués : une coroutine gérait l’accélération/décélération du moteur, tandis qu’une autre indiquait simplement dans quelle direction aller. Je l’ai aussi déjà utilisée dans une bibliothèque réseau[1]. La bibliothèque standard contient également des fonctions de type coroutine, comme
strtok()[2].Pour rendre ça gérable, il n’est pas nécessaire d’aller jusqu’à l’enfer des macros, mais je n’ai jamais pris plaisir à lire un flot
switch/case.[1]: https://github.com/REONTeam/libmobile/blob/master/relay.c#L3...
[2]: https://manpages.debian.org/bookworm/manpages-dev/strtok.3.e...
Il y a aussi Simon Tatham's Portable Puzzle Collection, du même auteur.
https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
Si cela ressemble à de la magie noire en C, l’article du même auteur sur la création de structures de contrôle arbitraires avec des macros vaut aussi la lecture : https://www.chiark.greenend.org.uk/~sgtatham/mp/
Les coroutines sont amusantes, mais dans du vrai code il faut aussi envisager d’utiliser de vrais threads. Les processeurs modernes ont beaucoup de cœurs, alors que les coroutines n’utilisent souvent qu’un seul cœur.
C’est aussi un vrai problème. Jusqu’à récemment, qemu, qui utilise beaucoup les coroutines, envoyait une bonne partie des E/S de périphériques bloc vers un seul thread, ce qui posait des problèmes de performance. Kevin Wolf et d’autres ont corrigé cela pendant des années, si bien que qemu moderne utilise désormais plusieurs threads pour les E/S, et ce travail devrait arriver dans RHEL 9.4.
Une coroutine est une manière de structurer une exécution monothread, et elle est utile en soi. Le schéma producteur-consommateur de l’exemple de l’article en est une bonne illustration ; raccorder un flux à un parseur n’est pas un algorithme parallèle, donc les threads ne sont d’aucune utilité pour l’écrire.
Utiliser un paradigme monothread pour des tâches parallélisables est évidemment inefficace, mais les coroutines ne sont pas du parallélisme du pauvre : ce sont des structures de contrôle qui ont un sens propre. Elles peuvent aussi se combiner productivement avec des threads, par exemple comme dans un serveur web où une boucle d’événements, avec un dispatcher, fait circuler des coroutines entre plusieurs événements bloquants ; et si le runtime parallélise en lançant un thread par cœur, la coordination entre threads peut se réduire à vérifier la profondeur de chaque file de tâches et à envoyer la requête du côté le moins chargé.
L’idée des coroutines est de les utiliser quand on a un travail local et des données synchrones, et qu’il est plus simple de l’exprimer sous une forme inversée où une fonction boucle sur quelque chose et « pousse » les résultats vers un consommateur abstrait situé ailleurs, plutôt que dans un paradigme fonctionnel où l’appelant « tire » la boucle interne.
Ensuite, on déplace très rarement les coroutines d’un planificateur à l’autre, et on partage très rarement des données entre des coroutines appartenant à des planificateurs différents.
Grâce à l’ordonnancement coopératif, les coroutines permettent un style de programmation concurrente pratique, sans aucun verrou. En général, les délais d’ordonnancement sont plus élevés, mais comme la surcharge des opérations atomiques/verrous disparaît et qu’aucun timer n’interrompt constamment l’exécution pour l’ordonnancement préemptif, le débit peut devenir assez élevé.
Version C++ de cette approche : https://www.codeproject.com/Tips/29524/Generators-in-C
Je l’utilise aussi dans mon Sciter, au cas où, et cela fonctionne plutôt bien tout en étant pratique.
La façon d’obtenir cela de manière modulaire et sûre serait probablement les gestionnaires d’effets. C’est proche du
yieldde Python, mais cela peut renvoyer des valeurs, et ce n’est pas limité aux appels de fonction : la portée se comporte comme celle des exceptions. Si vous ne connaissez pas, cet article est une bonne motivation.Chaque fonction écrite en style direct peut effectuer un « effet » lorsque le contrôle doit passer ailleurs. Ici, ce serait le cas de
c=getchar()etemit(c).Le contrôle passe alors au gestionnaire d’effets, et dans ce cas ce serait probablement l’appelant des deux fonctions qui déciderait quoi faire ensuite. Quand le décompresseur émet un caractère, on le transmet au code du parseur et on le reprend ; on continue jusqu’à ce que le parseur en demande davantage, puis on reprend à nouveau le décompresseur, et ainsi de suite.
Les effets peuvent être implémentés efficacement, surtout si l’on impose que la continuation ne puisse être appelée qu’une seule fois. C’est le cas d’OCaml. Cela permet du code en style direct avec sûreté de typage et de mémoire, et c’est aussi très utile dans les environnements concurrents.
Exemple ici : https://effekt-lang.org/docs/casestudies/lexer
Je ne suis pas du tout d’accord avec le passage disant que « cette astuce enfreint évidemment toutes les normes de codage… je soutiendrais que ce sont les normes de codage qui ont tort »
Ce n’est pas une erreur si une norme de codage rejette ce code : ce n’est qu’une petite astuce mignonne. Le génie logiciel à grande échelle consiste à éliminer les surprises et à produire du code lisible même par une personne en manque de sommeil appelée à 3 h du matin pour le déboguer. On ne peut pas attendre des programmeurs qu’ils gardent toujours en tête quatre règles de base
J’ai aussi du mal à accepter l’idée selon laquelle cacher des éléments importants comme
switch,returnetcasedans des macros « d’obfuscation » aurait brouillé la structure syntaxique tout en révélant la structure algorithmique. Un bon programme doit avoir une structure syntaxique et une structure algorithmique toutes deux claires, et cette approche n’est pas à la hauteur. À mon avis, la façon dont Rust crée implicitement une machine à états dans les fonctionsasyncdevrait servir de modèle iciDans le monde C, même l’opérateur conditionnel ternaire est trop audacieux, et C99 est traité comme une nouveauté. Dans le monde C++, la seule raison de déconseiller la métaprogrammation par templates est que le standard utilisé permet de faire la même chose avec
constexpr