Welche Opcode-Versandstrategien werden in effizienten Dolmetschern verwendet?

8

Welche Techniken fördern einen effizienten Opcode-Versand, um einen schnellen Interpreter zu erstellen? Gibt es einige Techniken, die nur gut auf moderner Hardware funktionieren und andere, die aufgrund von Hardware-Verbesserungen nicht mehr gut funktionieren? Welche Kompromisse müssen zwischen einfacher Implementierung, Geschwindigkeit und Portabilität gemacht werden?

Ich freue mich, dass Pythons C-Implementierung endlich über eine einfache switch (opcode) {...} -Implementierung für den Opcode-Versand als Option für das Kompilieren auf indirektes Threading hinausgeht, aber ich bin weniger erfreut, dass sie 20 Jahre gebraucht haben. Vielleicht, wenn wir diese Strategien auf Stackoverflow dokumentieren, wird die nächste Sprache schneller schneller.

    
joeforker 04.02.2009, 14:24
quelle

8 Antworten

13

Es gibt eine Reihe von Artikeln zu verschiedenen Versandarten:

M. Anton Ertl und David Gregg, Optimieren der indirekten Branch Prediction Accuracy in Virtual Machine Interpreters , in Proceedings der ACM SIGPLAN 2003 Konferenz über Design und Implementierung von Programmiersprachen (PLDI 03), S. 278-288, San Diego, Kalifornien, Juni 2003.

M. Anton Ertl und David Gregg, Das Verhalten effizienter virtueller Maschineninterpreter auf modernen Architekturen , in Proceedings der 7. Europäischen Konferenz für Parallel Computing (Europar 2001), S. 403-412, LNCS 2150, Manchester, August 2001.

Eine hervorragende Zusammenfassung bietet Yunhe Shi in seine Doktorarbeit .

Auch jemand hat vor ein paar Jahren eine neue Technik entdeckt , die ANSI C ist.

    
Paul Biggar 29.07.2009, 16:10
quelle
6

Bevor du etwas anfängst, schau Lua .

Es ist klein (150Kb), reines ANSI C, arbeitet an allem, was einen C-Compiler hat. Sehr schnell.

Und am wichtigsten - Quellcode ist sauber und lesbar. Es lohnt sich, es auszuprobieren.

    
dmajkic 04.02.2009 14:36
quelle
4

Indirektes Threading ist eine Strategie, bei der jede Opcode-Implementierung ihr eigenes JMP zum nächsten Opcode hat. Der Patch für den Python-Interpreter sieht etwa so aus:

%Vor%

opcode_targets bildet den Befehl im Bytecode der Sprache auf den Speicherplatz im Speicher der Opcode-Implementierung ab. Dies ist schneller, da der Verzweigungsprädiktor des Prozessors für jeden Bytecode eine unterschiedliche Vorhersage treffen kann, im Gegensatz zu einer switch -Anweisung, die nur einen Verzweigungsbefehl hat.

Der Compiler muss das berechnete goto unterstützen, damit dies funktioniert, was meistens gcc bedeutet.

Das direkte Threading ist ähnlich, aber beim direkten Threading wird das Opcode-Array durch Zeiger auf die Opcode-Implementierungen ersetzt:

%Vor%

Diese Techniken sind nur nützlich, weil moderne Prozessoren Pipelined sind und ihre Pipelines (langsam) auf einem falsch vorhergesagten Zweig löschen müssen. Die Prozessor-Designer setzen eine Verzweigungsvorhersage, um zu vermeiden, dass die Pipeline so oft gelöscht werden muss, aber die Verzweigungsvorhersage funktioniert nur für Verzweigungen, die eher einen bestimmten Pfad verwenden.

    
joeforker 04.02.2009 16:01
quelle
3

Just-in-time-Kompilierung ist eins.

    
Jason S 04.02.2009 14:28
quelle
1

Ein großer Gewinn besteht darin, den Quellcode in einer Zwischenform zu speichern, anstatt die lexikalische Analyse und das Parsing während der Ausführung zu wiederholen.

Dies kann von der Speicherung der Tokens über den Threading-Code im Stile von Forth und die JIT-Kompilierung reichen.

    
Darron 04.02.2009 15:05
quelle
0

Benchmarking ist eine gute Technik, um auf bestimmten Plattformen etwas schnell zu machen. Testen, verfeinern, erneut testen, verbessern.

Ich glaube nicht, dass Sie eine bessere Antwort bekommen können. Es gibt viele Techniken, um Dolmetscher zu machen. Aber ich gebe dir einen Tipp, tue keine Kompromisse, wähle einfach das, was du wirklich brauchst und verfolg diese Ziele.

    
Cheery 04.02.2009 14:58
quelle
0

Die Frage ist ein bisschen vage. Aber anscheinend wollen Sie einen Dolmetscher schreiben.

Interpreter verwenden normalerweise traditionelle Parsing-Komponenten: Lexer, Parser und Abstract Syntax Tree (AST). Dadurch kann der Entwickler gültige Syntax lesen und interpretieren und eine Baumstruktur von Befehlen mit zugehörigen Operatoren, Parametern usw. erstellen.

Sobald die AST-Form vorliegt, wird die gesamte Eingabe in Token umgewandelt und der Interpreter kann mit der Ausführung beginnen, indem er den Baum durchläuft.

Es gibt viele Optionen, aber ich habe kürzlich ANTLR als Parser-Generator verwendet, der Parser in verschiedenen Zielsprachen, einschließlich C / C ++, erstellen kann und C #.

    
spoulson 04.02.2009 15:14
quelle
0

Ich habe einen Blogbeitrag über die Implementierung von Thread-Interpretern gefunden, der nützlich war.

Der Autor beschreibt GCC-Label-basiertes Threading und auch, wie man dies in Visual Studio mit Inline-Assembler macht.

Ссылка

Die Ergebnisse sind interessant. Er berichtet 33% Performance-Verbesserung bei der Verwendung von GCC, aber überraschend ist die Inline-Assembly-Implementierung von Visual Studio 3 mal langsamer!

    
Ashley Davis 11.11.2010 17:33
quelle

Tags und Links