Quel est le but d’une stack? Pourquoi en avons-nous besoin?

J’apprends donc MSIL maintenant pour apprendre à déboguer mes applications C # .NET.

Je me suis toujours demandé: quel est le but de la stack?

Juste pour mettre ma question en contexte:
Pourquoi y a-t-il un transfert de mémoire à stack ou à “chargement?” D’un autre côté, pourquoi y a-t-il un transfert de stack en mémoire ou de “stockage”? Pourquoi ne pas simplement les placer tous dans la mémoire?

  • Est-ce parce que c’est plus rapide?
  • Est-ce parce que c’est basé sur la RAM?
  • Pour l’efficacité?

J’essaie de comprendre cela pour m’aider à comprendre les codes CIL beaucoup plus profondément.

MISE À JOUR: J’ai tellement aimé cette question que j’en ai fait le sujet de mon blog le 18 novembre 2011 . Merci pour la bonne question!

Je me suis toujours demandé: quel est le but de la stack?

Je suppose que vous voulez dire la stack d’évaluation du langage MSIL, et non la stack réelle par thread au moment de l’exécution.

Pourquoi y a-t-il un transfert de mémoire à stack ou à “chargement?” D’un autre côté, pourquoi y a-t-il un transfert de stack en mémoire ou de “stockage”? Pourquoi ne pas simplement les placer tous dans la mémoire?

MSIL est un langage “machine virtuelle”. Les compilateurs tels que le compilateur C # génèrent CIL , puis à l’exécution, un autre compilateur appelé le compilateur JIT (Just In Time) transforme l’IL en code machine réel pouvant être exécuté.

Alors d’abord, répondons à la question “Pourquoi avoir MSIL du tout?” Pourquoi ne pas simplement écrire le code machine sur le compilateur C #?

Parce que c’est moins cher de le faire de cette façon. Supposons que nous ne l’ayons pas fait de cette façon. Supposons que chaque langue doit avoir son propre générateur de code machine. Vous avez vingt langues différentes: C #, JScript .NET , Visual Basic, IronPython , F # … Et supposez que vous avez dix processeurs différents. Combien de générateurs de code devez-vous écrire? 20 x 10 = 200 générateurs de code. C’est beaucoup de travail. Supposons maintenant que vous souhaitiez append un nouveau processeur. Vous devez écrire le générateur de code pour cela vingt fois, un pour chaque langue.

De plus, c’est un travail difficile et dangereux. Ecrire des générateurs de code efficaces pour les puces sur lesquelles vous n’êtes pas un expert est un travail difficile! Les concepteurs de compilateurs sont des experts de l’parsing sémantique de leur langage, pas de l’allocation efficace des registres des nouveaux jeux de puces.

Maintenant, supposons que nous le fassions de manière CIL. Combien de générateurs CIL devez-vous écrire? Un par langue. Combien de compilateurs JIT devez-vous écrire? Un par processeur. Total: 20 + 10 = 30 générateurs de code. De plus, le générateur language-to-CIL est facile à écrire car CIL est un langage simple, et le générateur de code CIL-to-machine-code est également facile à écrire car CIL est un langage simple. Nous nous débarrassons de toutes les subtilités de C # et de VB et ainsi de suite et «réduisons» tout à un langage simple et facile à écrire.

Avoir un langage intermédiaire réduit considérablement le coût de production d’un nouveau compilateur de langue. Cela réduit également le coût de prise en charge d’une nouvelle puce de manière spectaculaire. Vous souhaitez prendre en charge une nouvelle puce, vous trouvez des experts sur cette puce et demandez-leur d’écrire une gigue CIL et vous avez terminé; vous supportez alors toutes ces langues sur votre puce.

OK, donc nous avons établi pourquoi nous avons MSIL; car avoir un langage intermédiaire réduit les coûts. Pourquoi alors la langue est-elle une “machine à stack”?

Parce que les machines à stack sont conceptuellement très simples à gérer pour les rédacteurs de compilateurs de langage. Les stacks sont un mécanisme simple et facile à comprendre pour décrire les calculs. Les machines à stack sont également très simples à gérer pour les auteurs de compilateurs JIT. L’utilisation d’une stack est une abstraction simplificasortingce et, par conséquent, elle réduit nos coûts .

Vous demandez “pourquoi avoir une stack du tout?” Pourquoi ne pas tout faire directement de mémoire? Eh bien, réfléchissons à ça. Supposons que vous souhaitiez générer du code CIL pour:

int x = A() + B() + C() + 10; 

Supposons que nous ayons la convention selon laquelle “append”, “appeler”, “stocker” etc. prennent toujours leurs arguments hors de la stack et placent leur résultat (s’il y en a un) sur la stack. Pour générer du code CIL pour ce C #, nous disons simplement quelque chose comme:

 load the address of x // The stack now contains address of x call A() // The stack contains address of x and result of A() call B() // Address of x, result of A(), result of B() add // Address of x, result of A() + B() call C() // Address of x, result of A() + B(), result of C() add // Address of x, result of A() + B() + C() load 10 // Address of x, result of A() + B() + C(), 10 add // Address of x, result of A() + B() + C() + 10 store in address // The result is now stored in x, and the stack is empty. 

Maintenant, supposons que nous l’avons fait sans stack. Nous le ferons à votre guise, où chaque opcode prend l’adresse de ses opérandes et l’adresse à laquelle il stocke son résultat :

 Allocate temporary store T1 for result of A() Call A() with the address of T1 Allocate temporary store T2 for result of B() Call B() with the address of T2 Allocate temporary store T3 for the result of the first addition Add contents of T1 to T2, then store the result into the address of T3 Allocate temporary store T4 for the result of C() Call C() with the address of T4 Allocate temporary store T5 for result of the second addition ... 

Vous voyez comment ça se passe? Notre code devient énorme parce que nous devons allouer explicitement tout le stockage temporaire qui normalement devrait normalement être placé sur la stack . Pire encore, nos opcodes eux-mêmes deviennent énormes car ils doivent tous maintenant prendre comme argument l’adresse dans laquelle ils vont écrire leur résultat et l’adresse de chaque opérande. Une instruction “add” qui sait qu’elle va retirer deux choses de la stack et mettre une chose dessus peut être un seul octet. Une instruction add qui prend deux adresses d’opérande et une adresse de résultat va être énorme.

Nous utilisons des opcodes basés sur des stacks car les stacks résolvent le problème commun . À savoir: je veux allouer du stockage temporaire, l’utiliser très bientôt et ensuite m’en débarrasser rapidement lorsque j’ai terminé . En faisant l’hypothèse que nous avons une stack à notre disposition, nous pouvons rendre les opcodes très petits et le code très laconique.

MISE À JOUR: Quelques reflections supplémentaires

Incidemment, cette idée de réduire drastiquement les coûts en (1) spécifiant une machine virtuelle, (2) en écrivant des compilateurs qui ciblent le langage VM et (3) en écrivant des implémentations de la VM sur une variété de matériel n’est pas une idée nouvelle. . Il ne provenait pas de MSIL, LLVM, bytecode Java ou de toute autre infrastructure moderne. La plus ancienne mise en œuvre de cette stratégie dont je suis au courant est la machine à codes-barres de 1966.

Le premier que j’ai personnellement entendu parler de ce concept, c’est quand j’ai appris comment les développeurs d’Infocom ont réussi à faire fonctionner Zork sur autant de machines différentes. Ils ont spécifié une machine virtuelle appelée Z-machine et ont ensuite fabriqué des émulateurs Z-machine pour tout le matériel qu’ils souhaitaient utiliser pour leurs jeux. Cela présentait l’avantage énorme de pouvoir implémenter la gestion de la mémoire virtuelle sur les systèmes primitifs à 8 bits. un jeu peut être plus volumineux que ce qui pourrait rentrer dans la mémoire, car il peut simplement renvoyer le code depuis le disque quand il en a besoin et le supprimer lorsqu’il doit charger un nouveau code.

Gardez à l’esprit que lorsque vous parlez de MSIL, vous parlez d’instructions pour une machine virtuelle . La machine virtuelle utilisée dans .NET est une machine virtuelle basée sur la stack. Contrairement à une VM basée sur un registre, la VM Dalvik utilisée dans les systèmes d’exploitation Android en est un exemple.

La stack dans la machine virtuelle est virtuelle, il appartient à l’interpréteur ou au compilateur juste-à-temps de traduire les instructions de la machine virtuelle en code réel qui s’exécute sur le processeur. Ce qui dans le cas de .NET est presque toujours une gigue, le jeu d’instructions MSIL a été conçu pour être envoyé dès le départ. Contrairement au bytecode Java, par exemple, il comporte des instructions distinctes pour les opérations sur des types de données spécifiques. Ce qui le rend optimisé pour être interprété. Un interpréteur MSIL existe cependant, il est utilisé dans .NET Micro Framework. Qui s’exécute sur des processeurs avec des ressources très limitées, ne peut pas se permettre la RAM requirejse pour stocker le code machine.

Le modèle de code machine réel est mélangé, ayant à la fois une stack et des registres. L’une des tâches majeures de l’optimiseur de code JIT consiste à trouver des moyens de stocker les variables stockées dans la stack dans les registres, améliorant ainsi considérablement la vitesse d’exécution. Une gigue de Dalvik a le problème inverse.

La stack de machines est par ailleurs une installation de stockage de base qui existe depuis très longtemps dans les conceptions de processeurs. Il a une très bonne localisation de référence, une caractéristique très importante sur les processeurs modernes qui grattent les données beaucoup plus rapidement que la RAM ne peut le fournir et supporte la récursivité. La conception du langage est fortement influencée par la présence d’une stack, visible dans la prise en charge des variables locales et de la scope limitée au corps de la méthode. Un problème important avec la stack est celui pour lequel ce site est nommé.

Il y a un article Wikipédia très intéressant / détaillé à ce sujet, Avantages des jeux d’instructions de machine à stack . Je devrais le citer entièrement, il est donc plus facile de mettre simplement un lien. Je citerai simplement les sous-titres

  • Code object très compact
  • Compilateurs simples / interprètes simples
  • État minimal du processeur

Ajouter un peu plus à la question de la stack. Le concept de stack dérive de la conception d’unité centrale où le code machine de l’unité logique arithmétique (ALU) fonctionne sur des opérandes situés sur la stack. Par exemple, une opération de multiplication peut prendre les deux opérandes du haut de la stack, les multiplier et placer le résultat sur la stack. Le langage machine a généralement deux fonctions de base pour append et supprimer des opérandes de la stack; POUSSER et POP. Dans de nombreux processeurs numériques (processeurs de signaux numériques) et contrôleurs de machines (tels que ceux qui contrôlent une machine à laver), la stack se trouve sur la puce elle-même. Cela donne un access plus rapide à l’ALU et consolide les fonctionnalités requirejses en une seule puce.

Si le concept de stack / tas n’est pas suivi et que les données sont chargées dans un emplacement de mémoire aléatoire OU que les données sont stockées à partir d’emplacements de mémoire aléatoires … ce sera très peu structuré et non géré.

Ces concepts sont utilisés pour stocker des données dans une structure prédéfinie afin d’améliorer les performances, l’utilisation de la mémoire … et donc les structures de données.

On peut avoir un système qui fonctionne sans stacks, en utilisant le style de codage de continuation de passage . Les frameworks d’appels deviennent alors des continuations allouées dans le tas récupéré (le ramasse-miettes aurait besoin d’une stack).

Voir les anciens écrits d’Andrew Appel: La compilation avec les continuations et la récupération de la mémoire peut être plus rapide que l’allocation de la stack

(Il pourrait se tromper un peu en raison de problèmes de cache)