Funktion optimieren

[Finnegan]

Sieht für mich bei grobem Überfliegen einigermaßen okay aus für nen simplen Benchmark. Ich bin allerdings etwas unglücklich darüber, wie in deinem Code vermieden wird, dass der Compiler das Ergebnis des gesamten Algorithmus via Constant Folding direkt zur Compile-Zeit berechnet. Ich denke das ist lediglich ein "Unfall" dass er nicht direkt die sortierten Arrays als "Compiler-Optimierung" erzeugt:

size_t arr[n];

Ein nicht-initialisiertes Array. Dessen Inhalt ist nicht für den Compiler vorhersehbar.

und

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

Hier verwendest du einen solchen unvorhersehbaren Wert (a[0]) um einen Random-Seed zu berechnen (du kannst ja mal probeweise ein memset(arr, 0, sizeof(arr)); einbauen. Gut möglich dass das zu überraschenden Ergebnissen führt ).

Ich würde empfehlen, das etwas sauberer und besser reproduzierbar zu lösen, z.B. so:

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

volatile macht hier seed effektiv zu so einem unvorhersehbaren Wert, indem es Compiler-Optimierungen verbietet, die annehmen, dass seed bei der Zuweisung in Zeile 2 immer noch den Wert 123 hat, auch wenn es tatsächlich immer noch 123 ist. Das verhindert auch alle weiteren Optimierungen, die darauf aufbauen.

random_value = seed; vor jedem Benchmark-Test zu setzen wäre auch nicht verkehrt. Das würde dafür sorgen, dass alle Algorithmen mit den selben Arrays arbeiten (bessere Vergleichbarkeit).

Nun zu den Benchmarks:

@Lennox sagte in Funktion optimieren:

Ich denke, für den Use-Case kann man selbst mit -O3 nicht mehr herausholen...

Ich hoffe deine Benchmarks sind auch bereits alle mit -O3 kompiliert. Sonst sind die Ergebnisse nämlich wenig aussagekräftig. Bei -O0 z.B. wäre es keine große Kunst den Compiler mit handgeschriebenem Assembler zu schlagen.

Zu dem Assembler-Code selbst kann ich nichts sagen. Ich finde AT&T-Syntax leider unlesbar und habe auch nicht den Nerv das komplett zu analysieren. Es sieht allerdings bereits von der Länge her umständlicher aus, als das was dein Compiler vermutlich mit -O3 aus deinem zuerst geposteten Algorithmus macht: https://godbolt.org/z/9PGE7jdT8.

Vielleicht kannst du beschreiben, was deine Optimierungs-Ideen waren und sicherstellen, dass der Compiler die nicht ohnehin schon mit -O3 umsetzt (?).

Wenn dein Assembler-Code tatsächlich äquivalent ist, der C-Code mit -O3 kompiliert wurde und der Benchmark auch konsistent einen Vorteil für deine Assembler-Implementierung ausweist (manchmal sind das auch Cache-Effekte oder der OS-Scheduler spielt da mit rein) dann würde mich auch interessieren, woran das liegt. Das wäre ja schon ein signifikanter Unterschied. Ich gehe aber erstmal davon aus, dass du wahrscheinlich nicht exakt das gemessen hast, was du eigentlich wolltest (fill ist unter anderem auch noch mit drin als Komponente in den Timings).

P.S.: Wenn du solche Micro-Benchmarks öfter machen willst, dann empfehle ich dir auch, dir mal Google Benchmark anzuschauen. Das hat bereits gute Lösungen für viele Fettnäpfchen, in die man dabei tapsen kann (ungewollte Compiler-Optimierungen, gute Timer, gute Zufallswerte, Cache- und Scheduler-Effekte und auch solche Konstruktions-Aufgaben, die man nicht mit in der Messung haben will wie dein fill z.B.).

[Finnegan]

@Lennox sagte in Funktion optimieren:

@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.

i kann nicht negativ werden, aber 0 sein. Und wenn du dann eins abziehst hats du das Überlauf-Verhalten und i wird irrsinnig groß.
Die Idee bei dieser Optimierung ist, i nur so weit zurückzusetzen, dass du die Elemente, die schon geprüft wurden und nicht geswappt werden müssen nicht nochmal zu prüfen.

Du hast hier an dieser Stelle gerade ein Element um eine Position nach oben "gebubbled", nun musst du prüfen, ob es weiter nach oben verschoben werden muss. Dafür musst du nochmal mit dem Vorgänger der neuen Position vergleichen. Das erreichst du, indem du i um 1 dekrementierst. Auf 0 setzen funktioniert auch, aber dann würdest du auch Vergleiche mit drin haben, die du schon gemacht hast und die durch den aktuellen Swap nicht beeinflusst werden:

Angenommen du tauschst a[100] mit a[101] (i = 100), dann musst du als nächstes nur a[99] mit a[100] vergleichen, da sich a[100] verändert hat. Alle anderen Element-Paare davor sind ja nicht von dem Swap betroffen, z.B. a[50] und a[51] ...die sind unverändert und bereits in der aktuellen Schleife geprüft worden. Unnötig, die nochmal zu prüfen.

[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"