webentwicklung-frage-antwort-db.com.de

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

Daher lerne ich gerade MSIL, um das Debuggen meiner C # .NET-Anwendungen zu erlernen.

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

Um meine Frage in einen Zusammenhang zu stellen:
Warum erfolgt eine Übertragung vom Speicher zum Stapel oder "Laden"? Warum wird andererseits vom Stapel in den Speicher übertragen oder "gespeichert"? Warum nicht alle in den Speicher legen?

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

Ich versuche dies zu verstehen, um zu verstehen, dass CIL viel tiefer geht.

315
Jan Carlo Viray

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

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

Ich nehme an, Sie meinen den Auswertungsstapel der MSIL-Sprache und nicht den tatsächlichen Stapel pro Thread zur Laufzeit.

Warum erfolgt eine Übertragung vom Speicher zum Stapel oder ein "Laden"? Warum wird andererseits vom Stapel in den Speicher übertragen oder "gespeichert"? Warum nicht einfach alle in Erinnerung behalten?

MSIL ist eine "virtuelle Maschinensprache". Compiler wie der C # -Compiler generieren CIL , und zur Laufzeit verwandelt ein anderer Compiler namens JIT (Just In Time) den IL in tatsächlichen Maschinencode, der ausgeführt werden kann .

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

Weil es billiger ist, es so zu machen. Angenommen, wir haben es nicht so gemacht. Angenommen, jede Sprache muss einen eigenen Maschinencode-Generator haben. Sie haben zwanzig verschiedene Sprachen: C #, JScript .NET , Visual Basic, IronPython , F # ... und nehmen 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 Code-Generator dafür zwanzigmal schreiben, einen für jede Sprache.

Darüber hinaus ist es eine schwierige und gefährliche Arbeit. Effiziente Codegeneratoren für Chips zu schreiben, für die Sie kein Experte sind, ist eine schwere 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 die CIL-Weise. Wie viele CIL-Generatoren müssen Sie schreiben? Eine pro Sprache. Wie viele JIT-Compiler müssen Sie schreiben? Einer pro Prozessor. Insgesamt: 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, weil CIL eine einfache Sprache ist. Wir werden alle Feinheiten von C # und VB und so weiter und "senken" alles auf eine einfache Sprache, für die man leicht einen Jitter schreiben kann.

Eine Zwischensprache zu haben, senkt die Kosten für die Erstellung eines neuen Sprachcompilers dramatisch. Es senkt auch die Kosten für die Unterstützung eines neuen Chips dramatisch. Wenn Sie einen neuen Chip unterstützen möchten, finden Sie einige Experten auf diesem Chip, die einen CIL-Jitter schreiben und fertig sind. Sie unterstützen dann alle diese Sprachen auf Ihrem Chip.

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

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

Sie fragen: "Warum überhaupt einen Stapel haben?" Warum nicht einfach alles direkt aus dem Gedächtnis heraus 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. ihre Argumente immer vom Stapel nehmen und ihr Ergebnis (falls vorhanden) auf den Stapel schreiben. 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.

Angenommen, wir haben es ohne Stapel geschafft. Wir machen es auf Ihre Art und Weise, wobei jeder Opcode die Adressen seiner Operanden und die Adresse, unter der er sein Ergebnis speichert:

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

Siehst du, wie das geht? Unser Code wird riesig, weil wir den gesamten temporären Speicher explizit zuweisen müssen das würde normalerweise nur auf dem Stapel abgelegt werden. 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 wollen, und die Adresse jedes Operanden. Ein "add" -Befehl, der weiß, dass er zwei Dinge vom Stapel nimmt und eine Sache anlegt, kann ein einzelnes Byte sein. Ein Addierbefehl, der zwei Operandenadressen und eine Ergebnisadresse enthält, wird enorm sein.

Wir verwenden stapelbasierte Opcodes, weil Stapel das allgemeine Problem lösen. Nämlich: Ich möchte einen temporären Speicher zuweisen, ihn sehr bald verwenden und ihn dann schnell wieder 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

Übrigens: Diese Idee, die Kosten drastisch zu senken, indem (1) eine virtuelle Maschine angegeben wird, (2) Compiler geschrieben werden, die auf die Sprache VM) abzielen, und (3) Implementierungen der Sprache VM auf einer Vielzahl von Hardware ist überhaupt keine neue Idee. Sie stammt nicht von MSIL, LLVM, Java Bytecode oder einer anderen modernen Infrastruktur. Die früheste Implementierung von Diese mir bekannte Strategie ist die pcode machine von 1966.

Das erste, was ich persönlich von diesem Konzept hörte, war, als ich erfuhr, wie die Infocom-Implementierer es schafften, Zork so gut auf so vielen verschiedenen Maschinen zum Laufen zu bringen. Sie gaben eine virtuelle Maschine mit dem Namen Z-Maschine an 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 Verwaltung des virtuellen Speichers auf primitiven 8-Bit-Systemen implementieren konnten; Ein Spiel könnte größer sein, als es in den Speicher passen würde, da es den Code nur von der Festplatte einblättern kann, wenn es benötigt wird, und ihn verwerfen kann, wenn neuer Code geladen werden muss.

434
Eric Lippert

Beachten Sie, dass es sich bei MSIL um Anweisungen für eine virtuelle Maschine handelt. Die in .NET verwendete VM ist eine stapelbasierte virtuelle Maschine. Im Gegensatz zu einer registrierungsbasierten VM ist die in Android Betriebssystemen verwendete Dalvik VM ein Beispiel dafür.

Der Stapel in VM ist virtuell. Es ist Sache des Interpreters oder des Just-in-Time-Compilers, die Anweisungen VM 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 ausgelassen wird. Im Gegensatz zu beispielsweise Java Bytecode enthält es unterschiedliche Anweisungen für Operationen mit bestimmten Datentypen. Das macht es für die Interpretation optimiert. Ein MSIL-Interpreter ist zwar vorhanden, wird jedoch in .NET Micro Framework verwendet. Was auf Prozessoren mit sehr begrenzten Ressourcen läuft, kann sich das RAM nicht leisten, das zum Speichern von Maschinencode erforderlich ist.

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 im 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 grundlegende Speichereinrichtung, die es bei Prozessorentwürfen seit sehr langer Zeit gibt. Es hat eine sehr gute Referenzlokalität, ein sehr wichtiges Merkmal moderner CPUs, das Daten viel schneller durchkaut, als es RAM liefern kann, und unterstützt die Rekursion. Das Sprachdesign wird stark durch einen Stapel beeinflusst, der zur Unterstützung lokaler Variablen sichtbar ist und dessen Umfang auf den Methodenkörper beschränkt ist. Ein signifikantes Problem mit dem Stack ist das, nach dem diese Site benannt ist.

86
Hans Passant

Es gibt einen sehr interessanten/detaillierten Wikipedia-Artikel darüber, Vorteile von Stapelmaschinenbefehlssätzen. Ich würde es komplett zitieren müssen, damit es einfacher ist, einfach einen Link zu setzen. Ich zitiere einfach die Untertitel

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

Um der Stapelfrage ein wenig mehr hinzuzufügen. Das Stack-Konzept leitet sich vom CPU-Design ab, bei dem der Maschinencode in der arithmetischen Logikeinheit (ALU) auf Operanden angewendet wird, die sich auf dem Stack befinden. Zum Beispiel kann eine Multiplikationsoperation die beiden obersten 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 der Steuerung einer Waschmaschine) befindet sich der Stapel auf dem Chip selbst. Dies ermöglicht einen schnelleren Zugriff auf die ALU und führt die erforderliche Funktionalität auf einem einzigen Chip zusammen.

8
skyman

Wenn das Konzept von Stack/Heap nicht befolgt wird und Daten in zufällige Speicherorte geladen werden OR Daten werden aus zufälligen Speicherorten gespeichert ... sie sind sehr unstrukturiert und werden nicht verwaltet.

Diese Konzepte werden zum Speichern von Daten in einer vordefinierten Struktur verwendet, um die Leistung, die Speichernutzung usw. zu verbessern. Sie werden daher als Datenstrukturen bezeichnet.

5
Azodious

Man kann ein System haben, das ohne Stapel arbeitet, indem man Continuation-Passing-Stil der Codierung verwendet. Dann werden Call-Frames zu Fortsetzungen, die im Garbage-Collector-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.)