Codeoptimierung

[pest]

Hallo :)

ich soll im Rahmen eines freiwilligen :redface: Vortrags, über Codeoptimierung (auf Hochsprachenebene) reden

nun ist es aber so, das ich nach 15 Jahren wohl Vieles automatisch beachte, was andere nicht wissen, oder trivial erscheint, was ich aber trotzdem erwähnen möchte

also Sachen wie Loop-Unrolling, Schleifen-Invarianten und Cache-Optimierung

hat da jmd. vielleicht ein paar gute Links zur Hand

den finde ich ganz gut
http://www.tech-text.de/jochen.ruhland/leseprobe/codeopt.html

Wäre für Hilfe und Tipps, sehr sehr dankbar, weil ich denke das das ein Fehler war zuzusagen :freak:

[Held0r]

Die von dir angesprochenen Dinge werden definitiv von den meisten Compiler um einiges intelligenter eingesetzt, als es 99.9% der Programmierer auf dieser Welt jemals könnten.

Wenn ich du wäre, würde ich lieber etwas über Parallesierung und ordentliches Lock-Free-Design erzählen.

[Monger]

Ich hoffe doch mal, dass Pest genau das meint: wie der Compiler gewisse Code Optimierungen vornimmt. Ist zwar ein sehr akademisches Feld, weil es fast nur die Compilerbauer wirklich berührt, aber uninteressant ist das nicht.


Wer heute Performance "Optimierungen" ohne konkreten Hinweis auf einen Flaschenhals macht, gehört sowieso gesteinigt.

[pest]

Parallelisierung soll aber nicht Teil des Vortrags sein, sondern die Vorstufe davon, also was kann ich tun, um seriellen Code in Fortran oder C, schneller zu bekommen.

Das das der Compiler zu 99% macht, ist mir auch klar, allerdings geht es eben auch darum zu zeigen, wie kann ich einem Compiler Tipps geben, die er ausnutzen kann.

Ich hoffe doch mal, dass Pest genau das meint: wie der Compiler gewisse Code Optimierungen vornimmt. Ist zwar ein sehr akademisches Feld, weil es fast nur die Compilerbauer wirklich berührt, aber uninteressant ist das nicht.
Wer heute Performance "Optimierungen" ohne konkreten Hinweis auf einen Flaschenhals macht, gehört sowieso gesteinigt.

nein es geht wirklich um individuelles Optimieren, und nicht was der Compiler macht

Hey, irgendwie muss ich diese 60min vollbekommen :eek:, und der Großteil des Auditoriums weiß nichtmal was ein Cache ist :wink:
der Vortrag ist auch in Englisch, also dreh ich hier gerade etwas frei

[Pinoccio]

Zwei Links: 1 (http://events.ccc.de/camp/2007/Fahrplan/events/1952.en.html) und 2 (pdf) (Fortsetzung von 1) (http://www.linux-kongress.org/2009/slides/compiler_survey_felix_von_leitner.pdf):
Learn what your compiler does
Then let the compiler do it.

Wie versiert ist dein Publikum? Was ist Ziel des Vortrags? (Ein Vortrag um des Vortragens willen? Mehr Wissen bei den Zuhörern? Mehr Wissen bei dir [durchs Ausarbeiten]?)

mfg

[Trap]

Die beste Optimierung ist wohl in 90% aller Fälle herauszufinden wie das Problem heißt, das man lösen will, dann rauszusuchen mit welchem Algorithmus es für den Anwendungsfall effizient gelöst wird und den Algorithmus dann zu implementieren (oder noch besser eine fertige Implementierung zu nehmen).

Damit bekommt man aber keinen Vortrag ausgefüllt ;)

Was sich anbietet ist einmal eine Betrachtung der verschiedenen Latenzen für verschiedene Aktionen (Registerzugriff, Cachezugriff, Hauptspeicherzugriff, Festplattenzugriff...), wenn man nicht zu sehr in Richtung Algorithmen/Datenstrukturen gehen will sollte man meiner Meinung nach trotzdem Memoization und Hashing ansprechen (falls es zum Publikum passt), das ist für viele Probleme anwendbar, die keine fertige effiziente algorithmische Lösung haben.

[pest]

Zwei Links: 1 (http://events.ccc.de/camp/2007/Fahrplan/events/1952.en.html) und 2 (pdf) (Fortsetzung von 1) (http://www.linux-kongress.org/2009/slides/compiler_survey_felix_von_leitner.pdf):
Learn what your compiler does
Then let the compiler do it.


sehr C-spezifisch, aber trotzdem gutes Material

allerdings muss ich zugeben, das es eben Situationen gibt,
wo man dem Compiler auf die Sprünge helfen muss, weil er gewisse Strukturen nicht erkennt.


ich weiß auch nicht, was so verkehrt daran wäre, Beispiele aus dieser Vortragsreihe (http://www.lrr.in.tum.de/Lehrstuhl/Lehre/Seminare/Old/seminar_ss98.html) zu verwenden.

Wie versiert ist dein Publikum?

Herren und Frauen Doktoren des Instituts, wobei ich die Programmierfähigkeiten eher auf durchschnittlich bezeichnen würde.


Was ist Ziel des Vortrags? (Ein Vortrag um des Vortragens willen? Mehr Wissen bei den Zuhörern? Mehr Wissen bei dir [durchs Ausarbeiten]?)


so wie ich das Verstanden habe, wollen die praktische Beispiele
dafür sehen, was sie in ihrem (skalaren) (Fortran-)Code anders machen können.


Damit bekommt man aber keinen Vortrag ausgefüllt ;)


richtig


Was sich anbietet ist einmal eine Betrachtung der verschiedenen Latenzen für verschiedene Aktionen (Registerzugriff, Cachezugriff, Hauptspeicherzugriff, Festplattenzugriff...), wenn man nicht zu sehr in Richtung Algorithmen/Datenstrukturen gehen will sollte man meiner Meinung nach trotzdem Memoization und Hashing ansprechen (falls es zum Publikum passt), das ist für viele Probleme anwendbar, die keine fertige effiziente algorithmische Lösung haben.

ja ne gewisse Einführung in grundlegende Rechnerarchitektur ist gewollt, und danke für die Tipps

ich mein, ich kann denen auch einfach das Erzählen was der Compiler zu 90% macht - ich hätte damit kein Problem :freak:
das gibt dann zwar anschließend ne Menge Diskussion (auf Englisch), aber naja, ist eh an einem fremden Department

[Monger]

Würde es sich dann nicht anbieten, ein praxisbezogenes Beispiel zu machen?

Sprich: nimm ein Stück Software, und demonstriere daran, wie man
a) Performance Flaschenhälse aufspürt (da gibts ja so einige Tools dafür)
b) diese behebt (da kommt dann mit hoher Sicherheit etwas Algorithmentheorie)
c) NICHT optimiert (Stichwort: Premature Optimizations)

Wie gesagt: wer heute optimiert, macht das eigentlich grundsätzlich am lebenden Beispiel. Wer sich nur auf statische Codeanalyse verlässt, gehört da geknüppelt.
Zumindest bei Hochsprachen. Aber vielleicht haben du und ich ein unterschiedliches Verständnis davon was eine Hochsprache ist.

[pest]

ich habe eben eher an Mini-Beispiele gedacht, den gesamten Vortrag an einem Beispiel durchzuexerzieren halte ich für wenig sinnvoll,
aber danke für die Tipps, die a),b),c) Geschichte leuchtet sogar mir ein ;)

die Geschichte ist folgende. Viele haben, wie auch ich, den Kurs über Parallelprogrammierung besucht, hatten danach aber genauso viel Ahnung wie vorher was sie jetzt eigentlich machen können.
Diese Rolle soll ich irgendwie übernehmen.


Zumindest bei Hochsprachen. Aber vielleicht haben du und ich ein unterschiedliches Verständnis davon was eine Hochsprache ist.

ich weiß das der Großteil der Leute, dem Compiler vertrauen, aber meine Erfahrung ist, das dies oft nicht funktioniert.

Ich hatte z.B. mal eine einfache SAD-Funktion (Summe der absoluten Differenzen über einen Pixelblock), und meine manuell ausgerollte-Variante mit ein paar anderen Tricks,
war auf jeden Fall viel schneller als die -O3 Variante.

die wollen halt auch Sachen hören wie, wenn die Zeilenlänge der Matrix 27 Elemente beträgt arbeitet man mit einem Stride von 32 oder 64, und sowas eben.

Die Leute implementieren hauptsächlich numerische Algorithmen mit Matrizen, Vektoren usw.

edit: genauso ist es z.B. imo wichtig auf einer x86-CPU mit einer bestimmten maximalen Wortbreite innerhalb ihrer Vektoreinheiten, darauf bei der Programmierung Rücksicht zu nehmen,
das heißt selbstständig Ketten von 4-8 Elementen bei der Bearbeitung zu erstellen. Wieviel da die Compiler können weiß ich nicht?
Wenn ich eine Schleife for(k=0,k<9,k++) a[k]=Berechnung habe, erkennt der Compiler das er die ersten 8 vielleicht mit einem SSE-Befehl bearbeiten kann?
Ich muss da selbst noch ein wenig experimentieren, um nicht allzu doof dazustehen.


ich danke euch erstmal, muss mir das mal alles durch den Kopf gehen lassen. Von allem ein bisschen und das wird schon, denke ich

[Monger]

ich habe eben eher an Mini-Beispiele gedacht, den gesamten Vortrag an einem Beispiel durchzuexerzieren halte ich für wenig sinnvoll

Das Problem an Minibeispielen ist halt, dass ihre Praxisrelevanz gleich Null ist. Kleine Programme laufen in aller Regel auch so schon schnell genug. In der Praxis hast du irgendeinen großen Klotz vor dir der rumlahmt, und du hast keine Ahnung warum.


Ich hatte z.B. mal eine einfache SAD-Funktion (Summe der absoluten Differenzen über einen Pixelblock), und meine manuell ausgerollte-Variante mit ein paar anderen Tricks,
war auf jeden Fall viel schneller als die -O3 Variante.

Wenn diese Funktion nicht kritisch für den gesamten Programmablauf ist, ist das vollkommen irrelevant.

Das kommt halt dann auf den Anwendungsfall an, und in 99% der Fälle macht der Compiler halt seine Sache vielleicht nicht optimal, aber ziemlich gut. Die wirklich kritischen Performance Löcher sind algorithmische Probleme.

Hab gerade vor ein paar Wochen ein Beispiel gehabt: hab da eine Datenstruktur, auf die Zugriffe ziemlich lahmarschig waren. Ich hab dann fünf verschiedene Algorithmen ausprobiert, z.B. an verschiedenen Stellen Cachen um häufige Zugriffe schneller abzuwickeln, irgendwelche HashMaps anlegen um die Suche schneller zu gestalten...
Im Endeffekt hat sich herausgestellt, dass das meiste von diesen ganzen Cache Optimierungen allenfalls ein paar Prozent Leistung gebracht haben, aber den Code unglaublich aufgebläht haben. Wenn meine Prozedur zwei Minuten läuft, sind fünf Sekunden Ersparnis den Ärger schlicht nicht wert. Caches müssen schließlich auch aktuell bleiben, womit man sich dann Validierungsprobleme einschleppt.

Sowas würde ich in so einem Vortrag eigentlich erwarten. Das schlimmste was du tun kannst, ist den Leuten zu erklären wie man optimiert, und sie tun es dann auch.

“The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet.” (http://en.wikipedia.org/wiki/Optimization_(computer_science))

[pest]

In der Praxis hast du irgendeinen großen Klotz vor dir der rumlahmt, und du hast keine Ahnung warum.


klar ist es wichtig diese Teile zu identifizieren, und danke für den Tipp
das kommt auf jeden Fall mit rein, allerdings sehe ich das so, das die Minibeispiele zeigen sollen, was man eben innerhalb der kritischen Stellen, anders machen kann.
Und da es sich Hauptsächlich um numersische Algorithmen handelt kann ich Ihnen nicht erzählen welche Algorithmen besser sind


Wenn diese Funktion nicht kritisch für den gesamten Programmablauf ist, ist das vollkommen irrelevant.


In diesem Fall handelte es sich um eine Bewegungsvorhersage und die SAD-Funktion war zeitkritisch.


Die wirklich kritischen Performance Löcher sind algorithmische Probleme.


Eröffnungs-und Schlusssatz meines Vortrages :freak:


Sowas würde ich in so einem Vortrag eigentlich erwarten. Das schlimmste was du tun kannst, ist den Leuten zu erklären wie man optimiert, und sie tun es dann auch.


was würdest du in so einem Vortrag erwarten? Letzteres sollen die Leute doch tun :freak:, natürlich kann ich den Vortrag auch allgemein halten,
so das sie zumindest verstehen, wie man einigermaßen sauber programmiert.


“The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet.” (http://en.wikipedia.org/wiki/Optimization_(computer_science))

das wird ein reinfall, ich weiß es jetzt schon

[Monger]

was würdest du in so einem Vortrag erwarten?

Wie gesagt: nicht nur WIE man optimiert, sondern vorallem WANN. Letzteres finde ich eigentlich viel wichtiger.

Du hast z.B. von einer x86er Architektur gesprochen. Was, wenn dein Kunde schon vorwiegend auf eine x64 Architektur setzt?

Im Grunde musst du dir bewusst sein, auf welchen Rechnern (grob anteilig) deine Software mal laufen soll, bevor du irgendwelche Optimierungen vornimmst. Wie gesagt: grundsätzlich am lebenden Objekt messen.

[pest]

ich habe keine Kunden ;)
allerdings arbeiten die Hauptsächlich auf x86, selbst unser Cluster ist 256x-Opteron, und ein paar PowerPC

ich denke ich werde von der Codelevel-Optimierung Abstand nehmen, und nur die allgemeinen Techniken vorstellen.

In den angegeben Wiki-Links, sind gute Hinweise auf "gutes Programmieren", dafür Beispiele finden, wie man Profiled, was man nicht machen sollte. Bisschen Datenstrukturen..
Es sollte eben nicht theoretisch sein, sondern praxisbezogen, das wird dann halt irgendwie schwerer imo, wenn ich denen 60min erzähle wann sie optimieren sollen,
sind sie genauso schlau wie vorher. Die wollen danach praktisch an ihren Rechner und sind heiß aufs Optimieren :freak:

hier laufen eben Programme die für einen Durchlauf bis zu 2 Wochen benötigen

[pest]

So (http://hpcs2003.ccs.usherbrooke.ca/tutorials/Code_Optimization.pdf) stelle ich mir das ungefähr vor. Was haltet ihr davon?

[Bietchiebatchie]

Ich hab die Slides mal überflogen; folgendes ist aufgefallen:
- 3: zu voll und insb. ohne Vortrag absolut unklar was gemeint ist (mir wurde erst später klar was die T_x bedeuten)
- 4: Rechtschreibung: "can be parallelized/optimized"
- 6: Rechtschreibung: "parallelization"
- 7: Das wichtigste (imo) vergessen: Solange man nicht eine sehr allgemeine Bibliothek entwickelt sondern ein konkretes Problem optimieren muss sollte der erste Schritt immer die Formulierung von vernünftigen Performance-Anforderungen sein; d.h. sowas wie "Alg. erfüllt Erwartung wenn schneller als 10 ms", "Datendurchsatz soll x Items pro sekunde sein" etc. und eben später erwähnen dass man aufhört zu optimieren sobald diese Ziele erreicht wurden
- 7: Außerdem könnte man verschieden Schritte gruppieren, da ansonsten optisch relativ unübersichtlich
- 10: Netzwerk (Lan/Inet) gehört als Resource (speedmäßig zwischen RAM und Disk) auf jeden Fall dazu.
- 24: statt "array considerations" würde ich das ganze eher "memory access patterns" o.ä. nennen

Allgemein: viele Slides könnten etwas weniger Text vertragen (soll dich nicht davon abhalten diese Dinge während dem Talk zu erwähnen); insb. längere Sätze vermeiden

Insgesamt relativ klar strukturierter Vortrag über (größtenteils) low-level-Optimierungen.

Achja, weil ich das gerade gelesen habe, könnte dich auch interessieren:
http://research.scee.net/files/presentations/gcapaustralia09/Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf

[Pinoccio]

http://research.scee.net/files/presentations/gcapaustralia09/Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf:up: Danke.

mfg

[pest]

Ich hab die Slides mal überflogen; folgendes ist aufgefallen:
- 3: zu voll und insb. ohne Vortrag absolut unklar was gemeint ist (mir wurde erst später klar was die T_x bedeuten)
- 4: Rechtschreibung: "can be parallelized/optimized"
- 6: Rechtschreibung: "parallelization"
- 7: Das wichtigste (imo) vergessen: Solange man nicht eine sehr allgemeine Bibliothek entwickelt sondern ein konkretes Problem optimieren muss sollte der erste Schritt immer die Formulierung von vernünftigen Performance-Anforderungen sein; d.h. sowas wie "Alg. erfüllt Erwartung wenn schneller als 10 ms", "Datendurchsatz soll x Items pro sekunde sein" etc. und eben später erwähnen dass man aufhört zu optimieren sobald diese Ziele erreicht wurden
- 7: Außerdem könnte man verschieden Schritte gruppieren, da ansonsten optisch relativ unübersichtlich
- 10: Netzwerk (Lan/Inet) gehört als Resource (speedmäßig zwischen RAM und Disk) auf jeden Fall dazu.
- 24: statt "array considerations" würde ich das ganze eher "memory access patterns" o.ä. nennen

Allgemein: viele Slides könnten etwas weniger Text vertragen (soll dich nicht davon abhalten diese Dinge während dem Talk zu erwähnen); insb. längere Sätze vermeiden


ich dachte schon du denkst, das wären meine slides, aber vielen Dank für die Tipps

klar werde ich das etwas anders machen, und lange sätze verbietet mein Englisch schon...because it is not very good :freak:


Achja, weil ich das gerade gelesen habe, könnte dich auch interessieren:
http://research.scee.net/files/presentations/gcapaustralia09/Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf

zwar für den Vortrag nicht direkt zu gebrauchen aber für mich interessant, danke


ich habe gestern mit dem letzten offiziellen MinGW-Compiler rumgespielt (GCC 3.x.x), und der kann ja gar nix :freak:, werde später mal ein paar Beispiele posten

[RMC]

Duff's Device (http://en.wikipedia.org/wiki/Duff%27s_device) nicht vergessen :freak:

Im Ernst:

Würde es sich dann nicht anbieten, ein praxisbezogenes Beispiel zu machen?

Sprich: nimm ein Stück Software, und demonstriere daran, wie man
a) Performance Flaschenhälse aufspürt (da gibts ja so einige Tools dafür)
b) diese behebt (da kommt dann mit hoher Sicherheit etwas Algorithmentheorie)
c) NICHT optimiert (Stichwort: Premature Optimizations)

Zustimm.

Viele wissen nichtmal, wie sie ihre Bottlenecks überhaupt richtig ausmachen können. Wenn dann irgendwelche praxisirrelevanten "Optimierungen" als Allheilmittel eingetrichtert werden, kann das auch Nachteile mit sich bringen. Ich würde auch eher da ansetzen, wo es sinnvoll ist, und die oben genannten Punkte klingen recht gut.


Und ansonsten:

“The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet.”

QFT

[Bietchiebatchie]

ich dachte schon du denkst, das wären meine slides, aber vielen Dank für die Tipps
"So stelle ich mir das ungefähr vor. Was haltet ihr davon?"
hab ich eben als "Hier ist die erste Version meines Vortrages - was haltet ihr davon?" interpretiert. Naja, egal ;)

[Gast]

Die wollen danach praktisch an ihren Rechner und sind heiß aufs Optimieren :freak:

Dann ist es deine Aufgabe als vortragender, sie aktiv genau DAVON abzuhalten. Bevor man Optimiert sollte man verstanden haben, wie man es richtig macht.

Es gibt nichts unsinnigeres, als während dem Codieren darauf zu achten, dass man ++obj anstatt obj++ verwendet "weil das ja schneller ist". Ja ich denke an sie, Herr Kolb.

Und dann exerziere das an einem kleinen Fallbeispiel durch. Denk dir irgendwelchen Code aus, bei dem du extra einen (von dir als solchen deklarierten) performancekritischen Abschnitt mittels eher langsamen Codes abarbeiten lässt. Dann kannst du profilen, verbessern, wieder profilen und ein Ergebnis präsentieren.

Es ist ja wohl kaum deine Aufgabe, die Profs in ihrem Falschglauben und Tatendrang zu unterstützen, oder?

[pest]

Es gibt nichts unsinnigeres, als während dem Codieren darauf zu achten, dass man ++obj anstatt obj++ verwendet "weil das ja schneller ist".


der vortrag für fanatiker kommt danach ;)


Denk dir irgendwelchen Code aus, bei dem du extra einen (von dir als solchen deklarierten) performancekritischen Abschnitt mittels eher langsamen Codes abarbeiten lässt. Dann kannst du profilen, verbessern, wieder profilen und ein Ergebnis präsentieren.

prob ist, mein compiler ist zu doof, und erkennt selbst die einfachsten sachen nicht
bzw. gut für mich und meinen vortrag :biggrin:


Es ist ja wohl kaum deine Aufgabe, die Profs in ihrem Falschglauben und Tatendrang zu unterstützen, oder?

falschglauben ist da nicht das richtige wort. es geht darum wie ich deren vorstellungen sinnvoll interpretiere ;)
es gibt ja verschiedene wege wie man seinen code optimieren kann.
beispiele die direkt im code rumpfuschen, nehmen dabei am ende nur einen relativ geringen anteil am vortrag ein

man muss auch bedenken, die schwierigkeit des vortrages besteht für mich darin, dass es so aussehen soll
als mache ich den lieben langen tag nix anderes als vorträge vor forschern in englisch halten :freak:
denn besonders kompliziert ist das thema an sich ja nicht