Funktion optimieren

Finnegan

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"

Lennox

@wob sagte in Funktion optimieren:

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

Welche denn?

esoka

Dieser Beitrag wurde gelöscht!

Lennox

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

Lennox

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.

Finnegan

@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 volatile is 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

Schlangenmensch

@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 constexpr haben die Compiler sehr vollständige C++ Interpreter, denn alles, was constexpr ist, muss zur Compiletime interpretiert werden.

Lennox

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

Finnegan

@Lennox hattest du nicht mal volatile size_t initial_seed = 123; da stehen? Warum das volatile weg? Mein einziger Kritikpunkt war ja, dass fill() dann bei jeder Iteration indirekt eine volatile-Variable liest, aber da du eh nicht die fill()-Performance messen willst ist das eigentlich egal. Ansonsten einfach den Wert 123 aus einer volatile-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".

volatile sagt dem Compiler hier: Du kannst dich nicht darauf verlassen, dass die Variable beim Lesen immer noch den Wert 123 hat. 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".

Quiche Lorraine

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

Lennox

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 volatile wieder hinzugefügt und berechne den total_hash nicht mehr...

Erhard Henkes

@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/Collapse

Das 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.
*/

wob

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

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.

Lennox

@Erhard-Henkes In C kann man doch auch /dev/urandom lesen, 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.

Lennox

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