High-end-Tuning in C gesucht

[Miq (Gast)]

Liebe Experten,

ich habe eine virtuelle Maschine programmiert, die einen speziellen Assembler emuliert. Kern des Ganzen ist eine Schleife, die die Opcodes ausführt. Am Ende jeden Opcodes kommt ein Stück Programm, das entweder den nächsten Opcode aufruft, oder das Programm bei Ablauf der maximalen Stepzahl beendet. Dieser Code sieht im Prinzip so aus:

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

Bitte nicht am goto stören, das ist für die Jumptable nötig. Dieser Code wird viele Millionen Mal ausgeführt, weshalb auch minimale Optimierungen Wirkung zeigen. Ich komm' nicht mehr weiter damit, deswegen: hat irgendwer noch eine schlaue Idee dazu?

MfG Miq

[Michael E.]

Ein bisschen mehr Code könnt man vielleicht besser optimieren...

[camper]

Michael E. schrieb:

Ein bisschen mehr Code könnt man vielleicht besser optimieren...

wohl wahr. immerhin ist dein code bereits deutlich vom 08/15 stil im sinne von

while(--steps) pointers[*pc++]();

entfernt

[Miq (Gast)]

Michael E. schrieb:

Ein bisschen mehr Code könnt man vielleicht besser optimieren...

Ja, sicher, nur wird das dann sehr umfangreich. Ich habe ein Array (pointers) von Zeigern auf die Opcodes eines Assemblerprogramms, in der Reihenfolge, wie die im Programm stehen. pc ist der Index auf den aktuellen Opcode, und steps ist die Anzahl noch zur Verfügung stehender Programmschritte.
Ich fange mit "goto pointers[0];" mit der Ausführung an, mit pc==0 und steps==Maximal_erlaubter_Wert. Dann wird der spezielle Code für den Opcode ausgeführt, und dann kommt eben die oben beschriebene Sequenz. Es bringt wenig, die 256 Codesequenzen für die Opcodes anzugeben, da die ja nur in 1/256 aller Fälle durchlaufen werden (stimmt nicht ganz, die Häufigkeit der Opcodes ist unterschiedlich, aber p(Op)<1...). Dagegen wird die Abschlusssequenz _immer_ durchlaufen.
Die Ganze Wahrheit ist allerdings, dass es zwei Varianten gibt; nach Opcodes, die zu einer mathematischen Ausnahme führen können, sieht die Abfrage so aus:

if(--stp && isfinite(*sp)) goto ...

*sp ist der Wert unter dem aktuellen Stackpointer.

MfG Miq

[Miq (Gast)]

...Nachtrag: ich dachte eigentlich an irgendwas, damit ich das

if(--stp)

nicht jedesmal machen muss, immerhin interessiert mich ja nur der Zustand stp==0 als Ausnahme.

[camper]

ich kenne ja deinen assembler nicht, aber ich würde mal vermuten, dass nicht jeder opcode zu einem abbruch durch diese ausnahmebedingung führen kann. in diesem falle wäre es wohl zweckmässig den test nur für opcodes durchzuführen für die er potentiell fehlschlagen kann.

[rapso]

camper schrieb:

Michael E. schrieb:

Ein bisschen mehr Code könnt man vielleicht besser optimieren...

wohl wahr. immerhin ist dein code bereits deutlich vom 08/15 stil im sinne von

while(--steps) pointers[*pc++]();

entfernt

sein code schaut so aus wie jeder 08/15 emulatorcode ausschaut, es wäre sehr unperformant für jeden opcode einen funktionsaufruf durchzuführen.

rapso->greets();

[Korbinian]

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.

[toolazy]

Miq (Gast) schrieb:

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

wie macht man eigentlich pointer auf labels?

[Miq (Gast)]

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.

[Miq (Gast)]

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();

[Miq (Gast)]

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

[Gunnar_]

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();

[Miq (Gast)]

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.

[Miq (Gast)]

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