2026_TD1_DEV51_Qualite_Algo/COMPTE_RENDU.md

Compte rendu — TD 1 : utilisation de gprof

Nathan COUCHOT et Lucas POT

1. Mesurer le programme sans instrumentation

La mesure sans profiler se réalise avec les commandes suivantes, depuis le dossier du programme :

gcc -O0 analyseur.c -o analyseur
time ./analyseur

La nouvelle exécution sans -pg, sur le même volume de texte que le profil, donne :

Mesure	Temps
Temps réel (real)	1,200 s
Temps CPU utilisateur (user)	1,164 s
Temps CPU système (sys)	0,022 s

L'empreinte du rapport est 03c7b78f93838d02. Cette empreinte sert de référence pour vérifier que le résultat reste identique lors d'une comparaison effectuée avec les mêmes données.

Les dix mots les plus fréquents sont :

Rang	Mot	Occurrences
1	rane	2 811
2	fasi	2 399
3	mopo	2 161
4	tata	2 086
5	vesi	1 979
6	laganomo	1 784
7	boto	1 697
8	nopebo	1 653
9	cofi	1 612
10	siri	1 593

2. Compiler avec -pg et produire le profil

Pour activer l'instrumentation de gprof, on compile avec -O0 -pg, puis on exécute le programme et on génère le profil :

gcc -O0 -pg analyseur.c -o analyseur
time ./analyseur
gprof ./analyseur gmon.out > profil_avant.txt

On passe d'une mesure de 1,200 s sans -pg à un temps réel relevé de 2,750 s avec -pg, soit une durée environ 2,29 fois plus longue et un écart de 1,550 s (environ 129 % d'augmentation). Le profil affiche cependant seulement 0,91 s de temps effectif estimé dans les fonctions analysées.

L'option -pg ajoute du travail à chaque entrée dans une fonction pour compter les appels. Avec des dizaines de millions d'appels à de petites fonctions, ce surcoût devient très important : le profiling perturbe donc fortement la durée d'exécution.

3. Analyser le profil plat et le graphe d'appels

Profil plat : où passe le temps ?

Le profil plat indique le temps propre de chaque fonction, sans le temps de ses fonctions appelées. Les principaux résultats de profil_avant.txt sont :

Fonction	Part du temps propre	Temps propre affiché	Nombre d'appels
egales	28,02 %	0,26 s	121 889 737
est_mot_vide	13,74 %	0,12 s	2 500 000
analyser_bigrammes	12,09 %	0,11 s	1
decouper_lignes	7,69 %	0,07 s	1
generer_texte	6,59 %	0,06 s	1
est_lettre	5,49 %	0,05 s	52 929 320

La fonction egales est le principal point chaud : elle compare des chaînes et représente environ 28 % du temps propre mesuré. Son coût vient surtout de son nombre d'appels, supérieur à 121 millions.

analyser_bigrammes, decouper_lignes et generer_texte ne sont appelées qu'une fois, mais parcourent de grandes quantités de données. Elles peuvent donc consommer un temps significatif malgré leur faible nombre d'appels.

Graphe d'appels : pourquoi ces fonctions coûtent-elles du temps ?

main appelle compter_mots_ligne, qui vérifie chaque mot avec est_mot_vide avant de le compter. Cette étape représente environ 51 % du temps du profil, fonctions appelées comprises.

Pour vérifier si un mot est vide, est_mot_vide le compare aux éléments d'une liste de 60 mots avec egales. Comme cette vérification est répétée pour les 2 500 000 mots du texte, elle entraîne plus de 120 millions de comparaisons et représente environ 41 % du temps du profil.

Le principal coût vient donc de la vérification des mots vides.

4. Proposer des améliorations

Les pistes suivantes sont classées par gain attendu :

1. Optimiser est_mot_vide. Regrouper les mots vides par longueur et première lettre éviterait de parcourir toute la liste et réduirait fortement les appels à egales.

2. Optimiser longueur_moyenne. Mémoriser la longueur des mots et réutiliser la moyenne dans ecart_type_longueur éviterait des parcours inutiles. Le gain attendu est plus faible.

5. Optimisations réalisées

Dans est_mot_vide, les 60 mots vides sont regroupés une seule fois par longueur et première lettre. Pour chaque mot du texte, seules les chaînes du groupe correspondant sont comparées avec egales. La longueur est déjà connue lors du découpage du mot.

La longueur de chaque mot compté est aussi mémorisée dans la table pour calculer les statistiques. La moyenne déjà calculée est transmise à ecart_type_longueur pour éviter de la recalculer.

6. Vérifier les résultats et mesurer le gain

Après compilation avec gcc -O0 -pg analyseur.c -o analyseur, deux exécutions donnent :

Mesure	Après : essai 1	Après : essai 2
Temps réel	1,200 s	1,231 s
Temps CPU utilisateur	1,147 s	1,183 s
Temps CPU système	0,016 s	0,019 s

Le temps réel moyen avec -pg est de 1,216 s, contre 2,750 s avant optimisation, soit environ 55,8 % de temps en moins et une exécution 2,26 fois plus rapide. Cette comparaison concerne les versions instrumentées : elle inclut la réduction du surcoût de -pg grâce aux appels supprimés.

La comparaison de profil_avant.txt et profil_après.txt confirme la réduction du travail :

Mesure du profil	Avant	Après
Temps total estimé par gprof	0,91 s	0,45 s
Appels à egales	121 889 737	3 413 876
Temps propre de egales	0,26 s	0,02 s
Temps propre de est_mot_vide	0,12 s	0,02 s
Appels à longueur	39 162	20 994
Appels à longueur_moyenne	2	1

Les appels à egales diminuent d'environ 97 %. Les 60 appels à longueur ajoutés par l'initialisation des groupes expliquent le passage de 20 934 appels après la seule optimisation des statistiques à 20 994 dans la version finale.

L'empreinte reste 03c7b78f93838d02 dans les deux exécutions. Le Top 10 et les statistiques affichées restent identiques.