High-end-Tuning in C gesucht

Korbinian schrieb:

schon mal drüber nachgedacht, dass evtl der compiler besser optimieren kann als du? nicht immer ist es sinnvoll höchst komplizierte dinge zu schreiben, da der compiler dann nicht so gut ansetzen kann.

Ja, im Prinzip hast Du Recht, aber ich bin da schon eine Weile drüber hinaus - ohne arrogant klingen zu wollen.
Ich benutze gcc auf verschiedenen Plattformen, und habe viele Sachen ausprobiert. Die Version mit Jumptable und gotos ist generell etwa 25% schneller, als ein vom Compiler optimierter Riesen-switch, von if-Gebirgen ganz abgesehen.

toolazy schrieb:

Miq (Gast) schrieb:

if(--steps) goto *pointers[++pc];
goto Ende;

wie macht man eigentlich pointer auf labels?

Das ist eine nicht ANSI-konforme Erweiterung des gcc. Man kann void-Pointer mit Labeladressen initialisieren, etwa so:

void *ziel = &&Ziel_Label;

Der Aufruf geht dann mit

goto *ziel;

Das ist extra in gcc eingebaut worden, weil solche Jumptables häufiger gefragt sind, und man sie sonst nur über Assembler bauen kann.

Lesco

beim borland compiler geht das z.B. nicht

Helium

Miq (Gast) schrieb:

Das ist extra in gcc eingebaut worden, weil solche Jumptables häufiger gefragt sind, und man sie sonst nur über Assembler bauen kann.

Naja, was verstehst du unter häufiger? Das ist wohl eine der am seltesten genutzte Erweiterung, die die gcc überhaupt bietet.

rapso

Helium schrieb:

Miq (Gast) schrieb:

Das ist extra in gcc eingebaut worden, weil solche Jumptables häufiger gefragt sind, und man sie sonst nur über Assembler bauen kann.

Naja, was verstehst du unter häufiger?

so häufig wie man eben switch/case verwenden möchte.. aber in schnell.

Helium schrieb:

Das ist wohl eine der am seltesten genutzte Erweiterung, die die gcc überhaupt bietet.

quelle für diese statistik?

rapso->greets();

Helium schrieb:

Miq (Gast) schrieb:

Das ist extra in gcc eingebaut worden, weil solche Jumptables häufiger gefragt sind, und man sie sonst nur über Assembler bauen kann.

Naja, was verstehst du unter häufiger? Das ist wohl eine der am seltesten genutzte Erweiterung, die die gcc überhaupt bietet.

Na ja, es gibt diverse Open Source-Projekte, die sich mit Emulatoren beschäftigen, oder Java oder eine Scriptsprache integrieren, und sofern die mit gcc erzeugt werden, ist fast immer eine Jumptable beteiligt. Wenn man portabel programmieren will/muss, ist die Assembler-Variante keine Lösung, und gcc gibt's ja für fast jede Plattform. Ich entwickele z.B. gleichzeitig für SPARC/Solaris und i386/Linux/Windows, und das geht mit identischem Quelltext.

MfG Miq

Miq (Gast) schrieb:

Korbinian schrieb:

schon mal drüber nachgedacht, dass evtl der compiler besser optimieren kann als du? nicht immer ist es sinnvoll höchst komplizierte dinge zu schreiben, da der compiler dann nicht so gut ansetzen kann.

Ja, im Prinzip hast Du Recht, aber ich bin da schon eine Weile drüber hinaus - ohne arrogant klingen zu wollen.
Ich benutze gcc auf verschiedenen Plattformen, und habe viele Sachen ausprobiert. Die Version mit Jumptable und gotos ist generell etwa 25% schneller, als ein vom Compiler optimierter Riesen-switch, von if-Gebirgen ganz abgesehen.

Ich habe fuer den selben Zweck auch mal erwaegt, eine Jumptable zu erstellen, nur habe ich festgestellt, dass der g++-Compiler sowieso grosse Switchbloecke ab -O3 (oder so) autmatisch zu Jumptables macht. Allerdings habe ich nur in C++ geschrieben..

rapso

Gunnar_ schrieb:

Ich habe fuer den selben Zweck auch mal erwaegt, eine Jumptable zu erstellen, nur habe ich festgestellt, dass der g++-Compiler sowieso grosse Switchbloecke ab -O3 (oder so) autmatisch zu Jumptables macht.

das hab ich auch immer gedacht, als ich dann letztens mir den asm output durchschaute, war das nicht so, nur so bin ich dann auf die extension von gcc gestossen (war die neuste für ARM verfügbare version vom GCC).
als ich das mal geschaft hatte, mußte ich von U32 auf U8 casten, dann hat er das gemacht gehabt, aber das ganze kostet auf dem ARM auch zeit, deswegen muss ich das zZ per hand machen.

rapso->greets();

Yep, dass kann ich bestätigen, ansonsten hätte ich mir das goto (schauder!) erspart

Eine kleine zusätzliche Beschleunigung kommt beim "Handcodieren" auch daher, dass am Ende jeder Opcodeverarbeitung direkt via Jumptable gesprungen wird. Die "Standardjumptable" ist nur an einer Stelle codiert, und nach jedem Opcode geht's erst zu einer zentralen Nachverarbeitung, und dann wieder zur Jumptable, was etwas länger dauert.

MfG Miq

camper

Miq (Gast) schrieb:

Yep, dass kann ich bestätigen, ansonsten hätte ich mir das goto (schauder!) erspart

Eine kleine zusätzliche Beschleunigung kommt beim "Handcodieren" auch daher, dass am Ende jeder Opcodeverarbeitung direkt via Jumptable gesprungen wird. Die "Standardjumptable" ist nur an einer Stelle codiert, und nach jedem Opcode geht's erst zu einer zentralen Nachverarbeitung, und dann wieder zur Jumptable, was etwas länger dauert.

MfG Miq

hast du das mal nachgemessen? iirc verfügen alle neueren (pc-) prozessoren über einen interen call stack so dass returns keine extra zeit brauchen. es kommt allerdings auch auf die operationen für die einzelnen opcodes an, da sprungbefehle generell nur über einen geringen throughput verfügen. ich schätze mal das ergebnis wird für verschiedene compiler und prozessoren unterschiedlich ausfallen. wenn das problem wirklich die sprünge sind (also pro opcode im grunde so gut wie nichts getan wird), wäre es evtl. überlegenswert, die sprungtabelle zu vergrössern (also zwei opcodes auf einmal verarbeiten) - dann wird man allerdings ein bisschen template magie anwenden müssen, damit der quellcode nicht explodiert. ausserdem wird der vorteil der geringeren sprunganzahl dann möglicherweise durch erhöhte cache misses wieder aufgefressen.

camper schrieb:

hast du das mal nachgemessen?

Ja, deswegen mach' ich das ja selbst. s.o., ca. 25% schneller.

camper schrieb:

...wenn das problem wirklich die sprünge sind (also pro opcode im grunde so gut wie nichts getan wird), wäre es evtl. überlegenswert, die sprungtabelle zu vergrössern (also zwei opcodes auf einmal verarbeiten) - dann wird man allerdings ein bisschen template magie anwenden müssen, damit der quellcode nicht explodiert. ausserdem wird der vorteil der geringeren sprunganzahl dann möglicherweise durch erhöhte cache misses wieder aufgefressen.

Ja, habe ich auch drüber nachgedacht, aber theoretisch gibt es dann eine Jumptable mit 65536 Adressen (256x256 Opcodes). Teilweise ist die Opcodeverarbeitung trivial, aber einige sind länglich. Ich glaube nicht, dass ich um die Sprünge selbst herumkomme, aber wenn ich mir das dauernde "if(--stp)" sparen könnte...
Ich träume von irgendeiner Bitmanipulation, die in Abhängigkeit von stp>0 eine andere Jumptable benutzen lässt als bei stp==0. Ob sich damit aber gegenüber dem if() etwas sparen lässt?

MfG Miq

camper

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.

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...

camper

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.

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

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.

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.

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