4. Funktion optimieren

Funktion optimieren


  • 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;
}
    1
  • L

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

    0
  • E

    @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.
*/
    1
    L
     1 Antwort
  • W

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

    1
    L
     2 Antworten
  • L

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

    0
  • L

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

    0
  • L

    @wob
    So besser?

    #include <stdio.h>
#include <stdlib.h>
#include <time.h>

volatile size_t initial_seed = 123;

size_t total_hash = 23;

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

// Quicksort?
void sort_a(size_t n, size_t arr[])
{
    qsort(arr, n, sizeof(size_t), compare);
}

// Bubble sort
void sort_b(size_t n, 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 n, 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 n, 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;
            do
            {
                arr[k] = b;
                arr[l] = a;
                if (k == 0)
                {
                    break;
                }
                k--;
                l--;
                a = arr[k];
                b = arr[l];
            } while (a > b);
        }
        i++;
        j++;
    }
}

#pragma GCC push_options
#pragma GCC optimize("O0")
void sort_optimized(size_t n, size_t arr[])
{
    asm volatile(
        "  movq  %%rdi, -40(%%rbp)    \n"
        "  movq  %%rsi, -48(%%rbp)    \n"
        "  movq  $0, -8(%%rbp)        \n"
        "  movq  $1, -16(%%rbp)       \n"
        "  jmp  3f                    \n"
        "1:                           \n"
        "  movq  -8(%%rbp), %%rax     \n"
        "  leaq  0(,%%rax,8), %%rdx   \n"
        "  movq  -48(%%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  -48(%%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  -48(%%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  -48(%%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  -16(%%rbp), %%rax    \n"
        "  cmpq  -40(%%rbp), %%rax    \n"
        "  jb  1b                     \n"
        : /* No outputs. */
        : /* No inputs. */
        : "memory");
}
#pragma GCC pop_options

double profile_sort_func(void (*f)(size_t, size_t *), size_t n, size_t m, size_t arr[m][n])
{
    rfill(n, m, arr);
    print(n, m, arr);
    clock_t c1 = clock();
    for (size_t i = 0; i < m; i++)
    {
        (*f)(n, arr[i]);
    }
    clock_t c2 = clock();
    print(n, m, arr);
    return (double)(c2 - c1) / CLOCKS_PER_SEC;
}

int main(int argc, char const *argv[])
{
    size_t n = 10;
    size_t m = 100000;
    size_t arr[m][n];
    double secs[5] = {
        profile_sort_func(sort_a, n, m, arr),
        profile_sort_func(sort_b, n, m, arr),
        profile_sort_func(sort_c, n, m, arr),
        profile_sort_func(sort_d, n, m, arr),
        profile_sort_func(sort_optimized, n, m, arr),
    };
    double max = 0;
    for (size_t i = 0; i < 5; i++)
    {
        if (secs[i] > max)
        {
            max = secs[i];
        }
    }
    printf("%fs %f%%\n%fs %f%%\n%fs %f%%\n%fs %f%%\n%fs %f%%\n",
           secs[0], secs[0] * 100 / max,
           secs[1], secs[1] * 100 / max,
           secs[2], secs[2] * 100 / max,
           secs[3], secs[3] * 100 / max,
           secs[4], secs[4] * 100 / max);
    return 0;
}

    gcc -Wall main.c -o main
./main 
27 42 3 33 40 14 19 12 36 43 
a: 26.900000
...
24 36 36 26 49 36 47 1 48 40 
a: 34.300000
h: 5939366454565110528

3 12 14 19 27 33 36 40 42 43 
a: 26.900000
...
1 24 26 36 36 36 40 47 48 49 
a: 34.300000
h: 4429705970288659611

33 44 43 0 24 15 46 36 2 11 
a: 25.400000
...
28 20 39 12 2 25 18 43 16 50 
a: 25.300000
h: 6352222085557659981

0 2 11 15 24 33 36 43 44 46 
a: 25.400000
...
2 12 16 18 20 25 28 39 43 50 
a: 25.300000
h: 4505934733348363633

9 39 48 42 46 11 50 24 15 37 
a: 32.100000
...
1 23 45 46 29 44 24 3 7 40 
a: 26.200000
h: 4225079418598471750

9 11 15 24 37 39 42 46 48 50 
a: 32.100000
...
1 3 7 23 24 29 40 44 45 46 
a: 26.200000
h: 1630903755648978609

3 26 21 15 26 27 35 13 32 43 
a: 24.100000
...
45 8 6 21 47 31 28 6 45 24 
a: 26.100000
h: 4076123578238199228

3 13 15 21 26 26 27 32 35 43 
a: 24.100000
...
6 6 8 21 24 28 31 45 45 47 
a: 26.100000
h: 10126057256555243605

13 30 14 4 11 21 10 24 4 19 
a: 15.000000
...
32 12 45 33 31 9 41 32 21 46 
a: 30.200000
h: 14143251785556203417

4 4 10 11 13 14 19 21 24 30 
a: 15.000000
...
9 12 21 31 32 32 33 41 45 46 
a: 30.200000
h: 10117127439067026547

0.019759s 66.492798%
0.029716s 100.000000%
0.019451s 65.456320%
0.014100s 47.449186%
0.028555s 96.093014%

    ... Ich habe noch nicht angefangen, das Assembly zu optimieren. 😂

    0
    F
     1 Antwort
  • F

    @Lennox sagte in Funktion optimieren:

    ... Ich habe noch nicht angefangen, das Assembly zu optimieren. 😂

    Zu n = 10 muss man allerdings anmerken, dass es keine Neuigkeit ist, dass Bubblesort für sehr kleine Arrays im Allgemeinen ziemlich gut abschneidet. Gründe hierfür können u.a. sein:

    • kleinerer Overhead, weniger Code
    • weniger umständliche Pointer-Manipulationen, direkt in-place
    • weniger Branches und besser vorhersagbares Branching-Verhalten (Branch Prediction)
    • gute Cache-Lokalität kleinerer Arrays

    Insertion Sort hat allerdings auch diese Vorteile und meines Wissens ist das der Algorithmus der Wahl für kleine Arrays.

    Auch ist der Code natürlich nicht optimiert mit gcc -Wall main.c -o main. Meines Wissens ist -O0 Default. Aber das kann ja durchaus deine Absicht sein, wenn du allgemein über Optimierung lernen willst und eben nicht vorhast, den Compiler mit -O3 zu schlagen 😉

    Edit: Noch ein Tip: Gib doch auch mal den Namen der Algorithmen in deinem Output aus, auch wenn das für dich klar ist. Als Außenstehender finde ich es echt mühsam das korrekt zuzuordnen. Erst über den Array-Index, dann über den Funktionsnamen und dann haben die auch noch Namen wie sort_a oder sort_b und man erfährt eigentlich nur aus den Kommentaren, was da eigentlich passiert.

    1
    L
     1 Antwort
  • L

    Mit der O3-Option sollten die Ergebnisse ähnlich sein. Bubblesort ist sehr einfach zu implementieren, schneidet aber ca. um 1/3 schlechter ab als qsort. Insertionsort ist auch einfach zu implementieren, benötigt für kleine n aber ca. nur die Hälfte der Zeit von qsort. Mit den vergleichsbasierten Verfahren, die wiederum auf Vertausch, Selektion oder Einfügung (oder Teilung) basieren, haben wir damit alle wichtigen Verfahren einmal dem teilenden qsort-Verfahren gegenübergestellt.

    0
  • L

    @Finnegan
    Etwas aus dem Nähkästchen, dieses Thema sollte keine Überraschungen liefern... Vielmehr ging es mir darum, den gcc und Asm etwas besser zu verstehen... Sortierverfahren sind ja so ziemlich das erste, womit sich kluge Leute in der Informatik sehr ausgiebig beschäftigt hatten. Es würde einem Wunder gleichen, wenn ich dabei zu bahnbrechenden, neuen Erkenntnissen gelangt wäre... Aber immerhin konnte ich etwas (Neues) lernen.

    0
    S
     1 Antwort
  • S

    @Lennox Darum habe ich am Anfang gefragt, was Ziel der ganzen Aktion ist. Hättest du das da schon gesagt, hätte hier keiner was zum Thema Optimierungen gesagt. Aber seinerzeit hast du davon gesprochen dich mit Optimierungsverfahren auseinandersetzen zu wollen; Loop unrolling etc (etwas was man übrigens auch ohne Asm machen kann 😉 )

    0
    L
     1 Antwort
  • L

    @Schlangenmensch
    Es ging mir um beides: Übersetzungs- und Optimierungstechniken in C und Asm... Außerdem kann es ja nicht schaden... wenn man das (also den Benchmark) dabei von Anfang an richtig macht. 😅

    Ich muss leider für eine so genannte "Mixed-Prüfung" lernen, angefangen bei Strom/Elektrik, dann weiter mit Komponenten der Elektrotechnik, dann weiter mit Modellierung und Diagrammen, und dann weiter mit Low-Level-Programmierung und Optimierung. Verstehe auch nicht... warum das so thematisch breit, anstatt tief gefächert ist.

    0
  • L

    Jetzt habe ich ein wenig optimiert...

    Das Ergebnis ist, dass bis ca. n=28 Insertion-Sort schneller ist als Quicksort für -O0, und bis ca. n=72 Insertion-Sort schneller ist als Quicksort für -O3.

    Die Überraschung ist also, dass -O3 den Code langsamer anstatt schneller macht.

    #include <stdio.h>
#include <stdlib.h>
#include <time.h>

volatile size_t initial_seed = 123;

size_t total_hash = 23;

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

// Quicksort
void sort_a_quick(size_t n, size_t arr[])
{
    qsort(arr, n, sizeof(size_t), compare);
}

// Bubble sort
void sort_b_bubble(size_t n, 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_selection(size_t n, 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_insertion(size_t n, 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;
            do
            {
                arr[k] = b;
                arr[l] = a;
                if (k == 0)
                {
                    break;
                }
                k--;
                l--;
                a = arr[k];
                b = arr[l];
            } while (a > b);
        }
        i++;
        j++;
    }
}

#pragma GCC push_options
#pragma GCC optimize("O0")
void sort_e_insertion_optimized(size_t n, size_t arr[])
{
    asm volatile(
        "  movq  %%rdi, -56(%%rbp)    \n"
        "  movq  %%rsi, -64(%%rbp)    \n"
        "  movq  $0, -8(%%rbp)        \n"
        "  movq  $1, -16(%%rbp)       \n"
        "  movq  -16(%%rbp), %%rax    \n"
        "1:                           \n"
        "  movq  -8(%%rbp), %%rax     \n"
        "  leaq  0(,%%rax,8), %%rdx   \n"
        "  movq  -64(%%rbp), %%rax    \n"
        "  addq  %%rdx, %%rax         \n"
        "  movq  (%%rax), %%rax       \n"
        "  movq  %%rax, -40(%%rbp)    \n"
        "  movq  -16(%%rbp), %%rax    \n"
        "  leaq  0(,%%rax,8), %%rdx   \n"
        "  movq  -64(%%rbp), %%rax    \n"
        "  addq  %%rdx, %%rax         \n"
        "  movq  (%%rax), %%rax       \n"
        "  movq  %%rax, -48(%%rbp)    \n"
        "  movq  -40(%%rbp), %%rax    \n"
        "  cmpq  %%rax, -48(%%rbp)    \n"
        "  jnb  3f                    \n"
        "  movq  -8(%%rbp), %%rax     \n"
        "  movq  %%rax, -24(%%rbp)    \n"
        "  movq  -16(%%rbp), %%rax    \n"
        "  movq  %%rax, -32(%%rbp)    \n"
        "2:                           \n"
        "  movq  -24(%%rbp), %%rax    \n"
        "  leaq  0(,%%rax,8), %%rdx   \n"
        "  movq  -64(%%rbp), %%rax    \n"
        "  addq  %%rax, %%rdx         \n"
        "  movq  -48(%%rbp), %%rax    \n"
        "  movq  %%rax, (%%rdx)       \n"
        "  movq  -32(%%rbp), %%rax    \n"
        "  leaq  0(,%%rax,8), %%rdx   \n"
        "  movq  -64(%%rbp), %%rax    \n"
        "  addq  %%rax, %%rdx         \n"
        "  movq  -40(%%rbp), %%rax    \n"
        "  movq  %%rax, (%%rdx)       \n"
        "  cmpq  $0, -24(%%rbp)       \n"
        "  je   3f                    \n"
        "  subq  $1, -24(%%rbp)       \n"
        "  subq  $1, -32(%%rbp)       \n"
        "  movq  -24(%%rbp), %%rax    \n"
        "  leaq  0(,%%rax,8), %%rdx   \n"
        "  movq  -64(%%rbp), %%rax    \n"
        "  addq  %%rdx, %%rax         \n"
        "  movq  (%%rax), %%rax       \n"
        "  movq  %%rax, -40(%%rbp)    \n"
        "  movq  -32(%%rbp), %%rax    \n"
        "  leaq  0(,%%rax,8), %%rdx   \n"
        "  movq  -64(%%rbp), %%rax    \n"
        "  addq  %%rdx, %%rax         \n"
        "  movq  (%%rax), %%rax       \n"
        "  movq  %%rax, -48(%%rbp)    \n"
        "  movq  -40(%%rbp), %%rax    \n"
        "  cmpq  %%rax, -48(%%rbp)    \n"
        "  jb   2b                    \n"
        "3:                           \n"
        "  addq  $1, -8(%%rbp)        \n"
        "  addq  $1, -16(%%rbp)       \n"
        "  movq  -16(%%rbp), %%rax    \n"
        "  cmpq  -56(%%rbp), %%rax    \n"
        "  jb   1b                    \n"
        : /* No outputs. */
        : /* No inputs. */
        : "memory");
}
#pragma GCC pop_options

double profile_sort_func(void (*f)(size_t, size_t *), size_t n, size_t m, size_t arr[m][n])
{
    rfill(n, m, arr);
    print(n, m, arr);
    clock_t c1 = clock();
    for (size_t i = 0; i < m; i++)
    {
        (*f)(n, arr[i]);
    }
    clock_t c2 = clock();
    print(n, m, arr);
    return (double)(c2 - c1) / CLOCKS_PER_SEC;
}

int get_sort_winner(size_t n, size_t m)
{
    size_t arr[m][n];
    double secs[5] = {
        profile_sort_func(sort_a_quick, n, m, arr),
        profile_sort_func(sort_b_bubble, n, m, arr),
        profile_sort_func(sort_c_selection, n, m, arr),
        profile_sort_func(sort_d_insertion, n, m, arr),
        profile_sort_func(sort_e_insertion_optimized, n, m, arr),
    };
    int min_index = 0;
    double min = secs[0], max = secs[0];
    for (size_t i = 0; i < 5; i++)
    {
        if (secs[i] < min)
        {
            min_index = i;
            min = secs[i];
        }
        if (secs[i] > max)
        {
            max = secs[i];
        }
    }
    printf("%fs %f%%\n%fs %f%%\n%fs %f%%\n%fs %f%%\n%fs %f%%\n",
           secs[0], secs[0] * 100 / max,
           secs[1], secs[1] * 100 / max,
           secs[2], secs[2] * 100 / max,
           secs[3], secs[3] * 100 / max,
           secs[4], secs[4] * 100 / max);
    return min_index;
}

int main(int argc, char const *argv[])
{
    size_t n = 5;
    size_t m = 10000;
    while (get_sort_winner(n, m) != 0)
    {
        n++;
    }
}

    Edit: In der Assemblercodeoptimierung habe ich aus der äußeren while-Schleife eine do-while-Schleife gemacht... das ist natürlich gefährlich. Außerdem habe ich nop's und unnötige Labels bzw. Sprünge entfernt.

    0
Anmelden zum Antworten