Was ist der Zweck eines Stapels? Warum brauchen wir es?

UPDATE: ich mochte diese Frage, so sehr ich es gemacht das Thema von meinem blog am 18. November 2011. Vielen Dank für die tolle Frage!

Ich habe mich immer gefragt: was ist der Zweck des Stapels?

Ich nehme an, du meinst die evaluation stack der MSIL-Sprache, und nicht die tatsächlichen pro-thread-stack zur Laufzeit.

Warum gibt es eine übertragung aus dem Speicher auf den stack oder "laden?" Auf der anderen Seite, warum gibt es einen transfer vom stack-Speicher oder auf "speichern"? Warum nicht einfach haben, Sie alle in den Speicher?

MSIL ist ein "virtual machine" - Sprache. Compiler der C# - compiler erzeugen CILund dann zur Laufzeit einen anderen compiler aufgerufen, der JIT - (Just In Time) compiler wandelt den IL in Maschinensprache-Anweisungen, die ausgeführt werden können.

Also lassen Sie uns zunächst die Antwort auf die Frage "warum haben MSIL überhaupt?" Warum nicht einfach haben, den C# - compiler schreiben, die Maschinen-code?

Weil es billigeres zu tun auf diese Weise. Angenommen, wir habe es nicht so; angenommen, jede Sprache hat Ihre eigenen Computer-code-generator. Sie haben zwanzig verschiedene Sprachen: C#, JScript .NETVisual Basic, IronPythonF#... Und angenommen, Sie haben zehn verschiedene Prozessoren. Wie viele code-Generatoren haben Sie zu schreiben? 20 x 10 = 200 code-Generatoren. Das ist eine Menge Arbeit. Nehmen wir nun an, die Sie hinzufügen möchten, einen neuen Prozessor. Schreiben Sie die code-generator für die es zwanzig mal, eine für jede Sprache.

Darüber hinaus ist es schwierig und gefährlich die Arbeit. Schreiben von effizienten code-Generatoren für chips, dass Sie nicht ein Experte ist ein harter job! Compiler-Designer sind Experten für die semantische Analyse der Sprache, nicht auf effiziente registrieren Vergabe von neuen chip-sets.

Nun nehmen wir an, wir tun es auch die CIL Weg. Wie viele CIL-Generatoren haben Sie zu schreiben? Eine pro Sprache. Wie viele JIT-Compiler haben Sie zu schreiben? Eine pro Prozessor. Insgesamt: 20 + 10 = 30 code-Generatoren. Außerdem, die Sprache-zu-CIL-generator ist einfach zu schreiben, weil CIL ist eine einfache Sprache, und die CIL-to-machine-code-generator ist auch leicht zu schreiben, weil CIL ist eine einfache Sprache. Wir loszuwerden, alle die Feinheiten von C# und VB und so weiter und "untere" alles auf eine einfache Sprache, die leicht zu schreiben jitter.

Dass eine intermediate language, senkt die Kosten für die Herstellung einer neuen Sprache compiler dramatisch. Es senkt auch die Kosten für einen neuen chip drastisch. Sie benötigen Unterstützung für einen neuen chip finden Sie einige Experten auf diesem chip haben und Sie schreiben Sie eine CIL-jitter und Sie fertig sind; Sie unterstützen dann all jene Sprachen, die auf Ihren chip.

OK, also wir haben begründet, warum wir MSIL; denn eine intermediate-language-Kosten senkt. Warum ist dann die Sprache ein "stack machine"?

Weil stack-Maschinen sind im Prinzip sehr einfach, die Sprache mit compiler-Autoren zu beschäftigen. Stacks sind eine einfache, leicht verständliche Mechanismus für die Beschreibung von Berechnungen. Stack-Maschinen sind auch konzeptionell sehr einfach für den JIT-compiler-Autoren zu beschäftigen. Mit einem stack ist eine vereinfachende Abstraktion, und daher wieder es senkt unsere Kosten.

Fragen Sie "warum haben Sie einen stack überhaupt?" Warum nicht einfach alles direkt out-of-memory? Nun, lassen Sie uns darüber nachdenken. Angenommen, Sie möchten zu generieren CIL-code für:

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

Nehmen wir an, wir haben die Konvention, dass "hinzufügen", "anrufen", "speichern" und so weiter, nehmen Sie immer Ihre Argumente aus dem Stapel und legte deren Ergebnis (falls es eines gibt) auf den stack. Generieren CIL-code für die C# wir nur sagen, so etwas wie:

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.

Nun nehmen wir an, wir haben es ohne einen Stapel. Wir werden es tun, Ihren Weg, wo jeder opcode nimmt die Adressen der Operanden und an welche Adresse er speichert sein Ergebnis:

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
...

Sehen Sie, wie das geht? Unser code ist immer riesige denn wir haben ausdrücklich weisen die vorübergehende Lagerung die normalerweise von der Konvention gehen Sie einfach auf den Stapel. Noch schlimmer, unsere Befehle selbst sind alle immer enorm, weil Sie alle haben jetzt zu nehmen als argument die Adresse, die Sie gehen zu schreiben, deren Ergebnis-in und der Adresse des jeweiligen Operanden. Ein "add" - Befehl, der weiß, dass es geht um zwei Dinge, aus dem Stapel und legen Sie eine Sache, auf ein einzelnes byte. Ein add-Befehl mit zwei Operanden-Adressen und Folge Adresse wird enorm sein.

Verwenden wir die stack-basierte opcodes, weil stapeln lösen das gemeinsame problem. Nämlich: will ich weisen Sie einige temporäre Speicherung, die es verwenden, sehr bald und dann, es loszuwerden schnell, wenn ich fertig bin. Durch die Annahme, dass wir einen Stapel zu unserer Verfügung stehen, können wir die opcodes sehr klein und der code sehr kurz gehalten.

UPDATE: Einige weitere Gedanken

Übrigens, diese Idee zu einer drastischen Senkung der Kosten von (1) definieren einer virtuellen Maschine, (2) schreiben von Compilern, deren Ziel die VM Sprache, und (3) schreiben von Implementierungen der virtuellen Maschine auf einer Vielzahl von hardware -, ist nicht eine neue Idee. Es gar nicht aus mit MSIL, LLVM, Java-bytecode oder jedem anderen modernen Infrastrukturen. Die früheste Umsetzung dieser Strategie, die ich bewusst bin, ist die pcode-Maschine aus dem Jahr 1966.

Der erste, den ich persönlich gehört dieses Konzept wurde als ich erfuhr, wie die Infocom implementors geschafft, Zork läuft auf so vielen unterschiedlichen Maschinen so gut. Sie spezifiziert eine virtuelle Maschine namens Z-Maschine und dann Z-Maschine-Emulatoren für alle hardware, die Sie laufen wollten, Ihre Spiele auf. Dies hatte den zusätzlichen enormen Vorteilen, die Sie umsetzen konnte virtual memory management auf primitiven 8-bit-Systeme, ein Spiel größer sein kann als das würde passen in den Speicher, weil Sie nur Seite den code von der Festplatte, wenn Sie es brauchte und es zu verwerfen, wenn Sie benötigt, um zu laden code.

InformationsquelleAutor der Antwort Eric Lippert

Gibt es ein sehr Interessantes/ausführliche Wikipedia-Artikel auf dieser Vorteile der stack-Maschine Befehl setzt. Ich brauchen würde, nennen es vollständig, so ist es einfacher, einfach einen link setzen. Ich werde einfach zitieren, der sub-Titel

• Sehr kompaktes Objekt-code
• Einfache Compiler /einfache Dolmetscher
• Minimale Prozessor-Zustand

InformationsquelleAutor der Antwort

Wenn das Konzept der stack - /heap wird nicht befolgt, und die Daten werden geladen und die random-Speicher ODER gespeicherten Daten gegen zufällige Speicher-Orte ... es wird sehr unstrukturiert und nicht verwaltete.

Diese Konzepte dienen zum speichern von Daten in eine vordefinierte Struktur, die um die Leistung zu verbessern Speichernutzung, ... und damit als data-Strukturen.

InformationsquelleAutor der Antwort Azodious