Est-ce un type de chose hybride? (par exemple, mon programme .NET utilise-t-il une pile jusqu'à ce qu'il atteigne un appel asynchrone puis bascule vers une autre structure jusqu'à ce qu'il soit terminé, à quel point la pile est déroulée à un état où elle peut être sûre des éléments suivants, etc.? )
En gros oui.
Supposons que nous ayons
async void MyButton_OnClick() { await Foo(); Bar(); }
async Task Foo() { await Task.Delay(123); Blah(); }
Voici une explication extrêmement simplifiée de la façon dont les suites sont réifiées. Le vrai code est considérablement plus complexe, mais cela fait passer l'idée.
Vous cliquez sur le bouton. Un message est mis en file d'attente. La boucle de message traite le message et appelle le gestionnaire de clics, en plaçant l'adresse de retour de la file d'attente de messages sur la pile. Autrement dit, la chose qui se produit après la fin du gestionnaire est que la boucle de message doit continuer à fonctionner. Ainsi, la continuation du gestionnaire est la boucle.
Le gestionnaire de clics appelle Foo (), mettant l'adresse de retour de lui-même sur la pile. Autrement dit, la poursuite de Foo est le reste du gestionnaire de clics.
Foo appelle Task.Delay, mettant l'adresse de retour de lui-même sur la pile.
Task.Delay fait tout ce qu'il faut pour retourner immédiatement une tâche. La pile est sautée et nous sommes de retour à Foo.
Foo vérifie la tâche retournée pour voir si elle est terminée. Ce n'est pas. La suite de l' attente consiste à appeler Blah (), donc Foo crée un délégué qui appelle Blah () et signe cette délégation comme la continuation de la tâche. (Je viens de faire une fausse déclaration; l'avez-vous compris? Sinon, nous le révélerons dans un instant.)
Foo crée ensuite son propre objet Task, le marque comme incomplet et le renvoie dans la pile au gestionnaire de clics.
Le gestionnaire de clics examine la tâche de Foo et découvre qu'elle est incomplète. La suite de l'attente dans le gestionnaire consiste à appeler Bar (), de sorte que le gestionnaire de clic crée un délégué qui appelle Bar () et le définit comme la continuation de la tâche renvoyée par Foo (). Il renvoie ensuite la pile dans la boucle de message.
La boucle de messages continue de traiter les messages. Finalement, la magie du minuteur créée par la tâche de retard fait son travail et publie un message dans la file d'attente disant que la poursuite de la tâche de retard peut maintenant être exécutée. Ainsi, la boucle de message appelle la poursuite de la tâche, se mettant sur la pile comme d'habitude. Ce délégué appelle Blah (). Blah () fait ce qu'il fait et retourne dans la pile.
Maintenant, que se passe-t-il? Voici le morceau délicat. La poursuite de la tâche de retard n'appelle pas seulement Blah (). Il doit également déclencher un appel à Bar () , mais cette tâche ne connaît pas Bar!
Foo a en fait créé un délégué qui (1) appelle Blah (), et (2) appelle la continuation de la tâche que Foo a créée et rendue au gestionnaire d'événements. Voilà comment nous appelons un délégué qui appelle Bar ().
Et maintenant, nous avons fait tout ce que nous devions faire, dans le bon ordre. Mais nous n'avons jamais arrêté de traiter les messages dans la boucle de messages très longtemps, donc l'application est restée réactive.
Que ces scénarios soient trop avancés pour une pile est parfaitement logique, mais qu'est-ce qui remplace la pile?
Un graphique d'objets de tâche contenant des références les uns aux autres via les classes de fermeture des délégués. Ces classes de fermeture sont des machines d'état qui gardent une trace de la position de l'attente la plus récemment exécutée et des valeurs des locaux. De plus, dans l'exemple donné, une file d'attente d'état global mise en œuvre par le système d'exploitation et la boucle de message qui exécute ces actions.
Exercice: comment pensez-vous que tout cela fonctionne dans un monde sans boucles de messages? Par exemple, les applications de console. attendre dans une application console est très différent; pouvez-vous déduire comment cela fonctionne de ce que vous savez jusqu'à présent?
Quand j'ai appris cela il y a des années, la pile était là parce qu'elle était rapide et légère comme l'éclair, un morceau de mémoire alloué à l'application loin du tas car il supportait une gestion très efficace pour la tâche à accomplir (jeu de mots voulu?). Qu'est-ce qui a changé?
Les piles sont une structure de données utile lorsque les durées de vie des activations de méthode forment une pile, mais dans mon exemple, les activations du gestionnaire de clics, Foo, Bar et Blah ne forment pas une pile. Et donc la structure de données qui représente ce flux de travail ne peut pas être une pile; c'est plutôt un graphique des tâches et des délégués alloués en tas qui représente un flux de travail. Les attentes sont les points dans le flux de travail où la progression ne peut pas se poursuivre dans le flux de travail tant que le travail commencé plus tôt n'est pas terminé; pendant que nous attendons, nous pouvons exécuter d' autres travaux qui ne dépendent pas de la fin des tâches démarrées.
La pile n'est qu'un tableau d'images, où les images contiennent (1) des pointeurs vers le milieu des fonctions (où l'appel s'est produit) et (2) des valeurs de variables locales et de temps. Les continuations de tâches sont la même chose: le délégué est un pointeur vers la fonction et il a un état qui référence un point spécifique au milieu de la fonction (où l'attente s'est produite), et la fermeture a des champs pour chaque variable locale ou temporaire . Les cadres ne forment tout simplement plus un joli tableau soigné, mais toutes les informations sont les mêmes.
Appel a écrit qu'un ancien ramasse-miettes papier peut être plus rapide que l'allocation de pile . Lisez également son livre Compilation avec continuations et le manuel de collecte des ordures . Certaines techniques de GC sont (involontairement) très efficaces. Le style de passage de continuation définit une transformation canonique de programme complet (la transformation CPS ) pour se débarrasser des piles (remplacer conceptuellement les trames d'appel par des fermetures allouées en tas , en d'autres termes "réifier" les trames d'appel individuelles en tant que "valeurs" ou "objets" individuels). ).
Mais la pile d'appels est encore très largement utilisée, et les processeurs actuels ont du matériel dédié (registre de pile, machines de cache, ....) dédié aux piles d'appels (et c'est parce que la plupart des langages de programmation de bas niveau, notamment C, sont plus faciles à implémenter avec une pile d'appels). Notez également que les piles sont compatibles avec le cache (et cela compte beaucoup pour les performances).
En pratique, les piles d'appels sont toujours là. Mais nous en avons maintenant beaucoup, et parfois la pile d'appels est divisée en de nombreux segments plus petits (par exemple de quelques pages de 4 Ko chacun), qui sont parfois récupérés ou alloués par tas. Ces segments de pile pourraient être organisés dans une liste liée (ou une structure de données plus complexe, si nécessaire). Par exemple, les compilateurs GCC ont une
-fsplit-stackoption (notamment utile pour Go, et ses "goroutines" et ses "processus asynchrones"). Avec des piles fractionnées, vous pouvez avoir plusieurs milliers de piles (et les routines deviennent plus faciles à implémenter) constituées de millions de petits segments de pile, et le «déroulement» de la pile peut être plus rapide (ou au moins presque aussi rapide qu'avec un seul bloc). empiler).(en d'autres termes, la distinction entre pile et tas est floue, mais peut nécessiter une transformation de programme entier, ou changer incompatiblement la convention d'appel et le compilateur)
Voir aussi ceci et cela et de nombreux articles (par exemple ceci ) sur la transformation CPS. Lisez aussi sur ASLR & call / cc . En savoir plus (& STFW) sur les suites .
Les implémentations .CLR & .NET peuvent ne pas avoir une transformation GC & CPS de pointe, pour de nombreuses raisons pragmatiques. Il s'agit d'un compromis lié aux transformations de programme entières (et à la facilité d'utilisation des routines C de bas niveau et à un code d'exécution codé en C ou C ++).
Chicken Scheme utilise la pile de la machine (ou C) d'une manière non conventionnelle avec la transformation CPS: chaque allocation se produit sur la pile, et quand elle devient trop grande, une étape de copie et de transfert GC générationnelle se déplace pour déplacer les dernières valeurs allouées de la pile (et probablement la continuation actuelle) au tas, puis la pile est considérablement réduite avec un grand
setjmp.Lisez aussi SICP , Programming Language Pragmatics , the Dragon Book , Lisp In Small Pieces .
la source