C/C++-Programme optimieren mit dem Profiler gprof

ArticleCategory:

Software Development

AuthorImage:

TranslationInfo:

AboutTheAuthor:

Arnout Engelen studiert Informatik an der Universit�t von Nijmegen (Niederlande) und ist bei TUNIX besch�ftigt, einer Internet-Sicherheitsfirma. In seiner Freizeit l�uft er lange Strecken und spielt Tenorsaxophon.

Abstract:

Eine der wichtigsten Sachen, die man im Kopf behalten mu�, wenn man eine Applikation optimiert, ist: optimiere dort, wo es z�hlt. Es n�tzt nichts, stundenlang ein St�ck Code zu optimieren, das sowieso nur w�hrend 0,04 Sekunden l�uft.

gprof bietet einen �berraschend einfachen Weg, deine C/C++-Applikation zu profilieren und die interessanten Stellen gleich zu finden. Eine kleine Fallstudie zeigt, wie mittels gprof die Laufzeit einer realen Applikation von �ber 3 Minuten auf unter 5 Sekunden reduziert wurde, indem zwei Datenstrukturen als wichtig erkannt und optimiert wurden.

Historisch gesehen reicht das Programm bis 1982 zur�ck, als es auf dem SIGPLAN-Symposion �ber Compilerbau vorgestellt wurde. Es ist inzwischen ein Standardwerkzeug, das es auf praktisch allen UNIX-Arten gibt.

ArticleIllustration:

ArticleBody:

Profiling kurz und b�ndig

Das Konzept des Profiling ist sehr einfach: Indem man festh�lt, zu welchen Zeiten ein Programm Funktionen betritt und verl��t, ist es m�glich zu berechnen, in welchen Teilen des Programms es sich die meiste Zeit aufh�lt. Die Durchf�hrung dieser Messung klingt jetzt nach etwas, das viel M�he kostet - gl�cklicherweise ist dem nicht so! Man mu� lediglich mit einer zus�tzlichen gcc-Option kompilieren (-pg), das Programm laufen lassen (um die Daten f�r das Profiling zu erzeugen) und gprof mit der erzeugten Statistikdatei aufrufen, um sie in einer komfortableren Art darzustellen.

Fallstudie: Pathalizer

Ich benutze hier eine reale Applikation als Beispiel, einen Teil von pathalizer: das Programm event2dot, das eine „events“-Datei von Pathalizer in eine „dot“-Datei von graphviz �bersetzt.

Kurz gesagt, liest es die Ereignisse aus einer Datei und speichert sie als Graphen (mit den Seiten als Knoten und mit den �berg�ngen zwischen Seiten als Kanten). Diese Graphensammlung wird dann in einen gro�en Graph im graphviz „dot“-Format „zusammengefa�t“.

Zeitmessung der Applikation

Zuerst starten wir das Programm, das wir optimieren wollen, ohne Profiling und messen, wie lange es braucht. Die Programmquellen f�r das Beispiel sind ebenso wie Beispieldaten von betr�chtlicher Gr��e (55.000 Zeilen) verf�gbar.

Auf meinem Rechner dauerte ein Lauf von event2dot mehr als drei Minuten auf diesen Daten:

real    3m36.316s
user    0m55.590s
sys     0m1.070s

Das Profiling

Profiling mit gprof wird eingeschaltet, indem man die Option -pg zum Kompiliervorgang hinzuf�gt. Wir kompilieren die Applikation also:

g++ -pg dotgen.cpp readfile.cpp main.cpp graph.cpp config.cpp -o event2dot

Wir k�nnen jetzt event2dot abermals auf unserer Testdatei rechnen lassen. W�hrenddessen wird Profiling-Information zu event2dot gesammelt und eine Datei „gmon.out“ generiert. Wir sehen uns das Ergebnis mittels gprof event2dot | less an.

gprof zeigt uns jetzt die wichtigsten Funktionen:

 % cumulative  self              self     total           
 time seconds  seconds  calls s/call s/call name    
43.32   46.03  46.03 339952989  0.00  0.00 CompareNodes(Node *,Node *)
25.06   72.66  26.63    55000   0.00  0.00 getNode(char *,NodeListNode *&)
16.80   90.51  17.85 339433374  0.00  0.00 CompareEdges(Edge *,AnnotatedEdge *)
12.70  104.01  13.50    51987   0.00  0.00 addAnnotatedEdge(AnnotatedGraph *,Edge *)
 1.98  106.11   2.10    51987   0.00  0.00 addEdge(Graph *,Node *,Node *)
 0.07  106.18   0.07        1   0.07  0.07 FindTreshold(AnnotatedEdge *,int)
 0.06  106.24   0.06        1   0.06 28.79 getGraphFromFile(char *,NodeListNode *&,Config *)
 0.02  106.26   0.02        1   0.02 77.40 summarize(GraphListNode *,Config *)
 0.00  106.26   0.00    55000   0.00  0.00 FixName(char *)

Die interessanteste Spalte ist die erste: Das ist der prozentuale Anteil dieser Funktion an der gesamten Programmlaufzeit.

Die Optimierung

Das Programm verbringt demnach fast die H�lfte seiner Zeit in CompareNodes. Ein schnelles grep zeigt, da� CompareNodes nur von CompareEdges aufgerufen wird, welches wiederum nur von addAnnotatedEge benutzt wird - diese beiden befinden sich auch in der Liste. Das sieht nach einer interessanten Stelle zur Optimierung aus.

Wir stellen fest, da� addAnnotatedEdge eine verlinkte Liste durchl�uft. Obwohl eine verlinkte Liste einfach zu implementieren ist, ist sie nicht die beste aller Datenstrukturen. Wir entscheiden, g->edges durch einen Bin�rbaum zu ersetzen: Das sollte die Suche in der Struktur stark beschleunigen und trotzdem einen Durchgang erm�glichen.

Ergebnisse

Wir sehen, da� die Ausf�hrungszeit tats�chlich reduziert wird:

real    2m19.314s
user    0m36.370s
sys     0m0.940s

Ein zweiter Lauf

Der nochmalige Lauf von gprof offenbart:

%   cumulative self           self    total           
 time   seconds seconds calls  s/call  s/call name    
87.01     25.25  25.25  55000    0.00    0.00 getNode(char *,NodeListNode *&)
10.65     28.34   3.09  51987    0.00    0.00 addEdge(Graph *,Node *,Node *)

Eine Funktion, die bislang �ber die H�lfte der Zeit verbraucht hat, wurde bis in die Irrelevanz reduziert! Das wollen wir noch einmal versuchen: Wir ersetzen die NodeList durch eine NodeHashTable.

Auch das ist eindeutig eine gro�e Verbesserung:

real    0m3.269s
user    0m0.830s
sys     0m0.090s

Andere Profiler f�r C/C++

Es gibt einige Profiler, die die Daten von gprof benutzen, z.B. KProf (Screenshot) und cgprof. Obwohl die graphischen Ansichten eine nette Sache sind, finde ich pers�nlich gprof auf der Kommandozeile praktischer.

Profiling von anderen Sprachen

Wir haben nun das Profiling von C/C++-Applikationen mit gprof besprochen, aber �hnliches kann auch mit anderen Sprachen gemacht werden. F�r Perl kannst du das Modul Devel::DProf benutzen. Starte deine Applikation mit perl -d:DProf mycode.pl und sieh die Ergebnisse mit dprofpp an. Wenn du deine Java-Programme mit gcj kompilieren kannst, kannst du einfach gprof benutzen, es wird zur Zeit jedoch nur Java-Code mit einem einzigen Thread unterst�tzt.

Fazit

Wir haben gesehen, da� wir durch Profiling schnell die Teile einer Applikation finden k�nnen, die von einer Optimierung profitieren w�rden. Indem wir dort optimierten, wo es drauf ankam, haben wir die Laufzeit des Beispielprogramms von 3:36 Minuten auf weniger als f�nf Sekunden gesenkt.