Funktion optimieren
-
Ich möchte folgende Funktion in Inline-Assembler optimieren:
void sort_a(size_t arr[]) { for (size_t i = 0; i < n - 1;) { size_t a = arr[i]; size_t b = arr[i + 1]; if (a > b) { arr[i] = b; arr[i + 1] = a; i = 0; continue; } i++; } }Habt ihr vielleicht sachdienliche Hinweise für mich?
-
- Der Code kompiliert so nicht.
- Welcher Assambler?
- Kennst du https://godbolt.org/
- Warum? (Ich verstehe etwas optimieren zu wollen und ich verstehe was mit Assembler machen zu wollen, aber die Kombination verstehe ich nicht).
-
@Lennox Das ist eigentlich genau die Art von Code, den moderne Compiler bereits exzellent optimieren dürften. Schau dir daher erstmal den Code an, der generiert wird und überlege, ob du überhaupt eine Idee hast, wie man das "besser" machen könnte. Wenn das der Fall ist, dann kannst du sicher etwas konkretere Fragen stellen, wie das in Inline-Assember umzusetzen wäre. Wenn nicht, sei lieber froh darüber, das eben nicht machen zu müssen
Der zweite "sachdienliche Hinweis": Optimiere erstmal die Algorithmen selbst und vertraue darauf, dass der Compiler einen guten Job macht. Wenn mich mein menschliches Pattern Matching nicht täuscht ist das eine sehr naive Bubble-Sort Implementierung. Da gibt es sicher geeignetere Verfahren für deinen Anwendungsfall (es sei denn du willst ausschließlich winzigste Arrays sortieren). Da dürfte mehr bei rumkommen als bei selbstgeschriebenden Assembler-Routinen, die nur auf einer CPU laufen und irgendwann architekturbedingt veraltete Optimierungen verwenden (es gibt etliche alte Projekte mit "Assember-Optimierungen" die auf heutigen CPUs eher kontraproduktiv sind).
Eine erste algorithmische Optimierung wäre z.B. Zeile 11 durch
if (i > 0) i = i - 1;Zu ersetzen. Es macht keinen Sinn auf
0zurückzuspringen und all die Paare, die durch die "Swap Operation" nicht beeinflusst wurden erneut zu prüfen.
-
Ich habe mal damit angefangen, und drei Verfahren miteinander verglichen... Die Ausgabe ist:
./main 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 47 47 48 48 49 49 50 50 a: 24.810000 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 47 47 48 48 49 49 50 50 a: 24.810000 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 47 47 48 48 49 49 50 50 a: 24.810000 81542 65487 78784Die Verfahren benötigten also 0.81, 0.65 und 0.78 Sekunden... Meine Optimierung war das zweite Verfahren... Das dritte Verfahren stellt einen SelectionSort zum Vergleich dar. Hier ist die Test-"Suite":
#include <stdio.h> #include <sys/time.h> size_t n = 100; size_t my_rand(size_t seed, size_t max) { size_t a = 16807; return (a * seed) % max; } void fill(size_t a[]) { for (size_t i = 0; i < n; i++) { a[i] = my_rand(i + a[0], 51); } } double average(size_t a[]) { // The average should be around 25. double average = 0; for (size_t i = 0; i < n; i++) { average += (double)a[i] / (double)n; } return average; } void print(size_t a[]) { for (size_t i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\na: %f\n\n", average(a)); } void sort_a(size_t arr[]) { size_t i = 0, j = 1, a, b; do { a = arr[i]; b = arr[j]; if (a > b) { arr[i] = b; arr[j] = a; i = 0; j = 1; continue; } i++; j++; } while (j < n); } void sort_a_optimized(size_t arr[]) { asm volatile( " movq %%rdi, -40(%%rbp) \n" " movq $0, -8(%%rbp) \n" " movq $1, -16(%%rbp) \n" ".loop_start: \n" " movq -8(%%rbp), %%rax \n" " leaq 0(,%%rax,8), %%rdx \n" " movq -40(%%rbp), %%rax \n" " addq %%rdx, %%rax \n" " movq (%%rax), %%rax \n" " movq %%rax, -24(%%rbp) \n" " movq -16(%%rbp), %%rax \n" " leaq 0(,%%rax,8), %%rdx \n" " movq -40(%%rbp), %%rax \n" " addq %%rdx, %%rax \n" " movq (%%rax), %%rax \n" " movq %%rax, -32(%%rbp) \n" " movq -24(%%rbp), %%rax \n" " cmpq %%rax, -32(%%rbp) \n" " jnb .loop_increment \n" " movq -8(%%rbp), %%rax \n" " leaq 0(,%%rax,8), %%rdx \n" " movq -40(%%rbp), %%rax \n" " addq %%rax, %%rdx \n" " movq -32(%%rbp), %%rax \n" " movq %%rax, (%%rdx) \n" " movq -16(%%rbp), %%rax \n" " leaq 0(,%%rax,8), %%rdx \n" " movq -40(%%rbp), %%rax \n" " addq %%rax, %%rdx \n" " movq -24(%%rbp), %%rax \n" " movq %%rax, (%%rdx) \n" " movq $0, -8(%%rbp) \n" " movq $1, -16(%%rbp) \n" " jmp .loop_check \n" ".loop_increment: \n" " addq $1, -8(%%rbp) \n" " addq $1, -16(%%rbp) \n" ".loop_check: \n" " movq %[n], %%rax \n" " cmpq %%rax, -16(%%rbp) \n" " jb .loop_start \n" : /* No outputs. */ : [n] "m"(n) : "memory"); } void sort_b(size_t arr[]) { for (size_t i = 0; i < n - 1; i++) { size_t a = i; size_t b = arr[i]; for (size_t j = i + 1; j < n; j++) { if (arr[j] < b) { a = j; b = arr[j]; } } arr[a] = arr[i]; arr[i] = b; } } int main(int argc, char const *argv[]) { struct timeval tv; long long t1, t2, t3, t4, t5, t6; size_t arr[n]; size_t itreations = 10000; gettimeofday(&tv, 0); t1 = tv.tv_usec; for (size_t i = 0; i < itreations; i++) { fill(arr); sort_a(arr); } gettimeofday(&tv, 0); t2 = tv.tv_usec; print(arr); gettimeofday(&tv, 0); t3 = tv.tv_usec; for (size_t i = 0; i < itreations; i++) { fill(arr); sort_a_optimized(arr); } gettimeofday(&tv, 0); t4 = tv.tv_usec; print(arr); gettimeofday(&tv, 0); t5 = tv.tv_usec; for (size_t i = 0; i < itreations; i++) { fill(arr); sort_b(arr); } gettimeofday(&tv, 0); t6 = tv.tv_usec; print(arr); printf("%d\n%d\n%d\n", t2 - t1, t4 - t3, t6 - t5); return 0; }Ich denke, für den Use-Case kann man selbst mit
-O3nicht mehr herausholen...@Schlangenmensch sagte in Funktion optimieren:
Welcher Assambler?
Für den gcc (Linux).
@Schlangenmensch sagte in Funktion optimieren:
Warum?
Aus lernzwecken.
-
@Finnegan sagte in Funktion optimieren:
Eine erste algorithmische Optimierung wäre z.B. Zeile 11 durch
if (i > 0)
i = i - 1;Zu ersetzen.
Wie genau meinst du das? size_t kann doch nicht negativ werden. Meinst du, das arr von hinten nach vorn, nicht von vorn nach hinten, durchgehen? Alle drei Sortierverfahren sollten stabil sein, auch wenn das bei Nicht-Referenzen natürlich keine Rolle spielen würde.
To be fair: Ich habe die while- durch eine do-while-Schleife ersetzt... Falls es nicht mind. 2 Elemente gibt, würde es krachen...
Und
a[i] = my_rand(i + a[0], 51);
der+ a[0]-Trick greift natürlich nur so lange, wie das erste Element nicht den Wert 0 hat... Ich muss mir eigentlich noch etwas besseres überlegen, wie man an zufällige Werte kommen kann.