Funktion optimieren

[Lennox]

@Finnegan Vielen Dank für die ganzen Ideen. Ich setze mich morgen noch mal ran, heute schon etwas spät.

[Lennox]

So, habe den Zufall überarbeitet und das "fill" aus den Schleifen entfernt, damit die Ergebnisse nicht zu sehr abweichen...

#include <stdio.h>
#include <sys/time.h>

volatile 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 a[])
{
    for (size_t i = 0; i < n; i++)
    {
        a[i] = 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 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;
    unsigned long t1, t2, t3, t4, t5, t6, t_max = 0;
    size_t iterations = 10000;
    size_t arr[iterations][n];
    for (size_t i = 0; i < iterations; i++)
    {
        fill(arr[i]);
    }
    for (size_t i = 0; i < 2; i++)
    {
        print(arr[i]);
    }
    for (size_t i = iterations - 1; i >= iterations - 2; i--)
    {
        print(arr[i]);
    }

    gettimeofday(&tv, 0);
    t1 = tv.tv_usec;
    for (size_t i = 0; i < iterations; i++)
    {
        sort_a(arr[i]);
    }
    gettimeofday(&tv, 0);
    t2 = tv.tv_usec;
    if (t2 - t1 > t_max)
    {
        t_max = t2 - t1;
    }

    gettimeofday(&tv, 0);
    t3 = tv.tv_usec;
    for (size_t i = 0; i < iterations; i++)
    {
        sort_a_optimized(arr[i]);
    }
    gettimeofday(&tv, 0);
    t4 = tv.tv_usec;
    if (t4 - t3 > t_max)
    {
        t_max = t4 - t3;
    }

    gettimeofday(&tv, 0);
    t5 = tv.tv_usec;
    for (size_t i = 0; i < iterations; i++)
    {
        sort_b(arr[i]);
    }
    gettimeofday(&tv, 0);
    t6 = tv.tv_usec;
    if (t6 - t5 > t_max)
    {
        t_max = t6 - t5;
    }

    for (size_t i = 0; i < 2; i++)
    {
        print(arr[i]);
    }
    for (size_t i = iterations - 1; i >= iterations - 2; i--)
    {
        print(arr[i]);
    }
    printf("%d\n%d\n%d\n", t2 - t1, t4 - t3, t6 - t5);
    printf("%d %%\n%d %%\n%d %%\n", (t2 - t1) * 100 / t_max, (t4 - t3) * 100 / t_max, (t6 - t5) * 100 / t_max);
    return 0;
}

./main 
27 42 3 33 40 14 19 12 36 43 29 36 7 38 14 35 15 27 43 48 36 36 14 9 17 1 32 47 48 49 24 40 31 39 8 30 9 44 1 42 33 39 42 8 2 0 43 43 29 19 50 26 28 37 44 44 13 34 49 1 31 44 24 37 1 4 8 12 48 9 46 27 31 41 27 15 29 39 16 21 21 19 3 21 14 1 35 45 30 13 18 32 13 24 37 6 32 12 0 34 
a: 26.220000

23 40 8 41 35 10 3 5 35 39 17 26 33 23 30 36 24 8 45 18 13 44 42 43 22 2 49 50 20 34 22 23 35 8 48 27 11 22 28 47 39 39 26 34 25 10 25 38 31 27 3 45 6 26 50 11 48 24 11 14 41 27 30 33 37 22 30 43 20 46 3 5 45 28 32 25 8 10 1 11 29 43 44 39 15 31 39 4 30 8 12 11 5 11 31 16 30 18 21 40 
a: 25.950000

18 14 42 36 17 8 39 42 0 31 36 1 45 48 25 36 14 49 47 44 23 13 3 22 26 22 1 26 38 36 43 31 41 5 32 45 1 3 30 45 24 41 28 1 29 43 11 25 36 34 7 47 25 13 37 7 43 16 8 33 16 0 26 48 18 48 23 13 10 33 14 39 32 34 50 45 36 28 47 37 41 16 49 6 27 45 9 9 15 13 24 36 36 26 49 36 47 1 48 40 
a: 27.560000

9 0 8 49 11 44 0 12 2 9 21 48 45 8 25 11 3 28 13 29 46 31 1 42 23 3 42 6 17 40 46 20 49 26 9 38 5 33 10 37 6 17 48 41 43 24 46 7 28 14 14 35 9 6 47 50 0 46 7 6 38 23 50 19 40 41 33 25 11 29 37 46 4 13 17 31 14 10 4 47 49 28 6 22 33 2 6 12 33 41 20 44 25 8 44 24 42 48 3 26 
a: 24.410000

0 0 1 1 1 1 1 2 3 3 4 6 7 8 8 8 9 9 9 12 12 12 13 13 13 14 14 14 14 15 15 16 17 18 19 19 19 21 21 21 24 24 24 26 27 27 27 27 28 29 29 29 30 30 31 31 31 32 32 32 33 33 34 34 35 35 36 36 36 36 37 37 37 38 39 39 39 40 40 41 42 42 42 43 43 43 43 44 44 44 44 45 46 47 48 48 48 49 49 50 
a: 26.220000

1 2 3 3 3 4 5 5 5 6 8 8 8 8 8 10 10 10 11 11 11 11 11 11 12 13 14 15 16 17 18 18 20 20 21 22 22 22 22 23 23 23 24 24 25 25 25 26 26 26 27 27 27 28 28 29 30 30 30 30 30 31 31 31 32 33 33 34 34 35 35 35 36 37 38 39 39 39 39 39 40 40 41 41 42 43 43 43 44 44 45 45 45 46 47 48 48 49 50 50 
a: 25.950000

0 0 1 1 1 1 1 3 3 5 6 7 7 8 8 9 9 10 11 13 13 13 13 14 14 14 15 16 16 16 17 18 18 22 22 23 23 24 24 25 25 25 26 26 26 26 27 28 28 29 30 31 31 32 32 33 33 34 34 36 36 36 36 36 36 36 36 36 37 37 38 39 39 40 41 41 41 42 42 43 43 43 44 45 45 45 45 45 47 47 47 47 48 48 48 48 49 49 49 50 
a: 27.560000

0 0 0 1 2 2 3 3 3 4 4 5 6 6 6 6 6 6 7 7 8 8 8 9 9 9 9 10 10 11 11 11 12 12 13 13 14 14 14 17 17 17 19 20 20 21 22 23 23 24 24 25 25 25 26 26 28 28 28 29 29 31 31 33 33 33 33 35 37 37 38 38 40 40 41 41 41 42 42 42 43 44 44 44 45 46 46 46 46 46 47 47 48 48 48 49 49 49 50 50 
a: 24.410000

48197
1833
62191
77 %
2 %
100 %

Ich würde fast sagen, besser geht es nicht...

[Lennox]

Ach... Ich hab nicht daran gedacht, dass nach den "sort_a"-Aufrufen alle Arrays ja schon sortiert sind... BubbleSort ist dann natürlich schneller, und SelectionSort braucht ohnehin immer n^2. My fault

[Schlangenmensch]

@Schlangenmensch sagte in Funktion optimieren:

Welcher Assambler?

Für den gcc (Linux).

Also tippe ich auf x64

@Schlangenmensch sagte in Funktion optimieren:

Warum?

Aus lernzwecken.

Geht es darum Assembler zu lernen, oder darum dich mit Optimierungen zu beschäftigen?

[Lennox]

Also, aus der Ausgabe werde ich noch nicht richtig schlau... mal ist die optimierte Variante schneller, mal nicht... Und die Übersetzung mit -O3 klappt leider nicht.

#include <stdio.h>
#include <sys/time.h>

volatile 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("%d ", a[0][i]);
    }
    printf("\na: %f\n...\n", average(a[0]));
    // ...
    for (size_t i = 0; i < n; i++)
    {
        printf("%d ", a[m - 1][i]);
    }
    printf("\na: %f\n\n---\n\n", average(a[m - 1]));
}

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);
}

volatile 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;
    }
}

void set_time(unsigned long *t_old, long *t, unsigned long *max_dif)
{
    struct timeval tv;
    gettimeofday(&tv, 0);
    *t = tv.tv_usec;
    unsigned long dif = *t - *t_old;
    if (dif > *max_dif)
    {
        *max_dif = dif;
    }
}

int main(int argc, char const *argv[])
{
    unsigned 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_a_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_b(arr[i]);
    }
    set_time(&t5, &t6, &max_dif);
    print(iterations, arr);

    printf("%d\n%d\n%d\n", t2 - t1, t4 - t3, t6 - t5);
    printf("%d %%\n%d %%\n%d %%\n", (t2 - t1) * 100 / max_dif, (t4 - t3) * 100 / max_dif, (t6 - t5) * 100 / max_dif);
    return 0;
}

---

@Schlangenmensch sagte in Funktion optimieren:

Also tippe ich auf x64

Ja.

@Schlangenmensch sagte in Funktion optimieren:

Geht es darum Assembler zu lernen, oder darum dich mit Optimierungen zu beschäftigen?

Es geht darum, sich mit einfachen Optimierungstechniken (zum Beispiel Loop-Unrolling) zu beschäftigen. Ich kann mir nicht vorstellen, dass wir in der Prüfung Asm-Code zu Papier bringen sollen, aber man kann nie sicher sein...

[Schlangenmensch]

@Lennox https://quick-bench.com/q/uIcKyRz-V3Q69r_UNbAqG0_0TIM
Den Inline Assambler Code habe ich nicht geschafft, ans laufen zu bringen, da bekomme ich nen Segfault (kann auch insgesamt einfach ein Timeout sein). Ich habe aber gerade auch keine Zeit, den zu debuggen. Aber auf der Seite bekommt man recht schnell und einfach einen Überblick, was wie schnell ist.

[wob]

Wenn ich den Code versuche zu kompilieren, gibts erstmal einen Haufen Warnungen für falsche Formate.

Mit -O3 kompiliert es nicht, mit -O2 gibt der Code nen Segfault.

Der Grund für das Nicht-Kompilieren mit -O3 ist:

https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html

Under certain circumstances, GCC may duplicate (or remove duplicates of) your assembly code when optimizing. This can lead to unexpected duplicate symbol errors during compilation if your asm code defines symbols or labels. Using ‘%=’ (see AssemblerTemplate) may help resolve this problem.

Was mir unbedingt fehlt: was sind die vielen Zahlen in deinem Code? Also -40, -8, -16 - wo kommen die her? Da wäre Kommentare sehr hilfreich.

(und ich finde intel-Style assembler auch deutlich leichter lesbar - bei den vielen %-Zeichen und Klammern schaltet mein Gehirn immer ab)

[Finnegan]

@Lennox sagte in Funktion optimieren:

Ach... Ich hab nicht daran gedacht, dass nach den "sort_a"-Aufrufen alle Arrays ja schon sortiert sind... BubbleSort ist dann natürlich schneller, und SelectionSort braucht ohnehin immer n^2. My fault

Die Idee von mir war auch nicht, das fill rauszunehmen, sondern das Zufalls-Array für jeden Test mit dem gleichen Anfangs-Seed zu generieren, damit jeder Test mit den gleichen Zufallszahlen im Array durchgeführt wird.

Auch war meine Idee nur eine anfängliche Abhängigkeit von einer volatile-Variable zu haben und die nicht bei jeder Zufallszahl zu lesen. Sonst könnte er "zu wenig optimieren". In diesem Fall ist das aber nicht so wichtig, da du nicht die Performance von fill optimieren willst. Wolltest du das aber, dann wäre das ein Problem:

volatile size_t initial_seed = 123;

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 a[])
{
    for (size_t i = 0; i < n; i++)
    {
        a[i] = my_rand(51);
    }
}

Da initial_seed eine volatile-Variable ist, muss die jedes mal aus dem Speicher gelesen werden. Meine Idee war nur am Anfang einmal einen Zugriff auf die zu haben um die "Beweisführung" des Compilers zu "sabotieren", damit er nicht auf die Idee kommt er könnte deinen gesamten Benchmark ja auch zur Compile-Zeit ausführen und lediglich das Ergebnis der Sortierung in die Executable einbetten (der initiale Seed 123 und n = 100 sind ja hartcodiert, daher kann man alles weitere theoretisch zur Compile-Zeit vorberechnen)

Das hatte schon einen Grund, dass ich das so formuliert habe:

volatile size_t seed = 123;
size_t random_value = seed;

void fill(size_t a[]) {
    for (size_t i = 0; i < n; i++) {
        random_value = my_rand(random_value, 51);
        a[i] = random_value;
    }
}

Aber wie gesagt, da du nicht fill messen und optimieren willst, macht das hier jetzt keinen großen Unterschied. Ich denke aber du solltest den Zusammenhang kennen.

[Finnegan]

@Lennox sagte in Funktion optimieren:

Und die Übersetzung mit -O3 klappt leider nicht.

Es wäre hilfreich, wenn du da mal eine Fehlermeldung postest oder näher auf deine Schlussfolgerungen eingehst, die dich darauf gebracht haben.

@Schlangenmensch sagte in Funktion optimieren:

Geht es darum Assembler zu lernen, oder darum dich mit Optimierungen zu beschäftigen?

Es geht darum, sich mit einfachen Optimierungstechniken (zum Beispiel Loop-Unrolling) zu beschäftigen. Ich kann mir nicht vorstellen, dass wir in der Prüfung Asm-Code zu Papier bringen sollen, aber man kann nie sicher sein...

Um die Techniken zu lernen ist -O0 vielleicht doch nicht so schlecht. Es war am Anfang etwas unklar, wofür du das brauchst. Mit -O3 würde der Compiler eh schon all diese Optimierungen machen, auch Loop Unrolling (sofern es Sinn ergibt in dem Kontext). Da könnte es dann schwer werden mit handgeschriebenem Assembler überhaupt ein besseres Ergebnis als der Compiler zu erzielen. Das ist auch der Grund, weshalb man diese Optimierungen in der Praxis so gut wie nie braucht und solche Vorhaben meistens eine schlechte Idee sind (trotzdem gut, darüber zu lernen und die zu kennen!).

[Lennox]

-O3:

gcc -O3 main.c -o main
main.c: Assembler messages:
main.c:83: Error: symbol `.loop_start' is already defined
main.c:114: Error: symbol `.loop_increment' is already defined
main.c:117: Error: symbol `.loop_check' is already defined
main.c:83: Error: symbol `.loop_start' is already defined
main.c:114: Error: symbol `.loop_increment' is already defined
main.c:117: Error: symbol `.loop_check' is already defined

Ich vermute, er versucht dann auch, meine Inline-Asm-Optimierung zu optimieren (obwohl er das ja nicht soll), also er versucht, den Funktionsaufruf aufzulösen? Möglicherweise habe ich auch falsche Labelbezeichner, die intern schon reserviert sind.

Lässt man -O... ganz weg, sollte es klappen.

@wob sagte in Funktion optimieren:

Was mir unbedingt fehlt: was sind die vielen Zahlen in deinem Code? Also -40, -8, -16 - wo kommen die her? Da wäre Kommentare sehr hilfreich.
(und ich finde intel-Style assembler auch deutlich leichter lesbar - bei den vielen %-Zeichen und Klammern schaltet mein Gehirn immer ab)

An sich nicht kompliziert:

%[n] ist n (andere Schreibweise für n(%rip))
-8(%%rbp) müsste i sein
-16(%%rbp) müsste j sein
-24(%%rbp) sollte a oder b sein
-32(%%rbp) sollte a oder b sein
-40(%%rbp) Pointer aufs Array

Habe den Code auch noch nicht wirklich optimiert, bin mir nicht sicher, aber er nicht schon minimal wäre.

Vielleicht gibt es deshalb auch keinen Unterschied zwischen sort_a und sort_a_optimized.

Vielleicht wäre es auch sinnvoll, statt sort_a, mit C's qsort zu vergleichen... Asymptotisch betrachtet kann man Quick-, Merge- oder Heapsort natürlich nicht schlagen, aber hier geht es um genau 100 Elemente... das sollte eine Schranke sein.

@Finnegan sagte in Funktion optimieren:

Die Idee von mir war auch nicht, das fill rauszunehmen, sondern das Zufalls-Array für jeden Test mit dem gleichen Anfangs-Seed zu generieren, damit jeder Test mit den gleichen Zufallszahlen im Array durchgeführt wird.

Es geht ja nicht darum (wie bereits richtig erwähnt), das "fill" zu optimieren, sondern nur das "sort". Und mir gefällt das bisher eigentlich schon ganz gut...

Bin mir nicht sicher, ob man bei immer gleichen Eingabe-Arrays nicht in die Gefahr läuft, dass der Prozessor Optimierungen des "Mikrocodes" noch vornimmt... Angeblich soll ja nämlich zwischen Maschinencode und dem, was der Prozessor "macht", noch mal eine Abstraktionsschicht seien... Aber das ist nur eine Vermutung.

[Finnegan]

@Lennox sagte in Funktion optimieren:

-O3:

gcc -O3 main.c -o main
main.c: Assembler messages:
main.c:83: Error: symbol `.loop_start' is already defined
main.c:114: Error: symbol `.loop_increment' is already defined
main.c:117: Error: symbol `.loop_check' is already defined
main.c:83: Error: symbol `.loop_start' is already defined
main.c:114: Error: symbol `.loop_increment' is already defined
main.c:117: Error: symbol `.loop_check' is already defined

Jo, irgendeine Symbol-Kollision. Der GNU Assembler ist da etwas seltsam. Versuchs mal mit lokalen Labels. Die werden nicht zu Symbolen in der Objektdatei gemacht und müssen auch nicht eindeutig sein. Die beginnen mit .L, also sowas wie .Lloop_start, etc. Wenn das nicht hilft, dann mit einfachen numerischen Labels versuchen (1:, 2:, 3:, etc), die sind immer lokal, also sowas in diese Richtung:

1:
...
jb 1b

1b heisst hier: Springe "backwards" zum nächstgelegenen label mit der Nummer 1. Für Vorwärts-Sprung wäre das dann z.B. jmp 1f

@Finnegan sagte in Funktion optimieren:

Die Idee von mir war auch nicht, das fill rauszunehmen, sondern das Zufalls-Array für jeden Test mit dem gleichen Anfangs-Seed zu generieren, damit jeder Test mit den gleichen Zufallszahlen im Array durchgeführt wird.

Es geht ja nicht darum (wie bereits richtig erwähnt), das "fill" zu optimieren, sondern nur das "sort". Und mir gefällt das bisher eigentlich schon ganz gut...

Aber für die bessere Vergleichbarkeit willst du vielleicht die gleichen Eingabedaten verwenden. Sonst generierst du vielleicht Arrays die eher günstig für den einen Algorithmus und ungünstig für den anderen sind. Das nimmt eine Quelle für Bias raus.

Bin mir nicht sicher, ob man bei immer gleichen Eingabe-Arrays nicht in die Gefahr läuft, dass der Prozessor Optimierungen des "Mikrocodes" noch vornimmt... Angeblich soll ja nämlich zwischen Maschinencode und dem, was der Prozessor "macht", noch mal eine Abstraktionsschicht seien... Aber das ist nur eine Vermutung.

Vielleicht so was wie den Branch Predictor "vortrainieren"? Wenn du dir schon diese Gedanken machst, dann solltest du dich wirklich mal mit Google Benchmark beschäftigen. Die Bibliothek sollte eigentlich exakt solche Probleme minimieren. Und vermutlich auch noch viele andere, die wir beide noch gar nicht auf dem Schirm haben.

[Lennox]

Noch schnell ein Wort zur Architektur und warum das möglicherweise bei @Schlangenmensch und @wob noch nicht lief:

CPU: AMD Ryzen 5 3600
OS: Windows 11 und WSL 2 Backend
Linux: Docker und linuxserver/webtop mit amd64-debian-kde (latest)
Compiler: gcc

gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-linux-gnu/14/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none:amdgcn-amdhsa
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-linux-gnu
Configured with: ...
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 14.2.0 (Debian 14.2.0-19)

1: https://docs.linuxserver.io/images/docker-webtop/

2: docker-compose.yml:

services:
  webtop:
    image: lscr.io/linuxserver/webtop:amd64-debian-kde
    container_name: webtop
    security_opt:
      - seccomp:unconfined
    environment:
      - PUID=1000
      - PGID=1000
      - TZ=Europe/Berlin
      - SUBFOLDER=/
      - TITLE=Webtop-Desktop
    volumes:
      - ./config-2/:/config/  # entsprechend anpassen
      - /var/run/docker.sock:/var/run/docker.sock
    ports:
      - 127.0.0.1:3000:3000
    shm_size: "8gb"