Geschwindigkeitsfrage
-
Hi, soweit ich weis ist das Lesen im Ram ja schneller als das Schreiben. Macht es also Sinn z.B. bei einer Boolschen Variable vorher zu überprüfen ob sie nicht eh schon den Wert hat den man ihr zuweisen möchte? Mir ist klar dass der Geschwindigkeitsvorteil in diesem Fall wenn überhaupt nur minimal ist.
Z.B. so
void Invalidate() { if (isValid) { isValid = false; } }
-
Ja.
-
Ein Funktionsaufruf, ein Test = schnell ? Na ja ...
-
Stichwort: "Branching"
Stichwort: "Compileroptimierungen"
-
Nein.
-
knivil schrieb:
Nein.
Ach kommt, jetzt wirds's kindisch. Wie haben oft genug bei diversen Implementierungen des Siebes des Eratosthenes hier im Forum gesehen, daß es ein paar Prozent Geschwindigkeitsbonus ergibt.
-
volkard schrieb:
knivil schrieb:
Nein.
Ach kommt, jetzt wirds's kindisch. Wie haben oft genug bei diversen Implementierungen des Siebes des Eratosthenes hier im Forum gesehen, daß es ein paar Prozent Geschwindigkeitsbonus ergibt.
Mit anderen Worten: die korrekte Antwort lautet: möglicherweise.
-
Ich mochte es nicht glauben, konnte mich auch nicht an die erwähnten Threads in denen das gezeigt wurde erinnern:
int main() { const size_t N = 1 << 29; vector<int> numbers(N); cout << "Starting main algorithm\n"; clock_t start = clock(); for (size_t i = 2; i < N/2; ++i) if (!numbers[i]) for (size_t j = i+i; j < N; j += i) trueify(numbers[j]); clock_t end = clock(); double cpu_time_used = (static_cast<double>(end - start)) / CLOCKS_PER_SEC; cout << "Finished. CPU-Time: " << cpu_time_used << '\n'; // Anti-Optimierung size_t sum = 0; for (size_t i = 2; i < N; ++i) if (!numbers[i]) sum += i; cout << sum << '\n'; }Einmal mit
inline void trueify(int &number) { if (!number) number = 1; }und einmal mit
inline void trueify(int &number) { number = 1; }Intel-Compiler, O3, SSE4.2, laufen gelassen auf i7 mit virtuellen Kernen deaktiviert, je 6 Läufe. Bestzeit ohne Prüfung: 18.57 s. Bestzeit mit Prüfung 18.02 s. Kein einziger Lauf mit Prüfung war langsamer als 18.4 s. Also für 3 % Geschwindigkeitsbonus schreib ich gerne mal ein paar Zeilen mehr Code.
-
Ist ja interessant. Kann der Compiler Assembler-Output ? Dann könnte man mal nachsehen woher das kommt.
-
Das ist strange. man schreibt doch eigentlich nicht in den RAM, sondern in den Cache, oder? Oder muss der Cache sofort die Aenderungen in den Ram schreiben, damit es nicht zu inkonsistenzen kommt?
-
Scheppertreiber schrieb:
Ist ja interessant. Kann der Compiler Assembler-Output ? Dann könnte man mal nachsehen woher das kommt.
Klar, aber was erwartest du? Das liegt an der Technik, nicht am Programmcode:
Mit Prüfung (die eher technischen Kommentare des COmpilers habe ich der Übersicht halber weg gemacht):call clock #20.19 movq %rax, %rbx #20.19 movq 48(%rsp), %r8 #24.10 movq %r12, %r9 #23.3 cmpl $0, 8(%r8,%r9,4) #24.17 jne ..B1.22 # Prob 50% #24.17 lea 4(%r9,%r9), %rdi #25.25 lea (%r9,%r9), %rax #25.7 cmpq $536870912, %rdi #25.32 jae ..B1.22 # Prob 10% #25.32 movq %r12, %rsi #25.7 negq %rax #25.32 lea 536870909(%r9,%rax), %rax #25.32 lea 2(%r9), %rcx # cqto # idivq %rcx # cmpl $0, (%r8,%rdi,4) #26.9 jne ..B1.21 # Prob 50% #26.9 movl $1, (%r8,%rdi,4) #26.9 lea 2(%r9,%rdi), %rdi #25.35 incq %rsi #25.7 cmpq %rax, %rsi #25.7 jl ..B1.19 # Prob 82% #25.7 incq %r9 #23.3 cmpq $268435454, %r9 #23.3 jb ..B1.16 # Prob 99% #23.3 call clock #28.17Ohne Prüfung:
call clock #19.19 movq %rax, %rbx #19.19 movq 48(%rsp), %r8 #23.10 movq %r12, %r9 #22.3 cmpl $0, 8(%r8,%r9,4) #23.17 jne ..B1.20 # Prob 50% #23.17 lea 4(%r9,%r9), %rdi #24.25 lea (%r9,%r9), %rax #24.7 cmpq $536870912, %rdi #24.32 jae ..B1.20 # Prob 10% #24.32 movq %r12, %rsi #24.7 negq %rax #24.32 lea 536870909(%r9,%rax), %rax #24.32 lea 2(%r9), %rcx # cqto # idivq %rcx # movl $1, (%r8,%rdi,4) #25.9 lea 2(%r9,%rdi), %rdi #24.35 incq %rsi #24.7 cmpq %rax, %rsi #24.7 jl ..B1.19 # Prob 82% #24.7 incq %r9 #22.3 cmpq $268435454, %r9 #22.3 jb ..B1.16 # Prob 99% #22.3 call clock #27.17Kurz gesagt: Zeile 17 und 18 sind dazu gekommen. Manchmal ist mehr eben weniger
.edit: Wenn ihr von den Zeilennummerkommentaren verwirrt seid: Die sind vom oberem zum unterem um 1 verschoben, weil die Zeile mit der Prüfung fehlt.
-
volkard schrieb:
knivil schrieb:
Nein.
Ach kommt, jetzt wirds's kindisch. Wie haben oft genug bei diversen Implementierungen des Siebes des Eratosthenes hier im Forum gesehen, daß es ein paar Prozent Geschwindigkeitsbonus ergibt.
Ich kann mich an das nicht erinnern. Es ist auch etwas seltsam, dass 'aus dem Speicher/Cache holen, pruefen (mit jump, 50%) und Wert setzen' schneller sein soll als 'Wert setzen'.
-
knivil schrieb:
Ich kann mich an das nicht erinnern. Es ist auch etwas seltsam, dass 'aus dem Speicher/Cache holen, pruefen (mit jump, 50%) und Wert setzen' schneller sein soll als 'Wert setzen'.
Aber zumindest jetzt hast du einen Präzedenzfall. Der GCC liefert übrigens ein vergleichbares Ergebnis, was aber auch kein Wunder ist, da das vor allem an der Maschine selbst liegen sollte. Wenn jemand etwas moderneres oder weniger moderneres als den (für einen i7) schon etwas angestaubten i7 920 an dem ich gerade sitze hat: Immer her damit.
-
Hier werden riesen Mengen Speicher getestet/geschrieben, klar kann das dann was ausmachen.
Wenn er eine Cache-Line nur "shared" braucht, dann ist das billiger, als wenn er sie "exclusive" braucht.Im Beispiel des OP ist "isValid" dagegen eine einfache einzelne Variable, statt eine von Millionen.
D.h. es wird - meine Einschätzung - nix bringen, sondern im Gegenteil sogar schaden.
-
Das hat mich so gewundert, dass ich es mal getestet habe:
struct A { bool i; void trueify() { if (!i) i = true; } void foo() { unsigned j; std::cin >> j; // 50000 ist ein guter Wert j *= j; auto t = std::clock(); while (j--) { i = j % 2; trueify(); } double elapsed = (std::clock() - t) / static_cast<double>(CLOCKS_PER_SEC); std::cout << i << " Time: " << elapsed; } };Bei mir ist die Variante ohne if 3-4 mal schneller. Was mache ich falsch? (MSVC 10)
Mit if:
while (j--) 003816A6 mov eax,dword ptr [esp+38h] 003816AA test eax,eax 003816AC je A::foo+41h (3816C1h) 003816AE mov edi,edi 003816B0 dec eax { i = j % 2; 003816B1 mov cl,al 003816B3 and cl,1 003816B6 mov byte ptr [esi],cl trueify(); 003816B8 jne A::foo+3Dh (3816BDh) 003816BA mov byte ptr [esi],1 while (j--) 003816BD test eax,eax 003816BF jne A::foo+30h (3816B0h) 003816C1 dec eax 003816C2 mov dword ptr [esp+38h],eax }Ohne if:
while (j--) 001B16A6 mov eax,dword ptr [esp+38h] 001B16AA test eax,eax 001B16AC je A::foo+37h (1B16B7h) 001B16AE mov cl,byte ptr [esi] 001B16B0 dec eax { i = j % 2; trueify(); 001B16B1 mov cl,1 001B16B3 jne A::foo+30h (1B16B0h) 001B16B5 mov byte ptr [esi],cl while (j--) 001B16B7 dec eax 001B16B8 mov dword ptr [esp+38h],eax }
-
Irgendwie kann's mit der Optimierfähigkeit (oder eher den Einstellungen die du gewählt hast?) deines Compilers nicht weit her sein, GCC kann das vollständig wegoptimieren:
call clock movl $-1, 8(%rsp) movq %rax, %rbp call clock
-
SeppJ schrieb:
Irgendwie kann's mit der Optimierfähigkeit
Na ja, ich habe halt die Ausgabe genommen, die am einfachsten war - und es hat gleich geklappt. Ich habe jedenfalls alle Optimierungen an und alle auf Geschwindigkeit gestellt.
Sollte für die eigentliche Zeitmessung ja auch egal sein, nur doof dass das jetzt nur Leute mit dem hier schlechteren MSVC testen können.
-
cooky451 schrieb:
SeppJ schrieb:
Irgendwie kann's mit der Optimierfähigkeit
Na ja, ich habe halt die Ausgabe genommen, die am einfachsten war - und es hat gleich geklappt. Ich habe jedenfalls alle Optimierungen an und alle auf Geschwindigkeit gestellt.
Sollte für die eigentliche Zeitmessung ja auch egal sein, nur doof dass das jetzt nur Leute mit dem hier schlechteren MSVC testen können.Es bleibt jedenfalls festzustellen, dass der Unterschied zwischen den beiden Assemblerausgaben mehr ist als nur das
if(!i). Und das wird das Ergebnis kaputt machen. Wir müssen also feststellen: Das Ergebnis passt erst, wenn der Compiler es nicht wieder kaputt macht. Irgendwie scheint dem MSVC das if die Optimierung kaputt zu machen. Beim GCC übrigens auch, die totale Wegoptimierung schafft er erst beim Fall ohne if.edit: Ein bisschen viel "kaputt". Das kommt davon, wenn man einzelne Sätze mit ein paar Minuten Pause dazwischen schreibt. Aber ich gehe jetzt nicht nochmal mit dem Thesaurus drüber, mein ehemaliger Deutschlehrer liest hier bestimmt nicht mit :p .
-
SeppJ schrieb:
Intel-Compiler, O3, SSE4.2, laufen gelassen auf i7 mit virtuellen Kernen deaktiviert, je 6 Läufe. Bestzeit ohne Prüfung: 18.57 s. Bestzeit mit Prüfung 18.02 s.
GCC-4.6.2, -O2, march=corei7-avx, i7 mit HT (wollte jetzt nicht extra neu booten). Durchschnitt ohne Prüfung: 16,46, mit Prüfung: 15,25. Ein Plus von ca. 8%! O3 wurde nicht mehr schneller.
-
minime schrieb:
i7 mit HT (wollte jetzt nicht extra neu booten)
Du kannst Kerne im Betrieb ausschalten (Bei GCC nehm ich einfach mal an, dass du Linux benutzt). Dazu musst du in die
/sys/devices/system/cpu/cpuX/onlineentweder 0 oder 1 schreiben. Beim i7 kannst du so die Kerne 4, 5, 6, und 7 ausschalten und hast (zumindest effektiv) kein HT mehr
.
Ein kurzes Skript zum Ausschalten:#!/bin/bash echo 0 | sudo tee /sys/devices/system/cpu/cpu7/online echo 0 | sudo tee /sys/devices/system/cpu/cpu6/online echo 0 | sudo tee /sys/devices/system/cpu/cpu5/online echo 0 | sudo tee /sys/devices/system/cpu/cpu4/onlineUnd wieder an:
#!/bin/bash echo 1 | sudo tee /sys/devices/system/cpu/cpu7/online echo 1 | sudo tee /sys/devices/system/cpu/cpu6/online echo 1 | sudo tee /sys/devices/system/cpu/cpu5/online echo 1 | sudo tee /sys/devices/system/cpu/cpu4/onlineDu brauchst auch keine Angst haben, dass du dadurch irgendwelche Programme abschuießt, so doof ist der Scheduler nicht
.
