Funktion optimieren
-
Dieser Beitrag wurde gelöscht!
-
@wob Hattest recht, eine Menge Formate-Warnungen... Habe es mal mit -Wall kompiliert...
#include <stdio.h> #include <stdlib.h> #include <sys/time.h> size_t initial_seed = 123; size_t n = 100; size_t rand1(size_t seed, size_t max) { size_t a = 16807; return (a * seed) % max; } size_t my_rand(size_t max) { size_t r = rand1(initial_seed, max); initial_seed = rand1(initial_seed, -1); return r; } void fill(size_t m, size_t a[m][n]) { for (size_t i = 0; i < m; i++) { for (size_t j = 0; j < n; j++) { a[i][j] = my_rand(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 m, size_t a[m][n]) { for (size_t i = 0; i < n; i++) { printf("%zu ", a[0][i]); } printf("\na: %f\n...\n", average(a[0])); // ... for (size_t i = 0; i < n; i++) { printf("%zu ", a[m - 1][i]); } printf("\na: %f\n\n---\n\n", average(a[m - 1])); } // Comparison function for sort_a int compare(const void *a, const void *b) { return (*(size_t *)a - *(size_t *)b); } void sort_a(size_t arr[]) { qsort(arr, n, sizeof(size_t), compare); } #pragma GCC push_options #pragma GCC optimize("O0") void sort_b_optimized(size_t arr[]) { asm volatile( " movq %[arr], -40(%%rbp) \n" " movq $0, -8(%%rbp) \n" " movq $1, -16(%%rbp) \n" "1: \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 2f \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 3f \n" "2: \n" " addq $1, -8(%%rbp) \n" " addq $1, -16(%%rbp) \n" "3: \n" " movq %[n], %%rax \n" " cmpq %%rax, -16(%%rbp) \n" " jb 1b \n" : /* No outputs. */ : [n] "m"(n), [arr] "r"(arr) : "memory"); } #pragma GCC pop_options void sort_c(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; } } void set_time(long *t_old, long *t, long *max_dif) { struct timeval tv; gettimeofday(&tv, 0); *t = tv.tv_usec; long dif = *t - *t_old; if (dif > *max_dif) { *max_dif = dif; } } int main(int argc, char const *argv[]) { long t1, t2, t3, t4, t5, t6, max_dif = 0; size_t iterations = 10000; size_t arr[iterations][n]; fill(iterations, arr); print(iterations, arr); set_time(&t1, &t1, &max_dif); for (size_t i = 0; i < iterations; i++) { sort_a(arr[i]); } set_time(&t1, &t2, &max_dif); print(iterations, arr); fill(iterations, arr); print(iterations, arr); set_time(&t3, &t3, &max_dif); for (size_t i = 0; i < iterations; i++) { sort_b_optimized(arr[i]); } set_time(&t3, &t4, &max_dif); print(iterations, arr); fill(iterations, arr); print(iterations, arr); set_time(&t5, &t5, &max_dif); for (size_t i = 0; i < iterations; i++) { sort_c(arr[i]); } set_time(&t5, &t6, &max_dif); print(iterations, arr); printf("%ld\n%ld\n%ld\n", t2 - t1, t4 - t3, t6 - t5); printf("%ld %%\n%ld %%\n%ld %%\n", (t2 - t1) * 100 / max_dif, (t4 - t3) * 100 / max_dif, (t6 - t5) * 100 / max_dif); return 0; }Jetzt kann man es übersetzen mit
gcc -Wall main.c -o mainodergcc -O0 -Wall main.c -o mainodergcc -O3 -Wall main.c -o main.Das Ergebnis ist in allen drei Fällen (bei mir), dass ich nicht schneller bin als qsort... aber immerhin etwas schneller als SelectionSort (für n=100).
-
Meine Zeitrechnung für den Benchmark war ja komplett falsch... (Wall time vs. CPU time...) Wieso sagt keiner was?
#include <stdio.h> #include <stdlib.h> #include <time.h> size_t initial_seed = 123; size_t n = 100; size_t rand1(size_t seed, size_t max) { size_t a = 16807; return (a * seed) % max; } size_t my_rand(size_t max) { size_t r = rand1(initial_seed, max); initial_seed = rand1(initial_seed, -1); return r; } void fill(size_t m, size_t a[m][n]) { for (size_t i = 0; i < m; i++) { for (size_t j = 0; j < n; j++) { a[i][j] = my_rand(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 m, size_t a[m][n]) { for (size_t i = 0; i < n; i++) { printf("%zu ", a[0][i]); } printf("\na: %f\n...\n", average(a[0])); // ... for (size_t i = 0; i < n; i++) { printf("%zu ", a[m - 1][i]); } printf("\na: %f\n\n---\n\n", average(a[m - 1])); } // Comparison function for sort_a int compare(const void *a, const void *b) { return (*(size_t *)a - *(size_t *)b); } void sort_a(size_t arr[]) { qsort(arr, n, sizeof(size_t), compare); } #pragma GCC push_options #pragma GCC optimize("O0") void sort_b_optimized(size_t arr[]) { asm volatile( " movq %%rdi, -40(%%rbp) \n" " movq $0, -8(%%rbp) \n" " movq $1, -16(%%rbp) \n" "1: \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 2f \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 3f \n" "2: \n" " addq $1, -8(%%rbp) \n" " addq $1, -16(%%rbp) \n" "3: \n" " movq n(%%rip), %%rax \n" " cmpq %%rax, -16(%%rbp) \n" " jb 1b \n" : /* No outputs. */ : /* No inputs. */ : "memory"); } #pragma GCC pop_options void sort_c(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; } } void set_time(clock_t *t_old, clock_t *t, clock_t *max_dif) { *t = clock(); clock_t dif = *t - *t_old; if (dif > *max_dif) { *max_dif = dif; } } int main(int argc, char const *argv[]) { clock_t t1, t2, t3, t4, t5, t6, max_dif = 0; size_t iterations = 10000; size_t arr[iterations][n]; fill(iterations, arr); print(iterations, arr); set_time(&t1, &t1, &max_dif); for (size_t i = 0; i < iterations; i++) { sort_a(arr[i]); } set_time(&t1, &t2, &max_dif); print(iterations, arr); fill(iterations, arr); print(iterations, arr); set_time(&t3, &t3, &max_dif); for (size_t i = 0; i < iterations; i++) { sort_b_optimized(arr[i]); } set_time(&t3, &t4, &max_dif); print(iterations, arr); fill(iterations, arr); print(iterations, arr); set_time(&t5, &t5, &max_dif); for (size_t i = 0; i < iterations; i++) { sort_c(arr[i]); } set_time(&t5, &t6, &max_dif); print(iterations, arr); double t1_spent, t2_spent, t3_spent, max_spent; t1_spent = (double)(t2 - t1) / CLOCKS_PER_SEC; t2_spent = (double)(t4 - t3) / CLOCKS_PER_SEC; t3_spent = (double)(t6 - t5) / CLOCKS_PER_SEC; max_spent = (double)(max_dif) / CLOCKS_PER_SEC; printf("%f s\n%f s\n%f s\n", t1_spent, t2_spent, t3_spent); printf("%f %%\n%f %%\n%f %%\n", t1_spent * 100 / max_spent, t2_spent * 100 / max_spent, t3_spent * 100 / max_spent); return 0; }Leider bin ich jetzt am langsamsten. Kein Bock mehr.
Edit: Ok, es liegt daran, dass alle bis auf zwei
sort_c-Schleifen wegoptimiert werden. Der Compiler erkennt, dass zum Schluss nur noch das erste und letzte Array ausgegeben werden muss - und schneidet die Äste dann ab. So macht ein Vergleich keinen Sinn mehr.
-
@Lennox sagte in Funktion optimieren:
Edit: Ok, es liegt daran, dass alle bis auf zwei
sort_c-Schleifen wegoptimiert werden. Der Compiler erkennt, dass zum Schluss nur noch das erste und letzte Array ausgegeben werden muss - und schneidet die Äste dann ab. So macht ein Vergleich keinen Sinn mehr.Das ist genau das, weshalb ich die Sache mit dem
volatileis Spiel gebracht habe. Für solche Messungen muss man bestimmte Optimierungen unterbinden - aber eben auch nicht alle, man will ja wissen, ob man den Compiler schlagen kann
Aber das ist auch ne wertvolle Lektion: Moderne Compiler sind auch ziemlich fähige C und C++ Interpreter... von wegen "interpretierte" vs "kompilierte" Sprachen
-
@Lennox Aus diesem Grund ist Google Benchmark angesprochen worden, da kann man z.B. angeben, welche Variablen nicht wegoptimiert werden sollen.
Um damit schnell mal was zu probieren, habe ich schon versucht, dich auf https://quick-bench.com/ aufmerksam zu machen, da kann man das online mal kurz probieren.Aber, den Compiler zu schlagen ist halt schon eine Herausforderung.
P.S. Apropos C++ Interpreter, spätestens mit
constexprhaben die Compiler sehr vollständige C++ Interpreter, denn alles, wasconstexprist, muss zur Compiletime interpretiert werden.
-
Selbst noch etwas gebastelt... nun sollte es eigentlich funktionieren:
#include <stdio.h> #include <stdlib.h> #include <time.h> size_t initial_seed = 123; size_t total_hash = 23; size_t n = 100; size_t rand1(size_t seed, size_t max) { size_t a = 16807; return (a * seed) % max; } size_t my_rand(size_t max) { size_t r = rand1(initial_seed, max); initial_seed = rand1(initial_seed, -1); return r; } void fill(size_t m, size_t a[m][n]) { for (size_t i = 0; i < m; i++) { for (size_t j = 0; j < n; j++) { a[i][j] = my_rand(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; } // Fast, combining hash function with few collisions and h(a,b) often not equal to h(b,a)... size_t my_hash(size_t a, size_t b) { return a * 31 + b; } void add_to_total_hash(size_t m, size_t a[m][n]) { for (size_t i = 0; i < m; i++) { for (size_t j = 0; j < n; j++) { total_hash = my_hash(total_hash, a[i][j]); } } } void print(size_t m, size_t a[m][n]) { add_to_total_hash(m, a); for (size_t i = 0; i < n; i++) { printf("%zu ", a[0][i]); } printf("\na: %f\n...\n", average(a[0])); // ... for (size_t i = 0; i < n; i++) { printf("%zu ", a[m - 1][i]); } printf("\na: %f\nh: %zu\n\n---\n\n", average(a[m - 1]), total_hash); } // Comparison function for sort_a int compare(const void *a, const void *b) { return (*(size_t *)a - *(size_t *)b); } void sort_a(size_t arr[]) { qsort(arr, n, sizeof(size_t), compare); } #pragma GCC push_options #pragma GCC optimize("O0") void sort_b_optimized(size_t arr[]) { asm volatile( " movq %%rdi, -40(%%rbp) \n" " movq $0, -8(%%rbp) \n" " movq $1, -16(%%rbp) \n" "1: \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 2f \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 3f \n" "2: \n" " addq $1, -8(%%rbp) \n" " addq $1, -16(%%rbp) \n" "3: \n" " movq n(%%rip), %%rax \n" " cmpq %%rax, -16(%%rbp) \n" " jb 1b \n" : /* No outputs. */ : /* No inputs. */ : "memory"); } #pragma GCC pop_options void sort_c(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; } } void set_time(clock_t *t_old, clock_t *t, clock_t *max_dif) { *t = clock(); clock_t dif = *t - *t_old; if (dif > *max_dif) { *max_dif = dif; } } int main(int argc, char const *argv[]) { clock_t t1, t2, t3, t4, t5, t6, max_dif = 0; size_t iterations = 10000; size_t arr[iterations][n]; fill(iterations, arr); print(iterations, arr); set_time(&t1, &t1, &max_dif); for (size_t i = 0; i < iterations; i++) { sort_a(arr[i]); } set_time(&t1, &t2, &max_dif); print(iterations, arr); fill(iterations, arr); print(iterations, arr); set_time(&t3, &t3, &max_dif); for (size_t i = 0; i < iterations; i++) { sort_c(arr[i]); } set_time(&t3, &t4, &max_dif); print(iterations, arr); fill(iterations, arr); print(iterations, arr); set_time(&t5, &t5, &max_dif); for (size_t i = 0; i < iterations; i++) { sort_b_optimized(arr[i]); } set_time(&t5, &t6, &max_dif); print(iterations, arr); double t1_spent, t2_spent, t3_spent, max_spent; t1_spent = (double)(t2 - t1) / CLOCKS_PER_SEC; t2_spent = (double)(t4 - t3) / CLOCKS_PER_SEC; t3_spent = (double)(t6 - t5) / CLOCKS_PER_SEC; max_spent = (double)(max_dif) / CLOCKS_PER_SEC; printf("%f s\n%f s\n%f s\n", t1_spent, t2_spent, t3_spent); printf("%f %%\n%f %%\n%f %%\n", t1_spent * 100 / max_spent, t2_spent * 100 / max_spent, t3_spent * 100 / max_spent); return 0; }Edit: Nein, leider doch nicht...
-
@Lennox hattest du nicht mal
volatile size_t initial_seed = 123;da stehen? Warum dasvolatileweg? Mein einziger Kritikpunkt war ja, dassfill()dann bei jeder Iteration indirekt einevolatile-Variable liest, aber da du eh nicht diefill()-Performance messen willst ist das eigentlich egal. Ansonsten einfach den Wert123aus einervolatile-Variable lesen, z.B. so:volatile size_t do_not_optimize_anything_using_random_values = 123; size_t initial_seed = do_not_optimize_anything_using_random_values;(der lange Variablenname nur damit klar ist wofür das Spektakel gut ist).
... damit werden all die Optimierungen verhindert, die darauf beruhen, dass
123"hartcodiert" ist. Z.B. dass der Compiler wissen kann, wie die Arrays am Ende aussehen müssen und die dann eben direkt beim kompilieren "ausrechnet".volatilesagt dem Compiler hier: Du kannst dich nicht darauf verlassen, dass die Variable beim Lesen immer noch den Wert123hat. D.h. er kann nicht den Inhalt der Arrays schlussfolgern und muss daher Code generieren, mit der die CPU die (in letzter Konsequenz sortierten) Arrays berechnet. Der Compiler kann das in dem Fall eben nicht selbst tun und einfach die fertigen Arrays in die Executable "einbetten".
-
Sorry Leute aber wo ich hier gerade C++ lese, kann ich es nicht lassen eine modernere C++ Variante zu posten:
#include <vector> #include <algorithm> #include <random> #include <execution> #include <iostream> #include <format> static void FillValuesWithRandom(std::vector<int>& Values) { std::random_device RandomDevice; std::default_random_engine RandomEngine(RandomDevice()); std::uniform_int_distribution<int> Dist; std::ranges::generate(Values, [&]() { return Dist(RandomEngine); }); } int main() { static constexpr size_t TestSize = 30'000'000; std::vector<int> Values(TestSize); std::chrono::system_clock::time_point T0, T1; for (int i = 0; i < 5; i++) { std::cout << std::format("Generating {} random values... ", TestSize); FillValuesWithRandom(Values); std::cout << std::format("ok\n", TestSize); std::cout << "Sorting... "; T0 = std::chrono::system_clock::now(); std::stable_sort(std::execution::par, std::begin(Values), std::end(Values)); T1 = std::chrono::system_clock::now(); std::cout << std::format("ok (time = {} ms) ", std::chrono::duration_cast<std::chrono::milliseconds>(T1 - T0).count()) << " Sum = " << std::accumulate(std::begin(Values), std::end(Values), 0) << "\n"; } return 0; }
-
Ok, folgende Ergebnisse für n=10:
0.001933s 69.50% (C's Quicksort) 0.002763s 99.35% (Bubble sort) 0.002149s 77.27% (Selection sort) 0.001394s 50.12% (Insertion sort) 0.002781s 100.00% (Bubble sort in Asm, unmodified)Das heißt, für kleine n kann man C's Quicksort durchaus schlagen und in in Asm optimieren, man sollte vor der Optimierung aber ein geeignetes Verfahren wählen... spontan scheint für diese Anforderungen Insertion sort am besten abzuschneiden (siehe bspw. auch hier: https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_sorts).
#include <stdio.h> #include <stdlib.h> #include <time.h> volatile size_t initial_seed = 123; size_t total_hash = 23; size_t n = 10; size_t rand1(size_t seed, size_t max) { size_t a = 16807; return (a * seed) % max; } size_t my_rand(size_t max) { size_t r = rand1(initial_seed, max); initial_seed = rand1(initial_seed, -1); return r; } void fill(size_t m, size_t a[m][n]) { for (size_t i = 0; i < m; i++) { for (size_t j = 0; j < n; j++) { a[i][j] = my_rand(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; } // Fast, combining hash function with few collisions and h(a,b) often not equal to h(b,a)... size_t my_hash(size_t a, size_t b) { return a * 31 + b; } void add_to_total_hash(size_t m, size_t a[m][n]) { for (size_t i = 0; i < m; i++) { for (size_t j = 0; j < n; j++) { total_hash = my_hash(total_hash, a[i][j]); } } } void print(size_t m, size_t a[m][n]) { // add_to_total_hash(m, a); for (size_t i = 0; i < n; i++) { printf("%zu ", a[0][i]); } printf("\na: %f\n...\n", average(a[0])); // ... for (size_t i = 0; i < n; i++) { printf("%zu ", a[m - 1][i]); } printf("\na: %f\n\n---\n\n", average(a[m - 1])); } // Comparison function for sort_a int compare(const void *a, const void *b) { return (*(size_t *)a - *(size_t *)b); } // Quicksort? void sort_a(size_t arr[]) { qsort(arr, n, sizeof(size_t), compare); } // Bubble sort classic void sort_b(size_t arr[]) { size_t i = 0, j = 1, a, b; while (j < n) { a = arr[i]; b = arr[j]; if (a > b) { arr[i] = b; arr[j] = a; i = 0; j = 1; continue; } i++; j++; } } // Selection sort void sort_c(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; } } // Insertion sort void sort_d(size_t arr[]) { size_t i = 0, j = 1, k, l, a, b; while (j < n) { a = arr[i]; b = arr[j]; if (a > b) { k = i; l = j; while (a > b) { arr[k] = b; arr[l] = a; if (k == 0) { break; } k--; l--; a = arr[k]; b = arr[l]; } } i++; j++; } } #pragma GCC push_options #pragma GCC optimize("O0") void sort_optimized(size_t arr[]) { asm volatile( " movq %%rdi, -40(%%rbp) \n" " movq $0, -8(%%rbp) \n" " movq $1, -16(%%rbp) \n" "1: \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 2f \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 3f \n" "2: \n" " addq $1, -8(%%rbp) \n" " addq $1, -16(%%rbp) \n" "3: \n" " movq n(%%rip), %%rax \n" " cmpq %%rax, -16(%%rbp) \n" " jb 1b \n" : /* No outputs. */ : /* No inputs. */ : "memory"); } #pragma GCC pop_options void set_time(clock_t *t_old, clock_t *t, clock_t *max_dif) { *t = clock(); clock_t dif = *t - *t_old; if (dif > *max_dif) { *max_dif = dif; } } int main(int argc, char const *argv[]) { clock_t cs[2 * 5]; clock_t max_dif = 0; size_t iterations = 10000; size_t arr[iterations][n]; fill(iterations, arr); print(iterations, arr); set_time(&cs[0], &cs[0], &max_dif); for (size_t i = 0; i < iterations; i++) { sort_a(arr[i]); } set_time(&cs[0], &cs[1], &max_dif); print(iterations, arr); fill(iterations, arr); print(iterations, arr); set_time(&cs[2], &cs[2], &max_dif); for (size_t i = 0; i < iterations; i++) { sort_b(arr[i]); } set_time(&cs[2], &cs[3], &max_dif); print(iterations, arr); fill(iterations, arr); print(iterations, arr); set_time(&cs[4], &cs[4], &max_dif); for (size_t i = 0; i < iterations; i++) { sort_c(arr[i]); } set_time(&cs[4], &cs[5], &max_dif); print(iterations, arr); fill(iterations, arr); print(iterations, arr); set_time(&cs[6], &cs[6], &max_dif); for (size_t i = 0; i < iterations; i++) { sort_d(arr[i]); } set_time(&cs[6], &cs[7], &max_dif); print(iterations, arr); fill(iterations, arr); print(iterations, arr); set_time(&cs[8], &cs[8], &max_dif); for (size_t i = 0; i < iterations; i++) { sort_optimized(arr[i]); } set_time(&cs[8], &cs[9], &max_dif); print(iterations, arr); double spent[5]; for (size_t i = 0; i < 5; i++) { spent[i] = (double)(cs[2 * i + 1] - cs[2 * i]) / CLOCKS_PER_SEC; } double max_spent = (double)(max_dif) / CLOCKS_PER_SEC; for (size_t i = 0; i < 5; i++) { printf("%fs %f%%\n", spent[i], spent[i] * 100 / max_spent); } return 0; }Das heißt, als Erstes müsste ich mich mal vom Bubble sort verabschieden.
@Finnegan Habe jetzt
volatilewieder hinzugefügt und berechne dentotal_hashnicht mehr...
-
@Quiche-Lorraine sagte in Funktion optimieren:
#include <vector>
#include <algorithm>
#include <random>
#include <execution>
#include <iostream>
#include <format>static
void FillValuesWithRandom(std::vector<int>& Values)
{
std::random_device RandomDevice;
std::default_random_engine RandomEngine(RandomDevice());
std::uniform_int_distribution<int> Dist;std::ranges::generate(Values, [&]() { return Dist(RandomEngine); });}
int main()
{
static constexpr size_t TestSize = 30'000'000;
std::vector<int> Values(TestSize);
std::chrono::system_clock::time_point T0, T1;for (int i = 0; i < 5; i++) { std::cout << std::format("Generating {} random values... ", TestSize); FillValuesWithRandom(Values); std::cout << std::format("ok\n", TestSize); std::cout << "Sorting... "; T0 = std::chrono::system_clock::now(); std::stable_sort(std::execution::par, std::begin(Values), std::end(Values)); T1 = std::chrono::system_clock::now(); std::cout << std::format("ok (time = {} ms) ", std::chrono::duration_cast<std::chrono::milliseconds>(T1 - T0).count()) << " Sum = " << std::accumulate(std::begin(Values), std::end(Values), 0) << "\n"; } return 0;}
Expand/CollapseDas geht sicher noch "moderner":
#include <vector> #include <algorithm> #include <random> #include <execution> #include <iostream> #include <format> #include <numeric> #include <chrono> #include <cstdint> using namespace std; void FillValuesWithRandom(vector<int>& values, std::mt19937& engine, std::uniform_int_distribution<int>& dist) { std::ranges::generate(values, [&] { return dist(engine); }); } int main() { static constexpr size_t TestSize = 30'000'000; vector<int> values(TestSize); // RNG nur einmal initialisieren std::random_device rd; std::mt19937 engine(rd()); std::uniform_int_distribution<int> dist; // voller int-Bereich for (int run = 0; run < 5; ++run) { std::cout << std::format("Run {}: Generating {} random values... ", run + 1, TestSize); FillValuesWithRandom(values, engine, dist); std::cout << "ok\n"; std::cout << "Sorting... "; const auto t0 = std::chrono::steady_clock::now(); std::stable_sort(std::execution::par, values.begin(), values.end()); const auto t1 = std::chrono::steady_clock::now(); const auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(t1 - t0).count(); // Summe (hier bewusst int64_t) std::int64_t sum = std::reduce(std::execution::par, values.begin(), values.end(), std::int64_t{0}); std::cout << std::format("ok (time = {} ms) Sum = {}\n", ms, sum); } return 0; } /* - RNG nur einmal erstellt und sauber übergeben. - std::mt19937 statt default_random_engine. - std::steady_clock für Timing. - std::reduce mit Execution-Policy und 64-Bit Summe. */
-
@Lennox
Bei all deinen Sortierfunktionen ist immer n eine globale Konstante. Wenn du normale Sortierfunktionen haben willst, würde ich dasnauf jeden Fall noch als Parameter übergeben.Dann solltest du bei deinen Tests auch unterschiedliche Start-Reihenfolgen testen.
a) irgendwie zufällige Werte aus einem Wertebereich, der viel größer ist als die Array-Länge
b) irgendwie zufällige Werte aus einem Wertebereich, der kleiner ist als die Array-Länge (viele gleiche Zahlen)
b2) alles gleiche Zahlen
c) vorsortiertes Array
d) genau verkehrt herum vorsortiertes Array
e) andere Datentypen, z.B. kleinere oder größere Objekte sortieren (nicht immer nur size_t Werte)
f) ...Ansonsten besteht die Gefahr, dass du nur für den Spezialfall deiner Testdaten optimierst.
Wenn das n ein Funktionsargument ist, kannst du dann auch in einem Programm verschiedene Array-Längen testen.
-
@Erhard-Henkes In C kann man doch auch
/dev/urandomlesen, oder eine Online-Quelle bemühen, die eine (garantiert zufällige) Zufallszahl liefert (gibt es das?), oder den Benutzer eine bio-chemisch zufällige Zahl eingeben lassen... Aber diesen Aufwand wollte ich mir jetzt eigentlich nicht machen.
-
@wob sagte in Funktion optimieren:
Bei all deinen Sortierfunktionen ist immer n eine globale Konstante. Wenn du normale Sortierfunktionen haben willst, würde ich das n auf jeden Fall noch als Parameter übergeben.
Eigentlich wollte ich nur etwas Inline-Assembler lernen... Hätte nicht gedacht, dass das Thema so Fahrt aufnimmt.
-
@wob
So besser?#include <stdio.h> #include <stdlib.h> #include <time.h> volatile size_t initial_seed = 123; size_t total_hash = 23; size_t rand1(size_t seed, size_t max) { size_t a = 16807; return (a * seed) % max; } size_t my_rand(size_t max) { size_t r = rand1(initial_seed, max); initial_seed = rand1(initial_seed, -1); return r; } void rfill(size_t n, size_t m, size_t a[m][n]) { for (size_t i = 0; i < m; i++) { for (size_t j = 0; j < n; j++) { a[i][j] = my_rand(51); } } } double average(size_t n, 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; } // Fast, combining hash function with few collisions and h(a,b) often not equal to h(b,a)... size_t my_hash(size_t a, size_t b) { return a * 31 + b; } void add_to_total_hash(size_t n, size_t m, size_t a[m][n]) { for (size_t i = 0; i < m; i++) { for (size_t j = 0; j < n; j++) { total_hash = my_hash(total_hash, a[i][j]); } } } void print(size_t n, size_t m, size_t a[m][n]) { add_to_total_hash(n, m, a); for (size_t i = 0; i < n; i++) { printf("%zu ", a[0][i]); } printf("\na: %f\n...\n", average(n, a[0])); // ... for (size_t i = 0; i < n; i++) { printf("%zu ", a[m - 1][i]); } printf("\na: %f\nh: %zu\n\n", average(n, a[m - 1]), total_hash); } // Comparison function for sort_a int compare(const void *a, const void *b) { return (*(size_t *)a - *(size_t *)b); } // Quicksort? void sort_a(size_t n, size_t arr[]) { qsort(arr, n, sizeof(size_t), compare); } // Bubble sort void sort_b(size_t n, size_t arr[]) { size_t i = 0, j = 1, a, b; while (j < n) { a = arr[i]; b = arr[j]; if (a > b) { arr[i] = b; arr[j] = a; i = 0; j = 1; continue; } i++; j++; } } // Selection sort void sort_c(size_t n, 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; } } // Insertion sort void sort_d(size_t n, size_t arr[]) { size_t i = 0, j = 1, k, l, a, b; while (j < n) { a = arr[i]; b = arr[j]; if (a > b) { k = i; l = j; do { arr[k] = b; arr[l] = a; if (k == 0) { break; } k--; l--; a = arr[k]; b = arr[l]; } while (a > b); } i++; j++; } } #pragma GCC push_options #pragma GCC optimize("O0") void sort_optimized(size_t n, size_t arr[]) { asm volatile( " movq %%rdi, -40(%%rbp) \n" " movq %%rsi, -48(%%rbp) \n" " movq $0, -8(%%rbp) \n" " movq $1, -16(%%rbp) \n" " jmp 3f \n" "1: \n" " movq -8(%%rbp), %%rax \n" " leaq 0(,%%rax,8), %%rdx \n" " movq -48(%%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 -48(%%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 2f \n" " movq -8(%%rbp), %%rax \n" " leaq 0(,%%rax,8), %%rdx \n" " movq -48(%%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 -48(%%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 3f \n" "2: \n" " addq $1, -8(%%rbp) \n" " addq $1, -16(%%rbp) \n" "3: \n" " movq -16(%%rbp), %%rax \n" " cmpq -40(%%rbp), %%rax \n" " jb 1b \n" : /* No outputs. */ : /* No inputs. */ : "memory"); } #pragma GCC pop_options double profile_sort_func(void (*f)(size_t, size_t *), size_t n, size_t m, size_t arr[m][n]) { rfill(n, m, arr); print(n, m, arr); clock_t c1 = clock(); for (size_t i = 0; i < m; i++) { (*f)(n, arr[i]); } clock_t c2 = clock(); print(n, m, arr); return (double)(c2 - c1) / CLOCKS_PER_SEC; } int main(int argc, char const *argv[]) { size_t n = 10; size_t m = 100000; size_t arr[m][n]; double secs[5] = { profile_sort_func(sort_a, n, m, arr), profile_sort_func(sort_b, n, m, arr), profile_sort_func(sort_c, n, m, arr), profile_sort_func(sort_d, n, m, arr), profile_sort_func(sort_optimized, n, m, arr), }; double max = 0; for (size_t i = 0; i < 5; i++) { if (secs[i] > max) { max = secs[i]; } } printf("%fs %f%%\n%fs %f%%\n%fs %f%%\n%fs %f%%\n%fs %f%%\n", secs[0], secs[0] * 100 / max, secs[1], secs[1] * 100 / max, secs[2], secs[2] * 100 / max, secs[3], secs[3] * 100 / max, secs[4], secs[4] * 100 / max); return 0; }gcc -Wall main.c -o main ./main 27 42 3 33 40 14 19 12 36 43 a: 26.900000 ... 24 36 36 26 49 36 47 1 48 40 a: 34.300000 h: 5939366454565110528 3 12 14 19 27 33 36 40 42 43 a: 26.900000 ... 1 24 26 36 36 36 40 47 48 49 a: 34.300000 h: 4429705970288659611 33 44 43 0 24 15 46 36 2 11 a: 25.400000 ... 28 20 39 12 2 25 18 43 16 50 a: 25.300000 h: 6352222085557659981 0 2 11 15 24 33 36 43 44 46 a: 25.400000 ... 2 12 16 18 20 25 28 39 43 50 a: 25.300000 h: 4505934733348363633 9 39 48 42 46 11 50 24 15 37 a: 32.100000 ... 1 23 45 46 29 44 24 3 7 40 a: 26.200000 h: 4225079418598471750 9 11 15 24 37 39 42 46 48 50 a: 32.100000 ... 1 3 7 23 24 29 40 44 45 46 a: 26.200000 h: 1630903755648978609 3 26 21 15 26 27 35 13 32 43 a: 24.100000 ... 45 8 6 21 47 31 28 6 45 24 a: 26.100000 h: 4076123578238199228 3 13 15 21 26 26 27 32 35 43 a: 24.100000 ... 6 6 8 21 24 28 31 45 45 47 a: 26.100000 h: 10126057256555243605 13 30 14 4 11 21 10 24 4 19 a: 15.000000 ... 32 12 45 33 31 9 41 32 21 46 a: 30.200000 h: 14143251785556203417 4 4 10 11 13 14 19 21 24 30 a: 15.000000 ... 9 12 21 31 32 32 33 41 45 46 a: 30.200000 h: 10117127439067026547 0.019759s 66.492798% 0.029716s 100.000000% 0.019451s 65.456320% 0.014100s 47.449186% 0.028555s 96.093014%... Ich habe noch nicht angefangen, das Assembly zu optimieren.
