C++ Code Optimierung

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

[Gast]

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.

[nervenflatterer]

PiCiJi schrieb:

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.

Das sortieren ist quatsch. Beim Case wird eine Sprungtabelle erstellt in der steht, wo die zieladresse ist.
http://webster.cs.ucr.edu/AoA/Windows/HTML/LowLevelControlStructsa2.html
Also fast das selbe wie bei deinem array.

Du könntest die Klassen static al s Singleton machen, wobei ich bezweifle, dass das was bring.

Schaust du bei deinem Profiling immer nur auf die gesammtzeit? Du musst doch wissen welche funktionen lang brauchen und diese dann optimieren, nicht raten was was bringen könnte.

[Entenwickler]

Nichts als Spekulationen. Teste das ganze doch mal mit einem Profiler.

[PiCiJi]

Gibt es da spezielle Software für ein Profiling oder ein Zusatzmodul für Visual 2005 (hoffentlich kostenlos)? Es wäre ziemlich interessant mehr über die Abarbeitung einzelner Funktionen zu erfahren.

[lolz]

Ich verwende den profiler von compuware. Der Integriert sich nahtlos in das VS.

[PiCiJi]

Du meinst den Profiler DevPartner Performance Analysis Community Edition?

[ten]

hat vs nicht 'nen eingebauten profiler? der alte vs6 hatte das noch.

aber mal zum thema: wenn man ein array aus function pointern 'const' oder 'static const' definiert, alle elemente initialisiert und geschwindigkeitsoptimierung einschaltet, dann kann es sein, dass ein compiler sehr performanten code draus macht, der sich in puncto speed nicht von der switch/case-variante unterscheidet. man sollte sich auf jeden fall mal den erzeugten asm-code anschauen...
:xmas2:

[Badestrand]

PiCiJi schrieb:

Du meinst den Profiler DevPartner Performance Analysis Community Edition?

Doll, das Ding kostet n paar tausend Euro^^
Edit: Und ich hab auch noch nach nem Download-Link gesucht...

[hustbaer]

Profiler war beim VC6 dabei, beim 2003er und 2005er ist der leider nichtmehr dabei. Vom 2005er gibts die Team Edition oder wie die genau heisst, da ist wieder ein Profiler mit dabei. Kostet aber auch empfindlich mehr als die Pro Version...

@PiCiJi:
Du solltest gucken dass du sowenig wie möglich "ifs" hast deren Ausgang öfters wechselt. Ein gutes Beispiel ist das if in execute_cycle. Genauso sind aber alle "switch-case" in den einzelnen "opcode-Funktionen" betroffen, die werden im generierten Code genauso bedingte Sprünge werden, und die tun weh. Eine Möglichkeit einiges davon zu vermeiden wäre, jedem einzelnen Cyklus eines Opcodes eine eigene Funktion zu verpassen, und diese dann über einen Function Pointer aufzurufen. Das sollte nochmal einiges bringen. z.B. so:

class Cpu
{
public:
    // ...

    unsigned char read_pc()
    {
        ...
    }

    void fetch_instruction()
    {
        opcode = read_pc();
        cycle_pos = 1;
        cycle_function = first_cycle_function_for_opcode[opcode];
    }

    void execute_cycle() 
    {
        (this->*cycle_function)();
    }

    void op_and_absolute_c1()
    {
        aa_l = read_pc();
        cycle_pos = 2;
        cycle_function = &Cpu::op_and_absolute_c2;
    }

    void op_and_absolute_c2()
    {
        aa_h = read_pc(); 
        cycle_pos = 3;
        cycle_function = &Cpu::op_and_absolute_c3;
    }

    void op_and_absolute_c3()
    {
        if(reg_p_m)
        {
            check_for_interrupts(); 
            data_l = read_aa(DBR_, aa_w); 
            logic_and_b();

            cycle_pos = 0;
            cycle_function = &Cpu::fetch_instruction;
        }
        else
        {
            data_l = read_aa(DBR_, aa_w); 

            cycle_pos = 4;
            cycle_function = &Cpu::op_and_absolute_c4;
        }
    }

    void op_and_absolute_c4()
    {
        check_for_interrupts(); 
        data_h = read_aa(DBR_, aa_w + 1); 
        logic_and_w(); 

        cycle_pos = 0; 
        cycle_function = &Cpu::fetch_instruction;
    }

    // ...

    typedef void (Cpu::*CycleFunctionPtr)();
    CycleFunctionPtr cycle_function;

    static CycleFunctionPtr first_cycle_function_for_opcode[256];
};

Der Sprung über die Pointertabelle in execute_cycle wird durch einen Sprung über einen einzigen Pointer ersetzt, was schonmal gut ist, da das Sprungziel dadurch schon früher bekannt ist. execute_cycle sollte dabei natürlich auf jeden Fall inline gemacht werden, denn 2 Sprünge so knapp hintereinander kann die CPU auch nicht so gut verdauen wie wenn vor jedem Sprung noch ein paar Zyklen vergehen.
Weiters entfallen die ganzen "switch(cycle_pos)", was wiederum einiges bringen sollte.

Eventuell (ich kenne ja den restlichen Code nicht) kannst du dann sogar ganz auf die "cycle_pos" Variable verzichten.

Und es wäre noch eine Überlegung Wert die ganzen "opcode-Funtionen" static zu machen, und den this Pointer immer explizit mitzugegen -- ob das was bringt kommt allerdings darauf an wie gut (und schnell) dein Compiler mit Member-Function-Pointern umgehen kann (manche Compiler sind da ziemlich doof).

[lolz]

Badestrand schrieb:

PiCiJi schrieb:

Du meinst den Profiler DevPartner Performance Analysis Community Edition?

Doll, das Ding kostet n paar tausend Euro^^
Edit: Und ich hab auch noch nach nem Download-Link gesucht...

Die community edition kostet doch nix -> klick mich

[PiCiJi]

@hustbaer: danke für die Idee. Das sieht vielversprechend aus. Ich wandle alle Maschinenbefehle am WE derart ab. Der Methodenzeiger cycle_function wird also mit der Methode fetch_instruction initialisiert und dann steht am Ende jeder Zyklus Methode der nächste Zyklus durch Neubelegung des Methodenzeigers fest. Wird ein neuer opcode gefetcht, steht in einem 256 Elemente grossen Array jweils ein Zeiger auf die erste Zyklus Methode eines opcodes.

Auf die cycle_pos Variable kann ich dann verzichten, da ich diese nur noch in der Methode benötige, welche am Ende execute_cycle(); aufruft und neben einem DMA Transfer die Aufgabe hat am Ende eines abgearbeiteten Maschinenbefehls einen eventuell reingeschwebten Interrupt zu verarbeiten.

void Cpu::run()
{
	if(state_dma) {control_dma(); return;}

	if(cycle_pos == 0)
	{
		if(res_pending)
		{
			res_pending = false;
			perform_hardware_interrupt(true);
			sys.reset();
			return;
		}
		else if(nmi_pending)
		{
			nmi_pending = false;
			aa_w = (mode_e) ? 0xfffa : 0xffea;
			perform_hardware_interrupt();
			return;
		}
		else if(irq_pending)
		{
			irq_pending = false;
			aa_w = (mode_e) ? 0xfffe : 0xffee;
			perform_hardware_interrupt();
			return;
		}	
	}
	execute_cycle();
}

ich könnte "if(cycle_pos == 0)" ersetzen durch " if(cycle_function == &Cpu::fetch_instruction). Ok ich verwende execute_cycle auf jeden Fall inline. Obwohl das die Instrument Guided Optimization sicher selber erkennt, egal mit welchem Spiel ich evaluiere.

ok ich versuche mir auch den Profiler ziehen.

Wenn das was bringt, könnte ich deine Optimierung auch auf den 2. Instruktion Prozessor anwenden.

[hustbaer]

Da das eine GROSSE Änderung wird zieh dir auf jeden Fall vorher eine Kopie, bzw. falls du ein gutes Source-Control-System hast mach sie in einem Branch. Falls es nixe bringt oder sogar schlechter wird haste immer noch das Original. Obwohl ich sehr bezweifle dass es schlechter wird -- sicher sein kann man ja nie.

[PiCiJi]

so groß wird die Änderung nicht. Ich habe zur besseren Fehlerkorrektur der Maschinenbefehle diese komprimiert in einer Text Datei zusammengefasst. Befehle mit gleichen Zyklen aber unterschiedlicher Logik sind dort zusammengefasst. Die Logik wird in der Regel innerhalb eines Zykluses verarbeitet und die Zyklen haben die Aufgabe Speicherstellen zu lesen, diese in Register zu laden usw. Ein C++ Code wandelt diese 26 kb grosse Text Datei dann in eine 114 kb grosse C++ Datei um und natürlich die Initialisierung des Methoden Zeiger Array. Ich passe also nur diesen Code an.

[hustbaer]

Hehe. Auch nicht doof