Home

Optimierung

Dienstag, 15. Februar 2011 | Autor:

Ich mache mir oft Gedan­ken, ob mein Code „schnell” ist. Lahme und inef­fi­zi­ente Pro­gramme gibt es schließ­lich schon genug - meins dage­gen soll per­for­mant sein, jawoll!

Es gibt aller­dings ein paar Grund­re­geln beim Opti­mie­ren. Wahr­schein­lich auch mehr als nur ein paar - aber das hier sind die, die ich für mich als prak­tisch und sinn­voll her­aus­ge­fun­den habe.

1. Keine Opti­mie­rung ohne objek­tive Überprüfung!

Ganz ein­fach: Lauf­zeit der Ori­gi­nal­ver­sion mes­sen, Lauf­zeit der opti­mier­ten Ver­sion mes­sen und je nach Resul­tat die Opti­mie­rung behal­ten oder verwerfen.

Ich hatte erst neu­lich den Fall, dass ich eine wun­der­bare, intel­li­gente und ele­gante Alter­na­tive zu mei­nem ursprüng­li­chen Code geschrie­ben hatte. Dabei hatte ich eine bestimmte Eigen­schaft des Gol­de­nen Schnitts1 aus­ge­nutzt um eine mög­lichst gleich­mä­ßige, aber zugleich unre­gel­mä­ßige Ver­tei­lung von Punk­ten über eine Recht­eck­flä­che zu erhal­ten. Ich war ziem­lich stolz und sicher, dass mir das 10% Zeit­er­spar­nis brin­gen würde. Pus­te­ku­chen! Es war im Gegen­teil sogar lang­sa­mer als meine vor­he­rige, völ­lig unele­gante Methode…

Mes­sen kann man die Lauf­zeit eines Algo­rith­mus’ auf ver­schie­dene Arten. Wenn es lang genug dau­ert, kann man ein­fach auf die Uhr schauen. Ele­gan­ter sind natür­lich Metho­den, die direkt am Pro­gramm dran sind. In C++ kann man die Zeit recht ein­fach mes­sen mit­tels time. Hier ein klei­nes 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 inclu­den, darin ist die Funk­tion time() defi­niert, die die aktu­elle Zeit (in Sekun­den seit 1.1.19702) zurück­gibt. Das macht macht man ein­mal vor und ein­mal nach dem Stück Code des­sen Lauf­zeit man wis­sen will und bil­det die Dif­fe­renz - so ein­fach ist das.

Nun bekommt man bei jedem Pro­gramm­lauf mit, ob sich die Lauf­zeit durch die neu­es­ten Ände­run­gen ver­kürzt oder ver­län­gert hat.

2. Ver­frühte Opti­mie­rung ist die Wur­zel alles Bösen!

Eine der bekann­tes­ten Regeln stammt von Donald Knuth3:

We should for­get about small effi­ci­en­cies, say about 97% of the time: pre­ma­ture opti­miza­tion is the root of all evil.

Ver­frühte Opti­mie­rung ist also die Wur­zel alles Bösen. Warum?

Man­che Pro­gram­mie­rer las­sen sich im Zei­chen der Opti­mie­rung zu irgend­wel­chen, mal mehr, mal min­der cle­ve­ren Tricks hin­rei­ßen, die den Code einer­seits unwart­bar machen, ande­rer­seits nur ein Pro­zent Per­for­mance her­aus­ho­len oder so. Dar­über freut man sich auch nur so lange, bis in dem kryp­ti­schen Code ein Feh­ler ist. Dann fängt man näm­lich an, den stun­den­lang aus­ein­an­der zu fummeln.

Eines sollte jedem klar sein: Kor­rekt­heit geht vor Per­for­mance! Das schnellste Pro­gramm nützt nichts, wenn es Mist berechnet!

Außer­dem sollte man sich vor jeder Opti­mie­rung zunächst mal zurück leh­nen und gründ­lich nach­den­ken!4

3. Lass zuerst den Com­pi­ler optimieren!

Bevor man Stun­den damit zubringt, sei­nen Code umzu­bauen, sollte man die Opti­mie­rung des Com­pi­lers ein­schal­ten. Beim gcc geht das über das Flag -O gefolgt von der gewünsch­ten Opti­mie­rungs­stufe. -O2 zum Bei­spiel opti­miert rela­tiv stark, aber nicht so viel wie -O3. Viele der Stan­dard­tricks kann man sich jetzt spa­ren, weil der Com­pi­ler die auto­ma­tisch anwendet.

Auf der GCC-Website fin­det sich eine Über­sicht über die ver­schie­de­nen Opti­mie­rungs­op­tio­nen, die von GCC unter­stützt wer­den.

Zu den Opti­mie­rungs­stu­fen des GCC muss man sagen, dass die nicht ganz unum­strit­ten sind. Man­che Leute glau­ben, dass man mit -O3 ris­kiert, dass GCC feh­ler­haf­ten Code gene­riert. Auch über den Per­for­mance­ge­winn wird hef­tig dis­ku­tiert. Bringt -O3 tat­säch­lich mehr, oder sabo­tie­ren die dor­ti­gen Maß­nah­men nicht diese und jene Caching/Prefetching/Wasauchimmer-Maßnahme moder­ner Pro­zes­so­ren? Ist der erhöhte Platz­be­darf opti­mier­ter Pro­gramme den Geschwin­dig­keits­zu­wachs wert? Macht es nicht mehr Sinn, mit -Os auf Pro­gramm­größe hin zu opti­mie­ren? Kurze Pro­gramme müss­ten doch eigent­lich auto­ma­tisch schnell sein!? Mir fehlt lei­der die Erfah­rung, diese Dis­kus­sion zu bewer­ten - darum lasse ich es bleiben.

Womit man aber tat­säch­lich rech­nen muss, ist, dass Debug­ging auf opti­mier­tem Code manch­mal komisch ist, weil der geschrie­bene Code nicht mehr unbe­dingt mit dem aus­ge­führ­ten Code über­ein­stimmt, nach­dem die Opti­mie­run­gen ange­wandt wurden.

Neh­men wir nun als prak­ti­sches Bei­spiel noch­mal den Code von oben, kom­pi­lie­ren ihn und füh­ren ihn aus.

D:\Code>g++ time.cpp -o zeit

D:\Code>zeit
Dauer: 22s

Wir bekom­men eine Lauf­zeit von 22 Sekunden.

Kom­pi­lie­ren wir nun mit maxi­ma­ler Opti­mie­rung (-O3) und pro­bie­ren es nochmal:

D:\Code>g++ -O3 time.cpp -o zeit

D:\Code>zeit
Dauer: 13s

13 Sekun­den -- 40% gespart! Wahr­schein­lich ist es auch ein blö­des Bei­spiel, aber ich denke man sieht, dass es sich durch­aus loh­nen kann, mit den Opti­mie­rungs­flags rumzuspielen.

Ich per­sön­lich ver­danke -O3, dass das Pro­gramm für meine Bache­l­or­ar­beit nicht nen Monat, son­dern nur 20 Minu­ten gebraucht hat. ;) Ich war aller­dings kein beson­ders guter C++-Programmierer damals.

4. Opti­miere nur dort, wo es was bringt!

Man sollte auf kei­nen Fall irgendwo anfan­gen zu opti­mie­ren, son­dern sich zunächst mal fra­gen: Wo sind in mei­nem Code die Fla­schen­hälse? Wel­che Funk­tio­nen fres­sen am meis­ten Zeit? Wel­che Daten­struk­tu­ren den meis­ten Spei­cher? Das sind die Stel­len, an denen Opti­mie­rung anset­zen sollte.

Wie finde ich diese Stellen?

4.1. Pro­fi­ler

Pro­fi­ler wie val­grind oder gprof ana­ly­sie­ren ein Pro­gramm und sagen einem nach­her, in wel­chen Funk­tio­nen das Pro­gramm die meiste Zeit ver­bringt. Bevor man auf Ver­dacht opti­miert sollte man sein Pro­gramm unbe­dingt mal durch einen Pro­fi­ler gejagt haben. So fin­det man raus, wo wirk­lich Zeit drauf geht.

4.2. Opti­miere die innerste Schleife!

Nicht nur die Lauf­zeit einer Funk­tion ist inter­es­sant, son­dern auch, wie oft sie auf­ge­ru­fen wird.

Auch diese Infor­ma­tion gibt einem der Pro­fi­ler, aber mit etwas nach­den­ken kommt man auch ohne zu fol­gen­der Erkennt­nis: In vie­len Pro­gram­men hat man Schlei­fen und in den Schlei­fen sind wie­der Schlei­fen, die wie­derum Funk­tio­nen auf­ru­fen, die Schlei­fen ent­hal­ten, die Schlei­fen ent­hal­ten… usw. Die innerste Schleife wird dann oft mil­lio­nen­fach aus­ge­führt! Wenn man dort eine von vier Zei­len Code spa­ren oder in die nächst-äußere Schleife schie­ben kann, dann kann man teil­weise wirk­lich Per­for­mance gut machen!

0. Gutes Design

Die­ser Abschnitt trägt die Num­mer Null, denn er sollte eigent­lich über und zeit­lich vor all den ande­ren Maß­nah­men ste­hen. Er steht den­noch hier unten, weil er nicht so recht in die Kate­go­rie „Opti­mie­rung” passt.

Algo­rith­mus

Mit gutem Design meine ich meh­rere Dinge. Zum einen ist da der Algo­rith­mus selbst. Man kann so gut pro­gram­mie­ren und opti­mie­ren wie man will -- wenn der Algo­rith­mus, den man imple­men­tiert, an sich schon lang­sam ist, hat man den­noch ver­lo­ren. Des­we­gen sollte man sich vor­her gut über­le­gen, wel­chen Algo­rith­mus man für das aktu­elle Pro­blem nimmt.

Das ist die Stelle, an dem sich das Grund­wis­sen um Lauf­zeit­kom­ple­xi­tä­ten aus­zahlt, dass man als Pro­gram­mie­rer viel­leicht beige­bracht bekom­men hat. Man weiß dann zum Bei­spiel, dass man lie­ber eine Binär­su­che (O[log n]) neh­men sollte, statt die Liste linear durch­zu­ge­hen (O[n]).

Für kom­ple­xere Bei­spiele kann man aus der Lite­ra­tur den schnells­ten Algo­rith­mus her­aus­su­chen. Aber Vor­sicht! Dabei es gibt drei, teils inein­an­der­grei­fende Fall­stri­cke, die man ken­nen sollte:

Ers­tens: Bevor man sich daran macht, einen Algo­rith­mus oder eine Daten­struk­tur selbst zu pro­gram­mie­ren, sollte man schauen oder rum­fra­gen, ob es nicht schon eine fer­tige Biblio­thek gibt, die die gewünschte Funk­tio­na­li­tät bie­tet. Zum Bei­spiel die Stan­dard­bi­blio­thek, Boost oder Spe­zi­al­bi­blio­the­ken wie die CGAL. So spart man sich die zeit­rau­bende Neu­er­fin­dung des Rads und greift ein­fach auf jahr­zehn­te­lang bewähr­ten und opti­mier­ten Code zurück.

Zwei­tens: Wenn ein Algo­rith­mus sehr kom­pli­ziert ist, muss man sich manch­mal fra­gen was mehr kos­tet: Wochen­lang die­ses einen kryp­ti­schen Algo­rith­mus zu ver­ste­hen, zu schrei­ben, zu debug­gen? Oder einen ein­fa­che­ren Algo­rith­mus zu neh­men, der viel­leicht ein klei­nes biss­chen lang­sa­mer ist, dafür aber klar und ver­ständ­lich, oder gar schon fer­tig imple­men­tiert vorliegt.

Drit­tens: Man­che Algo­rith­men haben zwar eine theo­re­tisch bes­sere Lauf­zeit, d.h. brau­chen weni­ger Schritte - aber die ein­zel­nen Schritte sind der­art abstrus und auf­wen­dig, dass für rea­lis­ti­sche Pro­blem­grö­ßen ein ande­rer, eigent­lich lang­sa­me­rer, aber schlan­ke­rer Algo­rith­mus die Nase vorn hat.5

Daten­struk­tur

Neben der Wahl der zu ver­wen­den­den Algo­rith­men ist auch die Wahl der Daten­struk­tur ent­schei­dend. Bei einer ver­ket­te­ten Liste bei­spiels­weise kann man schnell ein Ele­ment ein­fü­gen - da wer­den intern nur ein paar Poin­ter umge­bo­gen und fer­tig. Bei einem Array sieht das anders aus, da müs­sen alle, mög­li­cher­weise viele, Ele­mente hin­ter der frag­li­chen Posi­tion um eins nach hin­ten ver­scho­ben werden.

Was bedeu­tet das in der Pra­xis? Man sollte die in der Stan­dard­bi­blio­thek zur Ver­fü­gung ste­hen­den Daten­struk­tu­ren ken­nen und wis­sen, wofür diese gut geeig­net sind und wofür nicht. Häu­fig ver­wen­dete Daten­struk­tu­ren bzw. Con­tai­ner aus der STL sind vec­tor und list. Die hier immer mal wie­der ver­linkte Refe­renz auf cplusplus.com ist übri­gens gene­rell toll, um sol­che Dinge nach­zu­schla­gen! Dort wird zu jedem Con­tai­ner erklärt, wofür er sich eig­net, außer­dem steht auf den Sei­ten zu den ein­zel­nen Funk­tio­nen deren Laufzeit.

Es gibt sicher noch mehr zu dem Thema zu sagen, als ich hier jetzt geschrie­ben habe - aber ich denke, die wich­tigs­ten Kon­zepte sind abge­deckt. Zusam­men­fas­send kann man eigent­lich das sagen, was man zum Thema Pro­gram­mie­ren immer sagen kann: Erst nach­den­ken, dann coden. ;)

  1. siehe Wikipedia:Goldener_Schnitt#Approximationseigenschaften_der_Goldenen_Zahl
  2. Das ist die berühmte Unix­zeit!
  3. Ein Name, den man als Pro­gram­mie­rer ken­nen sollte. Siehe Donald Ervin Knuth
  4. Pro­gram­mie­ren hat sehr viel mehr mit Nach­den­ken zu tun, als man gemein­hin so glaubt.
  5. Ich habe in der Tat mal ein Paper gele­sen, in dem exakt die­ses Pro­blem auf­ge­tre­ten war. Der ein­fa­che Algo­rith­mus war für alle prak­tisch rele­van­ten Pro­blem­grö­ßen schnel­ler als der super­tolle Algo­rith­mus mit der theo­re­tisch bes­se­ren Lauf­zeit.

Tags »

Trackback: Trackback-URL |  Feed zum Beitrag: RSS 2.0
Thema: Programmieren

Diesen Beitrag kommentieren.

Kommentar abgeben