Von der Compiler Optimierung O3 habe ich mir keine weiteren Geschwindigkeitsgewinn erhofft, aber dass das Programm doppelt so langsam! wurde, da stand mir dann doch der Mund offen ;)
\nDas ist btw. auch das erste mal in meinem Programmiererleben, dass O3 die Laufzeit wirklich deutlich verschlechtert. Bisher hatte ich nur davon geh\u00f6rt. Ein schneller Blick in den Profiler zeigt auch warum. Gab es bei O2 und der innersten Schleife ein paar 100k Branch Mispredicts, waren es bei O3 auf einmal ein paar Millionen! Die Stelle im Code war auch im ersten Teil schon etwas verwirrend. Anscheinend gibt es eine Code Optimierung, welche die Verzweigung in der min() Funktion entfernt, ganz ohne Bithacks.
\nNun war es schon sp\u00e4t am Abend, aber die Sache musste unbedingt untersucht werden! Also habe ich dem vom Compiler erzeugten Assembler Code studiert und konnte die Sache auf ein Minimalbeispiel runter brechen.<\/p>\n
Betrachtet werden muss nur die innerste Schleife, da nur hier die min() Funktion vorkommt.<\/p>\n
\r\n#include <string>\r\n#include <vector>\r\n\r\nvoid func(size_t N) {\r\n std::vector<int> v0(N+1), v1(N+1);\r\n\r\n for(size_t i=0; i < N; ++i) { \r\n v1[i+1] = std::min(v0[i], v0[i+1]);\r\n }\r\n}\r\n<\/pre>\nEs wird paarweise das Minimum gesucht. Wird der Eingangs Array mit Zufallszahlen gef\u00fcllt, so muss die spekulative Ausf\u00fchrung der min() Funktion, also Branch Mispredict 50% betragen. Der Compiler erkennt dies irgendwie, und produziert folgenden Assembler Code ohne spekulative min() Funktion.<\/p>\n
\r\n mov ecx, DWORD PTR [rbx] ecx = v0[0]\r\n xor edx, edx i = 0\r\n.L10: for()\r\n add rdx, 1 ++i\r\n mov esi, DWORD PTR [rbx+rdx*4] esi = v0[i+1]\r\n cmp esi, ecx v0[i+1] <= ecx ?\r\n cmovle ecx, esi Wenn true: ecx = esi Hier passiert die Magie.\r\n cmp rdx, rbp i < N\r\n mov DWORD PTR [rdi+rdx*4], ecx v1[i+1] = ecx\r\n mov ecx, esi ecx = v0[i+1]\r\n jb .L10\r\n<\/pre>\nDer Code ist nicht weiter schwer. Ich habe eine grobe \u00dcbersetzung in die rechte Spalte geschrieben. In der ersten Zeile wird das erste Element von v0 in das Register ecx kopiert. Und in der zweiten Zeile das Register edx, also die Laufvariable i, auf 0 gesetzt. Danach beginnt in Zeile 3 der Schleifenk\u00f6rper.
\nVariable i wird um eins erh\u00f6ht und Zeile f\u00fcnf erfolgt der lesende Zugriff auf v0[i+1] und der Wert wird in das Register esi geladen.
\nIn den Register esi und ecx stehen jetzt die beiden Werte die verglichen werden sollen. Dabei steht in ecx immer der Wert der Vorherigen Schleifeniteration. Damit wird nur ein RAM Zugiff pro Iteration ben\u00f6tigt.
\nVerglichen werden die Werte in Zeile 6 und das Ergebnis des Vergleichs wird in Zeile 7 ausgewertet. Nur wenn der neue Wert an Stelle i+1 kleiner oder gleich als der alte ist, wird mit dem neuen Wert der alte \u00fcberschrieben.
\nDas Ergebnis wird in Zeile 9 nach v1[i+1] kopiert und in Zeile 10 wird ecx f\u00fcr die n\u00e4chste Iteration vorbereitet. Zeile 8 und 11 entspricht noch dem Schleifenkopf mit dem R\u00fccksprung zum Label L10.<\/p>\n
Die Magie passiert bei der Assembler Instruktion cmovle. Hier wird ein Kopiervorgang nur dann ausgef\u00fchrt, wenn das Ergebnis des Vergleichs eine Zeile weiter oben ergeben hat, dass die Zahl kleiner ist. Es gibt also keine Verzweigung im Programmablauf und keine spekulative Ausf\u00fchrung. Daher auch kein Branch Mispredict. Der Code kann mit voller CPU Power laufen. Besser geht es nur noch mit SSE und prefetch.<\/p>\n
Dies erkl\u00e4rt also warum die min() Funktion keine Branch Mispredicts erzeugt. Aber warum l\u00e4uft der O3 Optimierte Code nicht schneller. Auch die Assembler Code hab ich untersucht und der Grund ist unter anderem tree vectorize und andere Schleifen Optimierungen die der Compiler vornimmt. Aber die Schleife ist so super einfach, dass jegliche Optimierung nur eine Verschlechterung verursacht. Auch Loop unroll, welches per default nicht mit O3 aktiviert wird, wird die Laufzeit nicht verbessern. Da der Compiler nicht wissen kann, wie oft die innerste Schleife laufen wird. Daher m\u00fcssen alle M\u00f6glichkeiten betrachtet werden und dies f\u00fchrt zu ein paar mehr Jumps im Code. Und schon f\u00fchrt die verlangsamte spekulative Code Ausf\u00fchrung wieder zu.<\/p>\n
Was haben wir gelernt? Optimierung O2 ist gut. O3 bringt in der Summe genauso viel wie sie wieder zerst\u00f6rt. Bei HPC macht es keinen Sinn immer mit O3 zu kompilieren. Vielmehr muss der Algorithmus und die Arbeitsweise der Ziel CPU bis ins Detail verstanden werden. Danach kann die passende Compiler Optimierung ausgew\u00e4hlt werden.<\/p>\n
Getestet mit GNU GCC 7.3<\/p>\n","protected":false},"excerpt":{"rendered":"
Von der Compiler Optimierung O3 habe ich mir keine weiteren Geschwindigkeitsgewinn erhofft, aber dass das Programm doppelt so langsam! wurde, da stand mir dann doch der Mund offen ;) Das ist btw. auch das erste mal in meinem Programmiererleben, dass O3 die Laufzeit wirklich deutlich verschlechtert. Bisher hatte ich nur davon geh\u00f6rt. Ein schneller Blick […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[17],"class_list":["post-3415","post","type-post","status-publish","format-standard","hentry","category-allgemein","tag-cpp"],"_links":{"self":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/3415","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3415"}],"version-history":[{"count":10,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/3415\/revisions"}],"predecessor-version":[{"id":3425,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/3415\/revisions\/3425"}],"wp:attachment":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3415"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3415"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3415"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}