rabot
36 KiB
Journal des mesures et optimisations
Ce journal conserve les commandes et sorties historiques, avec les chemins utilisés au moment des mesures. Les liens vers les profils et les données pointent vers leur emplacement actuel. Pour compiler et exécuter le projet avec la nouvelle arborescence, voir le README.
Lancement du programme après la compilation avec gcc -O0 analyseur.c -o analyseur
Lignes analysées : 21746
Mots au total : 250000
Mots distincts : 5866
Longueur moyenne : 6.712 (écart-type 1.873)
Bigramme le + courant : "me" (17607 fois, souvent suivi de 'n')
Top 10 :
1. rane 287
2. fasi 241
3. tata 219
4. mopo 214
5. cofi 180
6. vesi 179
7. laganomo 177
8. boto 172
9. nopebo 169
10. rotion 165
Empreinte du rapport : 1d53de903efd2b7c
Et ensuite la commande time sur l'exécutable avec time ./analyseur
Lignes analysées : 21746
Mots au total : 250000
Mots distincts : 5866
Longueur moyenne : 6.712 (écart-type 1.873)
Bigramme le + courant : "me" (17607 fois, souvent suivi de 'n')
Top 10 :
1. rane 287
2. fasi 241
3. tata 219
4. mopo 214
5. cofi 180
6. vesi 179
7. laganomo 177
8. boto 172
9. nopebo 169
10. rotion 165
Empreinte du rapport : 1d53de903efd2b7c
real 0m2.858s
user 0m2.821s
sys 0m0.013s
On recompile avec le flag -pg : gcc -O0 -pg analyseur.c -o analyseur
Et on relance time dessus
Lignes analysées : 21746
Mots au total : 250000
Mots distincts : 5866
Longueur moyenne : 6.712 (écart-type 1.873)
Bigramme le + courant : "me" (17607 fois, souvent suivi de 'n')
Top 10 :
1. rane 287
2. fasi 241
3. tata 219
4. mopo 214
5. cofi 180
6. vesi 179
7. laganomo 177
8. boto 172
9. nopebo 169
10. rotion 165
Empreinte du rapport : 1d53de903efd2b7c
real 0m6.354s
user 0m6.295s
sys 0m0.020s
On lance gprof : gprof -b ./analyseur gmon.out > profil_avant.txt
Optimisation de chercher_mot : recherche dichotomique
La recherche initiale parcourait toutes les entrées jusqu'à trouver le mot.
Pour 150 182 recherches, elle effectuait 296 656 203 appels à egales().
Le tableau est maintenant maintenu dans l'ordre alphabétique pendant le
comptage. chercher_mot utilise comparer() pour éliminer la moitié des
entrées restantes à chaque étape : la recherche passe de O(n) à O(log n).
Si le mot est absent, la fonction renvoie -(position d'insertion + 1) ;
compter_mot retrouve cette position avec -indice - 1, décale les entrées
et insère le nouveau mot. Cette insertion reste en O(n), mais elle n'a lieu
qu'à la première apparition de chacun des 5 866 mots distincts.
Le tableau existant est réutilisé, sans allocation supplémentaire.
Le tri final par fréquence produit le même classement.
Résultats du nouveau profil, conservé dans 01_dichotomie.txt :
| Mesure | Avant | Après |
|---|---|---|
Appels de chercher_mot |
150 182 | 150 182 |
Appels à egales() depuis chercher_mot |
296 656 203 | 0 |
Comparaisons de chaînes dans chercher_mot |
296 656 203 | 1 718 447 |
Appels à egales() dans tout le programme |
308 701 874 | 12 045 671 |
Temps réel sans profiling (gcc -O0) |
2,80 s | 1,45 s |
Les recherches effectuent environ 173 fois moins de comparaisons.
Les appels restants à egales() viennent de est_mot_vide.
Les temps ci-dessus correspondent à une mesure avant/après sur la même
machine pendant cette modification : environ 48 % de temps en moins
(accélération d'environ 1,93). Ce sont des mesures ponctuelles.
Validation : compilation avec -Wall -Wextra -Wpedantic, rapport et sortie
console identiques octet par octet à la version initiale, avec et sans -pg.
L'empreinte reste 1d53de903efd2b7c.
Un test temporaire sous AddressSanitizer et UndefinedBehaviorSanitizer a
également vérifié les recherches dans un tableau vide, les mots présents
ou absents, les insertions au début/milieu/fin, les doublons et les mots de
31 caractères, puis comparé 10 000 comptages à une référence linéaire.
Pour reproduire le profil sans écraser les fichiers du profil initial :
mkdir -p out/apres
gcc -O0 -pg analyseur.c -o out/apres/analyseur
(cd out/apres && ./analyseur && gprof -b ./analyseur gmon.out > ../profil_apres.txt)
Lignes analysées : 21746
Mots au total : 250000
Mots distincts : 5866
Longueur moyenne : 6.712 (écart-type 1.873)
Bigramme le + courant : "me" (17607 fois, souvent suivi de 'n')
Top 10 :
1. rane 287
2. fasi 241
3. tata 219
4. mopo 214
5. cofi 180
6. vesi 179
7. laganomo 177
8. boto 172
9. nopebo 169
10. rotion 165
Empreinte du rapport : 1d53de903efd2b7c
real 0m1.986s
user 0m1.934s
sys 0m0.011s
Optimisation des appels à longueur_moyenne
longueur_moyenne parcourt les mots une fois par appel. Le coût excessif
venait de ecart_type_longueur, qui recalculait cette même moyenne à
chaque itération, soit 5 866 fois. Avec l'appel de main, cela représentait
5 867 calculs de moyenne et 34 415 822 appels à longueur().
main calcule désormais la moyenne une seule fois et la transmet en
paramètre à ecart_type_longueur. La boucle utilise directement cette
valeur. Le calcul des statistiques passe ainsi de O(n²) à O(n), sans
allocation supplémentaire ni modification de la formule de variance.
Profil enregistré dans 02_moyenne.txt.
La colonne « Avant » correspond à la version déjà optimisée pour
chercher_mot, dont le profil reste dans ../resultats/profils/01_dichotomie.txt.
| Mesure | Avant | Après |
|---|---|---|
Appels à longueur_moyenne |
5 867 | 1 |
Appels à longueur() depuis longueur_moyenne |
34 415 822 | 5 866 |
Appels à longueur() dans tout le programme |
36 009 819 | 1 599 863 |
Temps réel sans profiling (gcc -O0) |
1,46 s | 0,88 s |
Cette mesure ponctuelle sur la même machine donne environ 40 % de temps en moins, soit une accélération d'environ 1,66 par rapport à l'étape précédente.
Validation : compilation avec -Wall -Wextra -Wpedantic sans avertissement,
puis comparaison du rapport et de la sortie console avant/après, avec et
sans -pg. Ils restent identiques octet par octet, y compris la moyenne
(6.712) et l'écart-type (1.873). L'empreinte reste 1d53de903efd2b7c.
Commandes pour reproduire ce profil :
mkdir -p out/apres_moyenne
gcc -O0 -pg analyseur.c -o out/apres_moyenne/analyseur
(cd out/apres_moyenne && ./analyseur && gprof -b ./analyseur gmon.out > ../profil_apres_moyenne.txt)
[rabot@salle235-06 out]$ time ./analyseur
Lignes analysées : 21746
Mots au total : 250000
Mots distincts : 5866
Longueur moyenne : 6.712 (écart-type 1.873)
Bigramme le + courant : "me" (17607 fois, souvent suivi de 'n')
Top 10 :
1. rane 287
2. fasi 241
3. tata 219
4. mopo 214
5. cofi 180
6. vesi 179
7. laganomo 177
8. boto 172
9. nopebo 169
10. rotion 165
Empreinte du rapport : 1d53de903efd2b7c
real 0m1.251s
user 0m1.214s
sys 0m0.004s
Remplacement de la dichotomie par une table de hachage
Un index de 40 001 cases associe chaque mot à son entrée dans le tableau.
hacher_mot calcule un entier à partir des caractères du mot ; le modulo
donne la première case à examiner. Chaque case contient l'indice de
l'entrée + 1, ou zéro si elle est libre.
En cas de collision, chercher_mot vérifie le mot avec egales() puis
avance à la case suivante, en revenant au début si nécessaire. Deux mots
ayant le même hachage restent donc bien distincts. Les nouveaux mots sont
ajoutés à la fin du tableau, sans décaler les entrées existantes.
La recherche et l'insertion sont en O(1) en moyenne pour ces mots de longueur bornée, avec un pire cas en O(n) en cas de nombreuses collisions. La limite de 20 000 mots distincts est vérifiée avant chaque nouvelle insertion ; avec 40 001 cases, l'index reste rempli à moins de 50 %.
Ce choix ajoute 40 001 * sizeof(int) octets, soit environ 156 Kio sur
cette machine. L'index est libéré après le comptage, avant le tri final
qui déplace les entrées. L'empreinte du rapport est conservée, mais cette
version utilise davantage de mémoire pendant le comptage.
Profil enregistré dans 03_hachage.txt.
La comparaison porte sur la version précédente avec dichotomie et moyenne
calculée une seule fois, conservée dans ../resultats/profils/02_moyenne.txt.
| Mesure | Dichotomie | Hachage |
|---|---|---|
Appels de chercher_mot |
150 182 | 150 182 |
Comparaisons de chaînes dans chercher_mot |
1 718 447 (comparer) |
153 101 (egales) |
Temps réel médian sans profiling (gcc -O0, 5 exécutions par version) |
0,888 s | 0,831 s |
Les recherches font environ 11,2 fois moins de comparaisons. Le temps total baisse d'environ 6,4 % : le gain reste limité car la normalisation et le tri occupent désormais l'essentiel du temps. L'ordre d'arrivée des mots remplace l'ordre alphabétique pendant le comptage ; le tri final effectue donc un nombre différent de comparaisons, tout en produisant le même classement.
Les cinq mesures, réalisées en alternant les deux versions sur la même machine, sont respectivement : 0,883 / 0,892 / 0,888 / 0,883 / 0,888 s avant, et 0,831 / 0,830 / 0,831 / 0,832 / 0,829 s après.
Validation : compilation sans avertissement avec -Wall -Wextra -Wpedantic,
rapport et sortie console identiques octet par octet sur les dix
exécutions et avec -pg. L'empreinte reste 1d53de903efd2b7c.
Des tests temporaires sous AddressSanitizer et UndefinedBehaviorSanitizer
ont vérifié les collisions avec retour à la première case, les doublons,
les mots de 0/1/31 caractères, 10 000 comptages comparés à une référence
linéaire, les 20 000 entrées possibles et le refus d'un dépassement.
Le programme complet a également été exécuté avec ces deux outils,
sans erreur et avec une sortie identique.
Commandes pour reproduire ce profil :
mkdir -p out/apres_hachage
gcc -O0 -pg analyseur.c -o out/apres_hachage/analyseur
(cd out/apres_hachage && ./analyseur && gprof -b ./analyseur gmon.out > ../profil_apres_hachage.txt)
Longueurs mémorisées et suppression des parcours répétés
Le champ taille de Entree mémorise la longueur du mot à son insertion.
La valeur vient directement de k, déjà calculé dans compter_mots_ligne :
aucun parcours supplémentaire n'est nécessaire. La moyenne et la variance
lisent désormais ce champ. Le tri déplace l'entrée entière, donc la longueur
reste associée au bon mot. Pour un mot tronqué, la taille enregistrée est
celle du mot conservé, soit au maximum 31 caractères.
Deux autres changements éliminent les recalculs sur les chaînes longues :
normaliser_lignes'arrête directement surligne[i] == '\0'. Le parcours d'une ligne de L caractères passe de O(L²) à O(L).ajouterreçoit une position de fin, qu'il avance pendant la copie des caractères ajoutés. Cette position est conservée lors de la construction du rapport et réinitialisée pour chaque mot du vocabulaire. Le préfixe déjà construit n'est plus parcouru à chaque ajout.
La fonction longueur, devenue inutilisée, a été supprimée.
Le champ supplémentaire fait passer sizeof(Entree) de 36 à 40 octets sur
cette machine : le tableau alloué pour 20 000 entrées prend 80 000 octets
supplémentaires, soit environ 78 Kio.
Profil enregistré dans 04_longueurs.txt.
La version précédente, avec la table de hachage, est décrite dans
../resultats/profils/03_hachage.txt.
| Mesure | Avant | Après |
|---|---|---|
Appels à longueur() depuis les statistiques |
11 732 | 0 |
Appels à longueur() depuis normaliser_ligne |
1 561 330 | 0 |
Appels à longueur() depuis ajouter |
26 801 | 0 |
Appels à longueur() au total |
1 599 863 | 0 |
Temps réel médian sans profiling (gcc -O0, 5 exécutions par version) |
0,832 s | 0,362 s |
Le temps total baisse de 56,5 %, soit une accélération d'environ 2,30. Cette mesure porte sur l'ensemble des trois changements, et ne doit pas être attribuée uniquement au stockage de la longueur des mots.
Les cinq mesures, réalisées en alternant les deux versions sur la même machine, sont respectivement : 0,835 / 0,838 / 0,830 / 0,832 / 0,829 s avant, et 0,362 / 0,369 / 0,366 / 0,362 / 0,361 s après.
Validation : compilation sans avertissement avec -Wall -Wextra -Wpedantic,
rapport et sortie console identiques octet par octet sur les dix exécutions,
avec -pg et sous AddressSanitizer et UndefinedBehaviorSanitizer.
L'empreinte reste 1d53de903efd2b7c, la moyenne 6.712 et l'écart-type
1.873. Des tests temporaires ont également vérifié les ajouts vides et
successifs jusqu'à la limite d'un tampon, la normalisation, les longueurs
avant/après tri, les statistiques, le rapport vide et les mots tronqués.
Commandes pour reproduire ce profil :
mkdir -p out/apres_longueurs
gcc -O0 -pg analyseur.c -o out/apres_longueurs/analyseur
(cd out/apres_longueurs && ./analyseur && gprof -b ./analyseur gmon.out > ../profil_apres_longueurs.txt)
[rabot@salle235-06 out]$ time ./analyseur
Lignes analysées : 21746
Mots au total : 250000
Mots distincts : 5866
Longueur moyenne : 6.712 (écart-type 1.873)
Bigramme le + courant : "me" (17607 fois, souvent suivi de 'n')
Top 10 :
1. rane 287
2. fasi 241
3. tata 219
4. mopo 214
5. cofi 180
6. vesi 179
7. laganomo 177
8. boto 172
9. nopebo 169
10. rotion 165
Empreinte du rapport : 1d53de903efd2b7c
real 0m0.751s
user 0m0.703s
sys 0m0.004s
Remplacement du tri à bulles par un tri par tas
Le tri à bulles effectuait systématiquement n(n - 1)/2 comparaisons,
soit 17 202 045 appels à doit_echanger pour 5 866 mots distincts.
trier_entrees utilise maintenant un tri par tas. La racine du tas contient
l'entrée qui doit apparaître le plus tard dans le classement. Elle est
échangée avec la dernière entrée de la partie non triée, puis retablir_tas
restaure cette propriété sur les entrées restantes. La construction du tas
coûte O(n), puis les extractions coûtent O(log n) chacune : le tri complet
passe de O(n²) à O(n log n), y compris dans le pire cas.
Le tri travaille directement dans le tableau, avec O(1) de mémoire
supplémentaire. doit_echanger reste inchangée : fréquence décroissante,
puis ordre alphabétique croissant. Chaque échange déplace l'entrée entière,
y compris la longueur mémorisée.
Profil enregistré dans 05_tri.txt.
La comparaison porte sur la version précédente, décrite dans
../resultats/profils/04_longueurs.txt.
| Mesure | Tri à bulles | Tri par tas |
|---|---|---|
Appels à doit_echanger pendant le tri |
17 202 045 | 129 602 |
Appels à comparer pour départager les fréquences égales |
12 172 087 | 32 813 |
Temps réel médian du programme sans profiling (gcc -O0, 5 exécutions par version) |
0,367 s | 0,113 s |
Le tri effectue environ 133 fois moins de comparaisons d'entrées. Le temps total baisse de 69,3 %, soit une accélération d'environ 3,25. Les cinq mesures, réalisées en alternant les deux versions sur la même machine, sont respectivement : 0,365 / 0,363 / 0,372 / 0,383 / 0,367 s avant, et 0,112 / 0,113 / 0,115 / 0,113 / 0,112 s après.
Validation : compilation sans avertissement avec -Wall -Wextra -Wpedantic,
rapport et sortie console identiques octet par octet sur les dix exécutions,
avec -pg et sous AddressSanitizer et UndefinedBehaviorSanitizer.
L'empreinte reste 1d53de903efd2b7c.
Des tests temporaires ont comparé le résultat à qsort sur des tableaux
de 0 à 20 000 entrées, aléatoires, déjà triés ou inversés. Ils vérifient
aussi les fréquences égales, les doublons, les préfixes, les valeurs
extrêmes de fréquence et la conservation des longueurs des mots.
Commandes pour reproduire ce profil :
mkdir -p out/apres_tri
gcc -O0 -pg analyseur.c -o out/apres_tri/analyseur
(cd out/apres_tri && ./analyseur && gprof -b ./analyseur gmon.out > ../profil_apres_tri.txt)
[rabot@salle235-06 out]$ time ./analyseur
Lignes analysées : 21746
Mots au total : 250000
Mots distincts : 5866
Longueur moyenne : 6.712 (écart-type 1.873)
Bigramme le + courant : "me" (17607 fois, souvent suivi de 'n')
Top 10 :
1. rane 287
2. fasi 241
3. tata 219
4. mopo 214
5. cofi 180
6. vesi 179
7. laganomo 177
8. boto 172
9. nopebo 169
10. rotion 165
Empreinte du rapport : 1d53de903efd2b7c
real 0m0.354s
user 0m0.314s
sys 0m0.008s
Réduction des vérifications dans analyser_bigrammes
L'ancienne boucle examinait des fenêtres de trois caractères et appelait
est_lettre jusqu'à trois fois par fenêtre. Les caractères des fenêtres
voisines étaient donc vérifiés plusieurs fois, pour un total de
3 757 672 appels dans cette fonction.
Les lignes sont déjà normalisées avant l'analyse : elles ne contiennent
que des lettres de a à z et des espaces. La nouvelle boucle utilise
cette propriété, explicitée dans le commentaire de la fonction, et
conserve les indices des deux lettres précédentes. Chaque nouvelle lettre
complète un trigramme si deux lettres la précèdent. Un espace ou une
nouvelle ligne réinitialise cet historique.
Les trigrammes qui se chevauchent sont conservés, sans compter à travers les séparateurs. Le calcul du meilleur bigramme et les règles de départage restent identiques. Les deux versions sont en O(nombre de caractères) : le gain vient des vérifications et des appels évités, sans tableau supplémentaire.
Profil enregistré dans 06_bigrammes.txt.
La comparaison porte sur la version précédente, décrite dans
../resultats/profils/05_tri.txt.
| Mesure | Avant | Après |
|---|---|---|
Appels à est_lettre depuis analyser_bigrammes |
3 757 672 | 0 |
Appels à est_lettre dans tout le programme |
5 297 256 | 1 539 584 |
Temps réel médian sans profiling (gcc -O0, 10 exécutions par version) |
0,1252 s | 0,1123 s |
Le gain médian mesuré est de 10,3 %. Les exécutions sont courtes et les temps fluctuent ; cette valeur est indicative. Les mesures ont été faites en alternant les deux versions sur la même machine :
- Avant : 0,1339 / 0,1132 / 0,1220 / 0,1146 / 0,1403 / 0,1118 / 0,1268 / 0,1235 / 0,1430 / 0,1373 s.
- Après : 0,1332 / 0,1035 / 0,1077 / 0,1133 / 0,1178 / 0,1131 / 0,1095 / 0,0994 / 0,1114 / 0,1193 s.
Validation : compilation sans avertissement avec -Wall -Wextra -Wpedantic,
rapport et sortie console identiques octet par octet sur les vingt
exécutions, avec -pg et sous AddressSanitizer et UndefinedBehaviorSanitizer.
L'empreinte reste 1d53de903efd2b7c. Le bigramme reste me, avec
17 607 occurrences et n comme troisième lettre la plus fréquente.
Un test temporaire a comparé 43 cas à l'ancienne fonction : entrées vides
ou courtes, chevauchements, espaces, changements de ligne, égalités,
normalisation et données pseudo-aléatoires.
Autres pistes, à mesurer séparément :
est_mot_videprovoque encore 12 045 671 appels àegales. Réutiliser la longueurkpour exclure les mots plus longs que tous les mots vides, puis consulter un index de hachage séparé, reste la priorité. L'ordre du tableauMOTS_VIDES, utilisé pour générer le texte, doit être conservé.normaliser_lignepourrait utiliser une table de conversion des octets en minuscules ou espaces, pour regrouper classification et conversion.decouper_lignespourrait utiliser des pointeurs dans le texte et remplacer les sauts de ligne par\0, évitant les allocations et copies par ligne. La libération de la mémoire devrait être adaptée en conséquence.
Commandes pour reproduire ce profil :
mkdir -p out/apres_bigrammes
gcc -O0 -pg analyseur.c -o out/apres_bigrammes/analyseur
(cd out/apres_bigrammes && ./analyseur && gprof -b ./analyseur gmon.out > ../profil_apres_bigrammes.txt)
Optimisation de est_mot_vide
La recherche linéaire dans les 60 entrées de MOTS_VIDES est remplacée
par un index de hachage de 121 cases, construit au premier appel seulement.
Chaque case contient l'indice d'un mot + 1, ou zéro si elle est libre.
Les collisions sont résolues en avançant à la case suivante, avec retour
au début. Le doublon ou réutilise la même case : l'index contient donc
59 mots distincts et reste rempli à moins de 50 %.
L'initialisation calcule aussi la longueur maximale des mots vides,
actuellement 5 caractères. est_mot_vide reçoit la longueur k, déjà
connue lors du découpage, et rejette immédiatement les mots plus longs.
Sur ce texte, 107 019 mots sont ainsi exclus avant même le hachage.
Les autres recherches sont en O(1) en moyenne pour ces mots de longueur
bornée, avec un pire cas linéaire en cas de nombreuses collisions.
L'index est séparé de MOTS_VIDES : la liste originale, son ordre et son
doublon sont conservés pour produire exactement le même texte.
L'index et la longueur maximale occupent 488 octets sur cette machine,
sans allocation dynamique supplémentaire.
Profil enregistré dans 07_mots_vides.txt.
La comparaison porte sur la version précédente, décrite dans
../resultats/profils/06_bigrammes.txt.
| Mesure | Avant | Après |
|---|---|---|
Appels à est_mot_vide |
250 000 | 250 000 |
Appels à egales depuis est_mot_vide |
12 045 671 | 202 444 |
Appels à egales lors de l'initialisation de l'index |
0 | 28 |
Appels à egales dans tout le programme |
12 198 772 | 355 573 |
Temps réel médian sans profiling (gcc -O0, 10 exécutions par version) |
0,1007 s | 0,0543 s |
La recherche des mots vides effectue environ 60 fois moins de comparaisons. Le temps total baisse de 46,1 %, soit une accélération d'environ 1,86. Les mesures ont été réalisées en alternant les deux versions sur la même machine :
- Avant : 0,0998 / 0,0953 / 0,0997 / 0,1015 / 0,1170 / 0,1067 / 0,1102 / 0,0999 / 0,1018 / 0,0989 s.
- Après : 0,0531 / 0,0535 / 0,0565 / 0,0542 / 0,0554 / 0,0544 / 0,0577 / 0,0579 / 0,0520 / 0,0522 s.
Validation : compilation sans avertissement avec -Wall -Wextra -Wpedantic,
rapport et sortie console identiques octet par octet sur les vingt
exécutions, avec -pg et sous AddressSanitizer et UndefinedBehaviorSanitizer.
L'empreinte reste 1d53de903efd2b7c.
Un test temporaire a comparé les réponses à une recherche linéaire pour
les 60 entrées, leurs préfixes et suffixes, les 18 278 chaînes minuscules
de 1 à 3 caractères, 50 000 mots pseudo-aléatoires et les 7 000 mots du
vocabulaire. Un dictionnaire synthétique dans un processus séparé a
également vérifié les collisions avec retour à la première case et
l'adaptation automatique à des mots vides de plus de 5 caractères.
Commandes pour reproduire ce profil :
mkdir -p out/apres_mots_vides
gcc -O0 -pg analyseur.c -o out/apres_mots_vides/analyseur
(cd out/apres_mots_vides && ./analyseur && gprof -b ./analyseur gmon.out > ../profil_apres_mots_vides.txt)
[rabot@salle222-12 out]$ gcc -O0 ../analyseur.c -o analyseur
[rabot@salle222-12 out]$ time ./analyseur
Lignes analysées : 21746
Mots au total : 250000
Mots distincts : 5866
Longueur moyenne : 6.712 (écart-type 1.873)
Bigramme le + courant : "me" (17607 fois, souvent suivi de 'n')
Top 10 :
1. rane 287
2. fasi 241
3. tata 219
4. mopo 214
5. cofi 180
6. vesi 179
7. laganomo 177
8. boto 172
9. nopebo 169
10. rotion 165
Empreinte du rapport : 1d53de903efd2b7c
real 0m0.078s
user 0m0.059s
sys 0m0.001s
Table de conversion pour normaliser_ligne
Une table de 256 cases mémorise le résultat de la normalisation de chaque
octet. Elle est initialisée au premier appel : les majuscules deviennent
des minuscules, les minuscules sont conservées et les autres caractères
deviennent des espaces. La boucle applique ensuite directement
conversion[(unsigned char)ligne[i]], jusqu'au premier \0.
La conversion en unsigned char garantit un indice entre 0 et 255,
y compris pour les octets supérieurs à 127. Le comportement reste celui
du programme initial : seules les lettres ASCII sont conservées.
Les fonctions est_lettre et en_minuscule, devenues inutilisées, sont
supprimées. Le parcours reste en O(longueur de la ligne), avec moins de
tests et sans appel de fonction pour chaque caractère.
La table occupe 256 octets, auxquels s'ajoute l'indicateur d'initialisation de 4 octets sur cette machine, sans allocation dynamique.
Profil enregistré dans 08_normalisation.txt.
La comparaison porte sur la version précédente, décrite dans
../resultats/profils/07_mots_vides.txt.
| Mesure | Avant | Après |
|---|---|---|
Appels à normaliser_ligne |
21 746 | 21 746 |
Appels à est_lettre |
1 539 584 | 0 |
Appels à en_minuscule |
1 266 663 | 0 |
Temps réel médian sans profiling (gcc -O0, 10 exécutions par version) |
0,0577 s | 0,0508 s |
Le gain médian mesuré est de 11,9 %. Les mesures ont été réalisées en alternant les deux versions sur la même machine :
- Avant : 0,0578 / 0,0587 / 0,0577 / 0,0574 / 0,0569 / 0,0573 / 0,0576 / 0,0572 / 0,0580 / 0,0583 s.
- Après : 0,0506 / 0,0509 / 0,0528 / 0,0511 / 0,0506 / 0,0503 / 0,0508 / 0,0512 / 0,0512 / 0,0503 s.
Validation : compilation sans avertissement avec -Wall -Wextra -Wpedantic,
rapport et sortie console identiques octet par octet sur les vingt
exécutions, avec -pg et sous AddressSanitizer et UndefinedBehaviorSanitizer.
L'empreinte reste 1d53de903efd2b7c.
Des tests temporaires ont comparé la nouvelle fonction à l'ancienne sur
les 256 valeurs d'octet, une ligne vide, des caractères mélangés, des
octets après le premier zéro et une ligne de 65 536 octets. Ils vérifient
aussi qu'une seconde normalisation ne change plus le résultat, avec
-fsigned-char et -funsigned-char.
Commandes pour reproduire ce profil :
mkdir -p out/apres_normalisation
gcc -O0 -pg analyseur.c -o out/apres_normalisation/analyseur
(cd out/apres_normalisation && ./analyseur && gprof -b ./analyseur gmon.out > ../profil_apres_normalisation.txt)
Vérification de la normalisation sur le même PC
Pour vérifier le gain malgré les changements de machine, les deux versions ont été recompilées et comparées directement sur salle235-06, équipé d'un Intel Core i7-8700 à 3,20 GHz, avec GCC 16.2.1.
La référence est le commit 1331811, juste après l'optimisation de
est_mot_vide. La version comparée est le fichier analyseur.c avec la
table de conversion de normaliser_ligne. La différence de code porte
uniquement sur cette normalisation et la suppression des deux fonctions
utilitaires devenues inutilisées.
Protocole : mêmes options -std=c11 -Wall -Wextra -Wpedantic -O0, sans
-pg, cinq exécutions de chauffe par version, puis 50 mesures par
version. Les versions sont exécutées successivement, en inversant
l'ordre à chaque paire, sur le même CPU logique (CPU 0). Le temps CPU
correspond à la somme des temps utilisateur et système du programme.
| Mesure médiane | Après est_mot_vide |
Avec la nouvelle normalisation | Temps gagné |
|---|---|---|---|
| Temps réel | 56,91 ms | 50,83 ms | 10,7 % |
| Temps CPU | 56,35 ms | 50,35 ms | 10,7 % |
La nouvelle version est plus rapide dans 50 paires sur 50, en temps
réel comme en temps CPU. Le gain de la normalisation est donc confirmé
sur cette machine avec -O0. Il représente environ 6 ms par exécution.
Le rapport et la sortie console sont identiques sur les 110 exécutions,
chauffe incluse. L'empreinte reste 1d53de903efd2b7c.
Les 100 mesures brutes sont conservées, ainsi que les conditions et statistiques détaillées, qui identifient le commit de référence et les deux sources utilisées.
Découpage en place dans le tampon du texte
Après la réorganisation du dépôt, le programme se trouve dans
src/analyseur.c et les commandes de validation sont make check et
make profile.
decouper_lignes reçoit maintenant un char * modifiable. Chaque saut
de ligne est remplacé par \0, et le tableau retourné contient des
pointeurs vers le début des lignes dans le tampon texte. Les allocations
et copies individuelles disparaissent ; le tableau de pointeurs conserve
son allocation initiale et ses agrandissements par realloc.
Les lignes restent valides tant que texte existe. La normalisation agit
directement sur ce tampon. À la fin du programme, on libère le tableau de
pointeurs, puis texte, sans appeler free sur chaque ligne.
Les lignes vides sont conservées. Seules les lignes terminées par \n
sont retournées, comme dans la version précédente ; le générateur produit
déjà un saut de ligne final. Le parcours reste en O(taille du texte), mais
il évite les allocations et les copies de son contenu.
Sur le corpus complet, cela supprime 21 746 allocations de lignes et autant de libérations. Le stockage de leurs copies représentait 1 561 330 octets, soit environ 1,49 Mio, hors coût de l'allocateur.
Le profil est archivé dans 09_decoupage.txt.
La comparaison utilise le commit 875af6fe9eaee7a2a9a997c7fe4102d216a1b9fb
comme référence avant modification. Les deux versions sont compilées avec
-std=c11 -Wall -Wextra -Wpedantic -O0, sans -pg, puis exécutées sur
salle235-06, CPU logique 0, avec GCC 16.2.1.
Après cinq exécutions de chauffe par version, 50 mesures par version
sont réalisées en alternant l'ordre à chaque paire. Le temps réel inclut
le lancement du programme et ses écritures dans build/. Le temps CPU
est la somme des temps utilisateur et système du processus. Le pic RSS
est mesuré dans une série séparée avec /usr/bin/time -f %M, cinq fois
par version, sur le même CPU.
| Mesure | Avant : copies des lignes | Après : pointeurs dans le texte |
|---|---|---|
| Allocations du contenu des lignes | 21 746 | 0 |
| Octets alloués pour le contenu des lignes | 1 561 330 | 0 |
| Temps réel médian | 84,36 ms | 79,60 ms |
| Temps CPU médian | 54,75 ms | 49,38 ms |
| Pic RSS médian | 6 688 Kio | 4 896 Kio |
Le gain médian est de 5,6 % en temps réel et de 9,8 % en temps CPU. La nouvelle version est plus rapide dans 36 paires sur 50 en temps réel et 39 sur 50 en temps CPU. Les temps fluctuent : la comparaison porte sur cette série avant/après, et non sur les mesures historiques de la normalisation. La baisse du pic RSS médian est de 1 792 Kio.
Les mesures de temps, les mesures de mémoire et les conditions et statistiques sont conservées. Le fichier de conditions contient aussi les empreintes SHA-256 des sources avant et après modification.
Validation : make check et make profile passent sans avertissement de
compilation. Les 110 exécutions de comparaison, chauffe comprise, et les
10 mesures de mémoire produisent un rapport et une sortie console
identiques octet par octet à la référence. L'empreinte reste
1d53de903efd2b7c.
Des tests temporaires sous AddressSanitizer et UndefinedBehaviorSanitizer ont comparé le découpage à l'ancienne fonction sur les textes vides, les lignes vides, les suffixes sans saut de ligne, les zéros internes, les fins de ligne CRLF, une ligne de 65 536 caractères, les seuils de capacité jusqu'à 32 769 lignes et le corpus complet. Ils vérifient aussi que chaque pointeur vise le tampon initial et que les lignes restent identiques après normalisation. Le programme complet passe également avec ces outils, sans double libération ni accès mémoire invalide.
Commandes utilisées pour cette étape à 250 000 mots, avant l'augmentation du volume :
make check
make profile
cp build/profil/profil.txt resultats/profils/09_decoupage.txt
Comparaison du découpage sur 10 millions de mots
Le paramètre NB_MOTS_TEXTE passe à 10 000 000. Pour comparer le
découpage, ce changement est appliqué aussi à la version avant optimisation,
issue du commit 875af6fe9eaee7a2a9a997c7fe4102d216a1b9fb. Les différences
entre les deux versions restent le découpage en place et la suppression
des libérations individuelles des lignes.
Les deux versions sont compilées avec
-std=c11 -Wall -Wextra -Wpedantic -O0, sur salle235-06, avec
GCC 16.2.1, puis exécutées sur le CPU logique 0. Deux mesures sans
-pg sont réalisées par version, dans l'ordre avant/après puis après/avant.
Une exécution profilée supplémentaire par version produit les nouveaux
profils.
| Mesure | Avant découpage en place | Après découpage en place |
|---|---|---|
| Temps réels sans profiling | 2,042 s ; 1,993 s | 1,768 s ; 1,765 s |
| Temps réel moyen | 2,0175 s | 1,7664 s |
| Temps CPU moyen | 1,95 s | 1,72 s |
| Moyenne des pics RSS | 145 780 Kio | 72 054 Kio |
Temps propre de decouper_lignes avec -pg |
0,28 s | 0,12 s |
Temps total attribué par gprof |
1,65 s | 1,57 s |
Le gain observé sur les deux mesures sans instrumentation est de 12,4 % en temps réel et 11,8 % en temps CPU. Le pic RSS moyen baisse de 50,6 %, d'environ 142,4 Mio à 70,4 Mio. Les deux mesures individuelles donnent une version après découpage plus rapide.
Les nouveaux profils avant
et après reposent
respectivement sur environ 165 et 157 échantillons attribués, avec
une période de 0,01 s. Les anciennes captures à 250 000 mots n'en
contenaient que 3 et 7 : elles étaient trop courtes pour interpréter une
variation de quelques centièmes comme une régression. Les temps de
gprof restent des estimations ; le gain global est mesuré sans -pg.
Les mesures brutes et les conditions détaillées identifient les sources, leurs empreintes SHA-256, le protocole et les profils.
Le nouveau corpus contient 10 000 000 mots, 869 827 lignes et
6 098 mots distincts. Le bigramme reste me, avec 696 057 occurrences
et n comme troisième lettre la plus fréquente. Les six exécutions
produisent des rapports et sorties console identiques avant/après.
L'empreinte de ce nouveau volume est b35be1258a9cb3f6. Le
rapport de référence à 10 millions
est issu de la version avant découpage, puis vérifié avec la version
après découpage. Le rapport historique à 250 000 mots
et son empreinte 1d53de903efd2b7c sont conservés. make check utilise
désormais la référence à 10 millions de mots.