Benchmarking von High Performance code. wie macht man es richtig?

[abc.w]

Zusätzlich zu -O3 würde ich noch -g0, -fomit-frame-pointer und -ffast-math nehmen.
Übrigens, man könnte den Code als "Stand alone" bauen und z.B. mit Grub booten. Ich habe das mal gemacht, bei Interesse kann ich das Makefile zeigen und den passenden Eintrag für die menu.lst. Quellcode zeige ich nicht (schäme mich für die Frickelei)

[knivil]

Zwei Sachen im selben Programm zu messen ist gar kein Problem.

Kommt drauf an. Wenn gleiche Testdaten verwendet werden, dann hat der erste Kandidat vielleicht mehr Cachemisses als der zweite.

nimm von den Durchläufen nur den schnellsten lauf

Kommt drauf an. Wenn die Laufzeit abhaengig von den Daten ist, so ist das nicht gut. Quicksort wuerde ich so nicht messen.

Ist ein Algorithmus brauchbar, der darauf angewiesen ist, dass sich kein anderer Code auf dem Prozessor befindet?

Geh mal weg von deinem PC und schaue mal Richtung Mikrocontroller.

[volkard]

knivil schrieb:

Zwei Sachen im selben Programm zu messen ist gar kein Problem.

Kommt drauf an. Wenn gleiche Testdaten verwendet werden, dann hat der erste Kandidat vielleicht mehr Cachemisses als der zweite.

Fliegt raus, wemm man viele Messungen macht.

nimm von den Durchläufen nur den schnellsten lauf

Kommt drauf an. Wenn die Laufzeit abhaengig von den Daten ist, so ist das nicht gut. Quicksort wuerde ich so nicht messen.
[/quote]
Würdest Du Quicksort lieber ausmessen, indem Du die Summe von 10 zufälligen Läufen mißt? Dann kann man ja den random-seed festmachen das ja als einen großen Lauf nehmen und von den großen Läufen den kleinsten.

[knivil]

Ich wollte doch nur "Kommt drauf an" begruenden.

Intel E8400

Schon mal ueber SSE nachgedacht. Wieso nimmst du nicht gleich die Bibliotheken von Intel. Oder wie sieht es mit OpenCl bzw. deiner Grafikkarte aus?

Ich kenne mich nicht mit BLAS aus, aber

sum+=kernel(matA(0,j),blockStorage(columnC,j));

ist nicht Zeilenvektor mal Matrix. Wahrscheinlich beabsichtigt. Hier stimmt wahrscheinlich das Alignment/Speicherart (row_major). Fuer das Blas-Built-In ist das Alignment/Speicherart wahrscheinlich unguenstig, sofern trans nicht die gesamte Matrix umkopiert. Darueber hinaus ist deine Namensgebung irrefuehrend, der erste Index ist die Zeile, der zweite die Spalte.

Darueber hinaus: Warum sollten zwei geschachtelte for-Schleifen mit komischer Indexierung um ca. 25% besser sein, als eine Algebra-Bibliothek?

[rapso]

als erstes, bevor du irgendwas misst, solltest du bei so einfachen dingen das theoretisch moegliche ausrechnen. dann weisst du zumindestens, wenn du schneller als peak bist, machst du was falsch und wenn du <10% vom peak bist, ist die chance auch recht gross dass du etwas falsch machst.

z.b.
-anzahl der float operationen vs arithmetische leistung deiner fpu
-code segment groesse (zumindestens der kritischen schleife/funktion) vs icache size
-datenmenge und naive datentransfermenge (read+write) vs ram bzw cache bandbreite.

[Malissze]

volkard schrieb:

Miss immer so, daß die zufällig bremsenden Auswirkungen feindlicher Threads und der Hardware ausgeschlossen werden, das heißt, miss mindestens eine Sekunde lang, miss mindestens 100 Durchläufe und nimm von den Durchläufen nur den schnellsten lauf.

Was bringt das eigentlich nur den schnellsten Lauf zu nehmen? Wenn dein Chef/Kunde fragt um wieviel schneller es geworden ist und du dann sagst 3 mal so schnell und es dann bei Tests aber doch nur 2 mal so schnell ist, wird das doch keinen interessieren, dass es bei deinen 100 messungen einen gab, der 3 mal so schnell war.

[volkard]

Malissze schrieb:

volkard schrieb:

Miss immer so, daß die zufällig bremsenden Auswirkungen feindlicher Threads und der Hardware ausgeschlossen werden, das heißt, miss mindestens eine Sekunde lang, miss mindestens 100 Durchläufe und nimm von den Durchläufen nur den schnellsten lauf.

Was bringt das eigentlich nur den schnellsten Lauf zu nehmen? Wenn dein Chef/Kunde fragt um wieviel schneller es geworden ist und du dann sagst 3 mal so schnell und es dann bei Tests aber doch nur 2 mal so schnell ist, wird das doch keinen interessieren, dass es bei deinen 100 messungen einen gab, der 3 mal so schnell war.

Es geht von der Annahmen aus, daß die Einflüsse feindlicher Threads und der Hardware unabhängig vom eigenen Lauf sind. Das muß man natürlich durch Vorüberlegungen als sehr wahrscheinlich annehmen können, wie hier beim "High Performance code" sicherlich der Fall ist. :xmas2:

[Malissze]

Was auch immer "High Performance code" ist.

[Endomorphism]

rapso schrieb:

als erstes, bevor du irgendwas misst, solltest du bei so einfachen dingen das theoretisch moegliche ausrechnen. dann weisst du zumindestens, wenn du schneller als peak bist, machst du was falsch und wenn du <10% vom peak bist, ist die chance auch recht gross dass du etwas falsch machst.

Ziemlich weltfremd der Tipp.

[otze]

Danke schonmal für alle Antworten. Ich denke erstmal nicht, dass ich an den Compileroptionen schrauben werde. Ich möchte das Programm ja in dem Modus testen, in dem ich es später hauptsächlich anwenden will.

@volkard "Es geht von der Annahmen aus, daß die Einflüsse feindlicher Threads und der Hardware unabhängig vom eigenen Lauf sind."
Ich habe mich da etwas flapsig ausgedrückt. ich meinte damit eher die firekte Umgebung des Codes. Die Ergebnisse die ich gezeigt hatte waren Stabil über mehrere Läufe. Die Läufe unterschieden sich um maximal 0.1 Sekunden, aber die durchschnittliche Abweichung zwischen den Anordnungen war 0.7. Ich muss also davon ausgehen, dass die Reihenfolge einen erheblichen Einfluss hat. Die kann ich aber in einem echten Anwendungsfall nicht so frei festlegen.

In diesem Fall war zum Glück die Abweichung so, dass ich sagen konnte, dass mein Algorithmus schneller war. Aber was ist, wenn ich bei späteren Algorithmen kleinere Unterschiede habe und die Reihenfolge auf einmal relevant wird?

Malissze schrieb:

Was auch immer "High Performance code" ist.

die 1% des Codes in der das Programm sicherlich 50-60% der Programmzeit verbringt.

@knivil
SSE kommt später, erst einmal möchte ich testen, ob die Auto-Vektorisierung des Compilers das schafft. Ich bin da auch noch am Anfang der Optimierungsgeschichte.

Es gibt zwei Gründe für den Code. Zum einen brauchen wir in der Bibliothek einen sinnvollen Fallback für den Fall, dass es auf dem System keine schnelle BLAS gibt (zum Beispiel netlib implementation), bzw der Benutzer nicht in der Lage war, die Bibliothek zu konfigurieren. (In der Tat haben wir festgestellt, dass insbesondere Windows Benutzer mit der Konfiguration über CMake überfordert waren...).
Zum anderen bieten die BLAS nur Standardmatrixprodukte an, aber die Implementation soll zumindest noch 1-2 für uns sinnvolle Spezialfälle abdecken.

Zu deinem Codekommentar. Die Funktion basiert auf diesem Paper:
http://www.cs.utexas.edu/~flame/pubs/GotoTOMS_revision.pdf
Im Kontext des Papers bzw des kompletten Algorithmus macht die Vertauschung von Zeile und Spalte Sinn, da das Argument des Algorithmus die Transponierte der originalen Matrix ist.
Du hast aber bei deiner Analyse recht. Für uBLAS war an der Stelle die Speicheranordnung zu schlecht. Es gibt aber nichts schnelleres wie ich enttäuscht feststellen musste. Die Alternative axpy_prod war nochmal Faktor 2 langsamer. Leider scheinen die Macher dies aber nicht als Bug anzusehen?!?

[volkard]

otze schrieb:

Danke schonmal für alle Antworten. Ich denke erstmal nicht, dass ich an den Compileroptionen schrauben werde. Ich möchte das Programm ja in dem Modus testen, in dem ich es später hauptsächlich anwenden will.

@volkard "Es geht von der Annahmen aus, daß die Einflüsse feindlicher Threads und der Hardware unabhängig vom eigenen Lauf sind."
Ich habe mich da etwas flapsig ausgedrückt. ich meinte damit eher die firekte Umgebung des Codes. Die Ergebnisse die ich gezeigt hatte waren Stabil über mehrere Läufe. Die Läufe unterschieden sich um maximal 0.1 Sekunden, aber die durchschnittliche Abweichung zwischen den Anordnungen war 0.7. Ich muss also davon ausgehen, dass die Reihenfolge einen erheblichen Einfluss hat. Die kann ich aber in einem echten Anwendungsfall nicht so frei festlegen.

Die Reihenfolge hat vor allem dann einen erheblichen Einfluß, wenn der Compiler die Hardware nicht kennt. Dann kann er unter Umständen nicht zwischen Gut und Schlecht unterschieden, weil seinen Informationen nach beide Alternativen gleich sind. Dann haben aber auch zufällige Dinge beim Compilieren ebensogroßen Einfluß auf die Laufzeit, wie eben die Reihenfolge. Das wird ein spaßiges Messen, wenn ein cout<<'\n' am Anfang der main() gleich mal 5% kosten oder einbringen kann, also höre besser nicht auf mich.

[numbertheoretictransform]

Endomorphism schrieb:

rapso schrieb:

als erstes, bevor du irgendwas misst, solltest du bei so einfachen dingen das theoretisch moegliche ausrechnen. dann weisst du zumindestens, wenn du schneller als peak bist, machst du was falsch und wenn du <10% vom peak bist, ist die chance auch recht gross dass du etwas falsch machst.

Ziemlich weltfremd der Tipp.

<((((º>

[Powerpaule]

otze schrieb:

@knivil
SSE kommt später, erst einmal möchte ich testen, ob die Auto-Vektorisierung des Compilers das schafft. Ich bin da auch noch am Anfang der Optimierungsgeschichte.

Dazu möchte ich schonmal anmerken, dass du dir da nicht allzu große Hoffnungen machen darfst - SSE bringt unter Umständen nix oder macht es sogar langsamer (da du erstmal die Werte in extra Register kopieren musst, heutige Prozessoren sind aber im Rechnen an sich schon so schnell, dass sich das dann teilweise kaum noch lohnt. So haben Sinus/Cosinus-Tabellen heutzutage keinen Nutzen mehr)
Ich habe selber vor Kurzem eine Matrix-Klasse geschrieben, und da auch versucht mit SSE zu verbessern. Es hat fast überhaupt nichts gebracht. Die 64-Bit-Version ist mit SSE sogar deutlich langsamer. Oder besser gesagt, im normalen Modus (ohne SSE) ist der gleiche Code als 64-Bit-Programm ca. 60% schneller gewesen - ich vermute mal, das liegt daran dass der Compiler (Visual Studio) dann schlau genug ist die Sache so zu optimieren dass er pro Takt 2 float-Werte holen kann, statt einem. Die Multiplikationen an sich sind ja ein Klacks. Du hast natürlich Potenzen drin, da ist es vielleicht noch etwas anders. SSE bringt ja umso mehr, je komplexer die Berechnungen werden. Oder AVX ; )

Edit: Ich muss auch noch anmerken dass ich das Ganze nur auf einem relativ guten Prozessor (Core i5 2500) getestet habe, aber ich denke die Tendenz ist klar.^^

[knivil]

Wenn SSE so schlecht ist, warum wird es noch benutzt, angepriesen, vertrieben und erweitert? Wer mag kann gerne selber testen, hier was vorgefertigtes: http://www.cortstratton.org/articles/OptimizingForSSE.php oder http://fhtr.blogspot.com/2010/02/4x4-float-matrix-multiplication-using.html . In den Kommentaren steht was von Faktor 2. Darueber hinaus sollte man sich nicht auf eine Bibliothek wie uBlas beschranken, es gibt viele Fische im Meer: Eigen oder MTL beispielsweise.

[SeppJ]

knivil schrieb:

Wenn SSE so schlecht ist, warum wird es noch benutzt, angepriesen, vertrieben und erweitert?

Ist die Frage wirklich ernst gemeint?

SSE kann tatsächlich Programme (deutlich) langsamer machen, habe ich ebenfalls oft genug erlebt.

[knivil]

Und SSE kann Programme deutlich schneller machen. Diese Aussagen schliessen sich nicht aus.

[hustbaer]

Mal ne andere Frage die nur z.T. dazupasst: wie tut SSE eigentlich mit Denormals?
Gleich wie die die x87 (=software interrupt=laaaaaaangsam), oder wird da auf Denormals einfach verzichtet?

[rapso]

hustbaer schrieb:

Mal ne andere Frage die nur z.T. dazupasst: wie tut SSE eigentlich mit Denormals?
Gleich wie die die x87 (=software interrupt=laaaaaaangsam), oder wird da auf Denormals einfach verzichtet?

auf x87 kannst du zwischen normalisieren und exception waehlen, auf sse zwischen flush to zero (bzw denormals are zero) oder die hardware handled die exception, was aber nicht schneller ist als eine software exception.

[rapso]

Powerpaule schrieb:

Dazu möchte ich schonmal anmerken, dass du dir da nicht allzu große Hoffnungen machen darfst - SSE bringt unter Umständen nix oder macht es sogar langsamer (da du erstmal die Werte in extra Register kopieren musst, heutige Prozessoren sind aber im Rechnen an sich schon so schnell, dass sich das dann teilweise kaum noch lohnt.

man muss es natuerlich richtig machen, man kann so ziemlich alles falsch anwenden, was glaubst du wie langsam eine GPU ist wenn du ihr eine 4x4 matrix multiplikation gibst

Ich habe selber vor Kurzem eine Matrix-Klasse geschrieben, und da auch versucht mit SSE zu verbessern. Es hat fast überhaupt nichts gebracht. Die 64-Bit-Version ist mit SSE sogar deutlich langsamer. Oder besser gesagt, im normalen Modus (ohne SSE) ist der gleiche Code als 64-Bit-Programm ca. 60% schneller gewesen - ich vermute mal, das liegt daran dass der Compiler (Visual Studio) dann schlau genug ist die Sache so zu optimieren dass er pro Takt 2 float-Werte holen kann, statt einem. Die Multiplikationen an sich sind ja ein Klacks. Du hast natürlich Potenzen drin, da ist es vielleicht noch etwas anders. SSE bringt ja umso mehr, je komplexer die Berechnungen werden. Oder AVX ; )

ich hoffe dir ist klar, dass unter 64bit ausschliesslich SSE benutzt wird, windows unterstuetzt keine fpu (ist bei linux anders, aber du sprichst ja von visual studio).
wenn also deine SSE implementierung langsammer ist als die vom compiler generierte SSE implementierung, liegt es unmoeglich an SSE.

Edit: Ich muss auch noch anmerken dass ich das Ganze nur auf einem relativ guten Prozessor (Core i5 2500) getestet habe, aber ich denke die Tendenz ist klar.^^

gerade auf i7 prozessoren, sollte SSE bei der matrix multiplikation gut sein, da frueher shuffle und unaligned read recht teuer war, beides ist nun so schnell es geht, sprich, unaligned load auf eine aligned addresse ist so schnell wie ein aligned read und wenn du genausoviele schuffel instructions wie arithmetische instruction hast, sollten sie nicht auffallen, weil sie parallel in einer anderen pipe gleich schnell abgearbeitet werden und du somit eigentlich nicht langsammer sein solltest als mit der fpu (eben weil du mit unaligned reads und single muls+adds genau dasselbe machen kannst wie die fpu).

also sse, auf i7 ist wirklich top, sowas wie Sin/Cos ist zwar an sich langsammer, aber dafuer kann man 2/4 bzw 8mit AVX gleichzeitig berechnen und insgesammt bist du dann schneller. (und schuffle, um register als temporaere speicher zu benutzen sind auch um einiges schneller als L1 reads, was also 64float register bedeutet!)

also ich glaube du solltest deinem matrix mul nochmal eine chance geben

[Powerpaule]

rapso schrieb:

ich hoffe dir ist klar, dass unter 64bit ausschliesslich SSE benutzt wird, windows unterstuetzt keine fpu (ist bei linux anders, aber du sprichst ja von visual studio).
wenn also deine SSE implementierung langsammer ist als die vom compiler generierte SSE implementierung, liegt es unmoeglich an SSE.

Hm, nein, das war mir so nicht klar... D.h. Visual Studio optimiert es dann auch wenn möglich gleich dahingehend, dass mehrere Mutliplikationen/Additionen mit einem Mal ausgeführt werden? Wenn nicht wäre es wirklich etwas seltsam warum die SSE-Implementierung vom Compiler schneller ist...
Ich hatte es ja erst unter 32 Bit probiert, dort war SSE teilweise auch noch schneller (bei Vektor*Matrix hatte es noch einiges gebracht, ca. 25%, bei Matrix*Matrix war es dann schon fast nutzlos oder etwas langsamer) - das Gleiche unter 64Bit war dann deutlich langsamer als die Variante ohne eigenes SSE, weshalb ich davon ausging dass es dort dann keinen Sinn mehr hat (ich wollte ursprünglich dann noch AVX testen, hatte dann aber keine Lust mehr^^). Letztendlich hab ich mich dann auch nicht weiter genauer damit beschäftigt, weil ich nur mal interessehalber grob sehen wollte was man damit rausholen könnte. Ich wollte dann nur noch wissen, was daran eigentlich am langsamsten war, und das waren halt wie zu erwarten die Kopiervorgänge in die Register.
Na ja, vielleicht setze ich mich nochmal ran, je mehr Nanosekunden man rausholen kann, umso besser ; )