Discussion :

[me_myself]

Bonjour,

J'ai de nombreux calculs où je dois soit faire un calcul de doubles casté dans un integer, ou soit inversement faire une opération comme une division d'integers vers un double.

Rien de bien compliqué certes, mais multiplié par des millions d'opérations, cela peut y avoir des variations considérables de temps de calcul.

Quels sont toutes les différentes options et leur 'coût' en temps de calcul?


Merci d'avance

bv

[loufoque]

Un cast créé une nouvelle variable, éventuellement temporaire.

[me_myself]

OK, mais si je ne fais pas un cast explicite, je laisse le compilateur faire, il me donne un warning (possible data loss) mais évidemment ça marche.

Mais comment faire proprement et le plus efficacement?

Merci

bv

[Médinoc]

L'affectation d'un nombre à virgule flottante dans un entier, avec ou sans cast explicite, entrainera toujours la conversion à un moment ou à un autre.

"On" m'a dit qu'une conversion entre flottant et entier était plus couteuse qu'une simple opération de calcul flottant, et qu'il fallait réduire les conversions au minimum...

[Jan Rendek]

OK, mais si je ne fais pas un cast explicite, je laisse le compilateur faire, il me donne un warning (possible data loss) mais évidemment ça marche.

Mais comment faire proprement et le plus efficacement?

Merci
bv

Implicite ou explicite, la transformation d'un entier en double ou l'inverse sera rigoureusement la même. Le cast explicite indique au compilo que tu connais les conséquences (nombre tronqué, etc...), ce qui rend le warning inutile.

La seule solution c'est de revoir l'algorithme pour limiter les transtypages au strict minimum.

[bricerive]

Si tu dois vraiment faire du cast de double vers int en grande quantite, je te recommande cette petite merveille:
(Pour ceux qui voient vraiment pas comment ca peut marcher, au point de croire que ca marche pas, je ne saurais trop recommander de faire un essai)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
#define D2I_CONVERSION_FACTOR (1.5 * 4503599627370496.0)
inline int d2i(double val)
{
    union {
        int i[2];
        double d;
    } dlong;
    dlong.d = val + D2I_CONVERSION_FACTOR;
    return dlong.i[0];
}

C'est plus rapide qu'un cast standard par un facteur de 8, et meme plus rapide qu'un cast en assembleur du genre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
double d;
int val;
__asm {
  fld qword ptr[d]
  fistp dword ptr[val]
}

J'ai verifie moi-meme.

les limitations du truc:
-Tres difficile a comprendre (je peux filer une explication si tu cale et que ca t'interesse).
-Les ints doivent etre en 32 bits
-Les doubles doivent etre en representation standard (1/11/52)
-Marche tel quel uniquement sur une machine big-endian
-Pas du tout du tout de verification ou de traitement d'erreurs.
Les trois premieres peuvent etre contournees, la derniere non :-)

Il est possible de faire la fonction inverse ;-)

[Médinoc]

Ça joue sur la représentation standard.
Je suppose que ton D2I_CONVERSION_FACTOR sert à forcer l'exposant à une valeur connue...

Je me rappelle avoir écrit une macro qui, au lieu de passer par une union, faisait du transtypage de pointeur pour pouvoir accéder aux données du double en tant qu'entier...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
#define DBL2LONG_0(dbl) (reinterpret_cast< long *>(&(dbl))[0])
#define DBL2LONG_1(dbl) (reinterpret_cast< long *>(&(dbl))[1])
 
#ifdef BIG_ENDIAN //Ou tout autre #define dépendant de l'endianness
#define DBL2LONG_H(dbl) DBL2LONG_0(dbl)
#define DBL2LONG_L(dbl) DBL2LONG_1(dbl)
#else
#define DBL2LONG_H(dbl) DBL2LONG_1(dbl)
#define DBL2LONG_L(dbl) DBL2LONG_0(dbl)
#endif

De là, si le double est en représentation standard, on peut accéder à sa mantisse et à son exposant...

[bricerive]

Tu as raison, bravo.
Un peu plus de details:
4503599627370496.0 = 2^52
donc D2I_CONVERSION_FACTOR est egal a 2^52 + 2^51
Comme tu l'as compris, en ajoutant ca a un double (pas trop grand en valeur absolue), on force la mantisse a etre pile poil arrondie a l'int le plus proche par le FPU.
Ensuite il suffit d'y acceder directement avec l'union (ou avec le double cast comme dans ta macro).
J'adore :-)

Question subsidiaire: pourquoi "2^52+2^51" et pas simplement "2^52"

[Médinoc]

Pour forcer le second bit à 1, car le premier est implicite ?

[JolyLoic]

Parmi les inconvénients de cette méthode, j'ajouterai :
- Aucune garantie que ça fasse quoi que ce soit. Ecrire dans un membre d'une union et lire dans un autre est un comportement indéfini. Il se peut que ça marche sur une certaine machine, avec une certaine version d'un compilateur, avec certaines options de compilation, pendant certaines phases de la lune, mais rien n'est moins sur.

Là où je suis surpris, c'est quand tu annonces un rapport 8... A la base, ce n'est qu'une manipulation basique de la représentation des flottants, et on pourrait imaginer que c'est justement ce genre de manipulation que fait la conversion de base. Pris d'un doute, j'ai donc fait des tests (compilateur visualC++2005, options de compilaton par défaut en release)...

Déjà, le résultat n'est pas le même qu'un simple cast en int. Un cast tronque, ta méthode fait autre chose.

Pour des petits nombres positifs, en enlevant 0.5 à la valeur passée, on se ramène dans le cas où les valeurs produites sont identiques. Il faut ajouter 0.5 pour une valeur petite négative. Pour des grand nombres, proches des entiers de taille maximale, des erreurs subsistent, que je n'ai pas voulu corriger... L'écart entre les deux méthodes est au plus d'une unité.

Avec ce test, ta méthode est plus lente de 15% à 25% que la méthode de base. Sans ce test (en se limitant à des nombres positifs), elle est plus rapide de 10% à 20%. Les variations dépendent de si je fais beaucoup d'itérations sur des petits jeus de données, ou moins d'itération sur des plus grand (moins bonne utilisation de la mémoire, qui vient masquer les différences, ce qui tend à dire que dans une utilisation classique, la différence sera probablment elle aussi masquée par d'autres aspects)

On est quoi qu'il en soit loin du *8 sur cette architecture.

Voici mon code de test, si certains veulent s'amuser avec ou le critiquer :
main.cpp

clock.h

clock.cpp

[Jan Rendek]

Le code le plus tordu pour amélioré la vitesse du transtypage n'est à utiliser qu'APRES avoir revu et corrigé l'algorithme initial.
Le gain en temps de ce type de code 'funky' est souvent marginal sur l'algo revu et corrigé.

[thewho]

Bonjour,

@ bricerive:

Je ne vais pas critiquer ton code, mais tes affirmations:

J'ai testé les performances, car tes affirmations me paraissaient un peu trop optimistes, pour ne pas dire fausses (sans perdre de vue que les performances sont directement liées à la qualité de l'implémentation du compilateur, un peu moins dépendant pour la partie assembleur, en principe)

(tests faits sur un Athlon XP 2600, Windows, compilateur mingw, pas d'optimisation, résultats très similaires en activant les optimisations)

- Ca va plus vite que le cast classique d'un facteur 2.5

- MAIS en utilisant l'assembleur (celui que tu as donné), le rapport de vitesse s'inverse !

Je vais quand même critiquer un peu ton code : pourquoi cette définition

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

#define D2I_CONVERSION_FACTOR (1.5 * 4503599627370496.0)

au lieu de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

#define D2I_CONVERSION_FACTOR  6755399441055744.0

Après tout, c'est un astuce pour gagner en vitesse, pourquoi faire une multiplication dans le calcul, alors qu'on peut la faire en avance ?

[JolyLoic]

Je vais quand même critiquer un peu ton code : pourquoi cette définition

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

#define D2I_CONVERSION_FACTOR (1.5 * 4503599627370496.0)

au lieu de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

#define D2I_CONVERSION_FACTOR  6755399441055744.0

Après tout, c'est un astuce pour gagner en vitesse, pourquoi faire une multiplication dans le calcul, alors qu'on peut la faire en avance ?

Parce que c'est plus clair ? (bon, là, ya quand même une constante pas hyper lisible, mais bon...). Je ne connais pas de compilateur qui, en mode optimisé, ne génèrerait pas le même code avec les deux écritures.

[JolyLoic]

(tests faits sur un Athlon XP 2600, Windows, compilateur mingw, pas d'optimisation, résultats très similaires en activant les optimisations)

- Ca va plus vite que le cast classique d'un facteur 2.5

Ca m'étonne qu'il y ait peu de rapports entre les versions de base et optimisées. C'est quand même une fonction tellement courte qu'on pourrait s'attendre à ce que l'inlining ait de l'effet. Pour le rapport de 2.5, il est loin de mes mesures. Serait-il possible de poster ton code, car comme l'a dit je ne sais plus qui, il ne faut jamais croire un benchmark qu'on n'a pas trafiqué soi-même...

[thewho]

Bonjour,

Parce que c'est plus clair ? (bon, là, ya quand même une constante pas hyper lisible, mais bon...). Je ne connais pas de compilateur qui, en mode optimisé, ne génèrerait pas le même code avec les deux écritures.

C'est pour aller vite, la clarté est accessoire, et peut être établie avec une petite ligne de commentaire.
Mais il est vrai que normalement le pré-compilateur doit s'occuper de ça, mais ce n'est pas garanti (chez moi, j'observe une différence entre les 2 définitions, faible, mais reproductible).


Pour le code, il faut attendre que je sois rentré.

[thewho]

Bonjour,

Effectivement, les vitesses proches en optimisant ou non m'intriguaient quand même un peu.

Je viens de vérifier, et je m'aperçois que j'avais utilisé un mauvais batch (j'en ai défini quelques uns pour me faciliter la vie, pas toujours écrire la même chose)

Donc rectification :

Dans tous les cas avec optimisation, le cast gagne sur l'astuce

même si ce n'est pas énorme en gain.

Pour le code, comme c'est carrément brouillon (pour rester poli !), car c'est un programme qui ne me sert qu'à faire des tests, et ça finit par être très encombré.
Ça va me demander un peu de travail pour la mise au net, mais pour résumer :

- les temps d'exécution sont mesurés avec QueryPerformanceCounter sur un grand nombre de boucles, sans que je prenne la peine de tenir compte du temps passé à boucler, puisqu'il est le même dans les 2 mesures, à optimisations égales.

[bricerive]

Pour forcer le second bit à 1, car le premier est implicite ?

C'est en fait pour être certain de rester avec la mantisse alignée sur le bit 0 quand on a des doubles négatifs.

- Aucune garantie que ça fasse quoi que ce soit. Ecrire dans un membre d'une union et lire dans un autre est un comportement indéfini. Il se peut que ça marche sur une certaine machine, avec une certaine version d'un compilateur, avec certaines options de compilation, pendant certaines phases de la lune, mais rien n'est moins sur.

Tu as raison. On peut un peu réduire ce problème en utilisant le réinterpret_cast suggèré par Médinoc, mais de toute façon, le truc entier dépend d'un tas de conditions similaires: c'est un hack!

Déjà, le résultat n'est pas le même qu'un simple cast en int. Un cast tronque, ta méthode fait autre chose

Tu as raison, je me suis mal exprimé: c'est pour faire une conversion double vers int en arrondi, c'est en général ce dont tu as besoin pour faire du calcul. L'arrondi est exact.

Sans ce test (en se limitant à des nombres positifs), elle est plus rapide de 10% à 20%.

C'est le rapport que j'avais mesuré entre la version d2i et la version assembleur. Ce gain (que je trouve étonnant, personellement) semble être réellement une différence basique entre le add et le fistp.

Les variations dépendent de si je fais beaucoup d'itérations sur des petits jeus de données, ou moins d'itération sur des plus grand (moins bonne utilisation de la mémoire, qui vient masquer les différences, ce qui tend à dire que dans une utilisation classique, la différence sera probablment elle aussi masquée par d'autres aspects)

Bien entendu. N'importe quelle tentative d'optimisation de cette conversion souffrira de ce genre de problème. Comprends moi, je ne dis pas qu'il faut optimiser du code de cette manière, je file juste un hack qui peut aider dans certains cas particuliers. Ça m'a personnelement servi dans un cas particulier. Je n'en ai pas fait une recommendation auprès de Boost :-)

On est quoi qu'il en soit loin du *8 sur cette architecture.

Dans la mesure que j'avais faite qui donnait ce résultat, l'assembleur géneré par VC8 appelait une fonction (de la runtime lib, je crois) au lieu d'inliner l'operation, d'où le rapport plus élevé. Je ne me suis pas vraiment attardé sur le pourquoi du comment. Je vais voir si je peux retrouver mon code de test qui est peut-être érroné.

- MAIS en utilisant l'assembleur (celui que tu as donné), le rapport de vitesse s'inverse !

Il n'y a pas de secret. L'assembleur doit être différent (celui géneré pour d2i). Il faudrait comparer le code généré dans ton cas avec le mien.

Après tout, c'est un astuce pour gagner en vitesse, pourquoi faire une multiplication dans le calcul, alors qu'on peut la faire en avance ?

Tous les compilateurs réduisent ce genre d'expression au moment de la compilation (optimisée). C'était juste un indice pour le lecteur qui voulait comprendre ce qui se passe au niveau de la représentation du double.

Bon je vais m'arrêter là. Juste une petite remarque. À la base, j'essayais juste de filer un coup de main. Je pensais pas me faire assaillir de la sorte

[thewho]

Bonjour,

Personne ne t'a assailli. Il ne faut pas être paranoïaque et tout comprendre comme une agression ()

[Médinoc]

Pour le coût de la conversion, on m'a dit (mais j'ignore sur quelle architecture exactement) qu'une conversion entre flottants et entiers néccessitait de reconfigurer la FPU, sachant qu'il faudrait ensuite la reconfigurer dans l'autre sens pour refaire une opération flottante...

Ainsi, sans optimisations de calcul vectoriel, la conversion d'une liste de flottants en liste d'entiers aurait nécessité deux reconfigurations par nombres.

Mais j'ignore quelle confiance accorder à cette information car l'ami qui m'a dit ça travaille sur plusieurs architectures, dont certaines embarquées, et je ne crois pas qu'il m'avait spécifiquement désigné une architecture x86...

[thewho]

Bonjour,

Pour le coût de la conversion, on m'a dit (mais j'ignore sur quelle architecture exactement) qu'une conversion entre flottants et entiers néccessitait de reconfigurer la FPU, sachant qu'il faudrait ensuite la reconfigurer dans l'autre sens pour refaire une opération flottante...

Ainsi, sans optimisations de calcul vectoriel, la conversion d'une liste de flottants en liste d'entiers aurait nécessité deux reconfigurations par nombres.

Mais j'ignore quelle confiance accorder à cette information car l'ami qui m'a dit ça travaille sur plusieurs architectures, dont certaines embarquées, et je ne crois pas qu'il m'avait spécifiquement désigné une architecture x86...

Sur certaines FPU, peut-être, mais par exemple les processeurs Intel ne le nécessitent pas, il n'y a qu'à appeler la bonne fonction.
Par contre, on peut régler la manière dont se fait l'arrondi, etc..., mais en pratique on utilise pratiquement toujours la configuration par défaut, et quand ce n'est pas le cas, le programmeur qui travaille proprement se doit de rétablir cette configuration.

JolyLoic m'avait demandé mon code de test, le voici:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <stdarg.h>
#include <windef.h>
#include <winbase.h>
#include <string>
 
using namespace std;
 
typedef long long int_64;
 
//#define D2I_CONVERSION_FACTOR (1.5 * 4503599627370496.0)
#define D2I_CONVERSION_FACTOR          6755399441055744.0
inline int d2i(double val)
{
    union {
        int i[2];
        double d;
    } dlong;
    dlong.d = val + D2I_CONVERSION_FACTOR;
    return dlong.i[0];
}
 
// la fonction qui fait le test
 
void tt(void)
{
    // nombre de boucles à faire
 
    #define NB 100000000
 
    LARGE_INTEGER t1,t2,t3,t4; // pour stocker les points de QueryPerformanceCounter
                               // encadrant les boucles
 
    double d = -12345.1234665;
    int n1 = 0, n2 = 0;
 
    // boucle utilisant "l'astuce" d2i
 
    QueryPerformanceCounter(&t1);
    for (int i=0;i<NB;++i)
    {
        n1 = d2i(d);
    }
    QueryPerformanceCounter(&t2);
 
    // boucle utilisant le cast classique, ou l'assembleur
    // (commenter/décommenter la version à tester)
 
    QueryPerformanceCounter(&t3);
    for (int i=0;i<NB;++i)
    {
        // pour tester le cast classique
        //n2 = (int)d;
 
        // pour tester en assembleur
        __asm__ (
            "fldl %[orig]\n\t"
            "fistpl %[dest]\n\t"
            : [dest] "=g" (n2)
            : [orig] "m" (d)
            :
        );
    }
    QueryPerformanceCounter(&t4);
 
    // calcul des durées et du rapport, et affichage des résultats
 
    int_64 r12 = t2.QuadPart - t1.QuadPart;
    int_64 r34 = t4.QuadPart - t3.QuadPart;
 
    double rapport;
    if (r34)
    {
        rapport = (double)r12/(double)r34;
    }
    else
    {
        rapport = -1;
    }
 
    cout<<"special : "<<r12<<",   cast : "<<r34<<", rapport (astuce/cast) = "<<rapport<<endl;
 
    if (n1!=n2)
    {
        cout<<"error  (n1 = "<<n1<<") != (n2 = "<<n2<<")"<<endl;
        cout<<"n1 = "<<n1<<",  n2 = "<<n2<<endl;
    } else
    {
        cout<<"bravo, n1 == n2 = "<<n1<<endl;
    }
 
}
 
int main()
{
    tt();
 
    return 0;
}

Comme vous pouvez le voir, aux simples tests de vitesse, j'ajoute à la sortie des tests sur la validité des résultats, vieille habitude qui devrait être générale.

Ça va faire hurler Emmanuel "C'est pas portable !", mais comme j'utilise des API Windows, et il faut bien utiliser les types allant avec (LARGE_INTEGER).