mit Assembler optimieren

Andreas_L

Hallo, ich möchte gerne etwas Assembler lernen, um zeitkritischen Code in meinen C++ Programmen zu optimieren. Insbesondere möchte ich mit Assembler Rekursionen aus meinen Programmen entfernen.

Als Übungsaufgabe habe ich mir gestellt die Summe von 1 bis zu einer bestimmten Zahl zu berechnen, in C++ sieht das in etwa so aus:

int Summe = 0;
for(int i = 1; i <= GRENZE; i++) Summe+=i;

In Assembler hab ich dafür geschrieben:

int Summe2 = GRENZE;
__asm{
	pusha
	mov ecx, Summe2
	xor eax, eax
Label1:
	add eax, ecx
	dec ecx
	jnz Label1
	mov Summe2, eax
	popa
}

Kann man das noch weiter optimieren? - diese Version ist nämlich für große Zahlen etwas langsamer als die for-Schleife.

Um dem Ziel der Rekursionen etwas näher zu kommen wollte ich folgende Funktion (die die gleiche Summe berechnet) entrekursivieren:

int Funktion(int Wert)
{
	if(Wert > 1) return Funktion(Wert-1)+Wert;
	else return 1;
}

Mein AssemblerCode sieht dafür so aus:

int Summe3 = GRENZE;
__asm{
	pusha
	mov ecx, Summe3
	mov edx, esp
Pushen:
	push ecx
	dec ecx
	test ecx, 0FFFFFFFFh
	jnz Pushen
Popen: 
	pop eax
	add ecx, eax
	cmp edx, esp
	je Ende
	jmp Popen

Ende:
	mov Summe3, ecx
	popa
	}

Ich weiß das test ecx, 0FFFFFFFFh kann man sich sparen, da dec ecx auch die entsprechenden Flags setzt. Hab das nur eingebaut um eine Möglichkeit zu sehen wie man schneller als mit cmp einen Wert auf 0 prüfen kann. Gibt es denn noch schnellere Möglichkeiten - ist

or ecx, ecx

schneller?
Ist das normal, dass man den Pointer auf den Stack speichert um später erkennen zu können, dass der Stack wieder leer ist? Kann man den Code auch noch mehr optimieren?

Wenn ich einen rekursive Funktion, die einen Binärbaum durchwandern soll, mit Assembler entrekursivieren will, wie gehe ich dann mit Pointern um? Ich habe z.B. folgende Struktur:

struct BinaerKnoten
{
BinaerKnoten *lc, *rc;
short Hoehe;
}

Jetzt bekommt die Funktion den Wurzelknoten als Pointer übergehen - wie greife ich dann mit Assembler auf lc und rc zu?
Kann ich das so machen, um in ebx den Pointer auf den rechten Teilbaum zu erhalten?

mov eax, Wurzelknoten
mov ebx, [eax+4h]

könnte ich auch schreiben

mov eax, [eax+4h]

?
In diesem Beispiel habe ich vorrausgesetzt, dass ein Pointer 4 Byte groß ist - wie sieht das denn dann auf 64Bit Systemen aus? (in C++ nehme ich für so etwas immer den sizeof() Operator)

Und eine letzte Frage: Manchmal möchte ich in einer Abfrage mehrere Werte Vergleichen: z.B. in C++: if(Wert1 == 0 && Wert2 != 0)...
kann man so einer Verknüpfung auch in Assembler realisieren oder muss man da erst die eine Abfrage machen und dann entsprechen jumpen?

Vielen Dank für eine Antwort,

viele Grüße

Andreas

volkard

Andreas_L schrieb:

Als Übungsaufgabe habe ich mir gestellt die Summe von 1 bis zu einer bestimmten Zahl zu berechnen, in C++ sieht das in etwa so aus:
int Summe = 0;
for(int i = 1; i <= GRENZE; i++) Summe+=i;

Und beschleunigt sieht er zum Beispiel so aus:

int Summe = GRENZE%2!=0?(GRENZE+1)/2*GRENZE:GRENZE/2*(GRENZE+1);

Assembler führt Dich vermutlich nur auf Abwege, wenns um Speed geht. Aber viel Spaß damit.

taljeth

Andreas_L schrieb:

Kann man das noch weiter optimieren? - diese Version ist nämlich für große Zahlen etwas langsamer als die for-Schleife.

Das ist vermutlich die wichtigste Erkenntnis: Einfach was nach Assembler übersetzen, macht es nicht schneller. Der Compiler ist auch nicht völlig blöd geschrieben und weiß, wie er für die Hardware optimieren muss. Ich bin jetzt auch nicht der größte Experte darin, aber zwei Sachen, die der Compiler ziemlich sicher machen wird, ist zum einen, die Schleife richtig zu alignen und Loop Unrolling zu machen (also mehrere Schleifendurchläufe hintereinanderschreiben, bevor der Sprung kommt).

Viel besser optimieren kann man das ganze natürlich, indem man nicht Assembler nimmt, sondern die gute alte Formel n * (n + 1) / 2. Ein besserer Algorithmus toppt jede Optimierung eines schlechten Algorithmus.

Ich weiß das test ecx, 0FFFFFFFFh kann man sich sparen, da dec ecx auch die entsprechenden Flags setzt. Hab das nur eingebaut um eine Möglichkeit zu sehen wie man schneller als mit cmp einen Wert auf 0 prüfen kann. Gibt es denn noch schnellere Möglichkeiten - ist
or ecx, ecx
schneller?

test ecx, ecx ist die übliche Variante, glaube ich.

Ist das normal, dass man den Pointer auf den Stack speichert um später erkennen zu können, dass der Stack wieder leer ist? Kann man den Code auch noch mehr optimieren?

Das kommt mir eher kaputt als normal vor. Nimm ein Register her und merk dir, wie viele Einträge du auf den Stack gepusht hast. Wobei mir der ganze Code seltsam vorkommt, die Funktion sollte sich ganz ohne Stackeinsatz formulieren lassen.

Und eine letzte Frage: Manchmal möchte ich in einer Abfrage mehrere Werte Vergleichen: z.B. in C++: if(Wert1 == 0 && Wert2 != 0)...
kann man so einer Verknüpfung auch in Assembler realisieren oder muss man da erst die eine Abfrage machen und dann entsprechen jumpen?

Ja, mehrere bedingte Sprünge hintereinander.

- pushad/popad ist unnötig - wenn du die Register sichern musst, dann nur die, die du auch benutzt
- code/data aligment (-> nen richtigen Assembler verwenden)
- loop unrolling
- unter x64-64 gibt es sowohl 64bit als auch 32bit Pointer
- man kann mittels cmovXX/setXX mehrere Bedingungen verknüpfen. Mehr als 2 oder 3 sollte aber nicht sein

Andreas_L

Viel besser optimieren kann man das ganze natürlich, indem man nicht Assembler nimmt, sondern die gute alte Formel n * (n + 1) / 2. Ein besserer Algorithmus toppt jede Optimierung eines schlechten Algorithmus.

Sorry, vielleicht hab ich mich auch nicht so klar ausgedrückt - aber ich wollte mit den Beispielen nur Assembler lernen und gucken was man damit rausholen kann. Ich kenne die Formel n*(n+1)/2 - deshalb hab ich ja auch dieses Beispiel genommen, weil ich dann auch für große Zahlen direkt mit dem Taschenrechner nachprüfen kann, dass ich keinen Programmierfehler gemacht habe.

Das kommt mir eher kaputt als normal vor. Nimm ein Register her und merk dir, wie viele Einträge du auf den Stack gepusht hast.

An eine weitere Zählvariable habe ich auch gedacht, allerdings dachte ich, dass sei dann langsammer, weil ich ja immer noch diese Variable aktualisieren muss?!

Wobei mir der ganze Code seltsam vorkommt, die Funktion sollte sich ganz ohne Stackeinsatz formulieren lassen.

Klar, diese Aufgabe lässt sich leicht ohne Stack realisieren, aber das sollte ja nur eine Übung sein um eine Funktion zu entrekursivieren, denn bei einem Binärbaum kommt man nicht mehr ohne Stack aus (oder doch)? Ich hätte auch als Beispiel direkt den Binärbaum nehmen können aber da habe ich ja das Problem wie ich mit den Pointern umgehe -

Jetzt bekommt die Funktion den Wurzelknoten als Pointer übergehen - wie greife ich dann mit Assembler auf lc und rc zu?
Kann ich das so machen, um in ebx den Pointer auf den rechten Teilbaum zu erhalten?
Assembler Code:
mov eax, Wurzelknoten
mov ebx, [eax+4h]
Assembler Code:
mov eax, Wurzelknoten
mov ebx, [eax+4h]
Assembler Code:
mov eax, Wurzelknoten
mov ebx, [eax+4h]

könnte ich auch schreiben Assembler Code:
mov eax, [eax+4h]
Assembler Code:
mov eax, [eax+4h]
Assembler Code:
mov eax, [eax+4h]

War das hier korrekt?

- unter x64-64 gibt es sowohl 64bit als auch 32bit Pointer

Aber wie wird dann der Pointer in meinem C++ angelegt - kann ich einfach +4h machen?

Auf jeden Fall vielen Dank für eure Antworten, viele Grüße

Andreas

Icematix

Compiler optimieren besser als 95% der Programmierer.

Andreas_L

Das mag sein, aber meine mit Assembler programmierte Version (die mit dem Stack arbeitet, pushed und poped) war schneller als die in C++ geschriebene rekursive Methode. Von daher erhoffe ich mir Rekursionen aus meinen Programmen (eben beim Durchgehen eines Binärbaumes) mit Assembler entfernen zu können und so einen Geschwindigkeitsvorteil zu erhalten.

Icematix

Andreas_L schrieb:

Das mag sein, aber meine mit Assembler programmierte Version (die mit dem Stack arbeitet, pushed und poped) war schneller als die in C++ geschriebene rekursive Methode. Von daher erhoffe ich mir Rekursionen aus meinen Programmen (eben beim Durchgehen eines Binärbaumes) mit Assembler entfernen zu können und so einen Geschwindigkeitsvorteil zu erhalten.

Hast du dir mal den vom Compiler generierten Code im Disassembler angesehen?

abc.w

@Andreas_L: Da machst Du irgendwas falsch. Versuch doch mal, Dein C/C++ Programm mit verschiedenen Optimierungsstufen zu kompilieren (wenn es denn danach noch funktioniert)

Andreas_L

Hallo, also ich bin nochmal die Compiler-Einstellungen durchgegangen und hab explizit alles auf Geschwindigkeitsoptimierung und nicht Codegrößenoptimierung gesetzt.

Mit "QueryPerformanceCounter((LARGE_INTEGER*)&StartTimeNorm);" frage ich Start und Endzeit ab und berechne dann die Differenz.

Wenn ich die Summe von 1-5000 berechnen will, dann liefert diese Methode für die for-Schleife (also die Beste Möglichkeit) einen Wert von 11 (ich kenne die Einheit jetzt nicht- aber trotzdem ist ja ein quantitativer Vergleich möglich).

Meine Assembler-Methode (die mit dem Stack arbeitet) liefert einen Wert von 38 und die rekursive Variante 215. Auch wenn ich das mehrmals teste bleiben die Werte in dieser Größenordnung. D.h. für mich ist die Assembler-Methode schon ne recht gute Alternative, oder nicht?

Was mich bei der rekursiven Variante aber etwas gewundert hat ist, dass die Zeit nicht linear mit der Größenordnung ansteigt - für die Summe bis 2500 braucht sie nur einen Wert von 75 - weiß aber ehrlich gesagt nicht, warum das so ist.

Hast du dir mal den vom Compiler generierten Code im Disassembler angesehen?

Also da ich gerade erst mit Assembler anfange kenne ich mich noch nicht so gut damit aus - wisst ihr vielleicht ob Visual Studio 2008 die Möglichkeit bietet den erzeugten Code in Assembler anzuzeigen?

Vielen Dank und viele Grüße

Andreas

volkard

War das nicht Alt+8 ?
Aber nur im Debugger, also vorher Strg+F10 um hinzugehen.

Andreas_L

cool, vielen Dank das funktioniert!!!

Für die for-Schleife ergab sich folgender Code (bei GRENZE = 5000):

int Summe = 0;
0040104B  xor         ebx,ebx 
0040104D  xor         edx,edx 

	for(int i = 1; i <= GRENZE; i++) Summe+=i;
0040104F  mov         eax,1 
00401054  xor         ecx,ecx 
00401056  add         ebx,eax 
00401058  lea         ecx,[ecx+eax+1] 
0040105C  lea         edx,[edx+eax+2] 
00401060  lea         edi,[edi+eax+3] 
00401064  add         eax,4 
00401067  cmp         eax,1388h 
0040106C  jle         TestFunc+46h (401056h) 
0040106E  add         ecx,edx 
00401070  add         ecx,edi 
00401072  add         ebx,ecx

Um ehrlich zu sein verstehe ich den Code aber noch nicht komplett - mein größtes Problem sind diese Zeilen:

00401058  lea         ecx,[ecx+eax+1] 
0040105C  lea         edx,[edx+eax+2] 
00401060  lea         edi,[edi+eax+3]

Was macht er hier?

Was mich allerdings gewundert hat ist, dass er meine Assemblerbefehle ja gar nicht 1:1 umsetzt:

Pushen:
		//push ecx
004010AD  push        ecx  
		//	dec ecx
004010AE  dec         ecx  
		//	test ecx, 0FFFFFFFFh
004010AF  test        ecx,0FFFFFFFFh 
		//	jnz Pushen
004010B5  jne         Pushen (4010ADh)

ich hatte jnz Pushen geschrieben und er hat jne Pushen daraus gemacht - gibts dafür einen Grund?

Viele Grüße

Andreas

Andreas_L schrieb:

ich hatte jnz Pushen geschrieben und er hat jne Pushen daraus gemacht - gibts dafür einen Grund?

jnz und jne sind zwei Bezeichner für den selben opcode

Schablone

Andreas_L schrieb:

Um ehrlich zu sein verstehe ich den Code aber noch nicht komplett - mein größtes Problem sind diese Zeilen:
00401058  lea         ecx,[ecx+eax+1] 
0040105C  lea         edx,[edx+eax+2] 
00401060  lea         edi,[edi+eax+3]
Was macht er hier?

Da rechnet er ecx <- ecx + eax + 1. Die eckigen Klammern sind darum, weil lea eigentlich für Operationen auf Adressen gedacht ist.

Der Compiler hat da die Schleife ausgerollt, und rechnet immer 4 Werte in einem Durchlauf aus, wobei in eax immer 0, 4, 8, 12, ... addiert werden, in ecx immer 1, 5, 9, 13, etc., in edx 2, 6, 10, ... und in edi 3, 7, 11, ...

Ganz zum Schluss werden die Teilsummen dann zusammengerechnet.

Das hat zwei Vorteile (die je nach CPU unterschiedlich starke Effekte bringen)
* einmal wird die Schleife 4 mal so selten durchlaufen, d.h. es werden 4x weniger Vergleiche (cmp) und 4x weniger Sprünge (jle) ausgeführt, die ja eigentlich nichts mit der Berechnung zu tun haben.
* außerdem gibt es zwischen den Registern weniger dichte Abhängigkeiten, sodass die Pipeline besser gefüllt werden kann. Die Addition auf ecx, edx, und edi erfolgt eine gute Weile (relativ gesehen ;)) nachdem eax das letzte mal geändert wurde. Wenn du hintereinander auf das selbe Register zugreifen würdest, dann müsstest du u.U. auf das Ergebnis der vorherigen Operation warten. (Gerade dieser Effekt ist stark CPU-spezifisch)

Andreas_L

cool, vielen Dank für die Erklärung. Hab die Summe mal bis 4999 laufen lassen - da konnte er diese vierer Zerlegung nicht machen und hat auch etwas länger gebraucht^^

Kann ich also lea für beliebige, längere arithmetische Rechnungen verwenden? Ist das dann auch schneller als die Berechnungen einzeln zu machen?

Viele Grüße

Andreas

abc.w

Andreas_L schrieb:

Kann ich also lea für beliebige, längere arithmetische Rechnungen verwenden? Ist das dann auch schneller als die Berechnungen einzeln zu machen?

Das hängt von der CPU ab, hier gibt es mehr Info: http://www.agner.org/optimize/

Icematix

Das ist wie gesagt eigentlich der Grund warum Compilercode fast immer schneller sein sollte, der Compiler weiß ganz genau was die CPU am schnellsten/effektivsten ausführen kann und spart Zeit bei Aktionen die man als Highlevel-Coder gar nicht wahrgenommen hätte.

Lüttmoor

Andreas_L schrieb:

Kann ich also lea für beliebige, längere arithmetische Rechnungen verwenden

Nein, beliebige gehen nicht. LEA steht für Load Effective Address, und die Rechnungen, die du da durchführen kannst, müssen eine Berechnung der Effektiven Adresse sein. Diese haben die Form

Base + Index * Scale + Displacement

Base und Index sind Register. 
Scale ist 1, 2, 4 oder 8. 
Displacement ist eine Konstante.