Comment j'ai rejoint la communauté du bug 323

C'est l'histoire d'un bug à s'arracher les cheveux. Le genre de bug où vous finissez par vous dire : « mais c'est pas possible, c'est le compilateur qui déconne, je vois que ça ! »

Et un bug dans le compilateur, c'est pas rien : en 12 ans de programmation C++, j'en ai trouvé (et rapporté) en tout et pour tout… un seul. Et je peux vous dire qu'avant de faire le rapport de bug à GCC, j'ai testé/retesté/vérifié dans tous les sens pour être sûr de ne pas passer pour un con.

Bref. Je vous raconte.

La découverte

On est en avril 2023. La sortie du jeu étant prévue pour le 15 mai 2023, je suis dans une période de travail assez intense pour essayer de tenir les délais. Je travaille principalement sur la partie « artistique » (dessins, musiques), mais il arrive encore que j'ajoute/corrige des petites choses dans le code.

À l'époque, par habitude, je compile la version Windows avec la variante 32 bits de MinGW : l'inertie des vieilles versions de Windows ne supportant pas l'architecture 64 bits m'avait donné cette habitude qui, en réalité, n'a plus vraiment lieu d'être. Au moment de tester le jeu sur Windows, soudain… un bug. Un crash, pur et simple. Ah.

Je compare l'exécution du programme avec la version Gnunux et je trouve assez rapidement l'endroit où ça plante : au moment où on calcule le fameux « graphe du sol » pour représenter les endroits de la pièce où peuvent marcher les personnages, il y a une divergence dans l'exécution.

Pour faire simple, je crée à ce moment-là le contour du sol représenté par un graphe à partir des valeurs des pixels. Pour cela, je commence par représenter les bords du sol par une polyligne assez complexe qui suit les pixels, puis je fais tourner un algo de simplification de polyligne.

Cet algo, il utilise une queue de priorité : on insère chaque sommet dedans, et on les trie selon leur « déviation », c’est-à-dire selon la distance entre ce sommet et le segment qui rejoint ses deux sommets voisins. Les sommets qui ont la plus petite « déviation » sont ceux qui induiront la plus petite « distorsion » de la polyligne si on les supprime, on va donc commencer par supprimer ceux-là.

Lorsqu'on ne peut plus supprimer de sommet sans induire une distorsion supérieure à un certain seuil, on s'arrête : en pratique, ça permet de trouver rapidement une polyligne simple mais qui reste assez proche des bords du sol.

Eh bien je me rends compte que, pour une raison étrange, l'algorithme sur Windows se met à diverger de celui sur Gnunux après quelques itérations (il supprime un sommet différent et finit par supprimer des sommets qui ne sont pas censés l'être, d'où le crash). Ce qui est franchement bizarre, car l'algorithme est déterministe : donnez-lui la même image d'entrée, il doit vous ressortir exactement la même polyligne après avoir supprimé exactement les mêmes sommets dans l'exact même ordre.

Sur le moment, j'insulte un peu Windows/MinGW car, après avoir lu, relu, rerelu mon code, je soupçonne un bug du compilateur. Sauf que là, réalisant une différence de taille – mon MinGW était en 32 bits quand mon GCC sur Gnunux était sur 64 bits – je tente de compiler mon code sur Gnunux mais en 32 bits… et patatras. Le bug apparaît. Je retente avec Clang. Même bug.

Un bug qui apparaît sur plusieurs compilateurs, ça ne peut pas être un bug de compilateur, me dis-je. Haha. J'étais loin de me douter de la réalité…

Le cœur du bug

Ma queue de priorité est en fait représentée par un std::set (un ensemble d'éléments uniques et maintenus triés), ce qui me permet notamment de pouvoir retirer des éléments qui ne sont pas au début de la queue. La subtilité étant qu'on va donner une fonction de comparaison adaptée au set.

La comparaison est d'abord la fameuse déviation dont je parlais : lorsqu'on insère un sommet dans le set, on veut que les sommets avec la plus petite déviation soient placés en début de set. On va donc faire ça :

bool operator() (const GVertex& a, const GVertex& b)
{
  double da = deviation(a);
  double db = deviation(b);
  return da < db;
});

Mais attention, danger ! Deux sommets peuvent avoir la même déviation, ce qui, dans un std::set qui veille à l'unicité des éléments, signifie que seul le premier sommet serait inséré dans la queue de priorité. Évidemment, on veut pouvoir avoir deux sommets avec la même déviation dans la queue de priorité. Dans ce cas-là, bien sûr, on se fiche de savoir quel sommet va être supprimé en premier, et on va donc simplement prendre le premier sommet du graphe (les sommets sont comparés selon leurs indices), histoire que ça reste déterministe.

La fonction devient donc ça :

bool operator() (const GVertex& a, const GVertex& b)
{
  double da = deviation(a);
  double db = deviation(b);
  if (da == db)
    return a < b;
  return da < db;
});

Très vite, j'identifie que le problème vient de cette fonction : à un moment donné, le if() donne vrai en 64 bits et faux en 32 bits.

Aparté sur les tests d'égalité sur des doubles

Ici, je suis obligé de faire un aparté. J'ai eu le malheur de partager ce bout de code en ligne. Vous n'imaginez pas le nombre de commentaires que j'ai eu et qui disaient, en gros :

Ah ! Mais évidemment, tu fais un test d'égalité sur des doubles ! Faut jamais faire ça ! Le problème vient de là !

Tsss, mais faut JAMAIS tester l'égalité des doubles : si tu veux comparer, tu compares la différence avec une petite tolérance !

Deux double ne sont jamais égaux ! Forcément, tu fais un test d'égalité sur les doubles, tu cherches les ennuis.

Et j'en passe.

Alors.

Ça m'a un tantinet agacé de me retrouver à répondre à 15 messages des gens qui ont simplement intégré « égalité de doubles = danger » et qui me balancent ça sans avoir pris la peine d'essayer de piger ce que faisait le code. Et sans se dire que, peut-être, je suis un peu au courant et que, NON, ça ne vient pas de là.

Pour la petite histoire, avant d'être développeur de jeux vidéo, j'ai fait une thèse en géométrie algorithmique, puis j'ai bossé 6 ans dans une boîte qui éditait un logiciel de géométrie algorithmique. J'ai utilisé notamment des bibliothèques comme MPFR, qui permettent de faire des calculs multiprécisions pour éviter les problèmes que posent les doubles quand on veut faire des calculs sur des nombres réels. Je vous permets de me croire quand je dis que je sais ce que je fais quand je compare des doubles.

Bref. Si vous aussi, en voyant le test d'égalité de double, vous vous êtes dit « lol, le noob, évidemment, ça marche pas les tests d'égalité de double », je me permets quelques mises au point :

1. Un test d'égalité de doubles, c'est valide, c'est pas un tabou, c'est pas Voldemort, vous avez le droit d'en écrire, le monde ne va pas s'écrouler si vous en faites un, vous avez le droit de le faire. À condition de savoir ce que vous faites, oui, évidemment.

2. Le test d'égalité entre double pose problème uniquement si vous pensez être en train de tester l'égalité entre des nombres réels (au sens mathématique du terme). Effectivement, faites le test : (2.01-1.01) n'est pas égal à 1.00 dans la représentation en double, car la précision finie fait qu'une représentation différente d'un unique nombre réel peut donner des valeurs légèrement différentes. Par contre (et j'insiste sur ce point) : (2.01-1.01) est bien garanti d'être égal à (2.01-1.01) ; 1.00 est bien garanti d'être égal à 1.00 ; oui, MÊME en double. Ce que je veux dire, c'est que si vous avez deux doubles qui ont bien la même valeur (la même valeur au sens informatique du terme, avec les mêmes bits dans les mêmes octets), qui ont été calculés de l'exact même manière, alors le test d'égalité entre ces deux double renverra VRAI. Et encore heureux !

3. Dans mon cas précis, c'est même encore plus simple : le cas où les deux doubles sont égaux ne nous intéresse pas, c'est justement un cas particulier qu'on met en place par sécurité, parce que dans le cas où les double sont différents, c'est encore plus simple. Imaginons que vous ayez raison et que « deux doubles ne sont jamais égaux » (ce qui est complétement faux, hein) : dans ce cas-là, aucun problème, puisque le if ne sera jamais vrai et l'algorithme utilisera toujours la déviation comme priorité. En pratique, comme les polylignes viennent de pixels réguliers, évidemment qu'il y aura énormément de déviations égales entre elles…

4. Mettre une tolérance ? Là, pardon, mais il ne faut pas avoir lu le code, ou alors n'y avoir rien compris. Si au lieu de comparer da et db, je fais if(std::fabs(da-db)<epsilon), qu'est-ce qui va se passer ? Eh bien si deux sommets ont une déviation proche, au lieu de les trier par déviation, on va les trier par leurs indices. SUPER. Quel intérêt, à part de rendre l'algorithme moins optimal ?

Bref. C'est très bien d'avoir le réflexe de faire attention avec les comparaisons de doubles. Mais ce serait mieux de comprendre exactement pourquoi et dans quels cas de figure. Ce serait aussi sympa de s'assurer d'avoir pigé le code avant de me commenter des conseils qu'on apprend littéralement en première année de cours de prog.

Aparté terminé.

L'abandon

Je passe littéralement une journée de boulot sur ce bug. En plein rush pour finir le jeu. Je suis en stress, et j'ai beau retourner le problème dans tous le sens, je n'arrive pas à le comprendre. Encore moins à le corriger. Enfin si. J'arrive à le corriger de plusieurs manières qui n'ont aucun sens :

1. En désactivant les optimisations du compilateur
2. En ajoutant un std::cerr au niveau des comparaisons (le bug de Schrödinger : il disparaît quand tu l'observes)
3. En préstockant les valeurs de déviations au lieu de les calculer à la volée (non non, elles ne varient pas, j'ai vérifié)
4. Tout un tas d'autres trucs bizarre (déclarer une autre variable au milieu de la comparaison, par exemple)

Bref. Sur 64 bits ? Aucun problème. Sur 32 bits non-optimisé ? Aucun problème. Sur 32 bits optimisé ? Boum. Erreur.

J'en arrive à un moment où, dans le débuguer, je vois littéralement le programme faire ça :

1. Évaluer l'égalité entre doubles à faux (ce qui est une erreur)
2. Ne pas entrer dans le if()
3. Évaluer ensuite l'inégalité entre les doubles à faux (ce qui est exact mais contredit donc le point 1.)

Ça PUE le bug de compilateur à plein nez. Sauf que, comme je l'ai dit, j'ai l'erreur sur GCC comme sur Clang. Deux compilateurs différents avec le même bug ? Je n'y crois pas.

J'ai perdu une journée et je n'ai pas avancé. En plus, pour la petite histoire, ce bug n'apparaît que dans la version de développement du jeu (et dans la version 32 bits que finalement je ne distribuerai pas) : dans la version distribuée au public, ce fameux graphe du sol est précalculé. Donc dans l'absolu, ce bug ne touchera personne, mais ça m'agace énormément de ne pas comprendre.

N'empêche, je finis par jeter l'éponge : j'ai perdu trop de temps là-dessus, je dois avancer pour finir mon jeu. Je me note dans un coin qu'il faudra que je me repenche dessus plus tard, après la sortie.

La reprise

J'ai tenu les délais, le jeu est bien sorti le 15 mai (jetez-y donc un œil, il est cool).

Avance-rapide jusqu'à hier : on est mi-août, c'est calme, j'ai un moment de creux et je me dis que je vais me replonger dans ce bug, à tête reposée.

Le gros problème du bug de base, c'est qu'il est au milieu d'un très gros programme (le moteur du jeu), avec tout plein de fichiers et de dépendances compliquées. Le réflexe, dans ce cas, c'est d'isoler au maximum la partie qui bug pour s'assurer que le bug ne vient pas d'un truc beaucoup plus tordu (par exemple, une fuite mémoire quelque part dans le jeu qui irait écrire des bêtises dans la queue de priorité).

Je m'y attelle :

1. Je sors le calcul du graphe du moteur de jeu : on charge l'image et on ne fait que le calcul du graph, je dégage les dépendances inutiles (LZ4, YAML)
2. Je réduis au maximum l'image pour n'avoir qu'un petit graphe
3. Je finis par hardcoder le graphe de départ en question (j'arrive à reproduire le bug avec 16 sommets au lieu de 3900), plus besoin de charger l'image, je dégage la dépendance à la SDL
4. Je vire ma mini-bibliothèque de géométrie en ne gardant que les deux trois fonctions utiles
5. Je finis par réduire la queue de priorité au maximum, avec une erreur dès l'insertion du deuxième sommet

Au final, j'arrive à un programme de 50 lignes sans aucune dépendance autre que la STL, et qui déclenche le bug. Le voici :

#include <array>
#include <cmath>
#include <iostream>
#include <set>

using double2 = std::array<double, 2>;

struct Comparator
{
  static double deviation (double2 p)
  {
    const double2 p0 { 1, 0 };
    const double2 vp0p1 { -1 / std::sqrt(2), 1 / std::sqrt(2) };
    const double2 vp0p { p[0] - 1, p[1]};
    const double dotprod = vp0p1[0] * vp0p[0] + vp0p1[1] * vp0p[1];
    const double2 proj { 1 + dotprod * vp0p1[0], p0[1] + dotprod * vp0p1[1] };
    return std::sqrt ((proj[0] - p[0]) * (proj[0] - p[0]) +
                      (proj[1] - p[1]) * (proj[1] - p[1]));
  }

  bool operator() (const double2& a, const double2& b) const
  {
    const double da = deviation(a);
    const double db = deviation(b);
    if (da == db)
      return a < b;
    return da < db;
  }
};

void insert (std::set<double2, Comparator>& set, double2 point)
{
  const double deviation = Comparator::deviation(point);

  std::cerr << "Inserting " << std::defaultfloat << point[0] << " " << point[1]
            << " with deviation = " << deviation << " / hex="
            << std::hexfloat << deviation << std::endl;
  if (set.insert (point).second)
    std::cerr << " -> Success" << std::endl;
  else
    std::cerr << " -> Failure" << std::endl;
}

int main (int, char**)
{
  std::cerr.precision(18);
  std::set<double2, Comparator> set;
  insert(set, { 0, 0 });
  insert(set, { 1, 1 });
  return EXIT_SUCCESS;
}

En gros, ce programme insert deux points dans un std::set avec la fameuse fonction de comparaisons : ces deux points sont différents ((0,0) et (1,1)) mais ont la même valeur de déviation (égale à racine de deux sur deux).

Compilez ce programme en 64 bits et vous aurez comme sortie :

Inserting 0 0 with deviation = 0.707106781186547573 / hex=0x1.6a09e667f3bcdp-1
 -> Success
Inserting 1 1 with deviation = 0.707106781186547573 / hex=0x1.6a09e667f3bcdp-1
 -> Success

C'est effectivement le résultat attendu.

Compilez le en 32 bits avec au moins -O1 activé (-O2 si vous utilisez Clang) et vous aurez :

Inserting 0 0 with deviation = 0.707106781186547573 / hex=0x1.6a09e667f3bcdp-1
 -> Success
Inserting 1 1 with deviation = 0.707106781186547573 / hex=0x1.6a09e667f3bcdp-1
 -> Failure

Le second point n'est pas inséré, il y a un bug.

C'est clair et net.

À ce moment-là, je suis vachement plus sûr de moi sur le côté « mon code est correct, c'est un bug du compilateur ». Et j'ai bien identifié ce qui merdait.

Je cherche alors « c++ O1 optimization double comparison bug branch ». Et la réponse apparaît.

Le fameux bug 323 de GCC

Le bug numéro 323 de GCC, intitulé « optimized code gives strange floating point results » (soit « le code optimisé donne des résultats étranges sur les nombres flottants ») date du 14 juin 2000. Il a, à l'heure où j'écris cet article, 229 commentaires dont 101 qui référent à un « bug dupliqué » (un autre bug que quelqu'un a posté mais qui est en fait le même que celui-là). Voilà pour l'ambiance.

Si ce bug est là depuis si longtemps, c'est que, contrairement aux apparences, ce n'est pas vraiment un bug du compilateur : c'est un bug du processeur. Oui oui, carrément.

Plus précisément, c'est un comportement du FPU (Floating-Point Unit, l'unité de calcul sur les nombres flottants) qui provoque des comportements inattendus lorsque le code est optimisé.

L'idée, c'est que les calculs sur nombres flottants peuvent être faits avec différentes précisions : en RAM, les flottants float ont une précision de 32 bits, les fameux double ont une précision de 64 bits (double précision, donc)… et les calculs dans le FPU utilisent les registres du processeur avec une précision de 80 bits. Cette précision supplémentaire au cours d'un calcul minimise l'erreur d'arrondi.

Que se passe-t-il alors dans mon code ? Eh bien lorsque le code n'est pas optimisé, la valeur de déviation est calculée par le FPU sur 80 bits (dans les registres du processeur) pour chacun des deux sommets, puis stockée dans une variable double sur 64 bits en RAM (et donc arrondie car la précision est moindre) pour chacun des deux sommets. Tout va bien.

Mais lorsque le code est optimisé, le compilateur réalise qu'au moment de calculer la seconde déviation, il est inutile de la mettre dans la RAM (ce qui est coûteux en temps d'exécution) puisqu'elle va resservir immédiatement : autant la garder dans un registre du processeur et la réutiliser directement. Sauf que… elle n'aura donc pas été convertie sur 64 bits et aura donc une meilleure précision que la déviation du premier sommet. Et donc une valeur différente. Et paf, deux valeurs qui devraient être égales deviennent différentes, car l'une a été arrondie sur 64 bits et l'autre non.

C'est ce qui explique que le bug disparaît si on fait des choses apparemment sans rapport dans le code (déclarer une autre variable, ajouter un std::cerr, etc.) : en faisant faire autre chose au processeur entre temps, on va simplement forcer le stockage de la seconde déviation en RAM, ce qui règle le problème.

Évidemment, ce comportement a été corrigé dans les générations suivantes de FPU pour respecter la norme IEEE-754 qui dit notamment qu'un calcul flottant doit être déterministe. Mais voilà, comme c'est un problème au cœur du processeur, on retrouve le bug chez GCC comme chez Clang (comme chez d'autres, probablement). Et ce fameux bug 323 continue d'être régulièrement commenté et dupliqué, car ce n'est pas à proprement parler un bug de GCC.

Je suis quand même assez d'accord avec ce commentaire :

Appeler deux fois une fonction triviale avec un paramètre identique peut renvoyer une valeur inférieure, égale ou supérieure à elle-même (en fonction de l'allocation des registres dans le contexte des appels). Il s'agit là d'un comportement non-déterministe vraiment crade. Les compilateurs et les langages de « haut niveau » n'ont-ils pas été inventés pour contourner exactement ce type de dépendance matérielle ?

Et pour finir, un petit commentaire qui m'a fait rire car j'ai eu la sensation qu'il me parlait directement :

J'aimerais souhaiter la bienvenue aux nouveaux membres de la communauté du bug 323, où toutes les erreurs de virgule flottante x87 dans gcc viennent mourir ! Toutes les erreurs de virgule flottante qui utilisent le x87 sont les bienvenues, même si beaucoup d'entre elles sont facilement corrigeables, et que beaucoup ne le sont pas ! Nous sommes une famille heureuse, nous avons juste commis l'erreur scandaleuse de vouloir de la précision de la part du FPU le plus précis du marché !

Comment on corrige ça ?

Bon, ce comportement peut arriver, on a pigé pourquoi, mais maintenant une question pratique : comment on empêche notre code de déclencher ce comportement ?

Eh bien vous avez la méthode bourrine : vous pouvez utiliser l'option -ffloat-store au moment de la compilation. Cette option force littéralement le compilateur à stocker tous les flottants dans la RAM (ce qui rend donc l'erreur ci-dessus impossible). Alors certes, ça résout le bug, mais c'est aussi un peu dommage car ça neutralise un bon paquet d'optimisations qui peuvent être intéressantes (le fait de ne pas stocker les flottants en RAM lorsque ce n'est pas nécessaire est très avantageux et sans danger dans 99 % des cas).

Un moyen beaucoup plus fin (car vous pouvez ne l'intégrer qu'aux endroits potentiellement problématiques de votre code, typiquement sur les tests d'égalité de double), c'est d'utiliser le mot-clef « volatile ». Pour citer Wikipédia, « une variable volatile est une variable sur laquelle aucune optimisation de compilation n'est appliquée ». Tout simplement : on désactive les optimisations localement et non globalement.

Il suffit donc de modifier notre fonction de comparaison ainsi :

  bool operator() (const double2& a, const double2& b) const
  {
    const volatile double da = deviation(a);
    const volatile double db = deviation(b);
    if (da == db)
      return a < b;
    return da < db;
  }

Et le bug disparaît. Vous pouvez tester, le code fonctionne maintenant même en 32 bits avec les optimisations.

VICTOIRE !

Addendum (3 septembre 2023)

Bon, cet article a un peu tourné, et j'ai vu pas mal de gens réagir en disant : « ah, mais du coup, au final, c'était bien le bon réflexe de se méfier des tests d'égalité de double, tu vois, on avait raison ! »

Alors, si c'est votre conclusion, je vous invite à relire l'article. La solution à mon problème n'est pas de ne pas faire de test d'égalité sur des doubles, elle est de désactiver les optimisations, c'est très différent.

Si vous me dites « ne traverse pas la route, tu pourrais te faire heurter par une licorne », et qu'en traversant la route, je me fais renverser par une voiture, vous n'aviez pas raison. Alors oui, si je vous avez écouté, je n'aurai pas eu de problème, mais ça aurait impliqué quantité d'autres trucs problématiques. En l'occurrence, on a besoin de faire des tests d'égalité sur des doubles, sinon vous avez un paquet de bibliothéques scientifiques qui ne peuvent tout simplement plus exister.

J'insiste, mais on parle de deux comportements des nombres flottants qui n'ont rien à voir l'un avec l'autre :

• le fait que (2.01-1.01) ne soit pas égal à 1.00 en double est un résultat correct et attendu ; ça respecte la norme C++ ; si vous apprenez correctement à vous servir des nombres flottants, c'est clair et logique ; ça arrivera avec n'importe quelle implémentation des nombres flottants, sur n'importe quelle architecture ;

• le fait qu'un même et unique test donne vrai à un endroit du code puis faux est un bug ; ce n'est pas un résultat attendu ; ce n'est pas logique ; ça n'arrive qu'avec une certaine architecture et avec un certain niveau d'optimisation ; même en ayant bien lu la norme C++, ce n'est pas quelque chose que vous pouvez prévoir.

Et si vous commencez à coder en évitant certains trucs dans l'hypothèse qu'il puisse y avoir un souci dans l'architecture du processeur ou qu'un truc aussi simple qu'un test d'égalité puisse devenir non-déterministe, vous pouvez juste arrêter l'informatique tout de suite.

Au passage, ce bug ne se limite pas aux tests d'égalité, donc corriger cela en remplaçant le test d'égalité par un test de comparaison avec un epsilon ne vous en préserve absolument pas : votre comparaison peut tout aussi bien retourner faux puis vrai.

Bref, je ne vais pas épiloguer, mais restons carré sur les problèmes et les solutions : ici, c'est un problème d'optimisation, on désactive donc les optimisations (via le mot-clef volatile). Simple, non ?

Conclusion

Je croyais que les bugs de compilateur étaient les pires trucs qui pouvaient arriver en programmation (car le dernier truc qu'on soupçonne) : j'avais tort, les bugs du processeur sont pires.

Malgré toutes les heures perdues sur ce bug, je suis content d'une chose : avoir été suffisamment opiniâtre pour finalement arriver à comprendre ce qui se passait. Avec, cerise sur le gâteau, un correctif simple et optimal (l'usage de volatile).

Si je devais conclure sur un conseil : lorsque vous avez un bug, ne lâchez jamais l'affaire avant d'avoir vraiment compris le fond du fond du problème (bon, à condition d'avoir le temps pour le faire, ce qui est souvent le paramètre limitant). Souvent, vous allez comprendre un vrai souci dans votre code ; parfois, vous allez inopinément apprendre plein de trucs sur l'optimisation au niveau du processeur, et mine de rien, c'est pas tous les jours que ça arrive.