📊 TD1 – Analyse de performance et optimisation en C

🚀 Étapes initiales

Nous avons commencé par récupérer les programmes depuis le dépôt Git de Maxime Menault, puis nous les avons compilés et exécutés avec différentes valeurs.
Pour obtenir un temps d’exécution suffisamment long pour l’analyse, nous avons choisi 1000 et 1000 comme valeurs de test.

gcc -g -pg -o student_rank student_rank.c heapsort.c bubblesort.c
./student_rank 5000 1000 0

Ensuite, nous avons utilisé gprof pour analyser le programme :

gprof ./student_rank

📈 Analyse avec gprof

🔹 Flat Profile

Le Flat Profile donne un aperçu global :

Temps et nombre d’exécutions par fonction
Temps cumulé au fil des appels
Nombre d’appels effectués
Temps moyen par appel (ms)
Nom de la fonction

👉 Exemple (extrait) :

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 79.80      2.35     2.35  1001000     0.00     0.00  bubblesort
 19.35      2.92     0.57  1000000     0.00     0.00  find_rank_student

🔹 Call Graph

Le Call Graph montre :

Les relations entre les fonctions
Le temps consommé par chaque fonction et ses enfants
Le nombre total d’appels
Une vision hiérarchique (arbre d’exécution)

👉 Exemple (extrait) :

[1]    100.0    0.00    2.96                 main [1]
                0.01    2.92       1/1           sort_students [2]
-----------------------------------------------
[2]     99.3    0.01    2.92       1         sort_students [2]
                0.57    2.35 1000000/1000000     find_rank_student [3]
-----------------------------------------------
[3]     98.9    0.57    2.35 1000000         find_rank_student [3]
                2.35    0.00 1000000/1001000     bubblesort [4]

🔎 Résultats de l’analyse

La fonction la plus lente est bubblesort (≈80% du temps total).
Elle est appelée plus d’1 million de fois par find_rank_student.
Le tri est donc la source principale de ralentissement.

🛠️ Optimisations

✅ Correction du bug dans `bubblesort`

Le code initial validait sa condition en permanence.
Solution : vérifier qu’il n’y a plus aucun échange avant d’arrêter la boucle.

void bubblesort(int* array, int length)
{
    int swapped, i, tmp;
    do {
        swapped = 0;
        for(i = 1; i < length; i++) {
            if(array[i-1] > array[i]) {
                tmp = array[i-1];
                array[i-1] = array[i];
                array[i] = tmp;
                swapped++;
            }
        }
    } while(swapped > 0);
}

🚀 Remplacement de `bubblesort` par `heapsort`

En remplaçant bubblesort par heapsort, le temps d’exécution diminue drastiquement.
👉 Le tri devient beaucoup plus rapide et plus efficace.

📌 Résumé

Flat Profile → temps et nb d’exécutions par fonction (ici bubblesort ≈ 80%).
Call Graph → arbre d’appels entre fonctions + temps consommé.
Optimisation principale :
- Corriger la condition de bubblesort.
- Remplacer bubblesort par heapsort pour de meilleures performances.

✍️ Travail effectué dans le cadre du TD1 – Analyse de performance et optimisation en C.

3.4 KiB Raw Permalink Blame History Unescape Escape