Ich machte einen Blasensortierung Implementierung in C und testete seine Leistung, als ich bemerkte, dass die -O3
Flag ließ es sogar langsamer laufen als überhaupt keine Flags! In der Zwischenzeit -O2
ließ es viel schneller laufen als erwartet.
Ohne Optimierungen:
time ./sort 30000
./sort 30000 1.82s user 0.00s system 99% cpu 1.816 total
-O2
:
time ./sort 30000
./sort 30000 1.00s user 0.00s system 99% cpu 1.005 total
-O3
:
time ./sort 30000
./sort 30000 2.01s user 0.00s system 99% cpu 2.007 total
Der Code:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
int n;
void bubblesort(int *buf)
{
bool changed = true;
for (int i = n; changed == true; i--) { /* will always move at least one element to its rightful place at the end, so can shorten the search by 1 each iteration */
changed = false;
for (int x = 0; x < i-1; x++) {
if (buf[x] > buf[x+1]) {
/* swap */
int tmp = buf[x+1];
buf[x+1] = buf[x];
buf[x] = tmp;
changed = true;
}
}
}
}
int main(int argc, char *argv[])
{
if (argc != 2) {
fprintf(stderr, "Usage: %s <arraysize>\n", argv[0]);
return EXIT_FAILURE;
}
n = atoi(argv[1]);
if (n < 1) {
fprintf(stderr, "Invalid array size.\n");
return EXIT_FAILURE;
}
int *buf = malloc(sizeof(int) * n);
/* init buffer with random values */
srand(time(NULL));
for (int i = 0; i < n; i++)
buf[i] = rand() % n + 1;
bubblesort(buf);
return EXIT_SUCCESS;
}
Die generierte Assemblersprache für -O2
(aus godbolt.org):
bubblesort:
mov r9d, DWORD PTR n[rip]
xor edx, edx
xor r10d, r10d
.L2:
lea r8d, [r9-1]
cmp r8d, edx
jle .L13
.L5:
movsx rax, edx
lea rax, [rdi+rax*4]
.L4:
mov esi, DWORD PTR [rax]
mov ecx, DWORD PTR [rax+4]
add edx, 1
cmp esi, ecx
jle .L2
mov DWORD PTR [rax+4], esi
mov r10d, 1
add rax, 4
mov DWORD PTR [rax-4], ecx
cmp r8d, edx
jg .L4
mov r9d, r8d
xor edx, edx
xor r10d, r10d
lea r8d, [r9-1]
cmp r8d, edx
jg .L5
.L13:
test r10b, r10b
jne .L14
.L1:
ret
.L14:
lea eax, [r9-2]
cmp r9d, 2
jle .L1
mov r9d, r8d
xor edx, edx
mov r8d, eax
xor r10d, r10d
jmp .L5
Und das gleiche für -O3
:
bubblesort:
mov r9d, DWORD PTR n[rip]
xor edx, edx
xor r10d, r10d
.L2:
lea r8d, [r9-1]
cmp r8d, edx
jle .L13
.L5:
movsx rax, edx
lea rcx, [rdi+rax*4]
.L4:
movq xmm0, QWORD PTR [rcx]
add edx, 1
pshufd xmm2, xmm0, 0xe5
movd esi, xmm0
movd eax, xmm2
pshufd xmm1, xmm0, 225
cmp esi, eax
jle .L2
movq QWORD PTR [rcx], xmm1
mov r10d, 1
add rcx, 4
cmp r8d, edx
jg .L4
mov r9d, r8d
xor edx, edx
xor r10d, r10d
lea r8d, [r9-1]
cmp r8d, edx
jg .L5
.L13:
test r10b, r10b
jne .L14
.L1:
ret
.L14:
lea eax, [r9-2]
cmp r9d, 2
jle .L1
mov r9d, r8d
xor edx, edx
mov r8d, eax
xor r10d, r10d
jmp .L5
Es scheint, als wäre der einzige signifikante Unterschied für mich der offensichtliche Versuch, es zu verwenden SIMDdie scheint als ob es eine große Verbesserung sein sollte, aber ich kann auch nicht sagen, was um alles in der Welt damit versucht wird pshufd
Anweisungen … ist dies nur ein fehlgeschlagener SIMD-Versuch? Oder geht es bei den paar zusätzlichen Anweisungen vielleicht nur darum, meinen Anweisungs-Cache zu verdrängen?
Die Timings wurden auf einem AMD durchgeführt Ryzen 5 3600.
@Abel:
gcc -Ofast
ist nur eine Abkürzung für-O3 -ffast-math
, aber hier gibt es keine FP-Mathematik. Wenn Sie etwas versuchen wollen, versuchen Sie es-O3 -march=native
es AVX2 verwenden zu lassen, falls die Vektorisierungsstrategie von GCC bei breiteren Vektoren helfen könnte, anstatt zu schaden, was auch immer es versucht. Obwohl ich das nicht glaube; Es wird nur ein 64-Bit-Laden und -Shuffle ausgeführt, nicht einmal 128-Bit mit SSE2.– Peter Cordes
9. Oktober 2021 um 2:56 Uhr
Zumindest bei älteren Versionen von gcc,
-Os
(für Speicherplatz optimieren) produzierte manchmal den schnellsten Code aufgrund der Größe des Anweisungscache auf x86-64. Ich weiß nicht, ob das hier eine Rolle spielen würde oder ob es in aktuellen Versionen von gcc noch anwendbar ist, aber es könnte interessant sein, es auszuprobieren und zu vergleichen.– David Konrad
9. Oktober 2021 um 18:07 Uhr
@DavidConrad: -Os würde GCC dazu bringen, sich gegen die automatische Vektorisierung zu entscheiden, also wäre es ungefähr dasselbe wie
-O2
Ich würde erwarten, dass es sich nicht mit Store-Forwarding-Stalls und erhöhter Latenz in den Fuß schießt, bevor es Fehlvorhersagen für Zweige erkennen kann.– Peter Cordes
9. Oktober 2021 um 22:23 Uhr
Sie sollten den Assembler-Code einfügen, den Ihr tatsächlicher Compiler ausgibt, und nicht von godbolt.org.
– Benutzer253751
11. Oktober 2021 um 9:49 Uhr
@ user253751: nicht einverstanden; Solange der Abfragende die gleiche GCC-Version auf Godbolt ausgewählt hat wie lokal, damit die Anweisungen gleich sind, ist Godbolts nettes Filtern von Anweisungen besser. Und das Verlinken von source+asm auf Godbolt macht es besser für jeden, der sehen möchte, was andere GCC-Versionen / Optionen tun.
– Peter Cordes
11. Oktober 2021 um 20:41 Uhr