Performance: Switch vs. Methodenzeiger vs. X

[Demirug]

Es ist zwar kein echtes Leistungsproblem aber da die ganze Sache in der Regel CPU limitiert ist und ich letzten Endes nur noch an dieser Stelle etwas drehen kann wollte ich mal Meinungen einholen.

Die Situation ist folgenden. Eine C++ Klasse enthält viele virtuelle Methode die immer eine von 4 möglichen Varianten ausführen. Für jede Instanz wird beim Erzeugen für jede der Methode festgelegt welche Variante zum Einsatz kommt. Diese Festlegung ändert sich nachträglich auch nicht mehr. Allerdings kann jede Instanz eine völlig unterschiedliche Konfiguration enthalten.

Im Moment benutzte ich für jede der Methoden einen switch der dann die Methode anwählt welche beim Erzeugen festgelegt wurde. Ich könnte alternativ nun die Switchs gegen Methodezeiger tauschen die im Konstruktor initialisiere. Da das aber eine Menge arbeit ist wollte ich mal anfrage ob jemand so was schon mal gemacht hat und wie die Auswirkungen auf die Performances waren.

Alternativ bin ich natürlich auch für andere Vorschläge offen das Problem performant zu lösen. Die Möglichkeit für jede mögliche Konfiguration eine eigene Klasse zu schreiben scheidet aus. Bei über 40 Methode gibt das einfach zu viele Permutationen. Vom dynamischen Erzeugen von passenden VTables möchte ich aus wohl verständlichen Gründen auch die Finger lassen.

[micki]

ich mache das *hehe*


also switch ist abhängig vom compiler, bei manchen mußt du einfach nur die bedingung auf z.b. char casten, damit er eine jumptable anlegt, ist im endeffekt genau so aufwendig wie ein virtual-call.

aber wenn ich wirklich sicher gehen will, benutze ich funktionszeiger.

ja, funktionzeiger (nein, nicht methoden), den funktion übergeb ich dann als parameter den thispointer und ne referenz auf die parameter für die funktion die dann aufgerufen wird (die methode als z.b. __forceinline). so lös ich z.b. auf ziemlich generische weise den "collision"- und "respond"-teil beim particlesystem.

aber ich neige öfters, wenn es wirklich viele performancekritische permutationen gibt, templates zu benutzen. ich hatte mir mal nen kleinen an Dx angelehnten rasterizer geschrieben und für jedes mögliche/nötige fragmentformat und stagesetup dann die spezielle vertex/fragment-class und stagecombiner-class übergeben... leider hat sich dabei mein VS6-compiler die kugel gegeben ab einer gewissen projectgröße. aber ansonsten ist dieser ansatz sehr zu empfehlen, weil eben der compiler für einen alle permutationen macht. manchmal muss man jedoch sowas wie "edit&continue" abschalten damit der VS03-compiler damit klarkommt.
wenn du ein wenig mehr infos rausrücken würdest, könnte man aber eventuell noch mehr ideen spriessen lassen ;)

MfG
micki

[Demirug]

Die Permutationen von Compiler (wie auch immer) erzeugen zu lassen scheidet aus. Welche benötigt werden wird dynamisch zur Laufzeit durch eine veränderbare Konfiguration bestimmt. Deswegen brauche ich ja etwas generisches.

Ob ich nun Funktions oder Methoden Zeiger verwendete sollte da keinen Unterschied machen. Der Methodezeiger kümmert sich ja lediglich darum das auch this gleich mit Übergeben wird. Da ich in den Methoden auch auf die geschützten Membervariablen zugreifen muss ist ein Methodenzeiger funktionaler.

Die Switch werden zu Jumptables bei den verwendeten Compiler (VS03).

[micki]

Die Permutationen von Compiler (wie auch immer) erzeugen zu lassen scheidet aus. Welche benötigt werden wird dynamisch zur Laufzeit durch eine veränderbare Konfiguration bestimmt. Deswegen brauche ich ja etwas generisches.
mit templates kann man alle kombinationen erzeugen lassen... von wievielen möglichkeiten sprechen wir denn hier überhaupt? (btw. du könntests ja die faktoren deiner rechnung auch auflisten ;) )



Ob ich nun Funktions oder Methoden Zeiger verwendete sollte da keinen Unterschied machen. Der Methodezeiger kümmert sich ja lediglich darum das auch this gleich mit Übergeben wird. Da ich in den Methoden auch auf die geschützten Membervariablen zugreifen muss ist ein Methodenzeiger funktionaler.
das hatte ich deswegen erwehnt, weil du meintest

Da das aber eine Menge arbeit ist

wollte ich dir nur sagen wie das ralativ simpel ist, also auch tiparbeit sparrt, naja...


Die Switch werden zu Jumptables bei den verwendeten Compiler (VS03).
naja, dann bekommst du ja eventuell garnicht viel durch methodenzeiger, wenn die jumptable sehr gross ist, eventuell weniger cachemisses, aber ob dann intern mit

mov eax,[ecx]

oder

mov eax,[ebx+edx]

geladen wird, dürfte performancenmässig gleich sein.


MfG
micki

[Demirug]

Wie geschrieben über 40 Methoden mit jeweils 4 Möglichkeiten. Jede Kombination ist denkbar. Die Anzahl ist also größer als 4 hoch 40.

Von der Tiparbeit sehe ich keinen großen Unterschied ob ich nun Methoden oder Funktionszeiger verwende.

Die Jumptable hat 4 Einträge. Es geht mir allerdings nicht um die Auswirkungen auf die größe des Assemblerscode. Die Leistungfrage an dieser Stelle sollte IMHO eher von der Branchprediction der CPU abhängen. Hier ist nun die Frage ob diese besser mit einer Jumptable oder einem Sprung an eine dynamische adresse zurecht kommt.

[micki]

Die Jumptable hat 4 Einträge. Es geht mir allerdings nicht um die Auswirkungen auf die größe des Assemblerscode. Die Leistungfrage an dieser Stelle sollte IMHO eher von der Branchprediction der CPU abhängen. Hier ist nun die Frage ob diese besser mit einer Jumptable oder einem Sprung an eine dynamische adresse zurecht kommt.
das dürfte doch gleich sein, eine address wird in ein register geladen, mal aus einer member, mal aus einer table, und dann ein call auf die addresse im register. genau das sollte mein assembler oben zeigen, vielleicht hätte ich dann noch ein "call eax" einbauen müssen :).

[Demirug]

das dürfte doch gleich sein, eine address wird in ein register geladen, mal aus einer member, mal aus einer table, und dann ein call auf die addresse im register. genau das sollte mein assembler oben zeigen, vielleicht hätte ich dann noch ein "call eax" einbauen müssen :).

Der "call eax" war mir schon klar. Die Frage ist halt wirklich in wie weit das "gleich" ist. Ich werde wohl doch mal einen Testfall programmieren müssen um dann einen Performances Vergleich zu machen.

[ScottManDeath]

Mhmm, ich weis von dem Fall, dass es nur 2 Möglichkeiten gibts, dass ein
if(what) func1(); else func2(); wegen der Branchprediction fixer ist als ein Call über einen Function Pointer. Weiß aber nicht, wie das mit den Anzahl der Möglichkeiten skaliert.

[micki]

Mhmm, ich weis von dem Fall, dass es nur 2 Möglichkeiten gibts, dass ein
if(what) func1(); else func2(); wegen der Branchprediction fixer ist als ein Call über einen Function Pointer. Weiß aber nicht, wie das mit den Anzahl der Möglichkeiten skaliert.
das dürfte schneller sein als eine table, weil in dem fall hier die cpu wenigstens einen path anfangen kann abzuarbeiten und notfalls nen pipestall hat, zudem hat die prediction ebenfalls die möglichkeit sich von vorherigen durchläufen die counter für true/false zu merken, bei nem call über eine nicht kontante addresse (eine die nicht fix im code ist), ist es afaik auf heutigen CPUs auf jedenfall ein stall, da kein path (bis zum fertigladen der address) in die pipe kommt.

btw. das ist jetzt für 2funktionen gesprochen, bei 4 wie bei demi dürfte ne jumptable schneller sein, weil gegenüber einer trefferquote von 1:3 die wahrscheinlichkeit von 2stalls kommt, bei der jumptable/memberpointer hat man 1stall

MfG
micki

[zeckensack]

Die Jumptable hat 4 Einträge. Es geht mir allerdings nicht um die Auswirkungen auf die größe des Assemblerscode. Die Leistungfrage an dieser Stelle sollte IMHO eher von der Branchprediction der CPU abhängen. Hier ist nun die Frage ob diese besser mit einer Jumptable oder einem Sprung an eine dynamische adresse zurecht kommt.Mach eine Tabelle.

Call EAX kann keine vernünftige BP erreichen, da die Vorhersage an die Instruktion gebunden ist. Wenn du verschiedene Konfigurationen bunt mischst wäre es purer Zufall wenn die Vorhersage stimmt. Egal ob inline oder nicht.

Bei Indirektion über eine Tabelle sind die BP-Ressourcen an die Tabellendaten der Instanz gebunden, was viel besser funktioniert. Für den maximalen Knalleffekt sollten die Tabelleneinträge auf mindestens 8 Byte gepaddet werden.
void m1() {}
void m2() {}
void m3() {}
void m4() {}
...

#ifndef __x86_64
#define ASSIGN_FP(a) {(a),0}
#else
#define ASSIGN_FP(a) {(a)}
#endif

struct
{
void (*handler)(void);
#ifndef __x86_64
void* pad_dummy;
#endif
}
jumptab[4]={ASSIGN_FP(m1),ASSIGN_FP(m2),ASSIGN_FP(m3),ASSIGN_FP(m4)};
#undef ASSIGN_FP

void
rumble()
{
jumptab[0].handler();
...
}C++ mit Methodenzeigern geht sinngemäß genauso.

Evtl solltest du dich auch noch mit den calling conventions befassen. Wenn du bestimmte Bedingungen erfüllst, und dein Compiler clever genug ist, kann A)beim Delegieren das Kopieren der Parameter entfallen und manchmal auch B)CALL durch JMP ersetzt werden. Ich fürchte aber dass kein Compiler das hinkriegt, und du dir im Zweifelsfall selbst die Finger schmutzig machen musst.

Zur Theorie:
Funktion X und Funktion Y haben die gleichen Parameterlisten. Funktion X ruft Funktion Y auf, und reicht unverändert alle Parameter durch. Die liegen schon auf dem Stack! Man muss nur Funktion Y beibringen sie zu finden, und davon abhalten sie am Ende zu zerstören.

Das kann allgemein nur dann klappen, wenn der Frame-Pointer weggelassen wird, denn dieser drückt auf jeden Fall die Parameterliste nach oben, sodass sie eben runterkopiert werden muss.
Bei __cdecl sollte die delegierende Funktion als erstes in die Tabelle springen. Alles andere (inklusive anlegen lokaler Variablen!) sollte danach geschehen. Falls "alles andere" nichts ist, tritt B in Kraft.

Bei __stdcall geht's nur im trivialen Fall, weil die aufgerufene Funktion die Parameterliste auffrisst.

__thiscall ist wie __stdcall, nur mit ECX:=this (MSVC, MingW/GCC).

Das Problem in beiden Fällen ist, dass wenn B nicht in Kraft tritt, die alte Rücksprungadresse auf dem Stack liegt und somit Punkt A verhindert.
Man kann dieses Problem beinahe in C/C++ lösen, indem man der aufgerufenen Funktion einen zusätzlichen ungenutzten Parameter gibt (ganz links), wodurch einfach nur Platz für die auf dem Stack liegende Rücksprungadresse reserviert wird. Aber dann muss man natürlich einen (beliebigen) Wert übergeben, man kann dem Compiler nicht sagen dass er den Stack einfach in Ruhe lassen soll.

Also Assembler ahoi.
Ich habe schon ziemlich oft für performancerelevante Funktionen eigene calling conventions implementiert. Hat auch immer was gebracht. Ist aber nicht jedermanns Sache ;)

[Demirug]

Hemmungen ungewöhnliche Sache zu machen habe ich in dem Projekt schon lange keine mehr.

Der Ausschnitt dürfte das belegen:


BYTE buff[200+MAX_PATH];
DWORD bytes;

DWORD stringptr=(DWORD)&writebuff[100];
strcpy((char*)&buff[100], strpatchfile);

DWORD funcptr=(DWORD)&writebuff[50];
memmove(&buff[50],&function,4);

buff[0]=0x68;
memmove(&buff[1],&stringptr,4);
buff[5]=0xFF;
buff[6]=0x15;
memmove(&buff[7],&funcptr,4);
buff[11] = 0xEB;
buff[12] = 0xFE;

if (!WriteProcessMemory(hProcess,writebuff,buff,4096,&bytes))
return -13;


Wer rausbekommt für was die beiden Werte an der Stelle 11 und 12 gut sind ist wirklich gut.

Bei deinen Vorschlägen komme ich nun aber immer mehr zu dem Schluss das ich wohl doch am besten die VTable dynamisch erzeuge und damit den "switch" sowie den Call komplet überflüssig mache.

[zeckensack]

<...>
Wer rausbekommt für was die beiden Werte an der Stelle 11 und 12 gut sind ist wirklich gut.Das ist eine Endlosschleife =).label:
JMP short .labelDie Kurzform von jmp (mit Byte-Offset) ist zwei Bytes lang. Der Offset ist bei dir -2 (0xfe). Macht wenig Sinn, würde man meinen, doch kurioserweise gilt der Offset in Relation zu EIP nach dem jmp. Deswegen springt man mit Offset -2 nirgendwohin, sondern die Instruktion wird auf immer und ewig wiederholt.

Krieg' ich jetzt ein Eis? :)

[Demirug]

Das war ja der einfache Teil. Die Frage ist warum man auf die Idee kommt eine Endlosschleife in den Code zu bauen.

[Neomi]

Das war ja der einfache Teil. Die Frage ist warum man auf die Idee kommt eine Endlosschleife in den Code zu bauen.

Zur Synchronisation, ohne auch nur eine Millisekunde zu verschenken. Zur passenden Zeit wird die Schleife doch bestimmt mit NOPs überschrieben, oder mit einem Sprung zu einer anderen Routine.

[zeckensack]

Das war ja der einfache Teil. Die Frage ist warum man auf die Idee kommt eine Endlosschleife in den Code zu bauen.Du holst dir den Thread-Context, und schaust nach ob EIP=0x1000000B ist?
(dann wurde die Funktion mit dem Parameter aufgerufen, und du kannst das Teil killen)
Oder du überschreibst die 0xFE mit ... zB 0xF5. Oder sowas.

[zeckensack]

Zur Synchronisation, ohne auch nur eine Millisekunde zu verschenken.Sowas verschwendet zwar keine Zeit, aber Arbeitsleistung. In einem Multitasking-System sollte man das bleiben lassen.

[Demirug]

Du holst dir den Thread-Context, und schaust nach ob EIP=0x1000000B ist?
(dann wurde die Funktion mit dem Parameter aufgerufen, und du kannst das Teil killen)
Oder du überschreibst die 0xFE mit ... zB 0xF5. Oder sowas.

Ja, ich prüfe über den Thread Context ob der Punkt erreicht wurde um dann den Thread Context wieder auf einen vorher gesicherten Zustand zurück zu setzten. Wobei der EIB ja dynamisch ist weil ich vorher ja nicht weiß wo noch 4K Platz im Prozessraum sind.

[micki]

Call EAX kann keine vernünftige BP erreichen, da die Vorhersage an die Instruktion gebunden ist. Wenn du verschiedene Konfigurationen bunt mischst wäre es purer Zufall wenn die Vorhersage stimmt. Egal ob inline oder nicht.

Bei Indirektion über eine Tabelle sind die BP-Ressourcen an die Tabellendaten der Instanz gebunden, was viel besser funktioniert.
dafür ist die indizierung der tabelle an die Instruction gebunden, der zufall hat in beiden fällen schlechte chancen dass die Vorhersage stimmt.


Evtl solltest du dich auch noch mit den calling conventions befassen. Wenn du bestimmte Bedingungen erfüllst, und dein Compiler clever genug ist, kann A)beim Delegieren das Kopieren der Parameter entfallen und manchmal auch B)CALL durch JMP ersetzt werden. Ich fürchte aber dass kein Compiler das hinkriegt, und du dir im Zweifelsfall selbst die Finger schmutzig machen musst.

ich glaube mein VC03 macht das, meistens wenn ich im source

return Function();

schreibe, dann geht er mittels jump direkt in die funktion über, ohne call, und wenn diese dann ret aufruft, wird der stack der ersten function gepopt, aber wie du scho gesagt hast, nur wenn ich dieselben parameter weiterleite. zudem muss man afaik in den compilersettings "omit frame pointers" einstellen.