Vorteile der Kompilierung einer Sprache vs Ausführung der AST, sobald sie erstellt wird

Question

Was sind die Vor-/Nachteile beim Kompilieren eines Programms, um Code zu programmieren, anstatt einfach den AST von der Quelle zu konstruieren und Operationen auszuführen, während Sie den Baum durchlaufen?

Gibt es bestimmte Gründe, warum Sie einen über den anderen setzen möchten?

Answer 1

Interpretieren einer AST ist normalerweise viel langsamer als laufender Maschinencode, der das gleiche tut. Ein Faktor von 20 ist typisch.

Ein Vorteil ist, dass ein AST schneller zu produzieren ist, also weniger Zeit benötigt als die meisten Compiler, um Code zu generieren. AST-Interpreter neigen auch dazu, einfacher als Compiler zu sein, da die gesamte Codegenerierungsphase ignoriert werden kann.

Wenn Sie also ein Programm haben, das keine hohen Berechnungen durchführt, wird es mit einem Interpreter schneller ausgeführt. Auf der anderen Seite, wenn Sie einen Code haben, der häufig oder kontinuierlich in einer Umgebung läuft, in der Zyklen knapp sind, ist es besser kompiliert.

Einige Programmierumgebungen (z. B. viele Lisps) enthalten einen Interpreter zum Entwickeln von Code, da er schnelle Debugging-Zyklen unterstützt und einen Compiler zum Erstellen von schnellem Code, wenn die Entwicklung abgeschlossen ist. Einige dieser Systeme erlauben eine freie Mischung von interpretiertem und kompiliertem Code, was an sich interessant ist.

Kompilieren zu Bytecode ist ein Mittelweg: schneller kompilieren als Maschinencode, aber schneller auszuführen als ein AST. Nichtsdestoweniger kompilieren moderne Bytecode-Interpreter häufig nativem Code "just in time", während Ihr Programm läuft. Dies z.B. ist die Quelle des Namens für Suns HotSpot JVM. Er kompiliert die "Hot Spots" im Java-Bytecode zu nativem Code, um Programme zur Laufzeit zu beschleunigen.

Antwort auf Fragen in den Kommentaren

Es war eine Frage auf dem Faktor 20 oben erwähnt. Verweise auf diese Nummer sind alt, weil nur wenige moderne Sprachsysteme reine AST-Interpreter verwenden. (Eine bemerkenswerte Ausnahme bilden Kommandozeilen, aber die meisten von ihnen wurden schon vor langer Zeit entwickelt, und Geschwindigkeitsbenchmarks sind nicht üblich.) Sie sind einfach zu langsam. Mein Kontext ist Lisp-Dolmetscher. Ich habe ein Paar implementiert. Here for example is one set of Scheme benchmarks. Die Spalten, die den AST-Interpretern entsprechen, sind ziemlich leicht zu erkennen. Ich kann mehr und ähnliches aus dem Archiv der ACM Digital Library posten, wenn Bedarf besteht.

Ein weiterer grober Maßstab: Perl verwendet einen stark optimierten AST-Interpreter. Das Hinzufügen von 10 Millionen Schwimmern in einer engen Schleife auf meiner Maschine benötigt ungefähr 7 Sekunden. Kompiliertes C (gcc -O1) benötigt etwa 1/20 Sekunde.

Der Kommentator hat das Hinzufügen von 4 Variablen als Beispiel gegeben. Die Analyse hat die Kosten für Suchvorgänge vergessen. Eine klare Trennlinie zwischen Interpreter und Compiler sind vorberechnete Adressen oder Frame-Offsets für Symbole. In einem "reinen" Interpreter gibt es keinen. Das Hinzufügen von 4 Zahlen erfordert 4 Suchvorgänge in der Laufzeitumgebung, normalerweise eine Hash-Tabelle - mindestens 100 Anweisungen. In gut kompiliertem Code benötigt das Hinzufügen von 4 Ganzzahlen auf einem x86 2 Anweisungen und noch eine weitere, um das Ergebnis zu speichern.

Es gibt viele Schattierungen zwischen "reinen" AST-Interpetern und kompiliertem Maschinencode. Abhängig von der Sprache kann es möglich sein, Symboloffsets in den AST zu übersetzen. Dies wird manchmal als "schnelle Links" bezeichnet. Die Technik beschleunigt typischerweise die Dinge um einen Faktor oder 2 oder mehr. Dann gibt es "Compile-to-Bytecode und Go" -Systeme wie Python, PHP, Perl, Ruby 1.9+. Ihr Bytecode ist effektiv Threaded-Code (Opcodes können sehr komplizierte Dinge verursachen), also sind sie näher an ASTs als Maschinencode. Dann gibt es die oben erwähnten JIT-Bytecode-Interpreter.

Der Punkt ist, dass der Faktor von 20 reinen AST-Interpreter eine Buchstütze und Maschinencode der andere ist. In der Mitte gibt es viele Varianten mit Vor- und Nachteilen.

Answer 2

Ein weiterer noch nicht erwähnter Vorteil der Kompilierung ist, dass es oft viel einfacher ist als eine direkte Ad-hoc-Interpretation. Oft ist eine unverarbeitete Ausgangssprache für eine direkte Interpretation nicht sehr geeignet, und eine Verdopplung auf eine einfachere Sprache wird eine viel effizientere und einfachere Interpretation ermöglichen.

Zum Beispiel kann eine Sprache einen lexikalischen Bereich enthalten, der für jedes Mal, wenn eine Variable oder ein Funktionsargument dereferenziert wird, eine Namenssuche erfordert. Aber ein einfacher Transformationsdurchlauf, der die Variablen aufzählt und implizite Speicherverwaltungskonstruktionen einfügt, wird die Interpretation viel einfacher und viel effizienter machen - ein Array-Zugriff ist viel schneller als eine Hash-Tabelle mit einem Textschlüssel. Ein anderes Beispiel ist die Handhabung von Schließungen - ein Lambda-Hebepass ist viel einfacher als jeder mögliche Ad-hoc-Ansatz.

Es ist auch viel einfacher, einen flachen "Bytecode" als einen Baum zu interpretieren. Es gibt viele gut bekannte Optimierungstechniken (z. B. threaded code) für Bytecode-Interpreter, während ein AST-gehender Interpreter dazu verdammt ist, tot langsam zu sein.

Und, wenn Sie einige schwere Optimierungen (wie tote Code Beseitigung, konstante Faltung, Registerzuweisung, effiziente Befehlsplanung) müssen, ist die Kompilierung extrem trivial und can be split into ridiculously obvious small steps. Eine einfache Interpretation jeder nicht-trivialen Sprache ist dagegen immer kompliziert und kann nicht in etwas Einfaches und Offensichtliches aufgeteilt werden.