Quelques frivolités avec gcc (ou "goto vs. appels récursifs")
Rémy m'a envoyé un petit lien que
voici,
qui explique comment il faudrait écrire un programme qui imprime 100 fois
"Hello World" à l'écran, sans utiliser while, for ou do-while.
Cependant, je n'étais pas entièrement convaincu par l'approche récursive, et j'avais le sentiment que c'était moins optimal. Voici une traduction du pseudo-code proposé comme réponse :
#include <stdio.h>
void loop(int n) {
if (n > 100)
return;
else
printf("Hello World\n");
loop(n + 1);
}
int main() {
loop(1);
}
et voici ce que je propose :
#include <stdio.h>
int main() {
int i = 0;
loop_start:
printf("Hello World!\n");
if (++i < 100) goto loop_start;
return 0;
}
Je sais ce que vous allez me dire, que goto c'est le diable incarné, tout ça
tout ça. Mais comme je suis curieux de savoir comment le compilateur gèrerait
les deux codes source, on peut se proposer de comparer les codes assembleur
générés.
Pourquoi comparer ? Il est assez aisé d'imaginer qu'on risque d'allouer 100 trames dans la pile si on voulait exécuter la version récursive de cet algorithme, mais qu'on s'en passerait complètement avec la version goto. Mais peut-être que le problème disparaîtrait en expérimentant avec les niveaux d'optimisation de gcc.
J'ai compilé la version goto avec les flags -O0, -O1, -O2 et -O3 par simple curiosité pour ensuite passer un coup d'objdump dessus, et voir comment gcc optimiserait mon code. Voici la version non optimisée (-O0) :
080483c4 <main>:
80483c4: 55 push %ebp
80483c5: 89 e5 mov %esp,%ebp
80483c7: 83 e4 f0 and $0xfffffff0,%esp
80483ca: 83 ec 20 sub $0x20,%esp
80483cd: c7 44 24 1c 00 00 00 movl $0x0,0x1c(%esp)
80483d4: 00
80483d5: eb 01 jmp 80483d8 <main+0x14>
80483d7: 90 nop
80483d8: c7 04 24 c0 84 04 08 movl $0x80484c0,(%esp)
80483df: e8 14 ff ff ff call 80482f8 <puts@plt>
80483e4: 83 44 24 1c 01 addl $0x1,0x1c(%esp)
80483e9: 83 7c 24 1c 63 cmpl $0x63,0x1c(%esp)
80483ee: 7e e7 jle 80483d7 <main+0x13>
80483f0: b8 00 00 00 00 mov $0x0,%eax
80483f5: c9 leave
80483f6: c3 ret
Là, à l'adresse 0x80483cd, le movl correspond à l'initialisation de ma
variable locale i. Pourtant, un registre aurait très bien fait l'affaire.
Avec -O1, on voit que gcc attribue le registre %ebx à ma variable i:
080483c4 <main>:
80483c4: 55 push %ebp
80483c5: 89 e5 mov %esp,%ebp
80483c7: 83 e4 f0 and $0xfffffff0,%esp
80483ca: 53 push %ebx
80483cb: 83 ec 1c sub $0x1c,%esp
80483ce: bb 00 00 00 00 mov $0x0,%ebx
80483d3: c7 04 24 c0 84 04 08 movl $0x80484c0,(%esp)
80483da: e8 19 ff ff ff call 80482f8 <puts@plt>
80483df: 83 c3 01 add $0x1,%ebx
80483e2: 83 fb 64 cmp $0x64,%ebx
80483e5: 75 ec jne 80483d3 <main+0xf>
80483e7: b8 00 00 00 00 mov $0x0,%eax
80483ec: 83 c4 1c add $0x1c,%esp
80483ef: 5b pop %ebx
80483f0: 89 ec mov %ebp,%esp
80483f2: 5d pop %ebp
80483f3: c3 ret
Par contre, l'instruction mov $0x0,%ebx aurait pu être remplacée par xor
%ebx, %ebx, ce qui fait la même chose en prenant moins de place et en plus
rapide. C'est d'ailleurs une technique utilisée dans des shellcodes pour
initialiser un registre à zéro en évitant d'introduire des octets nuls dans le
code. Avec -O2, c'est effectivement ce qui se passe :
080483d0 <main>:
80483d0: 55 push %ebp
80483d1: 89 e5 mov %esp,%ebp
80483d3: 83 e4 f0 and $0xfffffff0,%esp
80483d6: 53 push %ebx
80483d7: 31 db xor %ebx,%ebx
80483d9: 83 ec 1c sub $0x1c,%esp
80483dc: 8d 74 26 00 lea 0x0(%esi,%eiz,1),%esi
80483e0: 83 c3 01 add $0x1,%ebx
80483e3: c7 04 24 c0 84 04 08 movl $0x80484c0,(%esp)
80483ea: e8 09 ff ff ff call 80482f8 <puts@plt>
80483ef: 83 fb 64 cmp $0x64,%ebx
80483f2: 75 ec jne 80483e0 <main+0x10>
80483f4: 83 c4 1c add $0x1c,%esp
80483f7: 31 c0 xor %eax,%eax
80483f9: 5b pop %ebx
80483fa: 89 ec mov %ebp,%esp
80483fc: 5d pop %ebp
80483fd: c3 ret
Remarquez le fameux xor. Avec -O3, cependant, il n'y a aucune différence
avec -O2.
Essayons maintenant avec la version récursive de cet algorithme. Voici le code avec -O0 :
080483c4 <loop>:
80483c4: 55 push %ebp
80483c5: 89 e5 mov %esp,%ebp
80483c7: 83 ec 18 sub $0x18,%esp
80483ca: 83 7d 08 64 cmpl $0x64,0x8(%ebp)
80483ce: 7f 1c jg 80483ec <loop+0x28>
80483d0: c7 04 24 d0 84 04 08 movl $0x80484d0,(%esp)
80483d7: e8 1c ff ff ff call 80482f8 <puts@plt>
80483dc: 8b 45 08 mov 0x8(%ebp),%eax
80483df: 83 c0 01 add $0x1,%eax
80483e2: 89 04 24 mov %eax,(%esp)
80483e5: e8 da ff ff ff call 80483c4 <loop>
80483ea: eb 01 jmp 80483ed <loop+0x29>
80483ec: 90 nop
80483ed: c9 leave
80483ee: c3 ret
080483ef <main>:
80483ef: 55 push %ebp
80483f0: 89 e5 mov %esp,%ebp
80483f2: 83 e4 f0 and $0xfffffff0,%esp
80483f5: 83 ec 10 sub $0x10,%esp
80483f8: c7 04 24 01 00 00 00 movl $0x1,(%esp)
80483ff: e8 c0 ff ff ff call 80483c4 <loop>
8048404: c9 leave
8048405: c3 ret
et avec -O2 (en ne montrant que la fonction loop) :
080483d0 <loop>:
80483d0: 55 push %ebp
80483d1: 89 e5 mov %esp,%ebp
80483d3: 53 push %ebx
80483d4: 83 ec 14 sub $0x14,%esp
80483d7: 8b 5d 08 mov 0x8(%ebp),%ebx
80483da: 83 fb 64 cmp $0x64,%ebx
80483dd: 7f 15 jg 80483f4 <loop+0x24>
80483df: 90 nop
80483e0: 83 c3 01 add $0x1,%ebx
80483e3: c7 04 24 e0 84 04 08 movl $0x80484e0,(%esp)
80483ea: e8 09 ff ff ff call 80482f8 <puts@plt>
80483ef: 83 fb 64 cmp $0x64,%ebx
80483f2: 7e ec jle 80483e0 <loop+0x10>
80483f4: 83 c4 14 add $0x14,%esp
80483f7: 5b pop %ebx
80483f8: 5d pop %ebp
80483f9: c3 ret
80483fa: 8d b6 00 00 00 00 lea 0x0(%esi),%esi
Pour ceux que ça gave de lire de l'assembleur : avec -O0, le code assembleur
appelle de manière stupide lui-même 100 fois avec call, ce qui fait aussi 100
créations et destructions de trames de pile. Imaginez si nous avions des
millions d'appels récursifs ! Sans parler du fait qu'aucun registre n'est alloué
pour les variables locales, alors qu'on n'en a qu'une seule dans notre fonction
et qu'elle aurait pu être dans %ebx. Cependant, avec -O2, gcc fait ce qu'on
appelle une optimisation des appels terminaux. En effet, nous avons ici
affaire à une récursion
terminale, ce qui
permet d'en faire un code optimisé qui ressemble pas mal à ma version goto
avec -O2. Trop fort, gcc !
Bref, en conclusion, la version récursive n'est pas si mauvaise que ça,
contrairement à ce que je pensais ; cependant, il faut absolument compiler
avec -O2 pour que ce soit réellement intéressant. Mais je souhaite quand même
en finir avec la diabolisation systématique du goto qui, lorsqu'il est bien
utilisé, peut rendre le code bien plus lisible. Par exemple, pour sortir d'un
switch et sortir du while qui le contient sans goto, il faudrait y
aller à coups de booléens susceptibles de rendre les conditions de sortie des
while en question plus compliqués, et ce juste pour un cas particulier.
C'est pourquoi, et plus particulièrement en programmation système, je tiens à
garder ce mot-clé dans mon arsenal.
En tout cas, c'est clair qu'on pouvait s'affranchir de goto dans notre exemple
(d'ailleurs, c'est pour ça qu'on a des structures de contrôle comme for ou
while). Mais regarder comment gcc optimise ce genre de programmes à chaque
fois reste une expérience intéressante.
