C++ Code Optimierung

PiCiJi

Ich versuche gerade Teile meines Codes zu optimieren und will im Vorfeld durch eure Meinungen überlegen ob es sinnvoll ist.

Ich habe eine Methode, welche eine von 256 weiteren Methoden aufrufen soll. Dafür befinden sich Zeiger auf diese 256 Methoden in einem Feld. Die initiale Methode ermittelt also eine Zielmethode und ruft diese im Zeigerfeld auf. siehe: (this->*array[Zielmethode])();

Diese Methode soll 2 - 3 Mio mal pro Sekunde durchlaufen.

Wäre es effizienter, wenn ich auf das Feld, welches Zeiger auf die 256 Methoden enthält, verzichte und das ganze über eine switch/case Anweisung löse? Also ein switch mit 256 cases. Jedes case enthält einen direkten Methodenaufruf.

akari

Hallo

schneller als der Array-Zugriff kann es nicht gehen, auch mit switch nicht. (Ich gehe davon aus, das das Erzeugen und Initialisieren des Arrays nicht mit in die Zeitfrage gerechnet wird)

bis bald
akari

ten

wieso brauchst du 256 verschiedene funktionen
ich wette, das kannste alles in eine schreiben
:xmas2:

akari schrieb:

schneller als der Array-Zugriff kann es nicht gehen

welch kühne behauptung. der 'this' ist auch noch dabei, immerhin zwei dereferenzierungen, wenn er pech hat...

ten schrieb:

wieso brauchst du 256 verschiedene funktionen
ich wette, das kannste alles in eine schreiben
:xmas2:

hey, da kann ich nur zugeben

Checker*amp*Murckser

Bevor ich mich zu irgendwelchen Behauptungen hinreißen alsse, hätte ich gerne mal was Code zwischen den Fingern.

PiCiJi

Ja das initialisieren des arrays ist für die Optimierung unrelevant.

Es handelt sich um einen Emulator und die 256 Funktionen sind Maschinenbefehle der zu emulierenden CPU. Diese Funktionen sind zu verschieden um sie sinnvoll zusammenzufassen. Ich frage mich also ob die switch/case Idee schneller abgearbeitet werden kann?

das Feld wird in der Klasse so initialisiert:

void (Cpu::*op_table[256])();

ein Feldelement(Methodenzeiger) wird derart eingefügt:

op_table[0x6d] = &Cpu::op_adc_absolute;

ten

welche cpu ist das?
du solltest vielleicht mal rauskriegen, wie die echte cpu befehle dekodiert, dann kommste bestimmt mit viel weniger als 256 funktionen aus...
:xmas2:

PiCiJi

Wie die Cpu Befehle dekodiert, weis ich. Das Zusammenfassen ähnlicher Maschinenbefehle würde weitere Verzweigungen erfordern und die Lesbarkeit verschlechtern. Ich bin mir auch nicht sicher ob die Performance spürbar steigt, wenn statt 256 nur noch 100 Methoden referenziert werden müssen?

PiCiJi schrieb:

Ich frage mich also ob die switch/case Idee schneller abgearbeitet werden kann?

Ja, die ist schneller weil dann für den Prozessor die u.U. aufwendige Adressenermittlung innerhalb des Arrays entfällt. Allerdings vergrössert sich dadurch der Code erheblich.

Entenwickler

Von was zum Teufel redest du?
Die Adresse von jeder Funktion steht zur Compilezeit fest!

akari

Hallo

aufwendige Adressenermittlung innerhalb des Arrays

Was denn für eine aufwendige Addressermittlung?
In einen Array sind die Elemente einfach aneinander gehängt. Die Addresse des Elements n ergibt sich also einfach aus Adresse des ersten Elements +n. Das ist einfache Integer-Addition und wird von jeder vernünftigen CPU in einem Schritt erledigt. Und schneller gehts nicht.

bis bald
akari

PiCiJi

ok ich poste mal etwas mehr Code. Diese Methode ruft den Maschinenbefehl auf.
Die Eigenschaft cycle_pos gibt an welcher Zyklus des aktuellen Maschinenbefehles abgearbeitet werden soll. Wenn cycle_pos = 0 ist, heißt das, daß der aktuelle Maschinenbefehl abgearbeitet wurde und der nächste eingelesen werden muss.

void Cpu::execute_cycle()
{
	if (cycle_pos) (this->*op_table[opcode])();
	else
	{
		opcode = read_pc(); //nächster Maschinenbefehl
		cycle_pos = 1;     //1. Zyklus des Befehls
	}
}

Ein abgearbeiteter Zyklus eines Maschinenbefehles erhöht cycle_pos automatisch um 1 oder setzt es am Ende wieder auf 0.

Ein Maschinenbefehl z.B.

void Cpu::op_and_absolute()
{
	switch(cycle_pos++)
	{
		case 1:
			aa_l = read_pc();
			break;
		case 2:
			aa_h = read_pc();
			break;
		case 3:
			if(reg_p_m) check_for_interrupts();
			data_l = read_aa(DBR_, aa_w);
			if(reg_p_m) { logic_and_b(); cycle_pos = 0; }
			break;
		case 4:
			check_for_interrupts();
			data_h = read_aa(DBR_, aa_w + 1);
			logic_and_w();
			cycle_pos = 0;
			break;
	}
}

So meine ich das :

if (cycle_pos) (this->*op_table[opcode])();

Hier muss der Prozessor erst den Wert von "opcode" ermitteln, dann anhand dieses Wertes den Index (Adresse) innerhalb von "op_table", dann kann die Adresse von "op_table[opcode]" geladen und ausgeführt werden.

switch(cycle_pos++)
{
  case 1:
  case 2:
  case 3:
 (...)
}

Hier "hüpft" der Prozessor ein paar mal und ist dann gleich dort wo er sein soll (ohne Umwege gewissermassen).

Bitte schreibt jetzt nicht, dass das "Erbsen zählen" ist :-).

Entenwickler

Vergleichst du Bananen mit Kirschen? Die beiden Codes stehen in keinem Zusammenhang.

Was du da laberst ist sowas von schwachsinnig. Ich sage auch das swich ist schneller, aber nur weil da der Compiler besser optimieren kann und die meisten Calls mit inlining einspart.

Entenwickler schrieb:

Was du da laberst ist sowas von schwachsinnig.

Fertig ? Gut.

Mein zweites BEISPIEL von oben kann auch so lauten :

switch(opcode)
{
  case 1: {op_and_absolute(); break;}
  case 2: {op_add_absolute(); break;}
  case 3: {op_xor_absolute(); break;}
 (...)
}

lolz

Hast du bereits getestet, dass dein bisheriger Code zu langsam ist? Oder bildest du dir ein er wäre zu langsam und optimierst auf Verdacht?

PiCiJi

Nein auf Verdacht optimiere ich nicht. Der Code läuft schnell genug auf meinem 3,5 GHz Amd aber viel Potenzial ist nicht mehr. Später soll jeweils ein zusätzliche Prozessor emuliert werden und dann wird es eng. Deswegen überlege ich bei den häufig frequentierten Funktionen, wie man sie optimieren könnte. Ausserdem kompiliere ich den Code mit Instrument Guided Optimization. Das bringt noch mal 30% mehr Leistung in meinem Fall. Ich verwende in meinem Code keine inlines oder sotiere case Anweisungen nicht mit den am häufigsten ausgeführten nach oben. Ich verlasse mich hierbei auf die Instrument Guided Optimization.

hustbaer

Schneller als ein indirekter Sprung? Weiss nicht...
Einen Versuch ist es Wert. Wenn dann solltest du auf jeden Fall sicherstellen dass der Compiler weiss dass alle Werte die "opcode" halten kann auch als "case" vorkommen, sonst könnte er auf die dumme Idee kommen statt eines Jumptables was komplizierteres zu verwenden.
Also z.B.

void foo(unsigned char opcode)
{
    switch(opcode) // wenn opcode ein int wäre müsste der Compiler hier Code erzeugen der dafür
                   // sorgt das der ganze Block übersprungen wird bei Werten < 0 oder > 255
    {
    case 0:
    //...
    case 255:
    // und _kein_ default:
    }
}

Nochwas: Als Jumptable werden soweit ich weiss 2 verschiedene Dinge bezeichnet, einmal das was du schon machst (mit dem Array aus Funktionszeigern), und einmal ein "Table" aus lauter "jump" Befehlen, also inetwa sowas:

table:
    jmp Case0Function
    jmp Case1Function
    jmp Case2Function
    ...
    jmp Case255Function

Bei so einem Table kannst du dann einfach die Adresse "table + opcode * N" auf einen Funktionszeiger casten, und die Funktion aufrufen (wobei N die Länge eines Sprundbefehls inklusive Daten ist). Der indirekte Sprung fällt dadurch weg, allerdings hast du dafür insgesamt einen Sprung mehr. N sollte dabei möglichst eine 2er Potenz sein, also wohl 8. Dazu padded man dann einfach die nicht vom Sprundbefehl verbrauchten Bytes mit einem NOP.

Sowas kann man natürlich nicht direkt in C++ implementieren, d.h. du müsstest inline Assembler verwenden.

Noch zwei Sachen:
Brauchst du wirklich eine zyklengenaue Emulation? Wenn nicht würde das sicher einiges an Speedup bringen auf die zu verzichten.

Oder guck dir doch mal den Source von anderen CPU Emulatoren an, gibt ja einige Open Source Emulatoren für z.B. 68k und andere CPUs. Im MAME Projekt wird davon z.B. massiv gebraucht gemacht.

PiCiJi

Wenn dann solltest du auf jeden Fall sicherstellen dass der Compiler weiss dass alle Werte die "opcode" halten kann auch als "case" vorkommen, sonst könnte er auf die dumme Idee kommen statt eines Jumptables was komplizierteres zu verwenden.

Ja das ist sichergestellt. opcode ist vom Typ unsigned char. also 8 bit = 256 Werte. Ich werde es also mal versuchen.
Auf Assembler will ich komplett verzichten. Die zyklengenaue Emulation ist auch notwendig. Zugegeben Nutzen und Kosten stehen in keinem guten Verhältnis. Nur wenige Spiele benötigen diese Genauigkeit.

PiCiJi

ok ich habe es getestet. Im Debug Modus war die Ausführung mit der switch/case Idee fast 10% langsamer. Im release Mode mit profile guided optimization war kein Unterschied festzustellen, da der Compiler die cases sicher neu sortiert nach den für das spezielle Spiel am häufigsten verwendeten nach oben. Zusammenfassend muss ich die switch/case Idee verwerfen.

Ich emuliere 4 Prozessoren. Jeder Prozessor ist innerhalb einer Klasse beschrieben. Für jede Klasse wird nur genau eine Instanz angelegt. Kann man da vielleicht ansetzen? Kann man dem Compiler mitteilen, dass es bei einer Instanz bleibt? Ich frage mich, ob es vorteilhafter wäre auf das Klassenkonzept zu verzichten in Bezug auf die Ausführungsgeschwindigkeit. Wobei ich gelesen habe, dass aktuelle Compiler das Klassenkonzept gut auflösen.