À quoi sert une pile? Pourquoi en avons-nous besoin?

J'apprends donc MSIL en ce moment pour apprendre à déboguer mes applications C # .NET.

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

Pour mettre ma question en contexte:
pourquoi y a-t-il un transfert de la mémoire vers la pile ou un "chargement"? D'un autre côté, pourquoi y a-t-il un transfert de la pile vers la mémoire ou "stockage"? Pourquoi ne pas simplement les avoir tous mis en mémoire?

• Est-ce parce que c'est plus rapide?
• Est-ce parce qu'il 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 grande question!

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

Je suppose que vous voulez dire la pile d'évaluation du langage MSIL, et non la pile réelle par thread lors de l'exécution.

Pourquoi y a-t-il un transfert de la mémoire vers la pile ou "chargement"? D'un autre côté, pourquoi y a-t-il un transfert de la pile vers la mémoire ou "stockage"? Pourquoi ne pas simplement les avoir tous mis en mémoire?

MSIL est un langage "machine virtuelle". Des compilateurs comme le compilateur C # génèrent du CIL , puis au moment de l'exécution un autre compilateur appelé le compilateur JIT (Just In Time) transforme l'IL en code machine réel qui peut s'exécuter.

Répondons donc d'abord à la question "pourquoi avoir MSIL?" Pourquoi ne pas simplement demander au compilateur C # d'écrire du code machine?

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

De plus, c'est un travail difficile et dangereux. Écrire des générateurs de code efficaces pour des puces dont vous n'êtes pas un expert est un travail difficile! Les concepteurs de compilateurs sont des experts de l'analyse sémantique de leur langage, et non de l'allocation efficace des registres de nouveaux jeux de puces.

Supposons maintenant que nous le fassions de la 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 de langage vers CIL est facile à écrire car CIL est un langage simple, et le générateur de code CIL vers machine est également facile à écrire car CIL est un langage simple. Nous nous débarrassons de toutes les subtilités de C # et VB et ainsi de suite et tout "abaisser" à un langage simple qui est facile d'écrire une gigue pour.

Avoir un langage intermédiaire réduit le coût de la production d' un nouveau compilateur de langage radicalement . Cela réduit également considérablement le coût de la prise en charge d'une nouvelle puce. Vous voulez prendre en charge une nouvelle puce, vous trouvez des experts sur cette puce et leur faire écrire une gigue CIL et vous avez terminé; vous prenez ensuite en charge toutes ces langues sur votre puce.

OK, nous avons donc établi pourquoi nous avons MSIL; car avoir une langue intermédiaire abaisse les coûts. Pourquoi alors le langage est-il une "machine à empiler"?

Parce que les machines à empiler sont conceptuellement très simples à gérer pour les rédacteurs de compilateurs de langage. Les piles sont un mécanisme simple et facile à comprendre pour décrire les calculs. Les machines à empiler sont également très faciles à gérer sur le plan conceptuel. L'utilisation d'une pile est une abstraction simplificatrice, et donc encore une fois, elle réduit nos coûts .

Vous demandez "pourquoi avoir une pile?" Pourquoi ne pas tout faire directement de mémoire? Eh bien, réfléchissons-y. Supposons que vous souhaitiez générer du code CIL pour:

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

Supposons que nous ayons la convention que "ajouter", "appeler", "stocker" et ainsi de suite, toujours retirer leurs arguments de la pile et mettre leur résultat (s'il y en a un) sur la pile. 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.

Supposons maintenant que nous l'avons fait sans pile. Nous le ferons à votre façon, où chaque opcode prend les adresses 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
...

Tu vois comment ça se passe? Notre code devient énorme car nous devons allouer explicitement tout le stockage temporaire qui, normalement, par convention, irait simplement sur la pile . Pire encore, nos opcodes eux-mêmes deviennent tous é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 pile et y mettre une chose peut être un seul octet. Une instruction d'ajout qui prend deux adresses d'opérande et une adresse de résultat va être énorme.

Nous utilisons des opcodes basés sur la pile car les piles 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 quand j'aurai fini . En faisant l'hypothèse que nous avons une pile à notre disposition, nous pouvons rendre les opcodes très petits et le code très concis.

MISE À JOUR: Quelques réflexions supplémentaires

Soit dit en passant, cette idée de réduire considérablement les coûts en (1) spécifiant une machine virtuelle, (2) écrivant des compilateurs qui ciblent le langage VM, et (3) écrivant des implémentations de la VM sur une variété de matériel, n'est pas du tout une nouvelle idée. . Il ne provenait pas de MSIL, LLVM, du bytecode Java ou d'autres infrastructures modernes. La première mise en œuvre de cette stratégie que je connaisse est la machine pcode de 1966.

La première fois que j'ai personnellement entendu parler de ce concept, j'ai appris comment les implémenteurs 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 créé des émulateurs Z-machine pour tout le matériel sur lequel ils voulaient exécuter leurs jeux. Cela a eu l'énorme avantage supplémentaire qu'ils pouvaient implémenter la gestion de la mémoire virtuelle sur les systèmes primitifs 8 bits; un jeu peut être plus volumineux que ce qu'il pourrait contenir en mémoire, car il peut simplement paginer le code depuis le disque quand il en a besoin et le jeter lorsqu'il a besoin de 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 pile. Contrairement à une machine virtuelle basée sur un registre, la machine virtuelle Dalvik utilisée dans les systèmes d'exploitation Android en est un exemple.

La pile dans la machine virtuelle est virtuelle, c'est à 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. Dans le cas de .NET, il s'agit presque toujours d'une gigue, le jeu d'instructions MSIL a été conçu pour être lancé dès le départ. Contrairement au bytecode Java par exemple, il a 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 le .NET Micro Framework. Qui s'exécute sur des processeurs avec des ressources très limitées, ne peut pas se permettre la RAM requise pour stocker le code machine.

Le modèle de code machine réel est mixte, ayant à la fois une pile et des registres. L'un des gros travaux de l'optimiseur de code JIT est de trouver des moyens de stocker les variables qui sont conservées sur la pile dans des registres, améliorant ainsi considérablement la vitesse d'exécution. Une gigue Dalvik a le problème opposé.

La pile de machines est par ailleurs une installation de stockage très basique qui existe depuis très longtemps dans les conceptions de processeurs. Il a une très bonne localité de référence, une caractéristique très importante sur les processeurs modernes qui parcourent les données beaucoup plus rapidement que la RAM ne peut les fournir et prend en charge la récursivité. La conception du langage est fortement influencée par le fait d'avoir une pile, visible à l'appui des variables locales et une portée limitée au corps de la méthode. Un problème important avec la pile est celui pour lequel ce site est nommé.

Il y a un article Wikipedia très intéressant / détaillé à ce sujet, Avantages des jeux d'instructions de la machine à pile . Il faudrait que je le cite entièrement, il est donc plus facile de simplement mettre un lien. Je citerai simplement les sous-titres

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

Pour ajouter un peu plus à la question de la pile. Le concept de pile dérive de la conception du processeur où le code machine dans l'unité de logique arithmétique (ALU) fonctionne sur des opérandes qui se trouvent sur la pile. Par exemple, une opération de multiplication peut prendre les deux opérandes supérieurs de la pile, les multiplier et replacer le résultat sur la pile. Le langage machine a généralement deux fonctions de base pour ajouter et supprimer des opérandes de la pile; PUSH et POP. Dans de nombreux processeurs numériques (processeur de signal numérique) et contrôleurs de machine (tels que ceux qui contrôlent une machine à laver), la pile est située sur la puce elle-même. Cela donne un accès plus rapide à l'ALU et consolide les fonctionnalités requises dans une seule puce.

Si le concept de pile / tas n'est pas suivi et que les données sont chargées dans un emplacement de mémoire aléatoire OU les données sont stockées à partir d'emplacements de mémoire aléatoires ... ce sera très non 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 fonctionnant sans piles, en utilisant un style de codage à passage continu . Ensuite, les trames d'appel deviennent des continuations allouées dans le tas de récupération de place (le garbage collector aurait besoin d'une pile).

Voir les anciens écrits d'Andrew Appel: La compilation avec les continuations et la collecte des ordures peut être plus rapide que l'allocation de pile

(Il a peut-être un peu tort aujourd'hui à cause de problèmes de cache)

J'ai cherché "interruption" et personne n'a inclus cela comme avantage. Pour chaque périphérique qui interrompt un microcontrôleur ou un autre processeur, il y a généralement des registres qui sont poussés sur une pile, une routine de service d'interruption est appelée, et lorsqu'elle est terminée, les registres sont extraits de la pile et replacés là où ils étaient. Ensuite, le pointeur d'instructions est restauré et l'activité normale reprend là où elle s'était arrêtée, presque comme si l'interruption ne s'était jamais produite. Avec la pile, vous pouvez réellement avoir plusieurs appareils (théoriquement) s'interrompent les uns les autres, et tout cela fonctionne simplement - à cause de la pile.

Il existe également une famille de langages basés sur la pile appelés langages concaténatifs . Ce sont tous (je crois) des langages fonctionnels, car la pile est un paramètre implicite transmis, et la pile modifiée est également un retour implicite de chaque fonction. Les deux Forth et le facteur (qui est excellent) sont des exemples, ainsi que d'autres. Factor a été utilisé de manière similaire à Lua, pour les jeux de script, et a été écrit par Slava Pestov, un génie qui travaille actuellement chez Apple. Son Google TechTalk sur youtube, j'ai regardé plusieurs fois. Il parle des constructeurs Boa, mais je ne sais pas ce qu'il veut dire ;-).

Je pense vraiment que certaines des machines virtuelles actuelles, comme la JVM, le CIL de Microsoft, et même celle que j'ai vue a été écrite pour Lua, devraient être écrites dans certains de ces langages basés sur la pile, pour les rendre portables sur encore plus de plates-formes. Je pense que ces langages concaténatifs manquent en quelque sorte leurs appels en tant que kits de création de VM et plates-formes de portabilité. Il existe même pForth, un Forth "portable" écrit en C ANSI, qui pourrait être utilisé pour une portabilité encore plus universelle. Quelqu'un a-t-il essayé de le compiler en utilisant Emscripten ou WebAssembly?

Avec les langages basés sur la pile, il existe un style de code appelé point zéro, car vous pouvez simplement lister les fonctions à appeler sans passer de paramètres (parfois). Si les fonctions s'emboîtent parfaitement, vous n'auriez rien d'autre qu'une liste de toutes les fonctions du point zéro, et ce serait votre application (théoriquement). Si vous explorez Forth ou Factor, vous verrez de quoi je parle.

Chez Easy Forth , un joli tutoriel en ligne écrit en JavaScript, voici un petit exemple (notez le "sq sq sq sq sq" comme exemple de style d'appel point zéro):

: sq dup * ;  ok
2 sq . 4  ok
: ^4 sq sq ;  ok
2 ^4 . 16  ok
: ^8 sq sq sq sq ;  ok
2 ^8 . 65536  ok

De plus, si vous regardez la source de la page Web Easy Forth, vous verrez en bas qu'elle est très modulaire, écrite dans environ 8 fichiers JavaScript.

J'ai dépensé beaucoup d'argent pour à peu près tous les livres de Forth sur lesquels je pouvais mettre la main pour essayer d'assimiler Forth, mais je commence à peine à mieux le comprendre. Je veux donner une tête à ceux qui viennent après, si vous voulez vraiment l'obtenir (je l'ai découvert trop tard), obtenez le livre sur FigForth et implémentez-le. Les Forth commerciaux sont trop compliqués, et le plus grand avantage de Forth est qu'il est possible de comprendre l'ensemble du système, de haut en bas. D'une certaine manière, Forth implémente tout un environnement de développement sur un nouveau processeur, et bien que la nécessitécar cela a semblé passer avec C sur tout, il est encore utile comme rite de passage pour écrire un Forth à partir de zéro. Donc, si vous choisissez de le faire, essayez le livre FigForth - il s'agit de plusieurs Forths implémentés simultanément sur une variété de processeurs. Une sorte de Rosetta Stone of Forths.

Pourquoi avons-nous besoin d'une pile - efficacité, optimisation, point zéro, enregistrement des registres lors d'une interruption, et pour les algorithmes récursifs, c'est "la bonne forme".