3. Bytecode Interpreter vs. AST Walker

Bytecode Interpreter vs. AST Walker

  • M

    Naja, das hab ich schon mal gelesen, aber es beantwortet meine Frage noch nicht ganz:

    - JavaScript ist ja schon eine komplexe Sprache. Ich könnte mir also grundsätzlich vorstellen, dass man hier mit einem Bytecode Interpreter viel mehr optimieren könnte. Lohnt sich das auch bei einfacheren Sprachen?
    - Aussagen wie "Compiling to bytecode implicitly strips away irrelevant grammatical structure" finde ich erstmal nicht überzeugend. Was sollen das für irrelevante Strukturen sein? Wenn ich einen Branch habe, dann hab ich entweder einen entsprechenden AST Node mit zwei Verzweigungen, oder einen entsprechenden Opcode. Läuft meiner Meinung nach erstmal auf dasselbe hinaus. Oder kann ich das mit einem Bytecode Interpreter wesentlich vereinfachen? Ich wüsste grad nicht, wie.
    - Man braucht ja nicht unbedingt einen Tree Visitor, man kann einfach eine virtuelle Methode execute einbauen. So, jetzt hat man auf der einen Seite eine virtuelle Funktion und auf der anderen eine jump table. Ich glaub jetzt erstmal nicht, dass eine jump table wesentlich schneller ist, als eine virtuelle Funktion. Auch wenn die branch prediction hier besser funktionieren sollte, wird es doch an der gesamten Ausführungszeit wahrscheinlich eher weniger ausmachen.

    Deswegen halt die Frage, ob hier jemand tatsächlich schon selber praktische Erfahrungen mit sowas gesammelt hat. Vielleicht hat ja schon jemand so einen Interpreter geschrieben und kann sagen, ja der ist Faktor x schneller geworden, und vor allem das und jenes hat was gebracht...

    0
  • E

    Was ich relativ ungut zum implementieren bei einem AST Walker finde sind Return Statements. Wenn dir da ein eleganter Weg in den Sinn kommt sag an. Ich hab es mit einem speziellen Exception-Typ gemacht und Programme waren meistens über 90% der Laufzeit mit Exceptionhandling beschäftigt.

    Was sehr unschön ist sind auch goto-Statements.

    0
  • V

    Hab den Link anders verstanden, nämlich so:
    AST-Walker ist an sich genauso schnell: Die ganzen Optimierungen gehen ja auch auf dem AST. AST-Walker ist anfangs einfach schneller, weil einfacher, und man supi leicht an die guten Optimierungen kommt x*1->x, x+0->x. Irgendwann dann stößt am an Grenzen, wo die Bytecoder noch ein wenig Luft haben.

    - Aussagen wie "Compiling to bytecode implicitly strips away irrelevant grammatical structure" finde ich erstmal nicht überzeugend.

    Fand keiner, wurde ja auch widersprochen.
    Der Poster meinte, ein simpler AST könnte erstmal als sum(factor(constant(5))) im Speicher liegen und um per eval() an die 5 zu kommen, muss er viel laufen.

    - Man braucht ja nicht unbedingt einen Tree Visitor, man kann einfach eine virtuelle Methode execute einbauen.

    Davon gingen die Leute auch aus.

    So, jetzt hat man auf der einen Seite eine virtuelle Funktion und auf der anderen eine jump table. Ich glaub jetzt erstmal nicht, dass eine jump table wesentlich schneller ist, als eine virtuelle Funktion.

    Vielleicht ein Winziges Bißchen. Dann ist der Speicher vielleicht lokaler 7nd der Code kompakter und hat mehr Cache-Treffer.

    Lohnt sich das auch bei einfacheren Sprachen?

    Hängt nicht von der Einfachheit der Sprache ab, sondern davon, ob damit VIEL gerechnet werden soll.

    Ich würde auf jeden Fall einen Optimierer bauen, der auf dem AST zu optimieren versucht. Weil ich annehme, daß ich da Mathe-Tricks besser sehe. Und dann bräuchte ich laange Zeit nicht an Bytecode zu denken, der wie es scheint, ja auch erst schneller wird, wenn gejittet, gefädelt oder native compiliert wird.

    0
  • M

    Ok, danke für die ausführliche Antwort. So in etwa hab ich mir das auch vorgestellt, war nur irritiert, dass viele gleich auf einen Bytecode Interpreter setzen. Da ich keine gravierenden Vorteile sehe, bleib ich erstmal bei meinen AST Walkern, die sind auch viel schneller zu implementieren.

    0
  • M

    Ethon schrieb:

    Was ich relativ ungut zum implementieren bei einem AST Walker finde sind Return Statements. Wenn dir da ein eleganter Weg in den Sinn kommt sag an.

    Keine Ahnung, ich hatte sowas eher weniger im Sinn. Konkret habe ich eher mit "Expressions" zu tun, die zwar auch Schleifen und Verzweigungen enthalten können, aber keine Unterfunktionen und damit keine returns.
    Spontan hätte ich gesagt, wenn ich sowas implementieren würde (da ich das aber noch nie wollte, ist die Antwort jetzt nicht wirklich durchdacht), würde ich wahrscheinlich entweder als Rückgabewert einen Struct benutzen, der zusätzliche Flags wie ShouldReturn oder so enthalten kann, oder ich reiche ein Context Objekt durch (würde ich wohl sowieso machen) und der ReturnNode setzt in dem Context Objekt das entsprechende Flag und der FunktionNode oder StatementBlockNode drüber wertet das aus und springt dann raus.

    0
  • G

    Wir gehen davon aus, dass unser Bytecode ein plattgeklopfter AST ist.
    Nun ist der Vorteil des Bytecodes, dass ich jede Position im Bytecode über einen Index erreichen kann, das ist im Baum nicht möglich.

    Wenn ich zB eine Schleife habe, dann wird im Bytecode am Ende der Schleife mithilfe eines Sprungbefehls wieder zum Schleifenkopf gesprungen.
    Im AST muss sich der AST-Interpreter den Schleifenknopf-Knoten merken, damit er nach dem Body wieder zum Schleifenkopf zurückkehren kann.
    Kurz wir haben Funktionsaufrufe, diese kann man mithilfe der Funktionsaufrufe der Implementierungssprache realisieren. Diese Aufrufe sind jedoch teuer und die Rekursionstiefe ist begrenzt.
    Je nach Implementierung kommt es sogar recht schnell zu Stackoverflows. (return mit Exceptions hab ich auch schon gesehen, man kann das auch nutzen um zum Schleifenkopf zurückzukommen)

    Hinzu kommt, dass die Größe der einzelenen Codeobjekte bei Bytecodes meist kleiner und kompakter sind, was dem Caching zugute kommt.
    Beispiel: ein bedingter Branch währe im AST der Branch-Opcode und zwei Zeiger, im Bytecode währe es der Opcode und ein Offset, wobei der Offset-Datentyp wahrscheinlich sogar kleiner ist als ein Zeiger (wer brauchte denn einen 64bit Offset).

    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.

    0
  • M

    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?

    0
  • E

    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.

    0
  • G

    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.

    0
  • G

    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?))

    0
  • M

    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.

    0
  • E

    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)

    0
  • G

    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.

    0
  • E

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

    0
  • V

    Weil C keine virtuellen Funktionen hat, Du Nase. 🤡

    0
  • E

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

    0
  • E

    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?

    0
  • M

    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.

    0
  • E

    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.

    0
  • V

    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.

    0
Anmelden zum Antworten