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

[otze]

1. mache ich, und 2. habe ich jetzt eingefügt, indem ich den iterations parameter einlese. Und da die resultate linear in dem Parameter sind, glaube ich nicht, dass der Compiler da irgendwas optimiert.

"Vergleiche nicht beides im selben Programm!"
Natürlich verstehe ich, dass man die beiden Routinen so isoliert wie möglich betrachten sollte. Wenn allerdings die Resultate die ich messe, so instabil sind - >0.7s Unterschied - macht es dann überhaupt Sinn, den Code alleine zu betrachten? Ist ein Algorithmus brauchbar, der darauf angewiesen ist, dass sich kein anderer Code auf dem Prozessor befindet?

[SeppJ]

otze schrieb:

macht es dann überhaupt Sinn, den Code alleine zu betrachten?

Da da offensichtlich was faul ist: Ja!

Und schalt auch Hyperthreading aus, falls dein Prozessor das hat, weil das die Ergebnisse verfälscht, wenn nebenher noch was läuft, selbst wenn du statt Echtzeit die CPU-Zeit misst. Außerdem betrachtest du jeweils das beste Ergebnis mehrerer Läufe.

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

Diese Aussage folgt nicht aus deinen Ergebnissen.

[volkard]

Miss immer mit -O3 -march=native. Zu leicht passiert es, daß Sprungziele auf diesem Prozessor besser 16-aligned sind, aber der Compiler das nicht weiß, und die eine Meßschleife 16-aligned und die andere nur 8-aligned macht und dann haben wir den Salat.

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

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.

Bei Kurzmessungen soll die Schleife 1000 Messungen machen und die kleinste Messung nehmen, aber immer, wenn eine kleiner gefunden wurde, die Schleifenzahl zurücksetzten. Das ist ein guter Kompromiß zwischen Meßgeschwindigkeit und Genauigkeit. Damit kommst Du auf 5 stabile Stellen, falls eine Einzelmessung kurz genug ist, um nicht vom sheduler unterbrochen zu werden. Ansonsten aber auch recht genau.

[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?