4. Funktion optimieren

Funktion optimieren

  • 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
    L
     1 Antwort
  • L

    @Lennox sagte in Funktion optimieren:

    " movq -16(%%rbp), %%rax \n"

    Habe gerade noch etwas gesehen... Diese Zeile (170) scheint überflüssig zu sein, denn in 172 bekommt rax ja schon wieder einen neuen Wert, Typo.

    0
  • L

    Weiter optimiert... Jetzt bin ich in den meisten Fällen schneller als der gcc:

        asm volatile(
        "  movq  %%rdi, -56(%%rbp)    \n"
        "  movq  %%rsi, -64(%%rbp)    \n"
        "  movq  $0, -8(%%rbp)        \n"
        "  subq  $1, -8(%%rbp)        \n"
        "  movq  $0, -16(%%rbp)       \n"
        "1:                           \n"
        "  addq  $1, -16(%%rbp)       \n"
        "  movq  -16(%%rbp), %%rax    \n"
        "  cmpq  -56(%%rbp), %%rax    \n"
        "  jnb  3f                    \n"
        "  addq  $1, -8(%%rbp)        \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  1b                    \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   1b                    \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"
        "  jnb  1b                    \n"
        "  jmp  2b                    \n"
        "3:                           \n"
        : /* No outputs. */
        : /* No inputs. */
        : "memory");

    Ich habe ein paar Vermutungen:

    • jnb ist schneller als jb
    • Viele Vergleichsoperationen sind relativ teuer
    • In der Summe sind viele kleine Sprünge schneller, als lange Sprünge, insofern es nicht zu viele Labels gibt

    Stimmt das?

    0
  • L

    Für eine bessere Übersicht habe ich noch ein kleines Bewertungssystem hinzugefügt. In jeder Runde bekommt der erstplatzierte 5 Punkte, der zweitplatzierte 4 usw. - der letztplatzierte bekommt 1 Punkt. Es werden die Runden n=5, n=6 usw. gespielt - bis Quicksort in einer Runde am schnellsten ist.

    Long story short, danach wird ausgegeben, wer die meisten Punkte gesammelt hat:

    ...
(0) 0.008103s 15.380965% (71 points)
(1) 0.052682s 100.000000% (27 points)
(2) 0.011104s 21.077408% (55 points)
(3) 0.008565s 16.257925% (104 points)
(4) 0.008230s 15.622034% (118 points)
n_max=29
(4.) 118 points
(3.) 104 points
(0.) 71 points
(2.) 55 points
(1.) 27 points

    Nach diesem Punktesystem, wäre mein optimiertes Verfahren auf Platz 1 und Quicksort auf Platz 3 - und das einfache Bubblesort-Verfahren ist am langsamsten.

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

volatile size_t initial_seed = 123;

size_t total_hash = 23;

// A structure for the future rating system.
typedef struct score
{
    size_t index;
    double seconds;
    size_t points;
} SCORE;

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

// Comparison function for score seconds
int compare_score_seconds(const void *a, const void *b)
{
    double a_dbl = ((SCORE *)a)->seconds;
    double b_dbl = ((SCORE *)b)->seconds;
    return a_dbl < b_dbl ? -1 : a_dbl > b_dbl ? +1
                                              : 0;
}

// Comparison function for score points
int compare_score_points(const void *a, const void *b)
{
    int a_int = ((SCORE *)a)->points;
    int b_int = ((SCORE *)b)->points;
    return b_int - a_int;
}

// 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"
        "  subq  $1, -8(%%rbp)        \n"
        "  movq  $0, -16(%%rbp)       \n"
        "1:                           \n"
        "  addq  $1, -16(%%rbp)       \n"
        "  movq  -16(%%rbp), %%rax    \n"
        "  cmpq  -56(%%rbp), %%rax    \n"
        "  jnb  3f                    \n"
        "  addq  $1, -8(%%rbp)        \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  1b                    \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   1b                    \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"
        "  jnb  1b                    \n"
        "  jmp  2b                    \n"
        "3:                           \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;
}

size_t num_of_funcs = 5;
size_t get_sort_scores(size_t n, size_t m, SCORE *scores)
{
    size_t arr[m][n];
    scores[0].seconds = profile_sort_func(sort_a_quick, n, m, arr);
    scores[1].seconds = profile_sort_func(sort_b_bubble, n, m, arr);
    scores[2].seconds = profile_sort_func(sort_c_selection, n, m, arr);
    scores[3].seconds = profile_sort_func(sort_d_insertion, n, m, arr);
    scores[4].seconds = profile_sort_func(sort_e_insertion_optimized, n, m, arr);
    SCORE scores_cpy[num_of_funcs];
    for (size_t i = 0; i < num_of_funcs; i++)
    {
        scores_cpy[i] = scores[i];
    }
    qsort(scores_cpy, num_of_funcs, sizeof(SCORE), compare_score_seconds);
    double factor = 100 / scores_cpy[num_of_funcs - 1].seconds;
    for (size_t i = 0; i < num_of_funcs; i++)
    {
        scores[scores_cpy[i].index].points += num_of_funcs - i;
    }
    for (size_t i = 0; i < num_of_funcs; i++)
    {
        printf("(%zu) %fs %f%% (%zu points)\n", i, scores[i].seconds, scores[i].seconds * factor, scores[i].points);
    }
    return scores_cpy[0].index;
}

int main(int argc, char const *argv[])
{
    size_t n = 5;
    size_t m = 10000;
    SCORE scores[] = {
        {0, 0, 0},
        {1, 0, 0},
        {2, 0, 0},
        {3, 0, 0},
        {4, 0, 0},
    };
    while (get_sort_scores(n++, m, scores) != 0)
        ;
    printf("n_max=%zu\n", n - 1);
    qsort(scores, 5, sizeof(SCORE), compare_score_points);
    for (size_t i = 0; i < num_of_funcs; i++)
    {
        printf("(%zu.) %zu points\n", scores[i].index, scores[i].points);
    }
}

    Btw., wäre die Nähe der profile_sort_func zur Sortierungsfunktionsdefinition (also dem Aufruf...) eigentlich auch relevant? Also, können lange "Call"-Strecken das Ergebnis auch beeinflussen?

    0
    F
     1 Antwort
  • L

    Hmm, unter den Blinden ist der einäugige König... Mit -O3 ist wieder der Compiler bzw. das unmodifizierte Insertionsort-Verfahren schneller.

    0
  • F

    @Lennox sagte in Funktion optimieren:

    Btw., wäre die Nähe der profile_sort_func zur Sortierungsfunktionsdefinition (also dem Aufruf...) eigentlich auch relevant? Also, können lange "Call"-Strecken das Ergebnis auch beeinflussen?

    Ich würde vermuten dass das höchstens mit -O0 auftritt und der Effekt dann auch nur minimal ist. Funktionsaufrufe sind nicht sonderlich teuer und auf höheren Optimierungstufen dürfte das auch ge-inlined werden. Soweit ich sehe ist das ja nur ein zusätzlicher Call je Sortierung. Das ist vernachlässigbar. Wäre das z.B. ein extra Call je "swap"-Operation in den Algorithmen würde ich mir mehr Gedanken machen.

    Wo das aber schadet ist, wenn ich als Außenstehender herausfinden will, welche dieser Zahlen überhaupt für welchen Algorithmus steht. Ich hatte ja schonmal angeregt, den Namen des Algorithmus mit auszugeben (das wäre eine tiefer hängende Frucht für die "Übersichtlichkeit" gewesen als ein Punktesystem). Ich mache mir jetzt zumindest nicht mehr die Mühe herauszufinden, welche Ergebnisse für welchen Algo stehen und denke mir nur "meh, irgendwelche Algorithmen laufen unterschiedlich schnell, nett" 😉

    Ansonsten: Nochmal, wenn du schon so viel in die Richtung machst, schau dir Google Benchmark an. Braucht vielleicht etwas Einarbeitung, aber du sparst dir eine Menge von dem Zeug drumherum und kannst dich auf die Algorithmen konzentrieren. Und es vermeidet jede Menge Probleme, die eventuell dein Ergebnis verfälschen. Wenn ich mich recht entsinne, kannst du die ganzen unterschiedlichen Parameter wie zu testende Array-Längen direkt beim Benchmark-Aufruf übergeben (z.B. via Skript) und ihm z.B. so Sachen sagen wie "teste mal für dieses Intervall von Array-Längen mit dieser Schrittweite" oder "erhöhe die Array-Länge exponentiell". Du kannst dir die Ergebnisse dann auch nach JSON oder CSV exportieren lassen und die Daten dann nutzen, um damit Diagramme zeichnen zu lassen (z.B. mit Excel oder anderen Tools). Da erkennt man dann oft ein bisschen mehr, z.B. die unterschiedlichen Stärken der verschiedenen Algorithmen abhängig von der Array-Größe. Da kann man dann auch gut ablesen, wann sich der eine Algorithmus, und wann der andere eher lohnt. Und das beste: Es zeigt auch die Test-Funktionsnamen in der Übersicht. Wenn die ordentlich benannt sind, können wir auch alle mehr mit den Zahlen anfangen 😛

    1
  • L

    Naja, Algorithmen/Funktionen gleicher Komplexitätsklasse laufen unterschiedlich lang. 😉 Ich finde, das ist schon etwas bemerkenswerter.

    Was die Ausgaben betrifft... so könnte noch ein sprechender Name dabei stehen, ja... aber das sind doch eigentlich, mit Verlaub gesagt, Peanuts. 😉

    Die Google Libs sind bestimmt auch prima... aber ich mache nur ungern etwas nicht selbst... insofern der Aufwand vertretbar wäre.

    0
  • L

    😊

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

volatile size_t initial_seed = 123;

size_t total_hash = 23;

// A structure for the future rating system.
typedef struct score
{
    size_t index;
    size_t index_2;
    double seconds;
    double total_seconds;
    size_t total_points;
    char *name;
    void (*func)(size_t, size_t *);
} SCORE;

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

// Comparison function for score seconds
int compare_score_seconds(const void *a, const void *b)
{
    double a_dbl = ((SCORE *)a)->seconds;
    double b_dbl = ((SCORE *)b)->seconds;
    return a_dbl < b_dbl ? -1 : a_dbl > b_dbl ? +1
                                              : 0;
}

// Comparison function for score total points
int compare_score_total_points(const void *a, const void *b)
{
    int a_int = ((SCORE *)a)->total_points;
    int b_int = ((SCORE *)b)->total_points;
    return b_int - a_int;
}

// 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"
        "  subq  $1, -8(%%rbp)        \n"
        "  movq  $0, -16(%%rbp)       \n"
        "1:                           \n"
        "  addq  $1, -16(%%rbp)       \n"
        "  movq  -16(%%rbp), %%rax    \n"
        "  cmpq  -56(%%rbp), %%rax    \n"
        "  jnb  3f                    \n"
        "  addq  $1, -8(%%rbp)        \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  1b                    \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   1b                    \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"
        "  jnb  1b                    \n"
        "  jmp  2b                    \n"
        "3:                           \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;
}

size_t scores_len = 5;
SCORE scores[] = {
    {0, 0, 0, 0, 0, "q-sort    ", sort_a_quick},
    {1, 1, 0, 0, 0, "bubble    ", sort_b_bubble},
    {2, 2, 0, 0, 0, "select    ", sort_c_selection},
    {3, 3, 0, 0, 0, "insert    ", sort_d_insertion},
    {4, 4, 0, 0, 0, "insert_asm", sort_e_insertion_optimized},
};
size_t get_sort_winner(size_t n, size_t m)
{
    // Prepare the array for testing
    size_t arr[m][n];
    for (size_t i = 0; i < scores_len; i++)
    {
        scores[i].seconds = profile_sort_func(scores[i].func, n, m, arr);
        scores[i].total_seconds += scores[i].seconds;
    }

    // Copy the results so that you can sort them
    SCORE scores_cpy[scores_len];
    for (size_t i = 0; i < scores_len; i++)
    {
        scores_cpy[i] = scores[i];
    }

    // Sort by current duration
    qsort(scores_cpy, scores_len, sizeof(SCORE), compare_score_seconds);
    double factor = 100 / scores_cpy[scores_len - 1].seconds;
    size_t winner = scores_cpy[0].index;
    for (size_t i = 0; i < scores_len; i++)
    {
        scores[scores_cpy[i].index].index_2 = i;
    }
    for (size_t i = 0; i < scores_len; i++)
    {
        scores[i].total_points += scores_len - scores[i].index_2;
    }

    // Sort by total points
    qsort(scores_cpy, scores_len, sizeof(SCORE), compare_score_total_points);
    for (size_t i = 0; i < scores_len; i++)
    {
        scores[scores_cpy[i].index].index_2 = i;
    }
    for (size_t i = 0; i < scores_len; i++)
    {
        printf("%s: (%zu %zu.) %fs %f%% %fts %zu total_points\n", scores[i].name, scores[i].index, scores[i].index_2 + 1, scores[i].seconds, scores[i].seconds * factor, scores[i].total_seconds, scores[i].total_points);
    }

    return winner;
}

// Compile with "gcc -Wall -O0 main.c -o main" or with "gcc -Wall -O3 main.c -o main"
int main(int argc, char const *argv[])
{
    size_t n = 10;
    size_t m = 10000;
    // Play until the current winner is equal to qsort
    while (get_sort_winner(n++, m))
        ;
    printf("n_max=%zu\n", n - 1);
}
    0
  • L

    Könnt ihr mir vielleicht noch beatworten, woher man weiß, welche Register in welchen Prozessorcache geladen werden? Also L1, L2 usw.

    0
    F
     1 Antwort
  • F

    @Lennox sagte in Funktion optimieren:

    Könnt ihr mir vielleicht noch beatworten, woher man weiß, welche Register in welchen Prozessorcache geladen werden? Also L1, L2 usw.

    Ich verstehe nicht ganz was du damit meinst. Wenn du in deinem Assembler-Code auf Registern arbeitest, dann sind das auch Register. Da ist kein Cache involviert. Der Cache greift nur bei RAM-Zugriffen, also z.B. sowas hier: movq -16(%%rbp), %%rax (Zeile 202)...wenn mich meine Kenntisse der furchbaren AT&T-Syntax nicht täuschen. Hier wird der Speicher an Adresse RBP - 16 in das Register RAX geladen. Ob die Daten aus dem L1, L2, L3 kommen oder ob der RAM direkt involviert ist, hängt davon ab, was vorher passiert ist. Wenn das der erste Zugriff auf den Bereich um diese Adresse ist, dann kommen die Daten sehr wahrscheinlich aus dem RAM (langsam), werden aber während dieses Zugriffs auch über die Caches verteilt. Soweit ich weiss wird bei solchen RAM-Zugriffen immer eine gesamte Cache Line geladen. Das ist CPU-abhängig und ist vielleicht so in der Größenordnung von 64 Bytes. Direkt folgende Zugriffe auf benachbarte Adressen, z.B. RBP - 8 dürften danach aus dem L1 Cache bedient werden. Deine folgende Lese-Operation cmpq -56(%%rbp), %%rax (Zeile 203) könnte daher also durchaus meistens as dem L1 kommen da die involvierten Adressen vermutlich in eine Cache Line passen.

    Ob man wirklich konkret herausfinden kann, wie wo die Daten herkommen, kann ich nicht sagen. Das handhabt jede CPU unterschiedlich nach ihren Caching-Strategien. Dazu sollte es aber Dokumentation geben. Als Faustregel kann man allerdings sagen, dass im Allgemeinen möglichst lineare Speicherzugriffe cache-freundlicher und effizienter sind. Wildes Lesen oder Schreiben weit voneinander entfernter Adressen ist eher schädlich.

    1
    L
     1 Antwort
  • L

    @Finnegan
    Danke. Na, dann scheine "ich" es ja bisher richtig gemacht zu haben, insofern sich der Prozessor/CPU beeinflussen lässt...

        "  movq  %%rdi, -56(%%rbp)    \n"
    "  movq  %%rsi, -64(%%rbp)    \n"
    "  movq  $0, -8(%%rbp)        \n"
    "  subq  $1, -8(%%rbp)        \n"
    "  movq  $0, -16(%%rbp)       \n"

    Am Anfang werden alle Variablen nach RBP geschoben (8 bis 64). Von RBP-8 wird noch einmal 1 abgezogen, da

        "1:                           \n"
    "  addq  $1, -16(%%rbp)       \n"
    "  movq  -16(%%rbp), %%rax    \n"
    "  cmpq  -56(%%rbp), %%rax    \n"
    "  jnb  3f                    \n"

    danach sofort der erste Inkrementierungsschritt erfolgt (vor dem ersten CMP).

    Im weiteren Verlauf, also innerhalb der zwei geschachtelten Schleifen... wird dann nur noch RBP und RAX (und die Konstante 1) gelesen und geschrieben. Das könnte komplett vom Prozessor "weggecachet" werden, also in L1 oder L2 gespeichert werden.

    Zu 100 % sicher bin ich mir da aber nicht... aber das müsste man eben in der Entwicklerdokumentation der CPU nachschauen, so es allgemein eine solche gibt.

    Edit: Aber noch einmal zur Erinnerung, wir sprechen nur über die Indexvariablen... Ob die Arraywerte auch, also das, worauf RDB-8 und 16(?) zeigen, gecached werden, weiß ich nicht.

    0
    L
    S
    *
     3 Antworten
  • L

    @Lennox sagte in Funktion optimieren:

    also das, worauf RDB-8 und 16(?) zeigen,

    RBP-64 meinte ich.

    0
  • S

    @Lennox Warum soll der Prozessor da was "weg cachen"? Register sind Teil der CPU, wenn das einmal im Register steht, steht das da.
    Du hast da Zugriffe auf den Stack; der Stack liegt höchstwahrscheinlich eh im Cache, da auf dem Regelmäßig gearbeitet wird, wobei ich mich mit Chaching Strategien nur sehr oberflächlich beschäftigt habe. Aber das bietet dir hier wenig/kein Optimierungspotenzial

    0
  • *

    @Lennox sagte in Funktion optimieren:

    Edit: Aber noch einmal zur Erinnerung, wir sprechen nur über die Indexvariablen... Ob die Arraywerte auch, also das, worauf RDB-8 und 16(?) zeigen, gecached werden, weiß ich nicht.

    Eine moderne CPU cached alles was technisch möglich ist. Daher sollte man zuerst Algorithmen auf Cache Hits optimieren, und erst danach an Assembler denken. Also frag das System wie lang eine Cache Line ist, und nutze diese Information im Algorithmus. Solange Du nur normale Register nutzt bringt Dir Assembler wahrscheinlich nichts, da der Compiler bessere Arbeit abliefern wird. Nur die Ausnutzung von SIMD ist aktuell noch schlechter, so dass sich Intrinsics für SIMD Code lohnt. Aber ich würde mir nicht die Mühe machen alles komplett in Assembler zu schreiben.

    Es gibt Profiling Tools mit denen Du sehen kannst wie viele Cache Misses das Programm verursacht hat.

    Nachtrag: Das einzige was wirklich CPU spezifisch ist, sind die Branch Predictor. D.h. wie verarbeitet die CPU im Voraus Code, der am wahrscheinlichsten ausgeführt werden wird. Daher lohnt es sich auch Loop Unrolling zu machen -> keine Sprünge, keine Probleme mit der Vorhersage.

    0
Anmelden zum Antworten