# Compte rendu — Optimisation de l'analyseur de mots

**R5.A.04 — Qualité algorithmique**

**Adrien RABOT — Théo ANASTASIO**

## 1. Objectif et méthode

Réduire le temps d'exécution sans modifier les résultats, sur un texte fixe
contenant 250 000 mots et 5 866 mots distincts retenus.

Les sections 2 à 4 présentent ce corpus historique. La section 5 compare
le découpage sur 10 000 000 mots, volume désormais utilisé par défaut.

Les temps sont mesurés avec `gcc -O0`, sans `-pg`. Le profil est obtenu
séparément avec `gcc -O0 -pg` et `gprof`, car l'instrumentation ralentit le programme.

## 2. Analyse et pistes prioritaires

Le profil initial conduit aux priorités suivantes, classées par gain attendu :

1. **Accélérer la recherche des mots.** La recherche linéaire provoque
   296 656 203 appels à `egales`. Une recherche dichotomique ou une table
   de hachage permet de réduire ces comparaisons.
2. **Calculer la moyenne une seule fois.** `longueur_moyenne` est appelée
   5 867 fois, car la variance recalcule la même moyenne pour chaque mot.
3. **Supprimer les parcours répétés des chaînes.** `longueur` est appelée
   36 009 819 fois au total. Mémoriser les longueurs et les positions de fin
   évite de reparcourir les mots, les lignes et le rapport.
4. **Remplacer le tri à bulles.** Ses 17 202 045 appels à `doit_echanger`
   justifient un tri en O(n log n).

## 3. Optimisations et gains mesurés

Chaque gain est relatif à la version précédente. Les deux premières étapes
reposent sur une mesure ponctuelle ; les étapes 03 à 05 utilisent la médiane
de cinq exécutions par version, les étapes 06 et 07 celle de dix exécutions,
et les étapes de normalisation et de découpage celle de cinquante exécutions.
Chaque comparaison est faite sur la même machine ; les conditions peuvent
varier entre les étapes.

| Optimisation | Modification | Avant | Après | Temps gagné |
| --- | --- | ---: | ---: | ---: |
| Recherche dichotomique | Tableau maintenu trié, recherche en O(log n) | 2,80 s | 1,45 s | ≈ 48 % |
| Moyenne | Un seul calcul, transmis au calcul de variance | 1,46 s | 0,88 s | ≈ 40 % |
| Table de hachage | Recherche et insertion en O(1) en moyenne | 0,888 s | 0,831 s | 6,4 % |
| Longueurs et chaînes | Champ `taille`, arrêt sur `\0`, position de fin conservée | 0,832 s | 0,362 s | 56,5 % |
| Tri par tas | Tri en O(n log n), sans tableau supplémentaire | 0,367 s | 0,113 s | 69,3 % |
| Bigrammes | Deux lettres précédentes conservées, aucun appel à `est_lettre` | 0,1252 s | 0,1123 s | 10,3 % |
| Mots vides | Filtre par longueur et index de hachage séparé | 0,1007 s | 0,0543 s | 46,1 % |
| Normalisation | Table de conversion des octets, comparaison sur le même PC | 0,0569 s | 0,0508 s | 10,7 % |
| Découpage | Pointeurs dans le texte, sans allocation ni copie par ligne | 0,0844 s | 0,0796 s | 5,6 % |

Le programme utilise le hachage à la place de la dichotomie. Son gain
supplémentaire reste limité car la recherche était déjà efficace.

Tous les appels à `longueur` sont supprimés. Le tri ne fait plus que
**129 602 appels à `doit_echanger`**, soit environ **133 fois moins**.
Le classement reste par fréquence décroissante, puis par ordre alphabétique.

La recherche des mots vides passe de **12 045 671 à 202 444 appels à
`egales`**. Les appels à `est_lettre` et `en_minuscule` sont supprimés.
Le gain de normalisation a été confirmé sur `salle235-06` : la nouvelle
version est plus rapide dans les 50 paires de mesures, en temps réel et CPU.

Le découpage évite **21 746 allocations et libérations de lignes** ainsi
que **1 561 330 octets de stockage**, sans changer les lignes retournées.
Sur les 50 paires de mesures, le gain médian est de **5,6 % en temps réel**
et **9,8 % en temps CPU**. Le pic mémoire résident médian, mesuré séparément
cinq fois par version, passe de **6 688 à 4 896 Kio**. Les lignes partagent
le tampon `texte`, qui est conservé jusqu'à la fin de leur utilisation.

## 4. Bilan et validation

Le bilan global ci-dessous a été mesuré après le tri par tas (étape 05),
sur cinq exécutions par version dans les mêmes conditions. Les gains des
étapes suivantes sont mesurés séparément dans le tableau précédent.

| Mesure | Version initiale | Après le tri par tas |
| --- | ---: | ---: |
| Temps réel | 2,81 s | 0,11 s |
| Pic mémoire résident (RSS) | 6 664 Kio | 6 668 Kio |

Après le tri par tas, le programme est environ **25,5 fois plus rapide**,
soit **96,1 % de temps en moins** sur ce jeu de données.

Sur le corpus de 250 000 mots, le rapport et la sortie console sont
identiques octet par octet. L'empreinte reste **`1d53de903efd2b7c`**.

Pour le découpage, `make check`, `make profile` et les tests sous
AddressSanitizer et UndefinedBehaviorSanitizer passent. Les cas vérifiés
incluent les lignes vides, les textes sans saut de ligne final et les
agrandissements du tableau de pointeurs.

## 5. Comparaison sur 10 millions de mots

`NB_MOTS_TEXTE` est porté à **10 000 000 dans les deux versions comparées**.
Sur le même CPU de `salle235-06`, deux mesures sans `-pg` sont effectuées
par version, en inversant l'ordre avant/après à la seconde paire. Un profil
est ensuite produit pour chaque version.

| Mesure | Avant découpage en place | Après découpage en place |
| --- | ---: | ---: |
| Temps réel moyen sans profiling | 2,0175 s | 1,7664 s |
| Temps CPU moyen sans profiling | 1,95 s | 1,72 s |
| Moyenne des pics RSS sans profiling | 145 780 Kio | 72 054 Kio |
| Temps propre de `decouper_lignes` dans le profil | 0,28 s | 0,12 s |

Sur ces deux mesures, le gain est de **12,4 % en temps réel**, **11,8 % en
temps CPU** et **50,6 % sur le pic RSS moyen**. Les profils contiennent
environ 165 et 157 échantillons attribués, contre seulement 3 et 7 dans
les anciennes captures comparées. Ils indiquent aussi une réduction du
temps du découpage ; les mesures sans `-pg` confirment le gain global.

Le nouveau texte contient **869 827 lignes** et **6 098 mots distincts**.
Le rapport et la sortie console sont identiques avant/après sur les six
exécutions. L'empreinte de ce volume est **`b35be1258a9cb3f6`**.
La référence historique à 250 000 mots est conservée séparément ;
`make check` utilise désormais la référence à 10 millions de mots.

Sources : [notes](docs/notes.md), [ordre des profils](resultats/README.md),
[profil initial](resultats/profils/00_initial.txt),
[profil après découpage à 250 000 mots](resultats/profils/09_decoupage.txt),
[mesures du bilan après tri](resultats/mesures/mesures_bilan_tri.csv),
[comparaison de normalisation](resultats/mesures/comparaison_normalisation_meme_pc.csv) et
[comparaison du découpage](resultats/mesures/comparaison_decoupage_meme_pc.csv),
[profils avant](resultats/profils/10000000_mots/avant_decoupage.txt) et
[après à 10 millions](resultats/profils/10000000_mots/apres_decoupage.txt),
[mesures à 10 millions](resultats/mesures/comparaison_decoupage_10000000.csv).