Geschwindigkeitsfrage
-
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
.
-
minime schrieb:
Ein Plus von ca. 8%! O3 wurde nicht mehr schneller.
Wobei ich den Code mit if häßlicher finde. Ich würde ihn beim Primzahlensieb schreiben, weil er da nicht stört und doch meßbar was bringt. Bei so einem Invalidate() dürften es so wenige Aufrufe sein im Vergleich zum Rest des Programms; sagen wir mal einmal Invalidate 1000-mal seltener (und das wäre noch enorm oft!), dann hätten wir wohl auch nur ca 8%/1000 nur noch als Gewinn, also quasi nichts.
Daß es enorm wenig bringen wird, hat der Threadersteller ja schon eingeräumt. Er wollte nur wissen, ob es überhaupt was bringt. Und da ist die richtige Antwort ein klares vielleicht. Aber:Ich gehe auch mit hustbaer d'accord, daß es bei selteten Aufrufen vielleicht sogar langsamer wird. Dann aber halt auch mit ca 8%/1000(=quasi nichts). Defensive Programmierung (in Bezug auf die Performance) wäre also derzeit, Seppjs Funktion inline void trueify(int &number) (warum nicht bool?) zu haben und gelegentlich zu benutzen. Schaden kanns ja nicht, aber falls jemand Invalidate gar oft aufruft (für eine Prograss-Bar in einer zweitinnersten Schleife, wobei die innerste Schleife kaum abzuschätzende Laufzeiten hat), bringt es was.
Und wenn die Prozessorbauer nachgerüstet haben und dieses if in die Hardware reinlöten oder die Compilerbauer die Optimierung einbauen, kann es wieder weg.
Wobei ich bei kommerzieller Software sowas eher nicht einbaue, sondern davon ausgehe, daß die nächste Compilerversion es schon richten wird. Bei MS die übernächste, auch egal. Für Auftraggeber schreibe ich defensiv (in Bezug auf die eventuellen Schlafnasen, die meinen Code mal warten dürfen).
-
volkard schrieb:
Seppjs Funktion inline void trueify(int &number) (warum nicht bool?) zu haben und gelegentlich zu benutzen.
Weil der nächste logische Schritt dann ein vector<bool> gewesen wäre und dann eine Referenz auf ein vector<bool>-Element da gestanden hätte.
-
SeppJ schrieb:
volkard schrieb:
Seppjs Funktion inline void trueify(int &number) (warum nicht bool?) zu haben und gelegentlich zu benutzen.
Weil der nächste logische Schritt dann ein vector<bool> gewesen wäre und dann eine Referenz auf ein vector<bool>-Element da gestanden hätte.
Autsch! Ja. vector<bool> wäre hier schmerzhaft.
-
Ist das Absicht, dass ihr euren bools immer den gleichen Wert gegeben habt? Wenn ich am Anfang den bools zufällige Werte zuweise, braucht bei mir die Version mit if 6x länger.
Auch wenn ich zu Beginn allen bools den gleichen Wert zuweise ist bei mir übrigens die if - Version schlechter. Ich vermute mal bei meinem Core i5 M520 ist das if einfach teurer als Speicherzugriff.Hier noch der code:
#include <iostream> #include <ctime> #include <cstdlib> #include <vector> const unsigned int array_size = 100000000; int main() { std::vector< unsigned int > a( array_size ); std::vector< unsigned int > b( array_size ); auto it_a = a.begin(); auto it_b = b.begin(); while( it_a != a.end() ) { unsigned int value = std::rand() % 2; *it_a = value; *it_b = value; //*it_a = 1; //*it_b = 1; ++it_a; ++it_b; } unsigned int t; t = std::clock(); it_a = a.begin(); while( it_a != a.end() ) { if( (*it_a) ) *it_a = false; ++it_a; } std::cout<< std::clock() - t << std::endl; t = std::clock(); it_b = b.begin(); while( it_b != b.end() ) { *it_b = false; ++it_b; } std::cout << std::clock() - t << std::endl; std::cin.get(); }
-
GorbGorb schrieb:
Ist das Absicht, dass ihr euren bools immer den gleichen Wert gegeben habt? Wenn ich am Anfang den bools zufällige Werte zuweise, braucht bei mir die Version mit if 6x länger.
Auch wenn ich zu Beginn allen bools den gleichen Wert zuweise ist bei mir übrigens die if - Version schlechter. Ich vermute mal bei meinem Core i5 M520 ist das if einfach teurer als Speicherzugriff.Ah, also ist if erst schneller, wenn die Verzweigungsvorhersage oft genug trifft. Im Anwendungsfall, wenn man oft Invalidate() aufruft, obwohl das Objakt schon invalid war. Oder Invalidate() immer nur, wenn es nicht invalid war.
Bei den Primzahlen: Die Zahlen sind eh vermutlich zusammengesetzt. Meistens werden nur zusammengesetzte Zahlen nochmal überbestätigt.
-
volkard schrieb:
GorbGorb schrieb:
Ist das Absicht, dass ihr euren bools immer den gleichen Wert gegeben habt? Wenn ich am Anfang den bools zufällige Werte zuweise, braucht bei mir die Version mit if 6x länger.
Auch wenn ich zu Beginn allen bools den gleichen Wert zuweise ist bei mir übrigens die if - Version schlechter. Ich vermute mal bei meinem Core i5 M520 ist das if einfach teurer als Speicherzugriff.Ah, also ist if erst schneller, wenn die Verzweigungsvorhersage oft genug trifft.
Nicht voreilig sein! Der Code von GorbGorb macht zwei ganz verschiedene Dinge. Wenn ich den Assembleroutput recht interpretiere wird das nämlich im zweiten Fall zu einer Art memset optimiert.
Womit auch die Frage von GorbGorb beantwortet wäre: Wir setzen das vorher auf 0, weil unser Algortihmus etwas sinnvolles tut. Bei diesen ganzen Trivialbeispielen rennt man sonst viel zu schnell in die Falle, dass der Compiler zu clever ist, wie dein Code eindrucksvoll zeigt.
-
Mit welchem compiler hast du das denn getestet (ich kann kein assembler, wollt ich irgendwann mal lernen, aber irgendwie...)?
Wenn ich am Anfang alles auf 1 oder 0 gesetzt hatte, hat die if-Version etwa 10% länger gebraucht (memset?), bei zufälligen Werten waren es ungefähr 600%.
