Les points flottants n°3 : ne mettez pas ça dans un float !

Beaucoup de jeux ont une sorte de fonction GetTime() qui retourne le temps écoulé depuis le début du jeu. Souvent elles retournent un nombre flottant par confort parce que cela autorise l'utilisation de la seconde comme unité, tout en autorisant également une précision en dessous de la seconde.

GetTime() est généralement implémenté avec une sorte de timer haute fréquence tel que QueryPerformanceCounter. Cela autorise une précision du temps à la microseconde ou mieux. Mais regardons ce qu'il advient de cette précision si le temps est retourné comme un float ou stocké dans un float. On peut le faire en utilisant une des fonctions TestFloatPrecision de l'article précédent - il suffit de les appeler depuis la fenêtre de watch du débuggeur. Dans le screenshot ci-dessous j'ai testé la précision disponible pour une minute, une heure, un jour, une semaine :

Il est important de comprendre ce que signifient ces données. Le nombre ‘60', comme tous les entiers jusqu'à 16777216, peut être représenté exactement dans un float. La fenêtre de watch montre que la valeur suivante après 60 pouvant être représentée dans un float est environ 60,0000038. Ainsi donc, si l'on utilise un float pour stocker “60 secondes” alors le temps suivant que l'on peut représenter est “60 secondes et 3,8 microsecondes”. Si l'on essaie de stocker une valeur entre les deux, alors elle sera arrondie au dessus ou en dessous.

Une des choses les plus courantes à faire avec des valeurs de temps est de les soustraire. Par exemple, on pourrait avoir un code comme celui-ci :

double GetTime();

float TimeSomethingBadly()
{
    float fstart = GetTime();
    DoSomething();
    float elapsed = GetTime() - fstart;
    return elapsed;
}

L'intérêt des calculs de précision plus haut est que si ‘fstart' est environ 60, alors ‘elapsed' sera un multiple de 3,8 microsecondes (2 à la puissance -18 secondes). C'est la meilleure précision que vous pouvez obtenir. Si moins de 3,8 microsecondes se sont écoulées alors ‘elapsed' sera arrondie soit en dessous à zéro, soit au dessus à 3,8 microsecondes.

Ainsi, si notre timer de jeu commence à zéro et que l'on stocke le temps dans un float alors après une minute la meilleure précision que nous pouvons obtenir est de 3,8 microsecondes. Après que notre jeu a tourné pendant une heure notre meilleure précision descend à 0,24 millisecondes. Après que notre jeu a tourné pendant un jour notre précision descend à 7,8 millisecondes, et après une semaine notre précision descend à 62,5 millisecondes.

C'est pour cela que stocker le temps dans un float est dangereux. Si vous utilisez un temps flottant pour essayer de calculer votre framerate, après avoir tourné durant un jour alors les seules réponses possibles au dessus de 30 fps sont l'infini ; 128 ; 64 ; 42,6 ou 32 (attendu que les durées de frame sont 0 ; 7,8 ; 15,6 ; 23,4 ou 31,2 millisecondes). Et ça ne fait qu'empirer si vous faites tourner plus longtemps.

Voici un autre exemple :

double GetTime();

void ThinkBadly()
{
    float startTime = (float)GetTime();
    //Faire toute l'IA ici
    float elapsedTime = GetTime() - startTime;
    assert(elapsedTime < 0.005);
}

L'utilité de ce code est d'avertir les développeurs lorsque le code de l'IA prend exceptionnellement trop longtemps. Mais lorsque le jeu a tourné pendant un jour (en réalité le problème survient ici après seulement 65,536 secondes), GetTime() retournera toujours un multiple de 0,0078 s, et ‘elapsedTime' sera toujours un multiple de cette durée. Dans la plupart des cas ‘elapsedTime' sera toujours égale à zéro, mais de temps en temps, qu'importe la vitesse à laquelle le code de l'IA s'exécute, le temps s'arrondira à la représentation suivante pendant les calculs de l'IA et ‘elapsedTime' sera à 0,0078 s au lieu de zéro. L'assertion se déclenchera même si le code de l'IA est en réalité en dessous de la limite imposée.

Le terme général pour ce qui arrive ici est la catastrophique perte de précision. Dans tous les exemples ci-dessus il y a deux valeurs de temps qui sont exactes sur environ sept chiffres. Mais elles sont si proches l'une de l'autre que lorsqu'elles sont soustraites le résultat a, dans le pire des cas, zéro chiffre significatif.

On peut voir la même chose arriver avec les nombres décimaux. Un float possède en gros sept chiffres décimaux de précision alors l'équivalent décimal serait une valeur de temps de 60,00000 et la valeur possible suivante serait de 60,00001. Étant donné un nombre décimal flottant à sept chiffres, nous ne pouvons obtenir une précision de plus d'un dixième de microseconde lorsque l'on utilise des temps d'environ 60 secondes. Lorsque l'on soustrait 60,00000 à 60,00001 alors six des sept chiffres s'annulent et on finit avec un seul chiffre significatif. Pour des temps de moins d'un dixième de microseconde c'est une catastrophe complète - les sept chiffres s'annulent et on se retrouve avec zéro chiffre de précision, exactement comme un binaire flottant.

La solution à tout cela est simple. GetTime() doit retourner un double, et son résultat doit être stocké dans un double. La perte apparaît toujours, mais n'est plus catastrophique. Un double a assez de bits dans la mantisse pour que même si vous laissez tourner votre jeu durant plusieurs millénaires votre timers précision double auront toujours une précision inférieure à la microseconde. Vous pouvez vérifier cela en utilisant la variation double précision de TestFloatPrecisionAwayFromZero():

union Double_t
{
    Double_t(double val) : f(val) {}
    // Extraction portable des composantes
    bool Negative() const { return (i >> 63) != 0; }
    int64_t RawMantissa() const { return i & ((1LL << 52) - 1); }
    int64_t RawExponent() const { return (i >> 52) & 0x7FF; }
    int64_t i;
    double f;
#ifdef _DEBUG
    struct
    {   // Champs pour l'exploration. Ne pas utiliser dans un code de production.
       uint64_t mantissa : 52;
       uint64_t exponent : 11;
       uint64_t sign : 1;
    } parts;
#endif
};
double TestDoublePrecisionAwayFromZero(double input)
{
    union Double_t num(input);
    // Incrémenter jusqu'à Infini ou NaN serait une mauvaise chose !
    assert(num.RawExponent() < 2047);
    // Incrémente la représentation entière de notre valeur
    num.i += 1;
    // On soustrait la valeur initiale pour trouver notre précision
    double delta = num.f - input;
    return delta;
}

Vous pouvez voir dans le screenshot ci-dessous que si vous stockez le temps dans des double alors après que votre jeu a tourné pendant une semaine vous avez encore une précision inférieure à la nanoseconde, et après trois millénaires vous avez encore une précision sous la milliseconde.

Un double est clairement un bazooka devant une mouche pour stocker le temps, mais puisqu'un float est insuffisant alors un double est le bon choix.

Note : mon calcul initial de la précision restante après trois millénaires était fausse parce que le calcul du nombre de secondes était fait avec les mathématiques entières, et cela avait donné un overflow ce qui entraînait une réponse totalement faussée. Ce qui prouve que les mathématiques entières peuvent être aussi piégeuses que les mathématiques flottantes.

Depuis le début j'ai assumé que vous stockiez votre temps en secondes. Mais votre choix d'unité n'affecte pas significativement les résultats. Si vous décidez que votre unité de temps est la milliseconde ou le jour, alors la précision disponible après que le jeu a tourné pendant un jour sera la même. C'est le ratio entre le temps écoulé et le temps mesuré qui est important.

Tom Forsyth nous montre que les mêmes problèmes surviennent avec les coordonnées d'un monde et que passer à des types entiers peut vous donner une meilleure précision dans le pire des cas aussi cohérente. Les fonctions GetTickCount() et GetTickCount64() de Windows utilisent cette technique, avec des millisecondes pour unités. Cette alternative aux double pour le temps est plutôt raisonnable, particulièrement si vous l'encapsulez bien. Un uint32_t avec comme unité la milliseconde provoquera un overflow tous les 50 jours ou presque, mais vous pouvez éviter cela en utilisant un uint64_t. Toutefois, malgré la menace de Tom d'invoquer sa règle OffendOMatic pour tous ceux qui utilisent des double, je préfère encore utiliser les double à cause de la combinaison des unités confortables (secondes) et de la précision plus que suffisante.

Alors que Tom et moi sommes en désaccord sur le choix d'utiliser ou non des double dans ce genre de situations, sous sommes d'accord sur le fait que les float ne marcheront pas.

Notez que même si GetTickCount() et GetTickCount64() ont une précision à la milliseconde, elles sont souvent en réalité bien moins précises que ce que l'on pourrait croire. À moins que vous n'ayez modifié la fréquence du timer Windows avec timeBeginPeriod() les fonctions GetTickCount retourneront une nouvelle valeur seulement toutes les 10~20 millisecondes (insérer ici un commentaire vigoureux sur précision vs exactitude).

Même si vous utilisez des double pour le temps, la précision disponible changera quand même quand le temps du jeu évoluera de zéro à la longueur de votre jeu. Ces changements de précision - bien que plus petits avec les double qu'avec les float - peuvent encore être dangereux. Heureusement il y a un moyen simple d'obtenir la précision consistante d'un entier, avec les unités pratiques du double.

Si vous démarrez votre horloge de jeu à environ 4 milliards (plus précisément 2^32, ou n'importe quelle grande puissance de 2) alors votre exposant, et donc votre précision, restera constante pour les ~4 milliards prochaines secondes, soit ~136 ans.

Et quand vous utilisez les double ainsi, la précision est d'environ une microseconde.

Voilà vous l'avez. La vraie réponse. Stockez le temps écoulé de votre jeu dans un double, en commençant à 2^32 secondes. Vous obtiendrez une précision constante de plus d'une microseconde pendant tout un siècle. Vous avez lu ça ici en premier.

Il est important de comprendre que la précision limitée d'un float n'est un problème que si vous faites une opération instable, comme la catastrophique perte de précision qui supprimera la plupart de vos chiffres. Le code ci-dessous, en revanche, est excellent :

double GetTime();
float TimeSomethingWell()
{
    double dStart = GetTime(); // Stocke le temps dans un double
    DoSomething();
    float elapsed = GetTime() - dStart; // Stocke le *résultat* dans un float
    return elapsed;
}

Dans TimeSomethingWell() on stocke le résultat de la soustraction dans un float - après la catastrophique perte de précision. Ainsi donc notre temps écoulé aura toute la précision désirée.

De même, si vous utilisez des float dans votre système d'animation pour représenter des temps courts, tels que la position d'une key-frame dans une animation de 60 secondes, alors les float sont parfaits. Par contre lorsque vous les ajoutez au temps actuel vous devez absolument stocker le résultat de l'addition dans un double.

Forrest Smith a réalisé un joli tableau montrant combien la précision d'un float change en même temps que la valeur augmente, et je l'ai modifié selon mes besoins. La voici pour le temps :

Et voici le tableau montrant combien la précision d'un float diminue quand vous l'utilisez pour mesurer de grandes distances, avec les mètres comme unités de mesure dans ce cas :

Il y a quelques temps de cela, j'ai entamé quelques recherches dans un système d'animation de particules. Les valeurs étaient out-of-range après moins d'une heure de jeu et je suis tombé sur une valeur ‘t' out-of-range passée à la fonction d'interpolation linéaire, qui exigeait qu'elle soit toujours entre 0,0 et 1,0. Le verrouillage était une solution évidente, mais j'ai commencé par rechercher pourquoi ‘t' était out-of-range.

Un des problèmes avec ce code était que les trois paramètres étaient tous des float, donc sur de longues périodes de temps la précision aurait été inévitablement insuffisante. Mais nous rencontrions une instabilité plus tôt que prévu et il aurait semblé que passer aux double immédiatement aurait seulement masqué un problème sous-jacent.

Les paramètres de la fonction, tous des valeurs de temps en secondes, correspondaient à la fin d'un segment d'animation, la longueur de ce segment et le temps actuel, qui était toujours entre le début du segment (segmentEnd-segmentLength) et ‘segmentEnd'. Le début du segment n'étant pas passé en argument, ce code le calculait, et faisait ensuite un calcul simple pour obtenir ‘t' :

float CalcTBad(float segmentEnd, float segmentLength, float time)
{
    float segmentStart = segmentEnd - segmentLength;
    float t = (time - segmentStart) / segmentLength;
    return t;
}

Simple, mais instable. Parce que l'on présume que ‘segmentLength' est plutôt petit comparé à ‘segmentEnd', il y a un arrondi durant la première soustraction et la différence entre ‘segmentStart' et ‘segmentEnd' sera un peu plus grande ou un peu plus petite que ‘segmentLength'. La différence qui en résulte sera toujours un multiple de la précision actuelle, donc elle se dégradera dans le temps, mais même au tout début du jeu le résultat ne sera pas parfait. Parce que la valeur pour ‘segmentStart' est légèrement fausse la valeur de “time - segmentStart” sera légèrement fausse, et parfois ‘t' sera en dehors de la fourchette 0.0 à 1.0.

Ceci arrivera même si vous utilisez les doubles. Les erreurs seront plus faibles, mais ‘t' peut tout de même se trouver en dehors de la fourchette 0.0 à 1.0. Pendant que le jeu avance, ‘t' se retrouvera plus loin à l'extérieur de la plage autorisée, mais après seulement quelques minutes de jeu les résultats montreront des signes d'instabilité.

La tendance naturelle est de dire “les maths flottantes sont floues, encadrez les résultats et avancez”, mais on peut faire mieux comme il est montré ici :

float CalcTGood(float segmentEnd, float segmentLength, float time)
{
    float howLongAgo = segmentEnd - time;
    float t = (segmentLength - howLongAgo) / segmentLength;
    return t;
}

Mathématiquement ce calcul est identique à CalcTbad, mais d'un point de vue stabilité il est largement amélioré.

Si on assume que ‘time' et ‘segmentEnd' sont grands comparés à ‘segmentLength', alors on peut raisonnablement supposer que ‘segmentEnd' est moins de deux fois plus grand que ‘time'. Et il en découle que si deux float sont aussi proches alors leur différence rentrera exactement dans un float. Toujours. Ainsi le calcul de ‘howLongAgo' est exact. Réfléchissez-y un moment - étant données quelques suppositions raisonnables nous avons des résultats exacts pour une de nos opérations de maths flottantes.

Avec ‘howLongAgo' exact, si ‘time' est dans la plage prescrite alors ‘howLongAgo' sera entre zéro et ‘segmentLength', de même pour ‘segmentLength' moins ‘howLongAgo'. Les maths flottantes IEEE garantissent un arrondi correct donc lorsque l'on divise par ‘segmentLength', nous sommes certains que ‘t' sera entre 0.0 et 1.0. Pas d'encadrement nécessaire, même avec des floats.

Cet exemple concret démontre quelques choses :

- A chaque fois que vous ajoutez ou soustrayez des float dont la magnitude varie grandement vous devez faire attention à la perte de précision ;

- Parfois utiliser ‘double' au lieu de ‘float' est la meilleure solution, mais souvent un algorithme plus stable est plus important ;

- CalcT devrait probablement utiliser des double (pour garantir une précision suffisante après plusieurs heures de gamaplay).

Avec Visual C++ avec le niveau d'avertissement par défaut vous obtiendrez le warning C4244 lorsque vous assignez un double à un float :

warning C4244: ‘initializing' : conversion from ‘double' to ‘float', possible loss of data

La perte possible de données n'est pas nécessairement un problème mais peut l'être. Supprimer les warnings avec #pragma warning ou un cast est quelque chose qui devrait être fait avec précaution, après avoir compris le problème. Autrement, le compilateur pourrait dire “je t'avais prévenu” lorsque votre jeu crashe après un test d'immersion de 24h.

Pour certains types de jeu, ce problème sera dénué de sens. Beaucoup de jeux se terminent en moins d'une heure, et un float qui contient 3,600 (secondes) a encore une précision sous la milliseconde, ce qui est assez dans la plupart des cas. Cela signifie que pour ces types de jeux vous pourriez parfaitement stocker le temps dans un float, du moment que vous réinitialisez le point de départ de GetTime() au début de chaque jeu, et que l'horloge arrête de tourner quand le jeu est mis en pause.

Pour les autres types de jeu - probablement la majorité des jeux - il est nécessaire de faire vos calculs de temps en utilisant double ou uint64_t. J'ai vu des problèmes sur de multiples jeux qui échouaient à suivre cette règle. Les problèmes sont particulièrement difficiles à traquer et à résoudre parce qu'ils peuvent prendre plusieurs heures à se montrer.

Stockez vos valeurs de temps dans un double, en commençant à 2^32 secondes, ainsi vous n'aurez pas besoin de vous inquiéter, du moins pas autant, tant que vous évitez les algorithmes instables.

Un grand nombre de personnes ont commenté cet article et dit que la justification pour utiliser un double à la place d'un entier de 64 bits n'était pas très importante. Je suis d'accord sur le fait que les deux fonctionnent mais je pense que double a quelques avantages. Le premier est le confort du développeur. Un nombre flottant comme 1.73 est bien plus simple à comprendre que 1730 (point fixe avec la précision à la milliseconde) et il a une meilleure précision. Plus vous donnez de précision à entier à point fixe, plus les nombres sont complexes à manier, et il y a un réel coût à cela.

L'autre raison est spécifique à l'industrie du jeu. Quand un jeu fait des calculs de temps, il utilise généralement les valeurs de temps pour la physique, l'IA, les graphismes ; et ces systèmes nécessitent généralement des nombres flottants. Donc, cela implique que vous ne pouvez pas éviter le temps en point flottant. Par conséquent, vous pourriez aussi bien avoir fait ainsi de prime abord, et l'avoir bien fait. La plupart des jeux utilisent déjà les nombres flottant pour le temps - je veux seulement les encourager à ne pas utiliser ‘float'.

Il est également intéressant de noter que Apple utilise double pour le temps - NSTimeInterval est un double. Comme ils le précisent : “NSTimeInterval est toujours spécifié en secondes ; ceci permet une précision inférieure à la milliseconde pour une durée de 10.000 ans.”

Dans le prochain post je pense qu'il pourrait finalement être temps de commencer à se jeter dans le sujet délicat qu'est la comparaison des nombres flottants, avec toutes les subtilités qu'il comporte.