| Autor |
Beitrag |
Thorsten83
 
Beiträge: 191
Erhaltene Danke: 1
|
Verfasst: Di 04.08.09 12:26
Hey,
gibt's da irgendwo was vernünftiges?
Ich seh halt immer wieder, dass hier Leute irgendwas in Assembler schreiben wollen, weil sie der Meinung sind, dass dadurch alles besser wird...
Wäre sonst am überlegen ob ich hier so etwas schreibe, besteht daran Interesse bzw. hätte jemand Lust mitzumachen?
Ich dachte da erstmal so an Spielereien bezüglich Pipelining, Lokalität etc. ...
Kleines Beispiel:
Kapitel 1 
Mal angenommen, man hat ein Array mit Zahlen darin, und möchte diese aufsummieren.
Das zu programmieren ist natürlich überhaupt kein Thema:
  Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
| asm(
"xorl %eax, %eax \n" // result = 0
"movl 0x8(%ebp), %ecx \n" // field
"movl 0xC(%ebp), %edx \n" // n
"shl $2, %edx \n" // n*=4
"addl %ecx, %edx \n" // end_address = start_address + 4*n
"cmpl %ecx, %edx \n" // end_address > start_address?
"jl end \n" // goto end
"loop: \n"
"addl (%ecx), %eax \n" // result += field[i]
"addl $0x4, %ecx \n" // field++
"cmpl %ecx, %edx \n" // edx > ecx ?
"jg loop \n"
"end: \n" // end: nop0
); |
Wenn man den Kram jetzt laufen lässt, sieht man, dass z.B. auf meinen Core Duo das Aufsummieren eines Feldes mit 2000 Elementen in 9000 Taktzyklen durchgeführt wird, also ~4,5 Taktzyklen pro Element.
Wie nicht anders zu erwarten geht das auch schneller:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
| asm(
"xorl %eax, %eax \n" // result1 = 0
"xorl %ebx, %ebx \n" // result2 = 0
"movl 0x8(%ebp), %ecx \n" // field in ecx
"movl 0xC(%ebp), %edx \n" // n
"shl $2, %edx \n" // n*=4
"addl %ecx, %edx \n" // end_address = start_address + 4*n
"cmpl %ecx, %edx \n" // start_address >= end_address?
"jl end \n" // goto end
"loop: \n"
"addl (%ecx), %eax \n" // result1 += field[i]
"addl 4(%ecx), %ebx \n" // result2 += field[i+1]
"addl $0x8, %ecx \n" // field+=2
"cmpl %ecx, %edx \n" // edx > ecx ?
"jg loop \n"
"end: \n" // end: nop0
"addl %ebx, %eax \n" // return result1 + result2;
); |
Das Ergebnis: ~2,4 Taktzyklen/Element!
Was ist passiert?
Beim ersten Beispiel sieht der Programmablauf ungefähr so aus:
Erstmal das Set-up,
dann wird die Addition des i-ten Elements angeschmissen.
Dieser Befehl verschwindet in der Pipeline, als nächstes wird das Inkrementieren des Feldzeigers angeschmissen, auch dies läuft in die Pipe.
Die Sprungvorhersage geht davon aus, dass man in der Schleife bleibt, und geht wieder zum Addieren über.
Die Addition wird aber noch abgearbeitet, also bleibt der Prozessor quasi stehen und muss warten, bis das Ergebnis verfügbar ist.
Im zweiten Fall sind zumindest die Additionen zu den Zwischenergebnissen unabhängig voneinander, können also parallel abgearbeitet werden, hieraus ergibt sich die Beschleunigung von knapp 90%.
So, keine Ahnung inwieweit das "Allgemeinwissen" ist, oder ob Interesse an mehr Kram besteht?
Man kann auch in vielen Fällen ohne Ahnung von Assembler zu haben in den Hochsprachen schon was tricksen, und dadurch ordentlich was an Geschwindigkeit rausholen...
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Di 04.08.09 13:20
Das Problem bei der Optimierung von Algorithmen ist, dass jede Optimierung immer einen Anwendungsspezifischen Anteil hat, den man nicht ohne Weiteres abstrahieren kann.
Außerdem hasse ich diese blöde Intel-Syntax (find NASM freundlicher zu lesen).
Außerdem, wenn man schon C nutzt, sollte man wenigstens auch die vollständig Parametrierung nutzen; liest sich nämlich noch mal besser in Bezug auf die Registerzuordnung.
Auch ein Outline in einer Hochsprache (gern auch C) wären für den ein oder anderen sicherlich hilfreich.
Edit: Da die Frage ja auch in Bezug auf die Sinnhaftigkeit zielte, hier mal noch ne kurze Ergänzung:
Es bringt nichts, die Optimierungstechniken für ASM zu zeigen, wenn die Grundlagen zum schreiben optimaler Algorithmen für Hochsprachen noch nicht bekannt sind. Die müssen für solch ein Tutorial mindestens an erster Stelle kommen, sonst passiert Dir das, was hier bereits in einigen AMS&Opti-Threads der Fall war, dass ASM-ler von Pascal-Puristen geschlagen wurden. Oder Leute mit der FPU (dem lahmsten Teil der CPU) schneller waren als Ansätze mit SSE3, die voll gepipelined waren.
Wichtig wäre hier mindestens ein Konzept, welche Punkte du ansprechen möchtest, und was alles vermittelt werden soll. Einfach nur an beliebigen Beispielen herausgreifen "DAS GEHT SCHNELLER!" bringt nur SEHR wenig, wenn man nicht das Wissen vermittelt, warum das der Fall ist.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
hazard999
Beiträge: 162
Win XP SP2
VS 2010 Ultimate, CC.Net, Unity, Pex, Moles, DevExpress eXpress App
|
Verfasst: Di 04.08.09 13:40
Wie BenBe schon festgestellt hat ist der Optimierungsvorgang (fast) immer Problem und Anwendungsspezfisch.
Von der reinen Laufzeit her würd ich mal sagen das ich das mit 2 Threads (hast ja einen CoreDuo) und ohne händische Assembler-Optimierung, warscheinlich schneller schaffen. Kommt halt auf die Aufgabe an.
Für 20.000 Zahlen ist das Thread-Spwaning wahrscheinlich schon zu viel oberhead.
Aber bei 2.000.000 Zahlen wär ich glaube ich mit Divide&Conquer auf jedenfall schneller
just my 2 cents
_________________ MOV EAX, Result;MOV BYTE PTR [EAX], $B9;MOV ECX, M.Data;MOV DWORD PTR [EAX+$1], ECX;MOV BYTE PTR [EAX+$5], $5A;MOV BYTE PTR [EAX+$6], $51;MOV BYTE PTR [EAX+$7], $52;MOV BYTE PTR [EAX+$8], $B9;MOV ECX, M.Code;MOV DWORD PTR [EAX+$9], ECX
|
|
Thorsten83 
Beiträge: 191
Erhaltene Danke: 1
|
Verfasst: Di 04.08.09 14:18
Hey,
danke für die Rückmeldungen
Ich wollte in erster Linie gucken ob überhaupt Interesse an solch einem Thread besteht, und mal hören was ihr da so reinschreiben würdet...
Natürlich muss man erstmal die asymptotischen Laufzeiten betrachten, z.B. einen BubbleSort zu pimpen wird im Allgemeinen eher nicht sinnvoll sein 
Ich glaube aber, dass das Thema zu umfangreich ist, um in diesem Thread groß behandelt zu werden.
In Assembler hab ich den Kram in erster Linie geschrieben weil ich dachte, dass das hier am besten passt.
Allerdings muss ich zugeben, dass das mein erster Assembler-Code seit dem zweiten Semester ist, das können hier bestimmt einige besser
Meine Idee ging in die Richtung, kleine Beispiele zu optimieren und dazu zu erklären, wie bzw. warum diese Optimierung funktioniert, wenn man das versteht kann man ja auch bei anderen Problemen gucken wie man das dann optimieren könnte, das ist wohl etwas kurz geraten.
Die optimierte Fassung würde z.B. in C so aussehen:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
| int sum(int * field, int n)
{
int result1 = 0, result2 = 0;
int i;
int size = n - (n & 0x1); // Das letzte Bit auf 0 setzen, damit bei ungeraden Feldgrößen nicht zu weit gelesen wird
for(i = 0 ; i < size ; i+=2)
{
result1 += field[i];
result2 += field[i+1];
}
if(i < n) result1 += field[i];
return result1 + result2;
} |
Die Ergänzung für ungerade Feldgrößen fehlt im Assembler-Beispiel allerdings.
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Di 04.08.09 14:27
 BenBE hat folgendes geschrieben  : | | Es bringt nichts, die Optimierungstechniken für ASM zu zeigen, wenn die Grundlagen zum schreiben optimaler Algorithmen für Hochsprachen noch nicht bekannt sind. |
Hier verlinke ich immer gerne etwas von den Wurzeln des FastCode Projects. OptimalCode war das damals, da ist im Moment Müll drauf. Was richtiges finde ich so in der Form nur noch im InternetArchive...
web.archive.org/web/...www.optimalcode.com/
Sehr lesenswert. Ist zwar schon älter, aber das Meiste trifft auch auf aktuelle (Delphi-)Compiler noch zu. _________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Di 04.08.09 14:45
| Thorsten83 hat folgendes geschrieben : | C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
| int sum(int * field, int n)
{
int result1 = 0, result2 = 0;
int i;
int size = n;
for(i = size-2 ; i >= 0; i-=2)
{
result1 += field[i];
result2 += field[i+1];
}
if(i<0) result1 += field[0];
return result2 + result1;
} | |
Hier mal noch eine Optimierung. Sollte optimaler sein, da:
1. Prüfung gegen 0 in Schleife
2. Keine Index-Berechnung bei ungeraden Index-Werten
3. Keine unnötigen arithmetischen Operationen
4. Vertauschung in Return um Compiler zu animieren, Result2 zuerst zu laden und somit Taktzyklen für die Addition von Result1 bereitzustellen.
@Martok: Thx für den Link _________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Thorsten83
Beiträge: 191
Erhaltene Danke: 1
|
Verfasst: Di 04.08.09 15:31
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Di 04.08.09 18:27
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Thorsten83
Beiträge: 191
Erhaltene Danke: 1
|
Verfasst: Di 04.08.09 19:44
|
|
|
