L
@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 main oder gcc -O0 -Wall main.c -o main oder gcc -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).
