Discussion :

[Lana.Bauer]

Bonjour,

Je vous présente ce tutoriel intitulé :

Optimisation des compilateurs

L'optimisation des compilateurs est la procédure qui minimise certains facteurs d'un programme exécutable pour maximiser son efficacité. Le facteur généralement minimisé est le temps d'exécution. Néanmoins, on pourrait éventuellement s'intéresser à minimiser la quantité de mémoire utilisée ou bien la consommation en énergie du programme.

Bonne lecture !

Vous voulez contribuer dans la FAQ ou en rédaction ? Contactez-moi sur l'e-mail rubrique en bas

[FR119492]

Salut!
La section I-C-1 est lacunaire. Il serait essentiel de préciser qu' une matrice est stockée de manière différente selon le langage utilisé: par exemple ligne par ligne en C et colonne par colonne en Fortran.
Jean-Marc Blanc

[miaous]

bonjour

Sujet intéressant, mais l'article est un peu cours.
quelque cas /exemples supplémentaire aurait été intéressent.

tu aurais pu parler par ex de l'optimisation sur les fonctions ( suppression des appels récursifs en créant une boucle).


Benoit

[Lana.Bauer]

Merci à tous pour vos remarques, si vous voulez proposer des corrections ou des exemples pour enrichir le tutoriel, je suis entièrement à votre écoute.

Merci pour votre réactivité !

[lautrec1]

Merci pour l'article ! J'ai lu attentivement et ai appris ! Des petits algos, de l'assembleur, de la structure processeur et j'en passe, un beau passage en revue.

Quatre questions en suspens:

Que se passe-t-il dans le cas suivant ?

1)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
int i, a[100], b[100];
for (i = 0; i < 100; i++)
{
  a[i] = 1;                     
}
for (j = 0; j < 100; j++)
{
  b[j] = 2;
}

Se produit-il une fusion de boucle car le j aurait été changé en i par le processus d'optimisation?

2)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
int i, a[100], b[100];
for (i = 0; i < 75; i++)
{
  a[i] = 1;                     
}
for (i = 0; i < 100; i++)
{
  b[i] = 2;
}

Se produit-il une fusion de boucle "partielle" : on passerait de 175 à 100 évaluations de conditions ?

3) Je n'ai pas compris si l'optimisation se fait après analyse du langage objet , ou au niveau de l'arbre syntaxique ?

4) Je n'arrive pas à m'imaginer le cas de figure de la "fission de boucle". Cela mériterait un exemple selon moi

Merci pour le temps.

[dourouc05]

3) Je n'ai pas compris si l'optimisation se fait après analyse du langage objet , ou au niveau de l'arbre syntaxique ?

Tu as plusieurs phases d'optimisation : d'abord, au niveau de l'arbre syntaxique, avant la génération de code machine, pour les optimisations valables pour toutes les plateformes (comme la fusion de boucles) ; ensuite, sur l'assembleur (réordonner les instructions pour profiter du pipeline, par exemple).

1) Se produit-il une fusion de boucle car le j aurait été changé en i par le processus d'optimisation?

Le nom des variables n'a pas d'importance dans l'optimisation : au niveau de l'arbre syntaxique, le nom des variables n'a plus aucune importance (sauf pour la gestion des erreurs). Le compilateur sait donc qu'il y a deux variables distinctes, mais utilisées sans qu'elles entrent en conflit : quand tu as fini de i, tu commences à utiliser j (plus techniquement, il est possible d'utiliser un seul et même registre pour les stocker). Déjà au niveau de l'arbre syntaxique, il peut donc optimiser pour ne plus avoir qu'une variable. Maintenant, les détails dépendent fortement du compilateur.

2) Se produit-il une fusion de boucle "partielle" : on passerait de 175 à 100 évaluations de conditions ?

À nouveau, ça dépend du compilateur : certains seront assez intelligents pour séparer les boucles et les fusionner. Tout dépend des heuristiques implémentées (ainsi que de leur ordre).

4) Je n'arrive pas à m'imaginer le cas de figure de la "fission de boucle". Cela mériterait un exemple selon moi

Ce à quoi je pense me semble en dehors de la portée d'un compilateur (à moins de laisser exploser les temps de calcul). Quand tu implémentes un produit matriciel (objectif purement factice, puisque BLAS existe, ses implémentations étant extrêmement optimisées), tu dois parcourir les deux matrices plusieurs fois. Une implémentation naïve passe son temps à jeter des données hors des caches du processeur :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for (int i = 0; i < m; i++)    for (int j = 0; j < q; j++)
        for (int k = 0; k < p; k++)
            prod[i][j] += first[i][k] * second[k][j];

Tu charges une série de first[i][k] et de second[j][k] : tous les first[i][k], puis tu recommences à les lire. Si tu as rempli tes caches avant d'avoir lu first[i][k] à i fixé, tu passes ton temps à aller voir en mémoire. L'idée, ici, serait de faire tous les k jusqu'à remplir une partie des caches, garder les second[k][j] qui entrent et sortent (impossible à éviter à moins d'utiliser deux formats de stockage différents) ; une fois que tu as fini de cette série de first[i][k], tu parcours le reste des k. Grosso modo :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
for (i = 0; i < m; i++) {    for (j = 0; j < q; j++) {
        int sum = 0; 
        for (k = 0; k < k1; k++) {
            sum += first[i][k] * second[k][j];
        }
        for (k = k1; k < p; k++) {
            sum += first[i][k] * second[k][j];
        }
        prod[i][j] = sum; 
    }
}

Dans ce cas, l'optimisation dépend très fortement du processeur (quantité de cache L1, qui dépend de beaucoup de facteurs).