3. High-end-Tuning in C gesucht

High-end-Tuning in C gesucht

  • C

    sowas wäre denkbar wenn du dir mehrere sprungtabellen leisten willst - eine art 'loop-unrolling'
    du bräuchtest für jeden opcode zwei varianten: eine mit und eine ohne test. dann hast du 2^n sprungtabellen und benutzt jeweils die mit stp&((1<<n)-1). mit ein bisschen mehr trickserei kannst du evtl. sogar das dekrementieren von stp sparen bis auf den teil wenn die abfrage kommt.

    bzgl. der erweiterung der sprungtabelle: das hängt stark vom byte code ab (gibt es eine beschreibunbg davon?)
    aber wenn 50% aller opcodes trivial sind und diese 80% des programms ausmachen dann könnte sich eine partielle erweiterung lohnen.

    0
  • ?

    camper schrieb:

    sowas wäre denkbar wenn du dir mehrere sprungtabellen leisten willst - eine art 'loop-unrolling'
    du bräuchtest für jeden opcode zwei varianten: eine mit und eine ohne test. dann hast du 2^n sprungtabellen und benutzt jeweils die mit stp&((1<<n)-1). mit ein bisschen mehr trickserei kannst du evtl. sogar das dekrementieren von stp sparen bis auf den teil wenn die abfrage kommt.

    bzgl. der erweiterung der sprungtabelle: das hängt stark vom byte code ab (gibt es eine beschreibunbg davon?)
    aber wenn 50% aller opcodes trivial sind und diese 80% des programms ausmachen dann könnte sich eine partielle erweiterung lohnen.

    Das mit den 2^n Sprungtabellen ist eine gute Idee, allerdings in gcc nur mit einem Cast-Albtraum zu verwirklichen. Da die Label alle vom Typ void* sind, verhindert gcc eine Berechnung á la "jumps[opcode][--stp&3]". Nur wenn ich das erst auf einen int* umcaste, und hinterher zurück, geht das durch - wohl fühle ich mich nicht dabei... 🙄

    0
  • C

    Miq (Gast) schrieb:

    Da die Label alle vom Typ void* sind, verhindert gcc eine Berechnung á la "jumps[opcode][--stp&3]". Nur wenn ich das erst auf einen int* umcaste, und hinterher zurück, geht das durch - wohl fühle ich mich nicht dabei... 🙄

    das begreife ich nicht. was hindert dich daran eine mehrdimensionale sprungtabelle zu deklarieren:

    void* jumps[256][4];

    oder so ähnlich. eine andere möglichkeit wäre direktes loop unrolling evtl. mittels duff's device. dann müssten die opcodes wieder in standalone funktionen verarbeitet werden, aber zumindest ist das dann auch wieder standard code.
    netto gerechnet benötigst du jetzt für jeden opcode einen indirekten sprung (der in der regel nicht korrekt vorhergesagt werden kann und einen bedingten sprung, der in der regel nicht durchgeführt wird - es ist hier sinnvoll das sprungziel hinter dem opcode-code anzuordnen so das das ziel bereits beim ersten mal korrekt vorhergesagt wird: bedingte vorwärtssprünge fallen durch wenn der prozessor keine anderen informationen hat).

    bei funktionen hättest du zunächst einen bedingten call (nicht vorhersagtbar), ein return das (hoffentlich) selbst keine zusätzliche zeit braucht und wieder einen bedingten sprung welcher aber nur einmal existiert - und somit durch loop unrolling weitgehend eliminiert werden kann. das problem des zusätzlichen zeitaufwands beim call ist darin zu suchen, dass die returnadresse auf dem stack gespeichert werden muss.

    int tmp = stp % 4;
stp = ( stp + 3 ) / 4;
switch ( tmp )
{
    case 0: do {
            jumps[ *pc++ ]();
    case 3: jumps[ *pc++ ]();
    case 2: jumps[ *pc++ ]();
    case 1: jumps[ *pc++ ]();
            } while ( --stp );
}

    falls alle befehle konstante länge haben, könntest du auch noch das inkrementieren von pc aus dem schleifenkörper verbannen.

    0
  • ?

    camper schrieb:

    ...das begreife ich nicht. was hindert dich daran eine mehrdimensionale sprungtabelle zu deklarieren:

    void* jumps[256][4];

    oder so ähnlich.

    Daraufhin habe ich das mit einem Fünfzeiler nochmal probiert - es geht?!? Ich muss nochmal prüfen, warum ich bei meinem Code "you may not use a pointer of type void * in calculations" oder so ähnlich bekommen habe.

    camper schrieb:

    int tmp = stp % 4;
stp = ( stp + 3 ) / 4;
switch ( tmp )
{
    case 0: do {
            jumps[ *pc++ ]();
    case 3: jumps[ *pc++ ]();
    case 2: jumps[ *pc++ ]();
    case 1: jumps[ *pc++ ]();
            } while ( --stp );
}

    Das ist gut, und ganz anders, als ich das versucht habe - mach' ich am Wochenende mal nach! 😃

    camper schrieb:

    falls alle befehle konstante länge haben, könntest du auch noch das inkrementieren von pc aus dem schleifenkörper verbannen.

    Nein, haben sie leider nicht, das ginge vermutlich nur, wenn ich Deinen Vorschlag mit Funktionspointern nachbaue.

    Danke schön für Deine Anregungen. 👍

    MfG Miq

    0
  • ?

    Also in unserer Firma entwickeln wir seit einigen Jahren einen Interpreter, der über zwei Stufen mit Tabellen aus Funktionszeigern arbeitet. Der Interpreter wurde schon in einigen Applikationen eingesetzt (wir haben eine Programmiersprache entwickelt, die an C angelehnt ist und einfach zu bedienen ist) und ich kann sagen, dass der Mechanismus mit den Funktionszeigern sehr performant ist, da der Opcode einen Index in der Tabelle darstellt und ich nur einen CALL ausführen muss. Durch switch/case-Konstrukte durchläuft man ja im worst case alle vorhandenen Befehle.

    0
  • ?

    Wie performant ist Euer Interpreter denn (Funktionspointeraufrufe/s)? Ich schaffe momentan maximal 5,5 Mio. Pseudo-ASM-Befehle/s mit meiner goto-Arie, auf einem AthlonXP 2200+, alles ohne I/O und komplett im Cache.

    0
  • ?

    Miq (Gast) schrieb:

    Wie performant ist Euer Interpreter denn (Funktionspointeraufrufe/s)? Ich schaffe momentan maximal 5,5 Mio. Pseudo-ASM-Befehle/s mit meiner goto-Arie, auf einem AthlonXP 2200+, alles ohne I/O und komplett im Cache.

    Gerade nochmal nachgecheckt: es sind eher 10 Mio./s 😃

    0
Anmelden zum Antworten