4. Funktion optimieren

Funktion optimieren

  • F

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

    1
    L
     1 Antwort
  • L

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

    0
  • L

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

    0
  • L

    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

    0
    F
     1 Antwort
  • S

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

    0
  • L

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

    0
    S
    F
     2 Antworten
  • S

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

    0
  • W

    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)

    0
  • F

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

    0
  • F

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

    0
  • L

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

    0
Anmelden zum Antworten