Tp 6 : Optimisation


L'objectif

Ce TP introduit la notion d'optimisation. Optimiser un programme, c'est le rendre plus efficace, donc en général plus rapide.
Il comporte plusieurs parties, chacune montrant une forme d’optimisation particulière.

Le sujet

Comme le nom du Tp l'indique, nous allons essayer de modifier le source de programmes écrit en langage d'assemblage afin de les optimiser. On pourra soit enlever des lignes de code "superflues", soit remplacer certaines lignes par d'autres.

A faire

Première partie

Nous allons voir qu'il est possible de jouer sur les registres d'entrée ou de sortie des fonctions afin d'optimiser un programme. Pour cela, nous allons écrire un petit programme en C (in_out.c) qui ne fait pas grand chose, mais qui met en oeuvre deux fonctions.

Saisir le programme suivant (en le comprenant !).

inOut.c
  1. #include <stdio.h>
  2. int main()
  3. {
  4. int a ;
  5. a=getchar() ;
  6. putchar(a) ;
  7. return a;
  8. }

Compiler ce programme en lançant la commande :

$ gcc -Wall inOut.c -o inOut

Lancer le programme et constater ce qu’il fait (pas grand chose, effectivement).
Traduire ce fichier en langage d’assemblage en lançant la commande :

$ gcc –S inOut.c

Vous devez obtenir quelque chose ressemblant à ceci :

  1. .file "inOut.c"
  2. .text
  3. .globl main
  4. .type main,@function
  5. main:
  6. pushl %ebp
  7. movl %esp,%ebp
  8. subl $8,%esp
  9. andl $-16,%esp
  10. movl $0,%eax
  11. subl %eax,%esp
  12. call getchar
  13. movl %eax,-4(%ebp)
  14. movl -4(%ebp),%eax
  15. movl %eax,(%esp)
  16. call putchar
  17. movl -4(%ebp),%eax
  18. leave
  19. ret
  20. .size main,.-main
  21. .ident "GCC: (GNU) 3.3.5 (Debian)"

Analyser ce fichier et l’optimiseren supprimant les lignes de code qui vous paraissent inutiles.
Tester chaque modification en recompilant le ficher assembleur (et non plus le programme C !)
Attention à ne pas écraser votre fichier source lors de vos compilation !!!

Recompiler le programme C avec les commandes :

$ gcc –S –Os inOut.o –o inOut_opt.s
$ gcc –S –O3 inOut.o –o inOut_opt3.s

Comparer les fichiers inOut_opt?.s avec le fichier in_out.s que vous avez optimisé manuellement.

inOut_opt.s
  1. .file "inOut.c"
  2. .text
  3. .global main
  4. .type main,@function
  5. main:
  6. pushl %ebp
  7. movl %esp,%ebp
  8. pushl %ebx
  9. call getchar
  10. pushl %ebx
  11. movl %eax,%ebx
  12. call putchar
  13. movl %ebx,%eax
  14. movl -4(%ebp), %ebx
  15. leave
  16. ret
  17. .size main,.-main
  18. .ident "GCC: (GNU) 3.3.5 (Debian)"

Remarque : l'option -Os optimise la taille du code, alors que -O3 optimise la vitesse du code. La seconde permet donc l'inlining, c'est-à-dire le remplacement d'un appel de fonction directement par son code, comme pour une macro.

Conclure sur les capacités d'optimisation de GCC.

Deuxième partie

Nous avons vu précédemment qu’il était possible pour le compilateur d’optimiser un programme en enlevant certaines lignes de codes assembleur superflues. Dans la suite de ce tp, nous allons voir qu’il est possible d’optimiser un programme en prenant quelques "initiatives" (pour le compilateur) et de ne pas tenir compte des lignes de codes C.

Boucle.c
  1. int main()
  2. {
  3. int i,j;
  4. for (i=0; i<=1000000;i++)
  5. j=5; /* sans intérêt dans le programme*/
  6. i=j;
  7. return i;
  8. }

Afin de gagner du temps pour tout ce qui est compilation et optimisation, il est préférable d’écrire un petit script que l’on va lancer à chaque modification du code source:

Chrono
  1. #! /bin/sh
  2. export prg=`basename $1 .c`
  3. echo 'Compilation'
  4. gcc -Wall $prg.c -o ${prg}
  5. gcc -Wall -O1 $prg.c -o ${prg}_opt
  6. gcc -Wall -O3 $prg.c -o ${prg}_opt3
  7. echo "Execution de ${prg}"
  8. time ./${prg}
  9. echo "Execution de ${prg}_opt"
  10. time ./${prg}_opt
  11. echo "Execution de ${prg}_opt3"
  12. time ./${prg}_opt3

Donner les droits d'exécution à ce script.
Lancer ce script en spécifiant le nom du programme à tester :

$ Chrono boucle

Ce script vous génère alors 3 fichiers assembleurs et 3 exécutables, compilés respectivement sans optimisation, avec optimisation rapide et avec optimisation complète. Il mesure ensuite les temps d'exécution de ces 3 exécutables.

Comparer ces temps et conclure.
Remarque : Il peut être utile de modifier le nombre d'itérations de la boucle pour avoir des différences de temps parlantes...

Visualiser les fichiers sources en langage d’assemblage et les analyser de façon à voir ce qu’à fait l’optimisation O1.
Conclure sur le devenir du code sans effet.

Troisième partie

En fonction du type de microprocesseur sur lequel il travaille, le compilateur va essayer d’utiliser tous les registres encore libres du microprocesseur afin de diminuer le temps d’exécution d’un programme, comme on l’avait constaté lors du Tp 4.
Afin de le mettre en évidence, voici deux programmes à tenter d'optimiser :

Sans_reg.c
  1. int main()
  2. {
  3. int i,j=0;
  4. for ( i=0 ; i<=2000000000 ; i++)
  5. j++;
  6. return j;
  7. }
Avec_reg.c
  1. int main()
  2. {
  3. register int i,j=0;
  4. for ( i=0 ; i<=2000000000 ; i++)
  5. j++;
  6. return j;
  7. }

Evaluer l'impact de la modification sur les temps d'exécution.
Visualiser les fichiers assembleur et les analyser de façon à voir ce qu’à fait l’optimisation.

Déclarer 5 variables de types int k, l, m, n et o, et ajouter les lignes k++, l++ etc… dans la boucle.
Comparer à nouveau les temps.
Visualiser le fichier source avec_reg.s et voir si les 7 variables ont chacune été affectées à un registre du microprocesseur.

Conclure en vous référant au cours sur les technologies RISC et CISC...