In letzter Zeit hatte ich ein bisschen damit zu tun Matlab Code, der zu langsam lief, zu optimieren.
Leider bin ich kein ausgebildeter theoretischer Informatiker, sodass ich leider nicht sagen kann, in welcher Komplexitätsklasse der Code vorher war und wohin ich ihn befördert habe. (Vermutlich um gar keine, da der Overhead, den ich beseitigt habe ja nicht wirklich zum Algorithmus gehört :/) Aber ich habe ein paar Dinge gelernt, die ich gerne festhalten würde. Allerdings sind dies auch Dinge, die vermutlich jeder, der sich kurz damit beschäftigt, ziemlich schnell herausfindet.
Profiler sind Toll:
Schritt Nummer eins sollte wohl immer sein, das Programm laufen zu lassen und zu sehen, in welchen Funktionen die meiste Zeit verbraten wird.
Egal wie genial die Optimierung sein mag: Sie hilft nicht, wenn das Programm in der optimierten Funktion vorher nur ein paar Millisekunden verbringt, sodass man maximal diese Millisekunden sparen kann.
Für Python zB. sollte man sich die
Dokumentation ansehen
In Matlab ruft man ihn mit
profview
Funktionsaufrufe sind Böse:
Angenommen du hast ein Gitter mit gut 10^5 Punkten.
Angenommen du hast außerdem einen Algorithmus, der den Abstand jedes Punktes zu einem Polygon ermittelt.
Dann solltest du die Funktion für diesen Algorithmus nicht für jeden Punkt einzeln aufrufen.
Nach Anpassen des Algorithmus, sodass er die Abstände aller Punkte zu einer Kante gleichzeitig berechnet hat, lief es in meinem Test Fall um Faktor 80 schneller. Für größere Punktwolken, was in dem Fall einer besseren Qualität entsprach, auch schneller.
Schleifen sind Böse:
Das gilt nicht für Sprachen wie C.
Aber bei Interpreter Sprachen, sollte man sie meiden wo möglich.
Beispielsweise wird dies im Matlab Jargon "
vektorisieren" genannt. (Was nicht mit dem
Vektorisieren compilierter Sprachen verwechselt werden sollte.) (Trotz JIT ist es empfehlenswert diese Vektorierung durchzuführen)
Oder in Python kann man es mit "
list comprehesions"/"
generator expressions" etwas beschleunigen, wie in diesem
lesenswerten Post festgestellt wurde.
C ist Toll:
Angenommen jemand hat einen Algorithmus in einer Interpretersprache umgesetzt (Warum finden in der Physik so viele Leute Matlab toll? Nur weil es einfach und schnell zu schreiben ist und wirklich gute Plot-Funktionen hat?), der nicht mehr stark verbesserbar ist -- zumindest nicht von dir. Aber du willst trotzdem, dass dein Computer das Problem in der Mittagspause löst, statt in der Nacht.
Dann geht es in manchen Fällen ziemlich gut den Code einfach nach C zu übersetzen, wo Schleifen, Funktionsaufrufe und sowieso alles sehr viel schneller geht als in einer Interpreter Sprache, wie Matlab (trotz JIT) .
In meinem Test-Fall hat es eine Beschleunigung um Faktor ~6 gegeben. Tja nicht so beeindruckend.
Aber vielleicht kann ich ein paar Leute damit ärgern, die den Code später abändern wollen, aber kein C sprechen.
Und in Projekte, die in einer freundlichen Interpreter Sprache geschrieben sind, kann man es meistens leicht einbinden.
Für Python habe ich
das noch nie ausprobiert.
Und für Matlab gibt es die
mex-Tools.
Parallelisierung ist Toll:
Angenommen der Faktor 6 aus obigen Beispiel reicht dir nicht. Und angenommen dein Problem ist genauso gutmütig wie meins ;)
Dann kannst du mehrere Prozesse parallel fahren und im Idealfall, je nach deiner Hardware nochmal Faktor 4-16 herausholen -- vorausgesetzt der Speicher reicht.
Das habe ich noch nicht umgesetzt. Ich werde mich aber mal dran machen, sobald ich zuviel Zeit habe.
In Matlab gibt es ein "parfor" dafür. Aber ich glaube dazu fehlt mir die passende Toolbox. Doofe unfreie Software.
Für Python klappt "
multiprocessing" sehr gut.
Und im neuen C11 Standard ist es auch drin.
Zusammenfassung:
Man kann seinen Code beschleunigen. Und am besten geht das durch einen echt guten Algorithmus. Allerdings ist das gleichzeitig auch der schwerste Punkt. Falls man es einfacher haben will, legt man sich einen Rechencluster zu und parallelisiert seinen Code ;)
