Optimierung
Dienstag, 15. Februar 2011 | Autor: Nico
Ich mache mir oft Gedanken, ob mein Code „schnell” ist. Lahme und ineffiziente Programme gibt es schließlich schon genug - meins dagegen soll performant sein, jawoll!
Es gibt allerdings ein paar Grundregeln beim Optimieren. Wahrscheinlich auch mehr als nur ein paar - aber das hier sind die, die ich für mich als praktisch und sinnvoll herausgefunden habe.
1. Keine Optimierung ohne objektive Überprüfung!
Ganz einfach: Laufzeit der Originalversion messen, Laufzeit der optimierten Version messen und je nach Resultat die Optimierung behalten oder verwerfen.
Ich hatte erst neulich den Fall, dass ich eine wunderbare, intelligente und elegante Alternative zu meinem ursprünglichen Code geschrieben hatte. Dabei hatte ich eine bestimmte Eigenschaft des Goldenen Schnitts1 ausgenutzt um eine möglichst gleichmäßige, aber zugleich unregelmäßige Verteilung von Punkten über eine Rechteckfläche zu erhalten. Ich war ziemlich stolz und sicher, dass mir das 10% Zeitersparnis bringen würde. Pustekuchen! Es war im Gegenteil sogar langsamer als meine vorherige, völlig unelegante Methode…
Messen kann man die Laufzeit eines Algorithmus’ auf verschiedene Arten. Wenn es lang genug dauert, kann man einfach auf die Uhr schauen. Eleganter sind natürlich Methoden, die direkt am Programm dran sind. In C++ kann man die Zeit recht einfach messen mittels time. Hier ein kleines Beispielprogramm:
#include <iostream>
#include <vector>
#include <ctime>
main() {
time_t start = time (NULL);
for(unsigned int i = 0; i!=40000000; ++i)
std::vector<double> liste(10);
time_t stopp = time (NULL);
std::cout << "Dauer: " << stopp-start << 's'<< std::endl;
}
Man muss nur ctime includen, darin ist die Funktion time() definiert, die die aktuelle Zeit (in Sekunden seit 1.1.19702) zurückgibt. Das macht macht man einmal vor und einmal nach dem Stück Code dessen Laufzeit man wissen will und bildet die Differenz - so einfach ist das.
Nun bekommt man bei jedem Programmlauf mit, ob sich die Laufzeit durch die neuesten Änderungen verkürzt oder verlängert hat.
2. Verfrühte Optimierung ist die Wurzel alles Bösen!
Eine der bekanntesten Regeln stammt von Donald Knuth3:
We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.
Verfrühte Optimierung ist also die Wurzel alles Bösen. Warum?
Manche Programmierer lassen sich im Zeichen der Optimierung zu irgendwelchen, mal mehr, mal minder cleveren Tricks hinreißen, die den Code einerseits unwartbar machen, andererseits nur ein Prozent Performance herausholen oder so. Darüber freut man sich auch nur so lange, bis in dem kryptischen Code ein Fehler ist. Dann fängt man nämlich an, den stundenlang auseinander zu fummeln.
Eines sollte jedem klar sein: Korrektheit geht vor Performance! Das schnellste Programm nützt nichts, wenn es Mist berechnet!
Außerdem sollte man sich vor jeder Optimierung zunächst mal zurück lehnen und gründlich nachdenken!4
3. Lass zuerst den Compiler optimieren!
Bevor man Stunden damit zubringt, seinen Code umzubauen, sollte man die Optimierung des Compilers einschalten. Beim gcc geht das über das Flag -O gefolgt von der gewünschten Optimierungsstufe. -O2 zum Beispiel optimiert relativ stark, aber nicht so viel wie -O3. Viele der Standardtricks kann man sich jetzt sparen, weil der Compiler die automatisch anwendet.
Auf der GCC-Website findet sich eine Übersicht über die verschiedenen Optimierungsoptionen, die von GCC unterstützt werden.
Zu den Optimierungsstufen des GCC muss man sagen, dass die nicht ganz unumstritten sind. Manche Leute glauben, dass man mit -O3 riskiert, dass GCC fehlerhaften Code generiert. Auch über den Performancegewinn wird heftig diskutiert. Bringt -O3 tatsächlich mehr, oder sabotieren die dortigen Maßnahmen nicht diese und jene Caching/Prefetching/Wasauchimmer-Maßnahme moderner Prozessoren? Ist der erhöhte Platzbedarf optimierter Programme den Geschwindigkeitszuwachs wert? Macht es nicht mehr Sinn, mit -Os auf Programmgröße hin zu optimieren? Kurze Programme müssten doch eigentlich automatisch schnell sein!? Mir fehlt leider die Erfahrung, diese Diskussion zu bewerten - darum lasse ich es bleiben.
Womit man aber tatsächlich rechnen muss, ist, dass Debugging auf optimiertem Code manchmal komisch ist, weil der geschriebene Code nicht mehr unbedingt mit dem ausgeführten Code übereinstimmt, nachdem die Optimierungen angewandt wurden.
Nehmen wir nun als praktisches Beispiel nochmal den Code von oben, kompilieren ihn und führen ihn aus.
D:\Code>g++ time.cpp -o zeit D:\Code>zeit Dauer: 22s
Wir bekommen eine Laufzeit von 22 Sekunden.
Kompilieren wir nun mit maximaler Optimierung (-O3) und probieren es nochmal:
D:\Code>g++ -O3 time.cpp -o zeit D:\Code>zeit Dauer: 13s
13 Sekunden -- 40% gespart! Wahrscheinlich ist es auch ein blödes Beispiel, aber ich denke man sieht, dass es sich durchaus lohnen kann, mit den Optimierungsflags rumzuspielen.
Ich persönlich verdanke -O3, dass das Programm für meine Bachelorarbeit nicht nen Monat, sondern nur 20 Minuten gebraucht hat. 😉 Ich war allerdings kein besonders guter C++-Programmierer damals.
4. Optimiere nur dort, wo es was bringt!
Man sollte auf keinen Fall irgendwo anfangen zu optimieren, sondern sich zunächst mal fragen: Wo sind in meinem Code die Flaschenhälse? Welche Funktionen fressen am meisten Zeit? Welche Datenstrukturen den meisten Speicher? Das sind die Stellen, an denen Optimierung ansetzen sollte.
Wie finde ich diese Stellen?
4.1. Profiler
Profiler wie valgrind oder gprof analysieren ein Programm und sagen einem nachher, in welchen Funktionen das Programm die meiste Zeit verbringt. Bevor man auf Verdacht optimiert sollte man sein Programm unbedingt mal durch einen Profiler gejagt haben. So findet man raus, wo wirklich Zeit drauf geht.
4.2. Optimiere die innerste Schleife!
Nicht nur die Laufzeit einer Funktion ist interessant, sondern auch, wie oft sie aufgerufen wird.
Auch diese Information gibt einem der Profiler, aber mit etwas nachdenken kommt man auch ohne zu folgender Erkenntnis: In vielen Programmen hat man Schleifen und in den Schleifen sind wieder Schleifen, die wiederum Funktionen aufrufen, die Schleifen enthalten, die Schleifen enthalten… usw. Die innerste Schleife wird dann oft millionenfach ausgeführt! Wenn man dort eine von vier Zeilen Code sparen oder in die nächst-äußere Schleife schieben kann, dann kann man teilweise wirklich Performance gut machen!
0. Gutes Design
Dieser Abschnitt trägt die Nummer Null, denn er sollte eigentlich über und zeitlich vor all den anderen Maßnahmen stehen. Er steht dennoch hier unten, weil er nicht so recht in die Kategorie „Optimierung” passt.
Algorithmus
Mit gutem Design meine ich mehrere Dinge. Zum einen ist da der Algorithmus selbst. Man kann so gut programmieren und optimieren wie man will -- wenn der Algorithmus, den man implementiert, an sich schon langsam ist, hat man dennoch verloren. Deswegen sollte man sich vorher gut überlegen, welchen Algorithmus man für das aktuelle Problem nimmt.
Das ist die Stelle, an dem sich das Grundwissen um Laufzeitkomplexitäten auszahlt, dass man als Programmierer vielleicht beigebracht bekommen hat. Man weiß dann zum Beispiel, dass man lieber eine Binärsuche (O[log n]) nehmen sollte, statt die Liste linear durchzugehen (O[n]).
Für komplexere Beispiele kann man aus der Literatur den schnellsten Algorithmus heraussuchen. Aber Vorsicht! Dabei es gibt drei, teils ineinandergreifende Fallstricke, die man kennen sollte:
Erstens: Bevor man sich daran macht, einen Algorithmus oder eine Datenstruktur selbst zu programmieren, sollte man schauen oder rumfragen, ob es nicht schon eine fertige Bibliothek gibt, die die gewünschte Funktionalität bietet. Zum Beispiel die Standardbibliothek, Boost oder Spezialbibliotheken wie die CGAL. So spart man sich die zeitraubende Neuerfindung des Rads und greift einfach auf jahrzehntelang bewährten und optimierten Code zurück.
Zweitens: Wenn ein Algorithmus sehr kompliziert ist, muss man sich manchmal fragen was mehr kostet: Wochenlang dieses einen kryptischen Algorithmus zu verstehen, zu schreiben, zu debuggen? Oder einen einfacheren Algorithmus zu nehmen, der vielleicht ein kleines bisschen langsamer ist, dafür aber klar und verständlich, oder gar schon fertig implementiert vorliegt.
Drittens: Manche Algorithmen haben zwar eine theoretisch bessere Laufzeit, d.h. brauchen weniger Schritte - aber die einzelnen Schritte sind derart abstrus und aufwendig, dass für realistische Problemgrößen ein anderer, eigentlich langsamerer, aber schlankerer Algorithmus die Nase vorn hat.5
Datenstruktur
Neben der Wahl der zu verwendenden Algorithmen ist auch die Wahl der Datenstruktur entscheidend. Bei einer verketteten Liste beispielsweise kann man schnell ein Element einfügen - da werden intern nur ein paar Pointer umgebogen und fertig. Bei einem Array sieht das anders aus, da müssen alle, möglicherweise viele, Elemente hinter der fraglichen Position um eins nach hinten verschoben werden.
Was bedeutet das in der Praxis? Man sollte die in der Standardbibliothek zur Verfügung stehenden Datenstrukturen kennen und wissen, wofür diese gut geeignet sind und wofür nicht. Häufig verwendete Datenstrukturen bzw. Container aus der STL sind vector und list. Die hier immer mal wieder verlinkte Referenz auf cplusplus.com ist übrigens generell toll, um solche Dinge nachzuschlagen! Dort wird zu jedem Container erklärt, wofür er sich eignet, außerdem steht auf den Seiten zu den einzelnen Funktionen deren Laufzeit.
Es gibt sicher noch mehr zu dem Thema zu sagen, als ich hier jetzt geschrieben habe - aber ich denke, die wichtigsten Konzepte sind abgedeckt. Zusammenfassend kann man eigentlich das sagen, was man zum Thema Programmieren immer sagen kann: Erst nachdenken, dann coden. 😉
- siehe Wikipedia:Goldener_Schnitt#Approximationseigenschaften_der_Goldenen_Zahl ↩
- Das ist die berühmte Unixzeit! ↩
- Ein Name, den man als Programmierer kennen sollte. Siehe Donald Ervin Knuth ↩
- Programmieren hat sehr viel mehr mit Nachdenken zu tun, als man gemeinhin so glaubt. ↩
- Ich habe in der Tat mal ein Paper gelesen, in dem exakt dieses Problem aufgetreten war. Der einfache Algorithmus war für alle praktisch relevanten Problemgrößen schneller als der supertolle Algorithmus mit der theoretisch besseren Laufzeit. ↩