Les coroutines C++20 sans pile posent-elles un problème ?

Question

Sur la base de ce qui suit, il semble que les coroutines dans C++20 seront sans pile.

https://en.cppreference.com/w/cpp/language/coroutines

Je suis inquiet pour de nombreuses raisons :

1. Sur les systèmes embarqués, l'allocation du tas n'est souvent pas acceptable.
2. Dans du code de bas niveau, l'imbrication de co_await serait utile (je ne crois pas que les co-routines de stackless le permettent).

Avec une coroutine sans pile, seule la routine de premier niveau peut être suspendue. Toute routine appelée par cette routine de niveau supérieur ne peut pas elle-même suspendre. Ceci interdit de fournir des opérations de suspension/reprise dans des routines routines dans une bibliothèque générale.

https://www.boost.org/doc/libs/1_57_0/libs/coroutine/doc/html/coroutine/intro.html#coroutine.intro.stackfulness

3. Un code plus verbeux en raison de la nécessité de recourir à des allocateurs personnalisés et à la mise en commun de la mémoire.

4. Plus lent si la tâche attend que le système d'exploitation lui alloue de la mémoire (sans mise en commun de la mémoire).

Compte tenu de ces raisons, j'espère vraiment me tromper sur la nature des coroutines actuelles.

La question comporte trois parties :

1. Pourquoi le C++ choisirait-il d'utiliser des coroutines sans pile ?
2. Concernant les allocations pour sauver l'état dans les coroutines sans pile. Puis-je utiliser alloca() pour éviter toute allocation du tas qui serait normalement utilisée pour la création de la coroutine.

L'état de la coroutine est alloué sur le tas par l'intermédiaire d'un tableau non linéaire. non matriciel. https://en.cppreference.com/w/cpp/language/coroutines

3. Mes hypothèses sur les coroutines c++ sont-elles fausses, pourquoi ?

EDIT :

Je suis en train de parcourir les discussions cppcon pour les coroutines, si je trouve des réponses à mes propres questions, je les posterai (rien jusqu'à présent).

CppCon 2014 : Gor Nishanov "Attendez 2.0 : Stackless Resumable Functions"

https://www.youtube.com/watch?v=KUhSjfSbINE

CppCon 2016 : James McNellis "Introduction aux coroutines C++" (en anglais)

https://www.youtube.com/watch?v=ZTqHjjm86Bw

Answer 1

J'utilise des coroutines sans pile sur de petites cibles ARM Cortex-M0 en temps réel dur, avec 32kb de RAM, où il n'y a pas du tout d'allocateur de tas : toute la mémoire est statiquement pré-allouée. Les coroutines sans pile sont un facteur déterminant, et les coroutines avec pile que j'utilisais auparavant étaient difficiles à mettre en place, et étaient essentiellement un hack entièrement basé sur un comportement spécifique à l'implémentation. Passer de cette pagaille à un C++ portable et conforme aux normes a été merveilleux. Je frémis à l'idée que quelqu'un puisse suggérer de revenir en arrière.

• Les coroutines sans pile n'impliquent pas l'utilisation du tas : vous avez contrôle total sur la façon dont le cadre de la coroutine est alloué (par l'intermédiaire de void * operator new(size_t) dans le type de promesse).

• co_await peuvent être imbriqués sans problème En fait, c'est un cas d'utilisation courant.

• Les coroutines à pile doivent également allouer ces piles quelque part, et il est peut-être ironique de constater qu'elles ne peut pas utiliser la pile primaire du thread pour cela. . Ces piles sont allouées sur le tas, peut-être via un allocateur de pool qui récupère un bloc du tas et le subdivise ensuite.

• Les implémentations de coroutine sans pile peuvent éluder l'allocation de trame, de sorte que la promesse operator new n'est pas appelé du tout, alors que les coroutines stackful allouent toujours la pile pour la coroutine, que cela soit nécessaire ou non, parce que le compilateur ne peut pas aider le runtime de la coroutine à l'élider (du moins pas en C/C++).

• Les allocations peuvent être évitées précisément en utilisant la pile où le compilateur peut prouver que la vie de la coroutine ne quitte pas la portée de l'appelant. Et c'est la seule façon d'utiliser la fonction alloca . Ainsi, le compilateur s'en occupe déjà pour vous. Comme c'est cool !

  Maintenant, il n'y a aucune exigence que les compilateurs fassent réellement cette élision, mais AFAIK toutes les implémentations le font, avec des limites raisonnables sur la complexité de cette "preuve" - dans certains cas, ce n'est pas un problème décidable (IIRC). De plus, il est facile de vérifier si le compilateur a fait ce que vous attendiez : si vous savez que toutes les coroutines avec un type de promesse particulier sont nested-only (raisonnable dans les petits projets embarqués mais pas seulement !), vous pouvez déclarer operator new dans le type de promesse mais sans le définir, et le code ne sera pas lié si le compilateur s'est "planté".

  Un pragma pourrait être ajouté à une implémentation particulière du compilateur pour déclarer qu'une frame coroutine particulière ne s'échappe pas même si le compilateur n'est pas assez intelligent pour le prouver - je n'ai pas vérifié si quelqu'un s'est donné la peine d'écrire cela, parce que mes cas d'utilisation sont suffisamment raisonnables pour que le compilateur fasse toujours la bonne chose.

  La mémoire allouée avec alloca ne peut pas être utilisée après le retour de l'appelant. Le cas d'utilisation de alloca en pratique, est une façon légèrement plus portable d'exprimer l'extension automatique des tableaux de taille variable de gcc.

Dans pratiquement toutes les implémentations de coroutines empilées dans des langages de type C, la fonction le seul et unique Le "bénéfice" supposé de l'empilement est que l'on accède à la trame en utilisant l'adressage habituel base-pointeur-relatif, et que l'on peut accéder à la trame en utilisant l'adressage de base-pointeur-relatif. push y pop le cas échéant, de sorte que le code C "ordinaire" peut fonctionner sur cette pile inventée, sans modification du générateur de code. Aucun benchmark ne supporte ce mode de pensée, cependant, si vous avez beaucoup de coroutines actives - c'est une bonne stratégie s'il y en a un nombre limité, et que vous avez la mémoire à gaspiller pour commencer.

La pile doit être surallouée, ce qui diminue la localité de référence : une coroutine typique avec pile utilise au minimum une page complète pour la pile, et le coût de la mise à disposition de cette page n'est partagé avec rien d'autre : la coroutine unique doit tout supporter. C'est pourquoi il valait la peine de développer un python sans pile pour les serveurs de jeux multi-joueurs.

S'il n'y a que quelques couroutines - pas de problème. Si vous avez des milliers de requêtes réseau, toutes traitées par une pile de coroutines, avec une pile réseau légère qui n'impose pas de surcharge monopolisant les performances, les compteurs de performance pour les manques de cache vous feront pleurer. Comme Nicol l'a indiqué dans l'autre réponse, cela devient moins pertinent au fur et à mesure qu'il y a des couches entre la coroutine et l'opération asynchrone qu'elle gère.

Il y a longtemps que les processeurs 32+ bits n'ont plus d'avantages en termes de performances inhérents à l'accès à la mémoire via un mode d'adressage particulier. Ce qui compte, ce sont les modèles d'accès respectueux du cache et l'exploitation de la préextraction, de la prédiction de branchement et de l'exécution spéculative. La mémoire paginée et sa mémoire de sauvegarde ne sont que deux niveaux supplémentaires de cache (L4 et L5 sur les processeurs de bureau).

1. Pourquoi le C++ choisirait-il d'utiliser des coroutines sans pile ? Parce qu'ils sont plus performants, et pas moins. Du côté des performances, elles ne peuvent avoir que des avantages. C'est donc une évidence, du point de vue des performances, de les utiliser.

2. Puis-je utiliser alloca() pour éviter toute allocation de tas qui serait normalement utilisée pour la création de la coroutine. Non. Ce serait une solution à un problème inexistant. Les coroutines Stackful ne s'allouent pas réellement sur la pile existante : elles créent de nouvelles piles, et celles-ci sont allouées sur le tas par défaut, tout comme les cadres de coroutine C++ le seraient (par défaut).

3. Mes hypothèses sur les coroutines c++ sont-elles fausses, pourquoi ? Voir ci-dessus.

4. Un code plus verbeux en raison de la nécessité de recourir à des allocateurs personnalisés et à la mise en commun de la mémoire. Si vous voulez que les coroutines empilées soient performantes, vous devrez faire la même chose pour gérer les zones de mémoire pour les piles, et il s'avère que c'est encore plus difficile. Vous devez minimiser le gaspillage de mémoire, et donc vous devez surallouer la pile au minimum pour le cas d'utilisation de 99,9%, et traiter d'une manière ou d'une autre les coroutines qui épuisent cette pile.

   Une façon dont j'ai traité ce problème en C++ était de faire des vérifications de la pile aux points de branchement où l'analyse du code indique que plus de pile peut être nécessaire, puis si la pile débordait, une exception était levée, le travail de la coroutine annulé (la conception du système devait le supporter !), puis le travail recommençait avec plus de pile. C'est un moyen facile de perdre rapidement les avantages des tas de piles serrées. Oh, et j'ai dû fournir mon propre __cxa_allocate_exception pour que ça marche. Amusant, hein ?

Une autre anecdote : Je m'amuse à utiliser des coroutines dans des pilotes Windows en mode noyau, et là, l'absence de pile est importante - dans la mesure où, si le matériel le permet, vous pouvez allouer le tampon de paquets et la trame de la coroutine ensemble, et ces pages sont épinglées lorsqu'elles sont soumises au matériel réseau pour exécution. Lorsque le gestionnaire d'interruption reprend la coroutine, la page est là, et si la carte réseau le permet, elle peut même la précharger pour vous afin qu'elle soit dans le cache. Cela fonctionne bien - c'est juste un cas d'utilisation, mais puisque vous vouliez de l'embarqué - j'ai de l'embarqué :).

Il n'est peut-être pas courant de considérer les pilotes des plates-formes de bureau comme du code "embarqué", mais je vois beaucoup de similitudes, et un état d'esprit "embarqué" est nécessaire. La dernière chose que vous voulez, c'est un code noyau qui alloue trop de ressources, surtout si cela ajoute une surcharge par thread. Un PC de bureau typique a quelques milliers de threads présents, et beaucoup d'entre eux sont là pour gérer les entrées/sorties. Imaginez maintenant un système sans disque qui utilise un stockage iSCSI. Sur un tel système, tout ce qui est lié aux E/S et qui n'est pas lié à l'USB ou au GPU sera lié au matériel réseau et à la pile réseau.

Enfin : Faites confiance aux benchmarks, pas à moi, et lisez aussi la réponse de Nicol ! . Ma perspective est façonnée par mes cas d'utilisation - je peux généraliser, mais je ne prétends pas avoir une expérience directe des coroutines dans du code "généraliste" où les performances sont moins importantes. Les allocations de tas pour les coroutines sans pile sont très souvent à peine perceptibles dans les traces de performance. Dans le code d'application généraliste, ce sera rarement un problème. Cela devient "intéressant" dans le code de la bibliothèque, et certains modèles doivent être développés pour permettre à l'utilisateur de la bibliothèque de personnaliser ce comportement. Ces modèles seront trouvés et popularisés au fur et à mesure que les bibliothèques utiliseront les coroutines C++.

Answer 2

En avant : Lorsque ce billet parle simplement de "coroutines", je fais référence aux concept d'une coroutine, et non la caractéristique spécifique du C++20. Lorsque je parlerai de cette fonctionnalité, je l'appellerai " co_await "ou "co_await coroutines".

Sur l'allocation dynamique

Cppreference utilise parfois une terminologie plus souple que celle de la norme. co_await en tant que fonctionnalité "nécessite" une allocation dynamique ; que cette allocation provienne du tas ou d'un bloc de mémoire statique ou autre est une question pour le fournisseur de l'allocation. De telles allocations peuvent être éludées dans des circonstances arbitraires, mais puisque la norme ne les précise pas, vous devez toujours supposer que toute coroutine co_await peut allouer dynamiquement de la mémoire.

Les coroutines co_await disposent de mécanismes permettant aux utilisateurs de fournir une allocation pour l'état de la coroutine. Ainsi, vous pouvez substituer l'allocation du tas/stock libre pour tout pool de mémoire particulier que vous préférez.

co_await en tant que fonctionnalité est bien conçu pour supprimer verbosité du point de vue de l'utilisation pour tout co_await -des objets et des fonctionnalités. Le site co_await La machinerie est incroyablement compliquée et complexe, avec de nombreuses interactions entre des objets de plusieurs types. Mais au point d'arrêt/de reprise, elle toujours ressemble à co_await <some expression> . L'ajout de la prise en charge des allocateurs à vos objets en attente et à vos promesses nécessite une certaine verbosité, mais cette verbosité se trouve en dehors de l'endroit où ces choses sont utilisées.

Utilisation de alloca pour une coroutine serait... très inapproprié pour... le plus les utilisations de co_await . Bien que la discussion autour de cette fonctionnalité tente de le cacher, le fait est que co_await en tant que fonctionnalité est conçu pour une utilisation asynchrone. C'est son but : arrêter l'exécution d'une fonction et planifier la reprise de cette fonction sur un autre thread potentiel, puis acheminer toute valeur éventuellement générée vers un code récepteur qui peut être quelque peu éloigné du code qui a invoqué la coroutine.

alloca n'est pas approprié pour ce cas d'utilisation particulier, puisque l'appelant de la coroutine est autorisé/encouragé à faire n'importe quoi pour que la valeur puisse être générée par un autre thread. L'espace alloué par alloca n'existerait donc plus, et c'est plutôt mauvais pour la coroutine qui y vit.

Notez également que les performances de l'allocation dans un tel scénario seront généralement éclipsées par d'autres considérations : l'ordonnancement des threads, les mutex, et d'autres choses seront souvent nécessaires pour planifier correctement la reprise de la coroutine, sans parler du temps nécessaire pour obtenir la valeur de n'importe quel processus asynchrone qui la fournit. Ainsi, le fait qu'une allocation dynamique soit nécessaire n'est pas vraiment une considération importante dans ce cas.

Maintenant, il y a sont les circonstances dans lesquelles l'allocation in situ serait appropriée. Les cas d'utilisation des générateurs sont ceux où vous souhaitez essentiellement mettre une fonction en pause et renvoyer une valeur, puis reprendre là où la fonction s'est arrêtée et éventuellement renvoyer une nouvelle valeur. Dans ces scénarios, la pile de la fonction qui invoque la coroutine sera certainement toujours là.

co_await prend en charge de tels scénarios (bien que co_yield ), mais il le fait d'une manière moins qu'optimale, du moins en ce qui concerne la norme. Parce que la fonction est conçue pour la suspension up-and-out, la transformer en coroutine suspend-down a pour effet d'avoir cette allocation dynamique qui n'a pas besoin d'être dynamique.

C'est pourquoi la norme n'exige pas d'allocation dynamique ; si un compilateur est suffisamment intelligent pour détecter un modèle d'utilisation de générateur, il peut supprimer l'allocation dynamique et allouer simplement l'espace sur la pile locale. Mais encore une fois, c'est ce qu'un compilateur peut faire, pas devoir faire.

Dans ce cas, alloca -L'allocation basée sur les résultats serait appropriée.

Comment il est entré dans la norme

La version courte est qu'elle a été intégrée à la norme parce que les personnes à l'origine de son élaboration ont fourni le travail nécessaire, alors que les personnes à l'origine des autres solutions ne l'ont pas fait.

Toute idée de coroutine est compliquée, et il y aura toujours des questions sur l'implémentabilité en ce qui les concerne. Par exemple, le " fonctions pouvant être reprises "Les propositions étaient superbes, et j'aurais aimé les voir dans le standard. Mais personne n'a réellement mis en œuvre dans un compilateur. Donc personne ne pouvait prouver que c'était réellement une chose que vous pouviez faire. Oh bien sûr, il sons réalisable, mais cela ne veut pas dire que cela est réalisable.

Souvenez-vous de ce qui s'est passé la dernière fois "semble pouvoir être mis en œuvre" a été utilisé comme base pour l'adoption d'une fonctionnalité.

Vous ne voulez pas normaliser quelque chose si vous ne savez pas si cela peut être mis en œuvre. Et vous ne voulez pas normaliser quelque chose si vous ne savez pas si cela résout réellement le problème prévu.

Gor Nishanov et son équipe chez Microsoft ont travaillé pour mettre en place co_await . Ils ont fait cela pour années en affinant leur mise en œuvre, etc. D'autres personnes ont utilisé leur implémentation dans du code de production réel et semblaient tout à fait satisfaites de sa fonctionnalité. Clang l'a même implémenté. Même si personnellement je n'aime pas ça, il est indéniable que co_await est un mature fonction.

En revanche, les alternatives de "core coroutines" qui ont été évoquées il y a un an comme des idées concurrentes avec les co_await n'a pas réussi à s'imposer en partie parce qu'ils étaient difficiles à mettre en œuvre . C'est pourquoi co_await a été adopté : parce qu'il s'agissait d'un outil éprouvé, mature et solide, que les gens voulaient et dont la capacité à améliorer leur code avait été démontrée.

co_await n'est pas pour tout le monde. Personnellement, je ne l'utiliserai probablement pas beaucoup, car les fibres fonctionnent bien mieux pour mes cas d'utilisation. Mais il est très bon pour son utilisation spécifique : la suspension de haut en bas.

Answer 3

Coroutines sans pile

• les coroutines sans pile (C++20) font transformation du code (machine à états)
• sans pile signifie dans ce cas que la pile de l'application n'est pas utilisée pour stocker les variables locales (par exemple les variables de votre algorithme).
• sinon les variables locales de la coroutine sans pile seraient écrasées par les invocations de fonctions ordinaires après la suspension de la coroutine sans pile.
• les coroutines sans pile ont aussi besoin de mémoire pour stocker les variables locales, surtout si la coroutine est suspendue, les variables locales doivent être préservées.
• à cette fin, les coroutines sans pile allouent et utilisent ce que l'on appelle un enregistrement d'activation (équivalent à un cadre de pile)
• suspendre à partir d'une pile d'appels profonde n'est possible que si toutes les fonctions intermédiaires sont également des coroutines sans pile ( viral sinon vous obtiendrez un pile corrompue )
• certains développeurs de clang sont sceptique que le Optimisation de l'allocation du tas de données (HALO) peut toujours être appliqué

coroutines empilées

• dans son essence, une coroutine empilée simplement commute la pile et le pointeur d'instruction
• allouer une pile latérale qui fonctionne comme une pile ordinaire (stockage des variables locales, avancement du pointeur de pile pour les fonctions appelées)
• la pile latérale ne doit être allouée qu'une seule fois (peut également être mise en commun) et tous les appels de fonction ultérieurs sont rapides (car il suffit d'avancer le pointeur de pile)
• chaque coroutine stackless nécessite son propre enregistrement d'activation -> lorsqu'elle est appelée dans une chaîne d'appels profonde, de nombreux enregistrements d'activation doivent être créés/alloués.
• Les coroutines empilées permettent de suspendre une chaîne d'appel profonde alors que les fonctions intermédiaires peuvent être des fonctions ordinaires ( non viral )
• une coroutine empilée peut survivre à son appelant/créateur
• une version des repères de Skynet apparaît. 1 million de coroutines empilées et montre que les coroutines empilées sont très efficaces (surpassant la version utilisant les threads).
• une version du benchmark skynet utilisant des coroutiens sans pile n'a pas encore été implémentée
• boost.context représente la pile primaire du fil comme une pile de coroutine/fibre - même sur ARM
• boost.context supporte piles de croissance à la demande (GCC split stacks)