<HTML>
<HEAD>
<!-- this stylesheet will later on be added by lfparser automatically: -->
<style type="text/css">
<!--
pre { font-family:monospace,Courier }
pre.code { font-family:monospace,Courier;background-color:#aedbe8; }
p.code { width:80%; alignment:center; background-color:#aedbe8;
border-style:none; border-width:medium; border-color:#aedbe8;
padding:0.1cm ; text-align:left }
-->
</style>
</HEAD>
<BODY>
<H1>Optimiser les programmes C/C+ + en utilisant GProf profiler</H1>
<H4>ArticleCategory:</H4>
Software Development
<H4>AuthorImage:</H4>
<IMG SRC="../../common/images2/ArnoutEngelen.png" ALT="Arnout Engelen" width="164" height="200">
<H4>TranslationInfo:</H4>
<P>original in en <A HREF="nospam:arnouten(Q)bzzt.net">Arnout Engelen</A> </P>
<p>en to fr <a href="nospam:fleuh - (at) - free.fr">Florent Morel</a></p>
<H4>AboutTheAuthor:</H4>
<P>
Arnout Engelen est �tudiant en informatique � l'universit� de Nijmegen,
Pays-Bas et est employ� chez TUNIX, une entreprise sp�cialis�e dans la
s�curit� Internet. Durant son temps libre, il aime courir et jouer du
saxophone.
</P>
<H4>Abstract:</H4>
Une des choses les plus importantes qu'il est bon de garder en t�te lorsque
l'on souhaite optimiser une application est : optimiser l� o� c'est utile.
Cela ne sert � rien de passer des heures � optimiser un morceau de code qui
met 0.04 secondes � s'ex�cuter.
<p>
GProf fournit une fa�on �tonnament simple de profiler (�tudier le temps
d'ex�cution) vos applications C/C++ et met en lumi�re les parties
int�ressantes tr�s rapidement. Une courte �tude de cas montre comment GProf
fut utilis� pour r�duire la dur�e d'ex�cution d'une application. En
identifiant 2 structures de donn�es importantes et en les optimisant, nous
sommes pass�s de 3 minutes � moins de 5 secondes.
<p>
Historiquement, le programme remonte � 1982, quand il fut introduit dans le
Symposium SIGPLAN sur la construction de compilateurs. C'est maintenant un
outil standard disponible sur pratiquement toutes les formes d'UNIX.
<H4>ArticleIllustration:</H4>
<IMG SRC="../../common/images2/article371/profilingpicture.png" ALT="Profiling with GProf" HSPACE=10 width="400" height="63">
<H4>ArticleBody:</H4>
<h2>Le Profiling en quelques mots</h2>
Le concept du profiling est vraiment tr�s simple : en enregistrant l'heure
d'entr�e et de sortie de chaque fonction, il est possible de calculer quelles
sont les parties du code qui prennent le plus de temps. Effectuer ces mesures
semble �tre une t�che n�cessitant beaucoup d'efforts - heureusement, ce n'est
pas le cas. C'est si simple qu'il suffit de compiler en rajoutant une option
gcc ('-pg'), lancer le programme (pour collecter les informations de
profiling) et de lancer 'gprof' sur le fichier contenant les statistiques
d'ex�cution afin de les pr�senter d'une mani�re plus agr�able.
<h2>Etude de cas : Pathalizer</h2>
<p>
Je vais prendre le cas d'une r�elle application, qui fait partie de
<a href="http://pathalizer.bzzt.net">pathalizer</a> : l'ex�cutable
<code>event2dot</code> qui traduit un fichier '�v�nements' de pathalizer en un
fichier contenant un graphique sous forme de points (format graphviz).
<p>
Pour r�sumer, il lit les �v�nements depuis un fichier, les stocke sous forme
de graphes (les pages sont transpos�es en noeuds et les transitions entre
pages en bords). Cette collection de graphes est ensuite 'condens�e' en un
gros graphe qui est imprim� sous forme de points au format graphviz.
<h3>Mesurer le temps d'ex�cution de l'application</h3>
En premier lieu, nous lan�ons le programme que nous voulons optimiser sans
profiling et mesurons le temps d'ex�cution. Les sources utilis�es sont
fournies ainsi qu'un fichier exemple d'entr�e d'une taille consid�rable
(55 000 lignes).
<p>
Sur ma machine, l'ex�cution de <code>event2dot</code> met plus de 3 minutes
avec ce fichier :
<pre class="code">
real 3m36.316s
user 0m55.590s
sys 0m1.070s
</pre>
<h3>Le profiling</h3>
Pour permettre le profiling, il suffit d'ajouter l'option '-pg' lors de la
compilation. Recompilons donc l'application avec cette option :
<pre class="code">
g++ -pg dotgen.cpp readfile.cpp main.cpp graph.cpp config.cpp -o event2dot
</pre>
<p>
Nous pouvons maintenant lancer <code>event2dot</code> � nouveau sur notre
fichier � test-events �. Durant cette ex�cution, les informations de profiling
concernant <code>event2dot</code> vont �tre r�cup�r�es et un fichier
'gmon.out' sera g�n�r�. Visualisons les r�sultats en lan�ant
'gprof <code>event2dot</code> | less'.
<p>
gprof montre que les fonctions suivantes sont importantes :
<pre class="code">
% 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 *)
</pre>
La colonne la plus int�ressante est la premi�re : il s'agit du pourcentage
de temps d'ex�cution du programme pris par cette fonction.
<h3>L'optimisation</h3>
Cela montre que le programme passe presque la moiti� du temps dans la
fonction <code>CompareNodes</code>. Un rapide grep montre que CompareNodes
n'est appel�e que par <code>CompareEdges</code>, qui elle-m�me n'est appel�e
que par <code>addAnnotatedEdge</code> - ces deux fonctions �tant aussi dans
la liste. Cela semble donc �tre un bon point de d�part pour r�aliser
l'optimisation.
<p>
Nous avons remarqu� que <code>addAnnotatedEdge</code> traverse une liste
cha�n�e. Bien que facile � impl�menter, une liste cha�n�e n'est pas le
meilleur type de donn�es. Nous d�cidons de remplacer g->edges par un arbre
binaire : cela devait permettre d'acc�l�rer sensiblement les recherches, en
laissant la possibilit� de le parcourir.
<h3>R�sultats</h3>
Nous pouvons remarquer la r�duction du temps d'ex�cution :
<pre class="code">
real 2m19.314s
user 0m36.370s
sys 0m0.940s
</pre>
<h3>Second passage</h3>
Lancer gprof � nouveau r�v�le :
<pre class="code">
% 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 *)
</pre>
Il semble que les fonctions qui prenaient plus de la moiti� du temps ont
maintenant �t� r�duites � une dur�e n�gligeable ! Essayons � nouveau :
rempla�ons NodeList par une NodeHashTable.
<p>
C'est aussi une r�elle am�lioration :
<pre class="code">
real 0m3.269s
user 0m0.830s
sys 0m0.090s
</pre>
<h2>Autres profilers C/C++</h2>
<img src="../../common/images2/article371/shot.png" align="right" width="565" height="337">
Plusieurs profilers disponibles utilisent les donn�es de gprof, c'est le cas
de <a href="http://kprof.sf.net">KProf</a> (capture d'�cran) et de
<a href="http://mvertes.free.fr/">cgprof</a>. Bien que l'interface graphique
soit agr�able, je pense que la ligne de commande de gprof est plus efficace.
<br clear="all">
<h2>Profiling avec d'autres langages</h2>
Ce tutoriel pr�sente le profiling d'applications C/C++ avec gprof, mais il
est possible de le faire pour d'autres langages : pour Perl, utilisez le
module Devel::DProf. Lancez l'application avec
<code>perl -d:DProf mycode.pl</code> et visualsez les r�sultats avec
<code>dprofpp</code>. Si vous pouvez compiler vos programmes Java avec gcj,
vous pouvez utiliser gprof, bien que l'utilisation soit limit�e � une seule
thread.
<h2>Conclusion</h2>
Nous avons vu que, en utilisant le profiling, il est possible de trouver des
portions d'une application pouvant b�n�ficier d'une optimisation. En
optimisant l� o� c'est utile, nous avons r�duit le temps d'ex�cution de
l'application test�e de 3min36s � moins de 5 secondes.
<h2>R�f�rences</h2>
<ul>
<li>Pathalizer: <a
href="http://pathalizer.sf.net">http://pathalizer.sf.net</a><br><br>
<li>KProf: <a
href="http://kprof.sf.net">http://kprof.sf.net</a><br><br>
<li>cgprof: <a
href="http://mvertes.free.fr">http://mvertes.free.fr</a><br><br>
<li>Devel::DProf <a
href="http://www.perldoc.com/perl5.8.0/lib/Devel/DProf.html">http://www.perldoc.com/perl5.8.0/lib/Devel/DProf.html</a><br><br>
<li>gcj: <a
href="http://gcc.gnu.org/java">http://gcc.gnu.org/java</a><br><br>
<li>Fichiers d'exemples de pathalizer : <a
href="../../common/src2/article371">download for article371</a><br><br>
</ul>
</BODY>
</HTML>
<!-- vim: set sw=2 ts=2 et tw=74: -->