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

Ich lerne gerade MSIL, um zu lernen, wie ich meine C # .NET-Anwendungen debugge.

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

Um meine Frage in einen Zusammenhang zu bringen:
Warum erfolgt eine Übertragung vom Speicher zum Stapel oder "Laden"? Warum gibt es andererseits eine Übertragung vom Stapel in den Speicher oder ein "Speichern"? Warum nicht einfach alle in Erinnerung behalten?

• Liegt es daran, dass es schneller ist?
• Liegt es daran, dass es RAM-basiert ist?
• Für Effizienz?

Ich versuche dies zu verstehen, um CIL- Codes besser verstehen zu können.

UPDATE: Diese Frage hat mir so gut gefallen, dass ich sie am 18. November 2011 zum Thema meines Blogs gemacht habe . Danke für die tolle Frage!

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

Ich gehe davon aus, dass Sie den Evaluierungsstapel der MSIL-Sprache meinen und nicht den tatsächlichen Pro-Thread-Stapel zur Laufzeit.

Warum gibt es eine Übertragung vom Speicher zum Stapel oder "Laden"? Warum gibt es andererseits eine Übertragung vom Stapel in den Speicher oder ein "Speichern"? Warum nicht einfach alle in Erinnerung behalten?

MSIL ist eine Sprache der "virtuellen Maschine". Compiler wie der C # -Compiler generieren CIL , und zur Laufzeit wandelt ein anderer Compiler namens JIT-Compiler (Just In Time) die IL in tatsächlichen Maschinencode um, der ausgeführt werden kann.

Beantworten wir also zuerst die Frage "Warum überhaupt MSIL?" Warum nicht einfach den C # -Compiler Maschinencode ausschreiben lassen?

Weil es billiger ist , es so zu machen. Angenommen, wir haben es nicht so gemacht. Angenommen, jede Sprache muss einen eigenen Maschinencodegenerator haben. Sie haben zwanzig verschiedene Sprachen: C #, JScript .NET , Visual Basic, IronPython , F # ... Und nehmen wir an, Sie haben zehn verschiedene Prozessoren. Wie viele Codegeneratoren müssen Sie schreiben? 20 x 10 = 200 Codegeneratoren. Das ist viel Arbeit. Angenommen, Sie möchten einen neuen Prozessor hinzufügen. Sie müssen den Codegenerator dafür zwanzig Mal schreiben, einen für jede Sprache.

Darüber hinaus ist es eine schwierige und gefährliche Arbeit. Das Schreiben effizienter Codegeneratoren für Chips, für die Sie kein Experte sind, ist eine schwierige Aufgabe! Compiler-Designer sind Experten für die semantische Analyse ihrer Sprache und nicht für die effiziente Registerzuweisung neuer Chipsätze.

Nehmen wir nun an, wir machen es auf CIL-Weise. Wie viele CIL-Generatoren müssen Sie schreiben? Eine pro Sprache. Wie viele JIT-Compiler müssen Sie schreiben? Eine pro Prozessor. Gesamt: 20 + 10 = 30 Codegeneratoren. Darüber hinaus ist der Language-to-CIL-Generator einfach zu schreiben, da CIL eine einfache Sprache ist, und der CIL-to-Machine-Code-Generator ist auch einfach zu schreiben, da CIL eine einfache Sprache ist. Wir werden alle Feinheiten von C # und VB los und so weiter und "senken" alles auf eine einfache Sprache, für die man leicht einen Jitter schreiben kann.

Eine Zwischensprache verfügt , senkt die Kosten , eine neue Sprache Compiler erzeugt dramatisch . Dies senkt auch die Kosten für die Unterstützung eines neuen Chips erheblich. Wenn Sie einen neuen Chip unterstützen möchten, finden Sie einige Experten auf diesem Chip und lassen sie einen CIL-Jitter schreiben, und Sie sind fertig. Sie unterstützen dann alle diese Sprachen auf Ihrem Chip.

OK, wir haben festgestellt, warum wir MSIL haben. weil eine Zwischensprache die Kosten senkt. Warum ist die Sprache dann eine "Stapelmaschine"?

Weil Stack-Maschinen für Sprachcompiler-Autoren konzeptionell sehr einfach zu handhaben sind. Stapel sind ein einfacher, leicht verständlicher Mechanismus zur Beschreibung von Berechnungen. Stapelmaschinen sind für JIT-Compiler-Autoren auch konzeptionell sehr einfach zu handhaben. Die Verwendung eines Stapels ist eine vereinfachende Abstraktion und senkt daher wiederum unsere Kosten .

Sie fragen: "Warum überhaupt einen Stapel?" Warum nicht einfach alles direkt aus dem Gedächtnis machen? Nun, lass uns darüber nachdenken. Angenommen, Sie möchten CIL-Code generieren für:

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

Angenommen, wir haben die Konvention, dass "add", "call", "store" usw. immer ihre Argumente vom Stapel nehmen und ihr Ergebnis (falls vorhanden) auf den Stapel legen. Um CIL-Code für dieses C # zu generieren, sagen wir einfach 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.

Nehmen wir nun an, wir hätten es ohne Stapel geschafft. Wir machen es auf Ihre Weise, wobei jeder Opcode die Adressen seiner Operanden und die Adresse, an die er sein Ergebnis speichert, übernimmt :

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

Sie sehen, wie das geht? Unser Code wird riesig, weil wir explizit den gesamten temporären Speicher zuweisen müssen , der normalerweise nur auf dem Stapel liegt . Schlimmer noch, unsere Opcodes selbst werden alle enorm, weil sie jetzt alle die Adresse als Argument nehmen müssen, in die sie ihr Ergebnis schreiben werden, und die Adresse jedes Operanden. Eine "Add" -Anweisung, die weiß, dass zwei Dinge vom Stapel genommen und eine Sache angelegt werden, kann ein einzelnes Byte sein. Ein Add-Befehl, der zwei Operandenadressen und eine Ergebnisadresse benötigt, wird enorm sein.

Wir verwenden stapelbasierte Opcodes, da Stapel das häufig auftretende Problem lösen . Nämlich: Ich möchte einen temporären Speicher zuweisen, ihn sehr bald verwenden und ihn dann schnell entfernen, wenn ich fertig bin . Wenn wir davon ausgehen, dass wir einen Stapel zur Verfügung haben, können wir die Opcodes sehr klein und den Code sehr knapp machen.

UPDATE: Einige zusätzliche Gedanken

Im Übrigen ist diese Idee, die Kosten drastisch zu senken, indem (1) eine virtuelle Maschine angegeben, (2) Compiler geschrieben werden, die auf die VM-Sprache abzielen, und (3) Implementierungen der VM auf einer Vielzahl von Hardware geschrieben werden, überhaupt keine neue Idee . Es entstand nicht mit MSIL, LLVM, Java-Bytecode oder anderen modernen Infrastrukturen. Die früheste Umsetzung dieser Strategie, die mir bekannt ist, ist die Pcode-Maschine von 1966.

Das erste, was ich persönlich von diesem Konzept hörte, war, als ich erfuhr, wie die Infocom-Implementierer es geschafft haben, Zork auf so vielen verschiedenen Computern so gut zum Laufen zu bringen . Sie spezifizierten eine virtuelle Maschine namens Z-Maschine und erstellten dann Z-Maschinen-Emulatoren für die gesamte Hardware, auf der sie ihre Spiele ausführen wollten. Dies hatte den zusätzlichen enormen Vorteil, dass sie die Verwaltung des virtuellen Speichers auf primitiven 8-Bit-Systemen implementieren konnten. Ein Spiel könnte größer sein, als in den Speicher passen würde, da sie den Code einfach von der Festplatte einblättern könnten, wenn sie ihn benötigen, und ihn verwerfen könnten, wenn sie neuen Code laden müssten.

Denken Sie daran, dass Sie bei MSIL über Anweisungen für eine virtuelle Maschine sprechen . Die in .NET verwendete VM ist eine stapelbasierte virtuelle Maschine. Im Gegensatz zu einer registergestützten VM ist die in Android-Betriebssystemen verwendete Dalvik-VM ein Beispiel dafür.

Der Stapel in der VM ist virtuell. Es liegt an dem Interpreter oder dem Just-in-Time-Compiler, die VM-Anweisungen in tatsächlichen Code zu übersetzen, der auf dem Prozessor ausgeführt wird. Was im Fall von .NET fast immer ein Jitter ist, wurde der MSIL-Befehlssatz so konzipiert, dass er von Anfang an jittert. Im Gegensatz zum Java-Bytecode enthält es unterschiedliche Anweisungen für Operationen mit bestimmten Datentypen. Das macht es optimiert, interpretiert zu werden. Es gibt tatsächlich einen MSIL-Interpreter, der in .NET Micro Framework verwendet wird. Was auf Prozessoren mit sehr begrenzten Ressourcen läuft, kann sich den zum Speichern von Maschinencode erforderlichen RAM nicht leisten.

Das tatsächliche Maschinencodemodell ist gemischt und hat sowohl einen Stapel als auch Register. Eine der großen Aufgaben des JIT-Code-Optimierers besteht darin, Möglichkeiten zum Speichern von Variablen zu finden, die auf dem Stapel in Registern gespeichert sind, wodurch die Ausführungsgeschwindigkeit erheblich verbessert wird. Ein Dalvik-Jitter hat das gegenteilige Problem.

Der Maschinenstapel ist ansonsten eine sehr einfache Speichereinrichtung, die es in Prozessorkonstruktionen schon sehr lange gibt. Es hat eine sehr gute Referenzlokalität, eine sehr wichtige Funktion bei modernen CPUs, die Daten viel schneller durchkauen, als RAM sie liefern kann, und die Rekursion unterstützt. Das Sprachdesign wird stark von einem Stapel beeinflusst, der zur Unterstützung lokaler Variablen und des auf den Methodenkörper beschränkten Bereichs sichtbar ist. Ein wesentliches Problem mit dem Stapel ist das, nach dem diese Site benannt ist.

Es gibt einen sehr interessanten / detaillierten Wikipedia-Artikel dazu, Vorteile von Stapelmaschinen-Befehlssätzen . Ich müsste es komplett zitieren, damit es einfacher ist, einfach einen Link zu setzen. Ich zitiere einfach die Untertitel

• Sehr kompakter Objektcode
• Einfache Compiler / einfache Interpreter
• Minimaler Prozessorstatus

Um der Stapelfrage etwas mehr hinzuzufügen. Das Stapelkonzept leitet sich aus dem CPU-Design ab, bei dem der Maschinencode in der arithmetischen Logikeinheit (ALU) mit Operanden arbeitet, die sich auf dem Stapel befinden. Beispielsweise kann eine Multiplikationsoperation die beiden oberen Operanden vom Stapel nehmen, multiplizieren und das Ergebnis wieder auf den Stapel legen. Die Maschinensprache verfügt normalerweise über zwei Grundfunktionen zum Hinzufügen und Entfernen von Operanden zum Stapel. PUSH und POP. In vielen CPU-DSPs (digitaler Signalprozessor) und Maschinensteuerungen (wie z. B. der Steuerung einer Waschmaschine) befindet sich der Stapel auf dem Chip selbst. Dies ermöglicht einen schnelleren Zugriff auf die ALU und konsolidiert die erforderliche Funktionalität in einem einzigen Chip.

Wenn das Konzept von Stack / Heap nicht befolgt wird und Daten in einen zufälligen Speicherort geladen werden ODER Daten aus zufälligen Speicherorten gespeichert werden, sind sie sehr unstrukturiert und nicht verwaltet.

Diese Konzepte werden verwendet, um Daten in einer vordefinierten Struktur zu speichern, um die Leistung, die Speichernutzung zu verbessern ... und werden daher als Datenstrukturen bezeichnet.

Man kann ein System ohne Stapel arbeiten lassen, indem man den Codierungsstil für die Weitergabe verwendet. Dann werden Aufrufrahmen zu Fortsetzungen, die im Garbage Collected Heap zugeordnet sind (der Garbage Collector würde einen Stapel benötigen).

Siehe Andrew Appels alte Schriften: Kompilieren mit Fortsetzungen und Garbage Collection kann schneller sein als Stack Allocation

(Er könnte heute wegen Cache-Problemen ein bisschen falsch liegen)

Ich habe nach "Interrupt" gesucht und niemand hat das als Vorteil aufgenommen. Für jedes Gerät, das einen Mikrocontroller oder einen anderen Prozessor unterbricht, gibt es normalerweise Register, die auf einen Stapel geschoben werden. Eine Interrupt-Serviceroutine wird aufgerufen, und wenn dies erledigt ist, werden die Register wieder vom Stapel entfernt und dort abgelegt, wo sie sich befinden wurden. Dann wird der Befehlszeiger wiederhergestellt und die normale Aktivität wird dort fortgesetzt, wo sie aufgehört hat, fast so, als ob der Interrupt nie stattgefunden hätte. Mit dem Stack können sich tatsächlich mehrere Geräte (theoretisch) gegenseitig unterbrechen, und alles funktioniert einfach - aufgrund des Stacks.

Es gibt auch eine Familie stapelbasierter Sprachen, die als verkettete Sprachen bezeichnet werden . Sie sind alle (glaube ich) funktionale Sprachen, da der Stapel ein impliziter Parameter ist, der übergeben wird, und auch der geänderte Stapel eine implizite Rückgabe von jeder Funktion ist. Sowohl Forth als auch Factor (was ausgezeichnet ist) sind Beispiele, zusammen mit anderen. Factor wurde ähnlich wie Lua für Skriptspiele verwendet und von Slava Pestov geschrieben, einem Genie, das derzeit bei Apple arbeitet. Sein Google TechTalk auf youtube habe ich mir ein paar mal angesehen. Er spricht über Boa-Konstrukteure, aber ich bin mir nicht sicher, was er meint ;-).

Ich denke wirklich, dass einige der aktuellen VMs, wie die JVM, die CIL von Microsoft und sogar die, die ich gesehen habe, für Lua geschrieben wurden, in einigen dieser stapelbasierten Sprachen geschrieben werden sollten, um sie auf noch mehr Plattformen portierbar zu machen. Ich denke, dass diesen verketteten Sprachen ihre Aufrufe als VM-Erstellungskits und Portabilitätsplattformen irgendwie fehlen. Es gibt sogar pForth, einen in ANSI C geschriebenen "tragbaren" Forth, der für eine noch universellere Portabilität verwendet werden könnte. Hat jemand versucht, es mit Emscripten oder WebAssembly zu kompilieren?

Bei den stapelbasierten Sprachen gibt es einen Codestil namens Nullpunkt, da Sie die aufzurufenden Funktionen einfach auflisten können, ohne (manchmal) Parameter zu übergeben. Wenn die Funktionen perfekt zusammenpassen, hätten Sie nur eine Liste aller Nullpunktfunktionen, und das wäre Ihre Anwendung (theoretisch). Wenn Sie sich entweder mit Forth oder Factor beschäftigen, werden Sie sehen, wovon ich spreche.

Bei Easy Forth , einem netten Online-Tutorial in JavaScript, finden Sie hier ein kleines Beispiel (beachten Sie das "sq sq sq sq" als Beispiel für einen Nullpunkt-Aufrufstil):

: 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

Wenn Sie sich die Quelle der Easy Forth-Webseite ansehen, werden Sie unten sehen, dass sie sehr modular ist und in etwa 8 JavaScript-Dateien geschrieben ist.

Ich habe viel Geld für fast jedes Forth-Buch ausgegeben, das ich in die Hände bekommen konnte, um Forth zu assimilieren, aber jetzt fange ich gerade an, es besser zu machen. Ich möchte denjenigen, die danach kommen, den Kopf zerbrechen. Wenn Sie es wirklich wollen (ich habe es zu spät herausgefunden), holen Sie sich das Buch über FigForth und setzen Sie es um. Die kommerziellen Forths sind allzu kompliziert, und das Beste an Forth ist, dass es möglich ist, das gesamte System von oben nach unten zu verstehen. Irgendwie implementiert Forth eine ganze Entwicklungsumgebung auf einem neuen Prozessor, und zwar bei Bedarfdenn das scheint mit C auf alles zu vergehen, es ist immer noch als Übergangsritus nützlich, einen Forth von Grund auf neu zu schreiben. Wenn Sie sich dazu entscheiden, probieren Sie das FigForth-Buch aus - es sind mehrere Forths, die gleichzeitig auf einer Vielzahl von Prozessoren implementiert sind. Eine Art Rosetta Stone of Forths.

Warum brauchen wir einen Stapel - Effizienz, Optimierung, Nullpunkt, Speichern von Registern bei Interrupt und für rekursive Algorithmen "die richtige Form".