Bytecode Interpreter vs. AST Walker

Mechanics

gary1195 schrieb:

Im AST muss sich der AST-Interpreter den Schleifenknopf-Knoten merken, damit er nach dem Body wieder zum Schleifenkopf zurückkehren kann.

Ich gehe nicht von einem "AST-Interpreter" aus (bin mir nicht ganz sicher, wie du das meinst), sondern von AST-Knoten, die ausgeführt werden können. Damit wäre die Schleife ein Knoten, der weiß, dass er eine Schleife ist und den Schleifenrumpf eh als Zeiger hat. Dann merkt ein Optimizer beim Aufbauen vielleicht auch, dass die Anzahl der Iterationen konstant ist und die virtuelle execute Funktion des LoopNodes muss nur for (int i = 0; i < count; i++) loopBody->execute() aufrufen.
Genauso bei den Verzweigungen.

gary1195 schrieb:

Hinzu kommt, dass die Größe der einzelenen Codeobjekte bei Bytecodes meist kleiner und kompakter sind, was dem Caching zugute kommt.

Ja, das seh ich natürlich ein. Aber ist der Unterschied so groß? Ich kann mir nicht vorstellen, dass da mehr als paar Prozent rausspringen.

gary1195 schrieb:

Ein weiterer Vorteil ist, dass man bei Bytecode, insbesondere bei dem für Registermaschinen, eine Menge Optimierungen vornehmen kann, die bei ASTs nicht möglich sind.

Hast du Beispiele dafür?

Ethon

Schleifenkopf merken?
Hier mal mein erster Versuch eine Skriptsprache zu machen, lief über einen AST Walker: https://github.com/Ethon/vanilla/

Eine while-Schleife war im Prinzip:

void vanilla::while_statement_node::eval(context& c)
{
    while(bool_object_to_cpp_bool(_condition->eval(c)->to_bool()))
        _code->eval(c);
}

Sehe da Performancetechnisch keinen Haken.

gary1195

Mechanics schrieb:

gary1195 schrieb:

Im AST muss sich der AST-Interpreter den Schleifenknopf-Knoten merken, damit er nach dem Body wieder zum Schleifenkopf zurückkehren kann.

Ich gehe nicht von einem "AST-Interpreter" aus (bin mir nicht ganz sicher, wie du das meinst), sondern von AST-Knoten, die ausgeführt werden können. Damit wäre die Schleife ein Knoten, der weiß, dass er eine Schleife ist und den Schleifenrumpf eh als Zeiger hat. Dann merkt ein Optimizer beim Aufbauen vielleicht auch, dass die Anzahl der Iterationen konstant ist und die virtuelle execute Funktion des LoopNodes muss nur for (int i = 0; i < count; i++) loopBody->execute() aufrufen.
Genauso bei den Verzweigungen.

Also merkst du dir woher du kommst mit Funktionsaufrufen.

Mechanics schrieb:

gary1195 schrieb:

Hinzu kommt, dass die Größe der einzelenen Codeobjekte bei Bytecodes meist kleiner und kompakter sind, was dem Caching zugute kommt.

Ja, das seh ich natürlich ein. Aber ist der Unterschied so groß? Ich kann mir nicht vorstellen, dass da mehr als paar Prozent rausspringen.

Ist stark abhängig von Prozessor, Programm, aktueller Auslastung ...

Mechanics schrieb:

gary1195 schrieb:

Ein weiterer Vorteil ist, dass man bei Bytecode, insbesondere bei dem für Registermaschinen, eine Menge Optimierungen vornehmen kann, die bei ASTs nicht möglich sind.

Hast du Beispiele dafür?

Ok ich muss mich korrigieren, man kann jeden Bytecode auch in einen AST umwandeln.
Du willst diese Optimierungen allerdings nicht auf einem AST machen, denn dann musst du einen Haufen Pointer umbiegen, und du kannst nur einfach rauf und runter Laufen, wenn du Backpoiner hast, nochmehr Pointer gedöns.

gary1195

Ethon schrieb:

Schleifenkopf merken?

void vanilla::while_statement_node::eval(context& c)
{
    while(bool_object_to_cpp_bool(_condition->eval(c)->to_bool()))
        _code->eval(c);
}

Sehe da Performancetechnisch keinen Haken.

Du rufst für jeden Body Durchlauf einmal eval mit c auf.
Bei einem Bytecode interpreter würdest du nur den Instruction Pointer (ip) nach jedem Body Durchlauf einmal nicht auf ip + 1 ändern, sondern auf den Index des Anfangsbefehls des Schleifenkopfes.
Aufruf mit Argument und zurückkehren vs eine Zahl setzen. (ich vermute, dass das zweite schneller ist (aber vll wird das erste ja super optimiert?))

Mechanics

gary1195 schrieb:

Ethon schrieb:
Schleifenkopf merken?
void vanilla::while_statement_node::eval(context& c)
{
    while(bool_object_to_cpp_bool(_condition->eval(c)->to_bool()))
        _code->eval(c);
}
Sehe da Performancetechnisch keinen Haken.
Du rufst für jeden Body Durchlauf einmal eval mit c auf.
Bei einem Bytecode interpreter würdest du nur den Instruction Pointer (ip) nach jedem Body Durchlauf einmal nicht auf ip + 1 ändern, sondern auf den Index des Anfangsbefehls des Schleifenkopfes.
Aufruf mit Argument und zurückkehren vs eine Zahl setzen. (ich vermute, dass das zweite schneller ist (aber vll wird das erste ja super optimiert?))

Was gibts da großartig zu optimieren? Der Funktionsaufruf hier ist eben ein Aufruf einer virtuellen Funktion. Der Parameter ist ein Zeiger, also ein push. Beim Bytecode Interpreter hast du zwar nicht zwangsweise einen Funktionsaufruf (würde man aber nicht trotzdem paar Funktionen einbauen, um das übersichtlicher zu machen, oder stellst du dir da einfach eine Funktion mit paar tausend Zeilen vor?), dafür hast du aber zusätzlich eine Schleife drum rum, mit Sprüngen, und du hast die Jump Table für das switch-case. Also ziemlich gleichwertig zu einem Funktionsaufruf. Ich seh hier keinen Performancevorteil. Und wenn, dann im einstelligen Prozentbereich, auch uninteressant.

Ethon

Hmm? Der Aufruf ist doch auf C++-Ebene. Da ist Argumente übergeben oder Werte zurückgeben doch praktisch geschenkt. Einen Zeiger in ein Register zu stopfen - wenn der nicht sowieso drin bleibt - ist wohl ne Sache im untersten ns-Bereich.

Die Kosten des virtuellen Funktionsaufrufs sind zu vernachlässigen da der Bytecode-Interpreter auch welche ausführen müsste. (Dynamische Typisierung über virtuelle Funktionen der Superklasse 'object' realisiert)

gary1195

Schau mal http://hg.python.org/cpython/file/3.3/Python/ceval.c#l1350 ab Zeile 1350, ohne Makros wärs noch schlimmer.
Die benutzen sogar wenn vorhanden computet-gotos weil die ein bisschen schneller sind als switch-case.

Ethon

Weil C kein goto case hat. Hätten sie den Interpreter in D geschrieben wäre das weit schöner.

volkard

Weil C keine virtuellen Funktionen hat, Du Nase.

Ethon

Hat C doch? Zwar nicht als Sprachfeature aber trivial nachzubauen.

Ethon

Man könnte natürlich den AST auch iterativ statt rekursiv abarbeiten und ihm ein Typ-Enum (ähnlich Op-Code) mitgeben, dann würde man sich sämtliche virtuellen Calls sparen.
Seht ihr darin einen spürbaren Geschwindigkeitsvorteil?

Mechanics

Ethon schrieb:

Man könnte natürlich den AST auch iterativ statt rekursiv abarbeiten und ihm ein Typ-Enum (ähnlich Op-Code) mitgeben, dann würde man sich sämtliche virtuellen Calls sparen.
Seht ihr darin einen spürbaren Geschwindigkeitsvorteil?

Also, ich glaubs nicht. Nochmal kurz an alle, mir gings nicht so um Microoptimierungen von 20-50%, sondern eher um grundlegende Unterschiede, ab Faktor 2 aufwärts.
Vom Gefühl her würde ich sagen, die rekursive Methode wäre hier schneller. Die Knoten wissen alle schon, was zu tun ist. Die iterative Methode müsste dazu erst eine Funktion aufrufen und dann wieder entscheiden, was zu tun ist. Und dann wieder Funktionen aufrufen, um an die Parameter zu kommen. Ich vermute, das kann ein Compiler viel schlechter optimieren.

Ethon

Wozu Funktionen aufrufen? Musst du nicht.
Sehe nur gerade die iterative Postorder-Traversierung für dieses Einsatzgebiet als recht unschön.
Und ein Bytecode-Interpreter weiß auch nicht was zu tun ist bevor er den Code nicht dekodiert hat.

volkard

Ethon schrieb:

Man könnte natürlich den AST auch iterativ statt rekursiv abarbeiten und ihm ein Typ-Enum (ähnlich Op-Code) mitgeben, dann würde man sich sämtliche virtuellen Calls sparen.
Seht ihr darin einen spürbaren Geschwindigkeitsvorteil?

Hmm, Softwarestack wie std::stack statt Hardwarestack? Das klingt schon spaßig. Damit allein wird man keinen spürbaren Geschwindigkeitsvorteil erringen, fürchte ich.

Mechanics

Hab jetzt etwas rumgespielt und mir einen recht trivial Interpreter gebastelt, der in einer Schleife (inc und compare) eine Addition und Multiplikation ausführt, insgesamt 2 Variablen. Bisher krieg ich den Bytecode Interpreter nicht wirklich schnell, mein AST Walker ist doppelt so schnell.

Mechanics

Die erste Erkenntnis wäre damit, dass man mit einem Bytecode Interpreter nicht einfach grundsätzlich etwas schneller ist, sondern dass es gar nicht so einfach ist, den schnell zu bekommen.
Hab den Bytecode Interpreter etwas optimiert. Zum einen habe ich Anfangs QByteArray verwendet, weil ich Qt gewohnt bin und den Bytecode mit QDataStream schreiben wollte. Mit einem const char * bin ich tatsächlich ein gutes Stück schneller. Und dann habe ich noch den Bytecode von Hand optimiert und ein bisschen was aus der Schleife rausgezogen. Das würde aber theoretisch den Compiler (wesentlich) komplizierter machen, der AST Walker ist auch ohne diese Optimierung "schnell". Damit ist mein Bytecode Interpreter in etwa gleich schnell wie der AST Walker, aber noch nicht schneller.
Das Problem sind die vielen Stackzugriffe. Bei dem Beispiel das ich konstruiert habe, wäre ein registerbasierter Interpreter dann wohl sicher schneller. Probier ich vielleicht noch aus. Das würde aber wieder den Compiler komplizierter machen, weil er sich um die optimale Zuteilung der Register kümmern muss. Auch nicht ganz einfach.

Mechanics

So, und mit einem registerbasierten Interpreter bin ich jetzt tatsächlich fast doppelt so schnell wie mit den anderen beiden.
Ist jetzt nur reingehakt und überhaupt nicht optimiert, aber ich denke, viel könnte man auch nicht mehr optimieren, das meiste kann der Compiler eh schon. Vielleicht noch die Hauptloop in Assembler schreiben, um die Register wiederzuverwenden, aber ich glaub fast, dass der Compiler das auch ganz gut kann.