mit Assembler optimieren
-
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
-
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.
-
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
-
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
-
Compiler optimieren besser als 95% der Programmierer.
-
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.
-
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?
-
@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)
-
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
-
War das nicht Alt+8 ?
Aber nur im Debugger, also vorher Strg+F10 um hinzugehen.
-
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
-
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)
-
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
-
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/
-
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.
-
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.