ComputerBase Menü
Aktuelles

C Sortierverfahren in Assembler optimieren

Hier noch eine Optimierung:

Optimierter C-Code:

C: 
#include <stdio.h>

int arr[] = {3, 5, 4, 1, 9, 7, 2, 6, 8};
int n = 9;
char str[] = "%d\n";

int iteration() {
  int i = -1, j = 0, a, b;
  while (i < n - 2) {
    i++;
    j++;
    a = arr[i];
    b = arr[j];
    if (a > b) {
      arr[i] = b;
      arr[j] = a;
      return 1;
    }
  }
  return 0;
}

void sort() {
  while (iteration())
    ;
}

void print() {
  int i = 0;
  while (i < n) {
    printf(str, arr[i]);
    i++;
  }
}

int main() {
  sort();
  print();
  return 0;
}

Optimierter Assemblercode:

Code: 
    .file    "sort.c"
    .text
    .globl    arr

    .data
    .align 32
    .type    arr, @object
    .size    arr, 36
arr:
    .long    3
    .long    5
    .long    4
    .long    1
    .long    9
    .long    7
    .long    2
    .long    6
    .long    8
    .globl    n
    .align 4
    .type    n, @object
    .size    n, 4
n:
    .long    9
    .globl    str
    .type    str, @object
    .size    str, 4
str:
    .string    "%d\n"

    .text
    .globl    iteration
    .type    iteration, @function
iteration:
    .cfi_startproc
    pushq    %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    $-1, -4(%rbp)
    movl    $0, -8(%rbp)
.L1:
    movl    n(%rip), %eax
    subl    $2, %eax
    cmpl    %eax, -4(%rbp)
    jge    .L2
    addl    $1, -4(%rbp)
    addl    $1, -8(%rbp)
    movl    -4(%rbp), %eax
    cltq
    leaq    0(,%rax,4), %rdx
    leaq    arr(%rip), %rax
    movl    (%rdx,%rax), %eax
    movl    %eax, -12(%rbp)
    movl    -8(%rbp), %eax
    cltq
    leaq    0(,%rax,4), %rdx
    leaq    arr(%rip), %rax
    movl    (%rdx,%rax), %eax
    movl    %eax, -16(%rbp)
    movl    -12(%rbp), %eax
    cmpl    -16(%rbp), %eax
    jle    .L1
    movl    -4(%rbp), %eax
    cltq
    leaq    0(,%rax,4), %rcx
    leaq    arr(%rip), %rdx
    movl    -16(%rbp), %eax
    movl    %eax, (%rcx,%rdx)
    movl    -8(%rbp), %eax
    cltq
    leaq    0(,%rax,4), %rcx
    leaq    arr(%rip), %rdx
    movl    -12(%rbp), %eax
    movl    %eax, (%rcx,%rdx)
    movl    $1, %eax
    jmp    .L3
.L2:
    movl    $0, %eax
.L3:
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
    .size    iteration, .-iteration

    .globl    sort
    .type    sort, @function
sort:
    .cfi_startproc
    pushq    %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
.L4:
    movl    $0, %eax
    call    iteration
    testl    %eax, %eax
    jne    .L4
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
    .size    sort, .-sort

    .globl    print
    .type    print, @function
print:
    .cfi_startproc
    pushq    %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    subq    $16, %rsp
    movl    $0, -4(%rbp)
.L5:
    movl    n(%rip), %eax
    cmpl    %eax, -4(%rbp)
    jge    .L6
    movl    -4(%rbp), %eax
    cltq
    leaq    0(,%rax,4), %rdx
    leaq    arr(%rip), %rax
    movl    (%rdx,%rax), %eax
    movl    %eax, %esi
    leaq    str(%rip), %rax
    movq    %rax, %rdi
    movl    $0, %eax
    call    printf@PLT
    addl    $1, -4(%rbp)
    jmp    .L5
.L6:
    leave
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
    .size    print, .-print

    .globl    main
    .type    main, @function
main:
    .cfi_startproc
    pushq    %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    $0, %eax
    call    sort
    movl    $0, %eax
    call    print
    movl    $0, %eax
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
    .size    main, .-main

    .ident    "GCC: (Debian 14.2.0-19) 14.2.0"
    .section    .note.GNU-stack,"",@progbits

Was hat sich geändert?

  • sort (in einer eigenen Funktion) steht jetzt näher an iteration,
  • zusätzliche Variable j, um i+1 zwischenzuspeichern,
  • return 1 und 0 stehen jetzt näher zusammen
 
@mae Es bleibt aber der x64 Befehlssatz? Meinem Verständnis nach wird x64 Assembly von der CPU (just in time?) in eigenen microcode übersetzt. Kann ich rein theoretisch auch diesen CPU spezifischen microcode schreiben bzw. das ist dann kein assembly mehr sondern halt microcode, right? Assembly für einzelne CPU Modelle definiert vermutlich niemand mehr heutzutage.

Bei GPUs gibt es keine einheitliche ISA, weswegen Shader auf jedem Rechner (und oft nach Treiberupdates) neu kompiliert werden müssen.
 
  • Gefällt mir
Reaktionen: kali-hi
Darf in Assembler eine "Funktion" (bzw. ein "Abschnitt") eigentlich auch zwei ret-Anweisungen haben? Dadurch ließe sich ein jmp einsparen.

Und n - 2 könnte auch noch einmal ein einer zusätzlichen Variable zwischengespeichert werden, dadurch entfiele noch ein subl $2, %eax.

Und allgemein: Vermutlich wäre es schneller, den BubbleSort nicht stabil zu implementieren (ein return entfiele) - oder den BubbleSort mal mit einem SelectionSort zu vergleichen (beide haben die gleiche asymptotische Laufzeit, aber SelectionSort wäre ggf. schneller).
Ergänzung ()

Edit: Naja... fast: https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_sorts
 
BeBur schrieb:
@mae Es bleibt aber der x64 Befehlssatz?
Zum Vergrößern anklicken....

Ja, mit Erweiterungen.

Meinem Verständnis nach wird x64 Assembly von der CPU (just in time?) in eigenen microcode übersetzt. Kann ich rein theoretisch auch diesen CPU spezifischen microcode schreiben bzw. das ist dann kein assembly mehr sondern halt microcode, right?
Zum Vergrößern anklicken....

Die Schnittstelle zwischen Software und Hardware ist der Maschinencode, der direkt dem Assemblycode entspricht. Die Prozessoren uebersetzen den Maschinencode intern in Micro-ops (uops), aber auf der Ebene kannst Du nicht programmieren (mit Ausnahmen, siehe unten). Die haeufigsten Befehle werden von Hardware-Decodern in uops uebersetzt, einige (langsame) ueber den Microcode-Store.

Die Prozessorhersteller haben als Versicherung gegen Bugs die Moeglichkeit eingebaut, nachtraeglich Befehle ueber den Microcode-Store auszufuehren. Das wird dann ueber die beruechtigten Microcode-Updates gemacht. In juengeren Prozessoren ist der Microcode kryptografisch vom Prozessorhersteller signiert und die Prozessoren akzeptieren keinen Microcode ohne Signatur.

Einige aelteren AMD-Prozessoren (irgendwelchen Phenoms, WIMRE) waren noch nicht so abgesichert, da sind findige Leute draufgekommen, wie der Microcode codiert ist und konnten dem Prozessor dann Microcode fuer ein paar Befehle vorgeben. Da haben sich manche Leute tolle Geschwindigkeitsvorteile erhofft, wenn man irgendwas per Microcode statt ueber den Befehlssatz macht, aber das Ergebnis war langsamer als wenn man das gleiche ueber den Befehlssatz macht. Ist ja auch kein Wunder, die uops sind letztlich dieselben, aber die Verwendung des Microcode-Sequencers verursacht zusaetzliche Kosten, weil die Mikroarchitektur auf die Verarbeitung von uops aus den Hardware-Decodern optimiert ist.
 
  • Gefällt mir
Reaktionen: TorenAltair, BeBur und kali-hi
@BeBur Vielleicht noch zum allgemeinen Verständnis von "Assembly == Machine code?": https://stackoverflow.com/questions/466790/assembly-code-vs-machine-code-vs-object-code

Assemblercode ist Klartext und (mehr oder weniger) menschenlesbarer Quellcode, der meist in einem direkten 1:1-Verhältnis zu Maschinenbefehlen steht. Dies wird durch die Verwendung von Mnemoniken für die eigentlichen Befehle, Register oder andere Ressourcen erreicht. Beispiele hierfür sind JMP und MULT für die Sprung- und Multiplikationsbefehle der CPU. Im Gegensatz zu Maschinencode versteht die CPU Assemblercode nicht. Sie konvertieren Assemblercode mit Hilfe eines Assemblers oder Compilers in Maschinencode, obwohl wir Compiler normalerweise in Verbindung mit höheren Programmiersprachen betrachten, die weiter von den CPU-Befehlen abstrahiert sind.


Übersetzt mit DeepL.com (kostenlose Version)
Zum Vergrößern anklicken....

Aber @mae hat es gerade besser beschrieben... Machine code ~ != Micro code 😬
 
Mir war gerade langweilig... Spaßeshalber könnte man hierbei die Zeiten für sort_a und sort_b messen und diese vergleichen...

C: 
#include <stdio.h>

size_t n = 100;

size_t my_rand(size_t seed, size_t max)
{
    size_t a = 16807;
    return (a * seed) % max;
}

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

double average(size_t a[])
{
    // The average should be around 25.
    double average = 0;
    for (size_t i = 0; i < n; i++)
    {
        average += (double)a[i] / (double)n;
    }
    return average;
}

void print(size_t a[])
{
    for (size_t i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\na: %f\n\n", average(a));
}

void sort_a(size_t arr[])
{
    for (size_t i = 0; i < n - 1;)
    {
        size_t a = arr[i];
        size_t b = arr[i + 1];
        if (a > b)
        {
            arr[i] = b;
            arr[i + 1] = a;
            i = 0;
            continue;
        }
        i++;
    }
}

void sort_b(size_t arr[])
{
    for (size_t i = 0; i < n - 1; i++)
    {
        size_t a = i;
        size_t b = arr[i];
        for (size_t j = i + 1; j < n; j++)
        {
            if (arr[j] < b)
            {
                a = j;
                b = arr[j];
            }
        }
        arr[a] = arr[i];
        arr[i] = b;
    }
}

int main(int argc, char const *argv[])
{
    size_t arr[n];

    fill(arr);
    print(arr);
    sort_a(arr);
    print(arr);

    fill(arr);
    print(arr);
    sort_b(arr);
    print(arr);

    return 0;
}

Also, was gibt -S, -O0 und -O3 aus, und dann es vergleichen mit dem optimierten Assemblercode...

PS: Ich hatte gar nicht daran gedacht, dass man für BubbleSort nur eine Schleife braucht
 
Weiß zufällig jemand, wie der gcc Inline-Assembler und der Pass von Array-Pointern funktioniert?

C: 
#include <stdio.h>

size_t n = 100;

size_t my_rand(size_t seed, size_t max)
{
    size_t a = 16807;
    return (a * seed) % max;
}

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

double average(size_t a[])
{
    // The average should be around 25.
    double average = 0;
    for (size_t i = 0; i < n; i++)
    {
        average += (double)a[i] / (double)n;
    }
    return average;
}

void print(size_t a[])
{
    for (size_t i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\na: %f\n\n", average(a));
}

void sort_a(size_t arr[])
{
    for (size_t i = 0; i < n - 1;)
    {
        size_t a = arr[i];
        size_t b = arr[i + 1];
        if (a > b)
        {
            arr[i] = b;
            arr[i + 1] = a;
            i = 0;
            continue;
        }
        i++;
    }
}

void sort_a_optimized(size_t arr[])
{
    asm volatile(
        "pushq    %%rbp;"
        "movq    %%rsp, %%rbp;"
        "movq    %%rdi, -40(%%rbp);"
        "movq    $0, -8(%%rbp);"
        "jmp    .Loop3;"
        ".Loop1:;"
        "movq    -8(%%rbp), %%rax;"
        "leaq    0(,%%rax,8), %%rdx;"
        "movq    -40(%%rbp), %%rax;"
        "addq    %%rdx, %%rax;"
        "movq    (%%rax), %%rax;"
        "movq    %%rax, -16(%%rbp);"
        "movq    -8(%%rbp), %%rax;"
        "addq    $1, %%rax;"
        "leaq    0(,%%rax,8), %%rdx;"
        "movq    -40(%%rbp), %%rax;"
        "addq    %%rdx, %%rax;"
        "movq    (%%rax), %%rax;"
        "movq    %%rax, -24(%%rbp);"
        "movq    -16(%%rbp), %%rax;"
        "cmpq    %%rax, -24(%%rbp);"
        "jnb    .Loop1;"
        "movq    -8(%%rbp), %%rax;"
        "leaq    0(,%%rax,8), %%rdx;"
        "movq    -40(%%rbp), %%rax;"
        "addq    %%rax, %%rdx;"
        "movq    -24(%%rbp), %%rax;"
        "movq    %%rax, (%%rdx);"
        "movq    -8(%%rbp), %%rax;"
        "addq    $1, %%rax;"
        "leaq    0(,%%rax,8), %%rdx;"
        "movq    -40(%%rbp), %%rax;"
        "addq    %%rax, %%rdx;"
        "movq    -16(%%rbp), %%rax;"
        "movq    %%rax, (%%rdx);"
        "movq    $0, -8(%%rbp);"
        "jmp    .Loop3;"
        ".Loop2:;"
        "addq    $1, -8(%%rbp);"
        ".Loop3:;"
        "movq    %[n], %%rax;"
        "subq    $1, %%rax;"
        "cmpq    %%rax, -8(%%rbp);"
        "jb    .Loop1;"
        : /* No outputs. */
        : [n] "r"(n)
        : /* No clobbers. */);
}

void sort_b(size_t arr[])
{
    for (size_t i = 0; i < n - 1; i++)
    {
        size_t a = i;
        size_t b = arr[i];
        for (size_t j = i + 1; j < n; j++)
        {
            if (arr[j] < b)
            {
                a = j;
                b = arr[j];
            }
        }
        arr[a] = arr[i];
        arr[i] = b;
    }
}

int main(int argc, char const *argv[])
{
    size_t arr[n];

    fill(arr);
    print(arr);
    sort_a(arr);
    print(arr);

    fill(arr);
    print(arr);
    sort_a_optimized(arr);
    print(arr);

    return 0;
}

In sort_a_optimized möchte ich inline asm einsetzen, um zu optimieren. rsp ist vermutlich die Länge und rdi ein Pointer auf das Array.

Das Problem ist, ich bekomme entweder eine Endlosschleife, einen Segmentation fault oder ich kann es gar nicht erst übersetzen.

Ich weiß nicht, wie man das Array über übergeben und ändern kann, und denke, pushq (und popq %%rbp;) wäre doch eigentlich nicht notwendig, weil durch den Funktionsaufruf von sort_a_optimized ein Stack doch schon vorbereitet wird...

Aus der offiziellen Dokumentation https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html werde ich leider auch nicht richtig schlau, und irgendwo habe ich auch gelesen, dass das Ganze ca. 30 Jahre alt ist und nicht mehr verwendet werden sollte...
 
Es hat doch noch geklappt :cheerlead:

main.c

C: 
#include <stdio.h>

size_t n = 100;

size_t my_rand(size_t seed, size_t max)
{
    size_t a = 16807;
    return (a * seed) % max;
}

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

double average(size_t a[])
{
    // The average should be around 25.
    double average = 0;
    for (size_t i = 0; i < n; i++)
    {
        average += (double)a[i] / (double)n;
    }
    return average;
}

void print(size_t a[])
{
    for (size_t i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\na: %f\n\n", average(a));
}

void sort_a(size_t arr[])
{
    for (size_t i = 0; i < n - 1;)
    {
        size_t a = arr[i];
        size_t b = arr[i + 1];
        if (a > b)
        {
            arr[i] = b;
            arr[i + 1] = a;
            i = 0;
            continue;
        }
        i++;
    }
}

void sort_a_optimized(size_t arr[])
{
    asm volatile(
        "movq    %%rdi, -40(%%rbp);\n"
        "movq    $0, -8(%%rbp);\n"
        "jmp    .Loop3;\n"
        ".Loop1:;\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, -16(%%rbp);\n"
        "movq    -8(%%rbp), %%rax;\n"
        "addq    $1, %%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"
        "cmpq    %%rax, -24(%%rbp);\n"
        "jnb    .Loop2;\n"
        "movq    -8(%%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    -8(%%rbp), %%rax;\n"
        "addq    $1, %%rax;\n"
        "leaq    0(,%%rax,8), %%rdx;\n"
        "movq    -40(%%rbp), %%rax;\n"
        "addq    %%rax, %%rdx;\n"
        "movq    -16(%%rbp), %%rax;\n"
        "movq    %%rax, (%%rdx);\n"
        "movq    $0, -8(%%rbp);\n"
        "jmp    .Loop3;\n"
        ".Loop2:;\n"
        "addq    $1, -8(%%rbp);\n"
        ".Loop3:;\n"
        "movq    %[n], %%rax;\n"
        "subq    $1, %%rax;\n"
        "cmpq    %%rax, -8(%%rbp);\n"
        "jb    .Loop1;\n"
        : /* No outputs. */
        : [n] "m"(n)
        : "memory");
}

void sort_b(size_t arr[])
{
    for (size_t i = 0; i < n - 1; i++)
    {
        size_t a = i;
        size_t b = arr[i];
        for (size_t j = i + 1; j < n; j++)
        {
            if (arr[j] < b)
            {
                a = j;
                b = arr[j];
            }
        }
        arr[a] = arr[i];
        arr[i] = b;
    }
}

int main(int argc, char const *argv[])
{
    size_t arr[n];

    fill(arr);
    print(arr);
    sort_a(arr);
    print(arr);

    fill(arr);
    print(arr);
    sort_a_optimized(arr);
    print(arr);

    return 0;
}

Mit gcc -S main.c macht der Compiler aus den zwei Funktionen dann:

main.s

Code: 
    .globl    sort_a
    .type    sort_a, @function
sort_a:
.LFB4:
    .cfi_startproc
    pushq    %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movq    %rdi, -40(%rbp)
    movq    $0, -8(%rbp)
    jmp    .L18
.L20:
    movq    -8(%rbp), %rax
    leaq    0(,%rax,8), %rdx
    movq    -40(%rbp), %rax
    addq    %rdx, %rax
    movq    (%rax), %rax
    movq    %rax, -16(%rbp)
    movq    -8(%rbp), %rax
    addq    $1, %rax
    leaq    0(,%rax,8), %rdx
    movq    -40(%rbp), %rax
    addq    %rdx, %rax
    movq    (%rax), %rax
    movq    %rax, -24(%rbp)
    movq    -16(%rbp), %rax
    cmpq    %rax, -24(%rbp)
    jnb    .L19
    movq    -8(%rbp), %rax
    leaq    0(,%rax,8), %rdx
    movq    -40(%rbp), %rax
    addq    %rax, %rdx
    movq    -24(%rbp), %rax
    movq    %rax, (%rdx)
    movq    -8(%rbp), %rax
    addq    $1, %rax
    leaq    0(,%rax,8), %rdx
    movq    -40(%rbp), %rax
    addq    %rax, %rdx
    movq    -16(%rbp), %rax
    movq    %rax, (%rdx)
    movq    $0, -8(%rbp)
    jmp    .L18
.L19:
    addq    $1, -8(%rbp)
.L18:
    movq    n(%rip), %rax
    subq    $1, %rax
    cmpq    %rax, -8(%rbp)
    jb    .L20
    nop
    nop
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE4:
    .size    sort_a, .-sort_a
    .globl    sort_a_optimized
    .type    sort_a_optimized, @function
sort_a_optimized:
.LFB5:
    .cfi_startproc
    pushq    %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movq    %rdi, -8(%rbp)
#APP
# 58 "main.c" 1
    movq    %rdi, -40(%rbp);
movq    $0, -8(%rbp);
jmp    .Loop3;
.Loop1:;
movq    -8(%rbp), %rax;
leaq    0(,%rax,8), %rdx;
movq    -40(%rbp), %rax;
addq    %rdx, %rax;
movq    (%rax), %rax;
movq    %rax, -16(%rbp);
movq    -8(%rbp), %rax;
addq    $1, %rax;
leaq    0(,%rax,8), %rdx;
movq    -40(%rbp), %rax;
addq    %rdx, %rax;
movq    (%rax), %rax;
movq    %rax, -24(%rbp);
movq    -16(%rbp), %rax;
cmpq    %rax, -24(%rbp);
jnb    .Loop2;
movq    -8(%rbp), %rax;
leaq    0(,%rax,8), %rdx;
movq    -40(%rbp), %rax;
addq    %rax, %rdx;
movq    -24(%rbp), %rax;
movq    %rax, (%rdx);
movq    -8(%rbp), %rax;
addq    $1, %rax;
leaq    0(,%rax,8), %rdx;
movq    -40(%rbp), %rax;
addq    %rax, %rdx;
movq    -16(%rbp), %rax;
movq    %rax, (%rdx);
movq    $0, -8(%rbp);
jmp    .Loop3;
.Loop2:;
addq    $1, -8(%rbp);
.Loop3:;
movq    n(%rip), %rax;
subq    $1, %rax;
cmpq    %rax, -8(%rbp);
jb    .Loop1;

# 0 "" 2
#NO_APP
    nop
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE5:
    .size    sort_a_optimized, .-sort_a_optimized

Die Ausgabe des Programms ist bei mir:

Code: 
./main
11 30 7 35 12 40 17 45 22 50 27 4 32 9 37 14 42 19 47 24 1 29 6 34 11 39 16 44 21 49 26 3 31 8 36 13 41 18 46 23 0 28 5 33 10 38 15 43 20 48 25 2 30 7 35 12 40 17 45 22 50 27 4 32 9 37 14 42 19 47 24 1 29 6 34 11 39 16 44 21 49 26 3 31 8 36 13 41 18 46 23 0 28 5 33 10 38 15 43 20
a: 24.860000

0 0 1 1 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 49 49 50 50
a: 24.860000

0 28 5 33 10 38 15 43 20 48 25 2 30 7 35 12 40 17 45 22 50 27 4 32 9 37 14 42 19 47 24 1 29 6 34 11 39 16 44 21 49 26 3 31 8 36 13 41 18 46 23 0 28 5 33 10 38 15 43 20 48 25 2 30 7 35 12 40 17 45 22 50 27 4 32 9 37 14 42 19 47 24 1 29 6 34 11 39 16 44 21 49 26 3 31 8 36 13 41 18
a: 24.810000

0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 47 47 48 48 49 49 50 50
a: 24.810000

Nun kann man hingehen und den Assemblercode für sort_a_optimized Schritt für Schritt anpassen, also optimieren...

Wer genau hinsieht, wird vielleicht feststellen, dass
movq %rdi, -8(%rbp) und movq $0, -8(%rbp);
"doppelt gemoppelt" ist, aber ich habe noch keine Idee, wie man das vermeiden kann.
 
Habe damit weitergemacht... für 2<n<30 ist mein Assemblercode (modifiziertes Insertion-Sort) schneller als C's qsort:

C: 
#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);
}
 
Jetzt müsstest Du das noch auf verschiedenen CPUs testen wie da jeweils der relative Unterschied ist.
 
  • Gefällt mir
Reaktionen: kuddlmuddl, dms und kali-hi
Du musst dich einloggen oder registrieren, um hier zu antworten.

Ähnliche Themen

kali-hi
  • Gesperrt
C Assemblerprogramm erklären?
2
Antworten
33
Aufrufe
1.642
hallo7
H
MR34L
C Assemblercode erklaeren
Antworten
3
Aufrufe
1.596
IceMatrix
I
Zurück
Oben

Willkommen auf ComputerBase!

Mit Werbung weiterlesen

Besuche ComputerBase wie gewohnt mit Werbung und Tracking. Die Zustimmung ist jederzeit widerrufbar.

Details im Privacy Center und in der Liste unserer Partner. Ein Widerruf ist möglich in der Datenschutzerklärung.

… oder ComputerBase Pro bestellen

Nutze ComputerBase ohne Werbebanner, Video-Ads und Werbetracking schon für 4 €/Monat oder 36 €/Jahr.

Mehr zu ComputerBase Pro

Bereits Pro-Nutzer? Hier anmelden.

Tracking: Wir und unsere 170 Partner verarbeiten personenbezogene Daten, indem wir mit auf Ihrem Gerät gespeicherten Informationen (z. B. eindeutige Kennungen in Cookies) ein Nutzungsprofil erstellen, um z. B. Anzeigen zu personalisieren. Verarbeitungszwecke: Genaue Standortdaten und Abfrage von Geräteeigenschaften zur Identifikation, Informationen auf einem Gerät speichern und/oder abrufen, Personalisierte Anzeigen und Inhalte, Anzeigen- und Inhaltsmessungen, Erkenntnisse über Zielgruppen und Produktentwicklungen.

Impressum Kontakt Datenschutz