Licence CC BY

Attention aux optimisations de Clang !

Quand le compilateur optimise trop

Dernière mise à jour :
Auteur :
Catégorie :
Temps de lecture estimé : 14 minutes

Si vous voulez en savoir plus sur les diverses optimisations réalisées par les compilateurs, allez consulter ce très bon tutoriel.

Bonjour !

J’écris cet article (mon premier, soyez indulgents ^^ ) pour vous montrer un petit exemple dans lequel les optimisations mises en place lors de la compilation peuvent créer des comportements inattendus, selon le programme utilisé. Dans le cas présenté ci-dessous, en langage C, le problème se produit avec Clang mais pas avec GCC.

Le code

Le code que nous allons utiliser va servir à chercher un contre-exemple de la conjecture de Syracuse. Pour rappel, la suite de Syracuse se construit de la façon suivante : on choisit un entier supérieur à 0, s’il est pair on le divise par 2 et s’il est impair on le multiplie par 3 et on ajoute 1. Puis on recommence avec la nouvelle valeur et ainsi de suite.

u0=NNu_0=N \in \mathbb{N}^*

nN , un+1={un2si un pair3×un+1si un impair\forall n \in \mathbb{N}~,~u_{n+1}=\left\lbrace\begin{array}{ll} \dfrac{u_n}{2} & \text{si }u_n\text{ pair} \\3\times u_n+1 & \text{si }u_n\text{ impair}\end{array}\right.

Il semblerait que la suite de Syracuse se termine systématiquement par la boucle 4 > 2 > 1 > 4 > … quel que soit le nombre de départ. Mais la conjecture n’a encore jamais été démontrée, il se pourrait donc qu’il existe des nombres pour lesquels la suite ne retombe jamais à 1.

Le code ci-dessous va chercher un éventuel contre-exemple en testant la suite de Syracuse pour chaque nombre. Tant qu’il n’a pas trouvé, il reste en boucle infinie. Seule la découverte d’un contre-exemple met fin au programme.

// Cherche un contre-exemple de la conjecture de Syracuse
// dont le vol ne finit pas par 4 > 2 > 1 > 4 > ...

#include <limits.h>
#include <stdio.h>

// Valeur maximum à tester (unsigned int)
// pour éviter l'overflow lors du 3*x+1
#define MAXVAL ((UINT_MAX / 3) - 1)

// Retourne 1 si un contre-exemple est trouvé, et boucle sinon
int syracuse(void)
{
    unsigned int nombre, vol, i;
    
    while(1) // Boucle infinie s'il n'y a pas de contre-exemple
    {
        for(nombre = 1; nombre <= MAXVAL; nombre++) // On teste chaque entier
        {
            vol = nombre;
            for(i = 0; i <= MAXVAL; i++)
            {
                if(vol == 1) break; // On retombe à 1, on passe à l'entier suivant
                if(vol >= MAXVAL) break; // Vol trop grand, on passe à l'entier suivant
                
                if(vol&1) vol = 3 * vol + 1; // Impair
                else vol = vol / 2; // Pair
            }
            
            // Si ici on a fait MAXVAL+1 étapes sans retomber à 1,
            // on a forcément fait une boucle à un moment, différente de 4 > 2 > 1 !
            if(i == MAXVAL + 1) return 1; // Contre-exemple trouvé
        }
    }
    return 0; // Code mort
}

int main(void)
{
    if(syracuse())
    {
        printf("Contre-exemple trouvé !\n");
    }
    return 0;
}

On est bien d’accord, ce programme est idiot, ne sert à rien, est mal foutu et occupe inutilement le CPU. Il n’y a aucune chance pour qu’il trouve un contre-exemple et il ne sert qu’à illustrer ce billet avec un cas plus ou moins concret.

Avec GCC

Bon, commençons par compiler notre ficher syracuse.c sans aucune optimisation avec GCC. La commande (avec Ubuntu) est la suivante :

$ gcc -O0 -o test_syracuse syracuse.c

On exécute alors le programme et…

Ça mouline…
Ça mouline…

Je vous laisse attendre chez vous un résultat aussi longtemps que vous voulez, si vous souhaitez mettre votre patience à l’épreuve, mais moi je vais tuer le processus. :P

On pouvait s’y attendre, puisque plein d’autres mathématiciens avant nous ont déjà essayé avec des programmes bien plus performants. Tentons à présent d’utiliser toutes les optimisations de GCC avec la commande suivante :

$ gcc -O3 -o test_syracuse syracuse.c

Vous pouvez essayer vous-mêmes ou me faire confiance, le comportement est exactement le même (à savoir : rien à l’écran ;) ). Du coup comment savoir si les optimisations sont bien présentes ? On peut regarder le nombre de lignes du code assembleur (fichier syracuse.s) généré par GCC avant la création de l’exécutable final.

$ gcc -O0 -S syracuse.c
$ wc -l syracuse.s
143 syracuse.s
$ gcc -O3 -S syracuse.c
$ wc -l syracuse.s
105 syracuse.s

On constate qu’il y a 143 lignes sans les optimisations et seulement 105 avec, donc le compilateur a bien fait son travail.

Avec Clang

Passons maintenant à Clang pour compiler notre fichier syracuse.c, toujours sans aucune optimisation pour commencer. La commande est la suivante :

$ clang -O0 -o test_syracuse syracuse.c

Quand on exécute le programme, ça alors ! il ne se passe toujours rien.

Ça mouline encore…
Ça mouline encore…

Je vous sens presque déçus. :D Allez, on ajoute à présent les optimisations de Clang et on regarde le résultat :

$ clang -O3 -o test_syracuse syracuse.c
On a trouvé ! O_o
On a trouvé ! O_o

Hein ?!? :waw: Le programme s’arrête instantanément en annonçant sa magnifique victoire, tuant une conjecture vieille de 90 ans ! o_O

Petit indice pour la suite : le problème vient de Clang, pas des maths. :-°

Alors que s’est-il passé ? Pourquoi ce résultat surprenant ? Il faut analyser le code assembleur généré par Clang pour mieux comprendre. Je vous rassure, pas besoin de connaître l’assembleur en détail, on ne va s’occuper que de quelques instructions.

Pour être exact, Clang ne produit pas vraiment de l’assembleur. En fait, il va compiler le C vers un langage qui ressemble à de l’assembleur et qui va ensuite être pris en charge par la LLVM (Low Level Virtual Machine) pour devenir un exécutable. LLVM est ainsi une seule infrastructure indépendante qui regroupe différents compilateurs selon les langages : pour le C, elle s’associe donc avec Clang. Dans la suite du billet, ces détails ne sont pas très importants donc on fera comme si c’était simplement de l’assembleur, mais c’est pour ça que je ne vais pas comparer les tailles des fichiers entre GCC et Clang.

Plus d’informations sur Clang et sur la LLVM. Le logo de ce billet est d’ailleurs celui de LLVM.

La commande pour obtenir le fichier assembleur syracuse.s sans optimisation est la suivante :

$ clang -O0 -S syracuse.c

Le fichier fait 113 lignes, nous ne nous intéresserons qu’à la fonction main :

main:                                   # @main
# %bb.0:
    pushl   %ebp
    movl    %esp, %ebp
    subl    $24, %esp
    movl    $0, -4(%ebp)
    calll   syracuse
    cmpl    $0, %eax
    je  .LBB1_2
# %bb.1:
    leal    .L.str, %eax
    movl    %eax, (%esp)
    calll   printf
    movl    %eax, -8(%ebp)          # 4-byte Spill
.LBB1_2:
    xorl    %eax, %eax
    addl    $24, %esp
    popl    %ebp
    retl

Ainsi, sans optimisation, on a les actions suivantes :

  • Le programme appelle bien la fonction syracuse à la ligne 7 (calll).
  • Puis, ligne 8, la valeur de retour est comparée à 0 (cmpl : compare).
  • Si c’est le cas (mais ça n’arrive jamais) on saute directement de la ligne 9 à la ligne 15 (je : jump if equal) puis fin.
  • Sinon, le code continue jusqu’à la ligne 13 qui appelle printf (calll) et affiche la phrase, puis fin.

C’est bien le comportement attendu. Comparons maintenant avec les optimisations :

$ clang -O3 -S syracuse.c

Le fichier fait cette fois 80 lignes, regardons à nouveau la fonction main :

main:                                   # @main
# %bb.0:
    subl    $12, %esp
    movl    $.Lstr, (%esp)
    calll   puts
    xorl    %eax, %eax
    addl    $12, %esp
    retl

C’est beaucoup plus court. Et remarquez-vous un problème ? L’appel à la fonction syracuse a totalement disparu ! :o Et en plus, même printf est parti ! Ce code optimisé réalise uniquement un appel à la fonction puts (ligne 5) et s’arrête.

Voilà donc pourquoi le programme optimisé avec Clang affiche immédiatement « Contre-exemple trouvé ! » et se termine.

Explications

La mise en place à priori étrange de cette optimisation à l’extrême s’explique par la structure particulière du code de la fonction syracuse : elle comporte une boucle infinie avec une seule porte de sortie, l’instruction return 1 et ne produit aucun effet de bord.

Chaque compilateur possède ses propres règles et méthodes d’optimisation, plus ou moins efficaces et justes. GCC a décidé dans un cas comme celui-ci de ne rien faire et de laisser la boucle en place. Concernant Clang, en revanche, il a constaté une chose : quel que soit le temps passé dans la boucle, quels que soient les calculs effectués à l’intérieur, la fonction ne peut retourner qu’une seule et unique valeur : un 1 (ligne 31). Du coup, son optimisation est simple et radicale : inutile d’appeler syracuse, la ligne 39 sera toujours vraie et il ne reste plus qu’à afficher directement le texte. Pas mal comme amélioration, non ? :soleil:

Pour éviter ce problème et obliger Clang à tenir compte de l’évolution des variables au sein de la boucle, la solution est d’utiliser le mot-clé volatile. La ligne 13 devient alors volatile unsigned int nombre, vol, i;.

Et concernant printf ? Cette fois, GCC et Clang ont tous les deux remplacé la fonction par un puts. En effet, la ligne 41 satisfait trois critères qui permettent cette optimisation :

  • La chaîne de caractères ne comprend pas de formats, elle n’affiche donc pas le contenu d’une variable.
  • La chaîne de caractères se termine par un retour à la ligne ('\n').
  • On ne récupère pas la valeur retournée par printf après l’affichage.

Dans ce cas, le résultat de puts est très exactement le même que celui de printf, mais ce dernier est moins rapide et efficace car il doit analyser chaque caractère de la chaîne pour vérifier s’il n’y a pas des formats à interpréter (par exemple %d, %c, %f…). Donc les compilateurs ont tout intérêt à utiliser puts à la place.


Voilà, c’est la fin de cet article. ^^
Si un jour vous constatez des comportements bizarres dans vos programmes sans pouvoir l’expliquer par rapport au code C qui semble correct, pensez peut-être à volatile. Que ce soit pour des projets scolaires ou professionnels, il m’a déjà aidé plusieurs fois !

7 commentaires

Juste, la promotion en article, c’est @Aabu qui a proposé, moi j’ai fais que confirmer ^^"
Tu n’aurais pas pu le savoir mais maintenant c’est dis, du coup merci Aabu :)

Édité par ache

ache.one                 🦹         👾                                🦊

+2 -0

Bonjour,

Intéressant, mais je suis dubitatif. Déjà, le code ne gère pas le cas où, vous atteignez votre limite de calcul différemment du cas du contre exemple. Donc, même si un jour, vous attendez assez longtemps la "fin" de votre programme, vous allez croire qu’il existe un contre exemple. En prenant en compte cela, le code nécessite une réécriture, qui, j’ose croire, fera que le programme ne pouvant plus être drastiquement optimisé.

On constate qu’il y a 143 lignes sans les optimisations et seulement 105 avec, donc le compilateur a bien fait son travail.

Pas nécessairement. Je veux dire par là, le nombre de ligne n’indique pas qu’il y a bien fait son travail. Notamment, on pourrait avoir plus de lignes, avec des cas de déroulage de boucle.

Il est très bien d’aller lire l’assembleur (et de savoir le lire) pour ce genre de cas.

Si un jour vous constatez des comportements bizarres dans vos programmes sans pouvoir l’expliquer par rapport au code C qui semble correct, pensez peut-être à volatile. Que ce soit pour des projets scolaires ou professionnels, il m’a déjà aidé plusieurs fois !

Je suis plutôt étonné qu’il y ai besoin d’un tel recours. J’aimerai bien voir un de ces cas pour mieux comprendre. Et puis, moi, en tant que gros débutant, lorsque j’ai des comportements bizarres, bah c’est surtout de ma faute, et non celle d’une optimisation brutale :D.

Ce qui me gêne, c’est que l’on croit que les optimisations de Clang, c’est le mal. Il manque une sorte de conclusion, qui, je pense, devrait dire : les optimisations du compilateur ne sont pas maléfiques, et cet article met simplement en œuvre les capacités d’optimisation du compilateur.

Édité par LittleWhite

+1 -0

Salut,

Merci pour ce message ! Je vais essayer de répondre aux différents points.

Déjà, le code ne gère pas le cas où, vous atteignez votre limite de calcul différemment du cas du contre exemple. Donc, même si un jour, vous attendez assez longtemps la "fin" de votre programme, vous allez croire qu’il existe un contre exemple.

Je ne comprends pas trop ? En fait, tel qu’il est écrit, le code ne peut pas finir autrement qu’avec un contre-exemple, parce que même si on atteint MAXVAL, la boucle for ligne 18 recommence puisqu’elle est dans le while.

Je veux dire par là, le nombre de ligne n’indique pas qu’il y a bien fait son travail. Notamment, on pourrait avoir plus de lignes, avec des cas de déroulage de boucle.

Tout à fait, je suis d’accord ! J’ai fait un raccourci rapide en disant ça, le but était surtout de montrer qu’il s’était bien passé quelque chose de différent au niveau de l’assembleur sans et avec l’optimisation.

Je suis plutôt étonné qu’il y ai besoin d’un tel recours. J’aimerai bien voir un de ces cas pour mieux comprendre. Et puis, moi, en tant que gros débutant, lorsque j’ai des comportements bizarres, bah c’est surtout de ma faute, et non celle d’une optimisation brutale :D.

Alors en fait moi je code presque exclusivement pour de l’embarqué, et dans ce cas, sur microcontrôleur, l’absence de volatile est très souvent la cause de problèmes dans la gestion des interruptions qui peuvent se produire à tout instant et qui perturbent le déroulement du programme. Dans ce cas il est impératif d’avertir le compilateur pour qu’il sache qu’il ne doit pas essayer d’optimiser le traitement des variables modifiées dans les interruptions. Quand on oublie d’en déclarer une avec volatile, ce n’est pas toujours facile de comprendre que l’erreur vient de là. ^^

Ce qui me gêne, c’est que l’on croit que les optimisations de Clang, c’est le mal. Il manque une sorte de conclusion, qui, je pense, devrait dire : les optimisations du compilateur ne sont pas maléfiques, et cet article met simplement en œuvre les capacités d’optimisation du compilateur.

Oui, apparemment ce n’est pas assez clair, on m’a déjà fait la remarque sur mon billet (avant qu’il ne devienne un article). Je poste à nouveau ici ce que j’avais écrit :

"Désolé si le billet donne l’impression que Clang est en tort et a fait une erreur, ce n’est pas du tout ce que je voulais dire. :( Je voulais juste montrer que chaque compilateur peut réagir différemment dans le cas d’un comportement indéfini, et qu’il n’y a pas de bons ou de mauvais choix. Simplement, ici, GCC laisse la boucle et tout semble normal contrairement à Clang qui donne à l’utilisateur une réponse inattendue. Donc on ne peut pas dire qu’il optimise mal, mais il fait un choix qui ne correspond pas à ce que l’utilisateur souhaitait. Mais oui je suis entièrement d’accord que le problème vient du code et pas des compilateurs. Mon programme d’exemple provoque volontairement un comportement indéfini pour bien montrer que si c’est mal codé, on peut s’attendre à avoir des résultats imprévus (ou pas, puisque la norme n’impose rien dans ce cas)."

“I don’t love studying. I hate studying. I like learning. Learning is beautiful.” – Natalie Portman

+1 -0

Merci pour votre réponse. :)

En effet, le mot clé volatile a toute son importance dans un programme embarqué, d’ailleurs c’est son rôle premier : indiquer au compilateur que la variable peut être modifiée par un élément externe. Je posais les questions, car la fin de l’article me fait penser à : "Si j’ai un comportement bizarre, je dois ajouter volatile" :D

Édité par LittleWhite

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte