Discussion :

[ppaul128]

Bonjour,

Je cherche à coder une fonction qui qui prend en parametre deux doubles et renvoie true si la distance entre ces deux doubles est plus petite qu'une valeur determinée à l'avance.(settée via un #define seuil par ex)

Ma contrainte est que cette fonction soit la plus performante possible( pour du calcul numérique, cette opération sera effectuée plusieurs milliards de fois)...

J'allais partir sur une implementation classique en utilisant std::abs ou fabs pour mesurer la distance entre mes deux nombres, puis faire une comparaison avec le seuil, mais je me demandais s'il n'y avait pas des astuces pour faire plus rapide ? (du style équivalent des bitwise operations qu'on peut faire sur des types entiers ?)

Si qqu'un à un lien ou un article à conseiller là dessus, ou des astuces je suis preneur

merci!

[salseropom]

Je ne sais pas si ça va te faire gagner du temps mais une macro du genre

Code :

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

1
2
3
 
#define SEUIL 1e-10
#define COMPARE(a,b) ((fabs((a)-(b)) < SEUIL) ? true : false)

et de l'utiliser ainsi

Code :

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

1
2
 
bool test=COMPARE(a,b);

je n'ai pas testé si tu allais gagner du temps...

[ppaul128]

Je vais tester ça.
Merci

[JolyLoic]

Cette macro ne fait rien d'autre que la comparaison que tu as dit vouloir éviter... Et en plus, c'est une macro

De plus, a<b retourne un booleen. Je ne vois donc pas le besoin de faire (a<b ? true : false) là où (a<b) est équivalent. Ou alors, autant faire ((a<b?true : false) ? true : false)

Honnêtement, sur ce genre de choses, je ne crois pas qu'il y ait plus rapide que le fabs. Mais je crois surtout qu'il est assez improbable que le temps passé à cette opération ait un impact significatif sur le temps global de calcul.

[koala01]

Salut,

Je rejoint pleinement l'avis de JolyLoic (une fois n'est pas coutume )

Selon moi, bien plus que d'essayer de gagner une ou deux fréquence d'horloge avec un sucre syntaxique quelconque, tu devrais déjà essayer d'améliorer ton algorithme pour, quitte à y passer un tout petit peu de temps, te permettre d'éviter toutes les itérations inutiles...

Ainsi, s'il t'es possible de créer un algorithme basé - par exemple - sur la dichotomie, tu pourrait en arriver à ne faire le test qu'à peine plus de 32 fois...(s'il s'agit de rechercher une valeur parmis 4 milliards de valeurs possibles)

Pour rappel, la principale condition pour pouvoir utiliser la dichotomie est le fait que les valeurs soient triées...

Les deux "structures" les plus aptes à la permettre étant l'arbre binaire (idéal s'il est complet) et le tableau (éventuellement le std::vector) car ce dernier autorise un accès aléatoire aux données

Sinon, il est fort vraisemblable que les milliards de fois où ce test sera effectués viennent de plusieurs boucles imbriquées.

Encore une fois, si tu arrive à supprimer toutes les itérations, en fonction de la boucle dans laquelle tu te trouves, pour les valeurs dont tu sais "pertinemment" qu'elle donneront un résultat donné (soit vrai, soit faux), tu en arrivera à gagner énormément de temps d'exécution, et ce... malgré le fait que tu ajoute sans doute un test.

La raison est simple, pour arriver à un milliard d'exécutions, on peut envisager entre autre un algorithme proche de

Code :

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

1
2
3
4
5
6
7
8
pour i= 0 à 1000
    pour j = 0 à 1000
        pour k = 0 à 1000
            if( fabs(a<b)
                faire quelque chose
        fin pour
    fin pour
fin pour

Si tu ajoutes un test proche de

Code :

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

si i%2 = 0

(simple exemple) dans la boucle "pour i" et décidant d'entrer dans la boucle "pour j", tu réduira déjà de moitié les tests effectués

[nicroman]

De plus fabs est une fonction intrinsic... donc est traduite directement en assembleur....

Au pire si tu as besoin de le faire absoluement (profiling avant), tu veux juste tester l'exposant du double (dont la representation est: S * 1.F x 2^E)... donc... (1 bit de signe, 11 bits d'exposant, et 52 bits de mantisse)

Code c++ :

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

1
2
3
4
5
6
7
 
#define  SEUIL        0x0030000000000000
#define  EXP_MASK  0x7FF0000000000000
inline boolean _fast_double_test(const double& d)
{
     return ((*((const int64*)&d)) & EXP_MASK) < SEUIL;
}

Mais encore une fois, je ne suis même pas sur que ca te permette de grapiller quelques ns... Le &EXP_MASK revenant grosso merdo au fabs ....

[koala01]

De plus fabs est une fonction intrinsic... donc est traduite directement en assembleur....

Ca, peut-être (c'est même plus que vraisemblable)

Au pire si tu as besoin de le faire absoluement (profiling avant), tu veux juste tester l'exposant du double (dont la representation est: S * 1.F x 2^E)... donc... (1 bit de signe, 11 bits d'exposant, et 52 bits de mantisse)

Code c++ :

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

1
2
3
4
5
6
7
 
#define  SEUIL        0x0030000000000000
#define  EXP_MASK  0x7FF0000000000000
inline boolean _fast_double_test(const double& d)
{
     return ((*((const int64*)&d)) & EXP_MASK) < SEUIL;
}

Mais encore une fois, je ne suis même pas sur que ca te permette de grapiller quelques ns... Le &EXP_MASK revenant grosso merdo au fabs ....

Ca, par contre, c'est loin d'être sûr...

Ne serait-ce que parce que si, de fait, un double est souvent considéré comme faisant 64 bits, la taille n'est pas définie (comme tous les types primitifs) explicitement dans la norme.

Ainsi, la norme précise que:

A floating literal consists of an integer part, a decimal point, a fraction part, an e or E, an optionally signed
integer exponent, and an optional type suffix. The integer and fraction parts both consist of a sequence of
decimal (base ten) digits. Either the integer part or the fraction part (not both) can be omitted; either the
decimal point or the letter e (or E) and the exponent (not both) can be omitted. The integer part, the
optional decimal point and the optional fraction part form the significant part of the floating literal. The
exponent, if present, indicates the power of 10 by which the significant part is to be scaled. If the scaled
value is in the range of representable values for its type, the result is the scaled value if representable, else
the larger or smaller representable value nearest the scaled value, chosen in an implementation-defined
manner. The type of a floating literal is double unless explicitly specified by a suffix. The suffixes f and
F specify float, the suffixes l and L specify long double. If the scaled value is not in the range of
representable values for its type, the program is ill-formed.

et que

There are three floating point types: float, double, and long double. The type double provides
at least as much precision as float, and the type long double provides at least as much precision as
double. The set of values of the type float is a subset of the set of values of the type double; the set
of values of the type double is a subset of the set of values of the type long double. The value representation
of floating-point types is implementation-defined. Integral and floating types are collectively
called arithmetic types. Specializations of the standard template numeric_limits (18.2) shall specify
the maximum and minimum values of each arithmetic type for an implementation.

De plus, il y a le "boutisme" de la machine qui peut intervenir.

Dés lors, le fait de partir du principe d'une représentation donnée (taille et signification des bits) pour les doubles (comme pour tous les types primitifs) revient à courir le risque que cette représentation ne soit valable que pour ton architecture particulière, et dans la limite de l'implémentation particulière de ton compilateur particulier.

Tu avoueras que cela fait beaucoup de particularités qui te sont propres pour en tirer une règle que tu présente comme immuable, non :quesiton:

[ppaul128]

J'ai fait qques tests de perfs, et le fabs est en effet pour l'instant ce qu'il y a de mieux. Je vais passer un peu de temps aussi sur mon algo pour appeler moins souvent cette fonction.

Merci pour les conseils, j'apprécie

[koala01]

J'ai fait qques tests de perfs, et le fabs est en effet pour l'instant ce qu'il y a de mieux. Je vais passer un peu de temps aussi sur mon algo pour appeler moins souvent cette fonction.

Merci pour les conseils, j'apprécie

La prochaine fois, tu pourras t'éviter la peine de faire des benchmarks en pensant à ceci:

Dans l'énorme majorité des cas (j'entends par là, surement dans plus de 90% des cas, et en dehors de toute circonstance extrêmement particulière) il faut d'abord réfléchir aux possibilités de revoir son algorithme, la logique suivie, afin de limiter le nombre de fois qu'un traitement doit être effectué. Et un simple changement de point de vue permet de gagner énormément de temps d'exécution.

Par changement de point de vue, je veux dire - sans exhaustivité - qu'il faut envisager:

• de repenser aux structures employées
• de repenser au "pré-traitement" à effectuer
• d'envisager une autre approche générale de ce que l'on veut faire

C'est sur ces changements de point de vue que tu gagnera le plus de temps (évite un traitement sur deux, et tu es gagnant, même si cela sous-entend de "perdre le temps" d'un test )

Si, une fois que tu es sur d'avoir le meilleur algorithme possible avec les meilleures structures possibles, il faut encore essayer de "grappiller" quelques nano-secondes (car c'est à peut près ce que tu va gagner grâce à tes "sucres syntaxiques" à chaque exécution), il sera toujours temps de réfléchir à comment arriver à les grappiller.

En anglais, la phrase couramment citée est la seconde partie de

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil

Autrement dit:

Nous devons oublier les petits gains d'efficacité, par exemple environ 97% du temps: l'optimisation prématurée est la racine de tous les maux

[nicroman]

Merci beaucou Koala pour ces précisions !

Ne serait-ce que parce que si, de fait, un double est souvent considéré comme faisant 64 bits, la taille n'est pas définie (comme tous les types primitifs) explicitement dans la norme.

Ha bon ?


Non sans déconner... si il faut vraiment optimiser un bout de code parcequ'on y passe dedans 1 million de fois par frame, qu'il coute 1ns, et qu'on doit conserver du 60fps... crois moi, on se fiche parfaitement que sur Cray-9143 le double ait une représentation en 96 bits....

On peut prendre par exemple la conversion float<->int (qui est une vraie plaie question rapidité à cause des stalls de FPU que ca engendre)...

Ce bout de code est environ 2 à 3 fois plus rapide que le le cast en int:

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
 
 
/** \brief      Tests if v is positive. Only works with 32 bits types. */
#define	IS_POSITIVE32(v) ((RW_ASINT32(v) & 0x80000000) == 0)
/** \brief      Tests if v is negative. Only works with 32 bits types. */
#define	IS_NEGATIVE32(v) ((RW_ASINT32(v) & 0x80000000) != 0)
 
 
/** \brief Fast conversion from Float32_t to SInt32_t. */
__inline SInt32_t FloatToSInt32(Float32_t f)
{
	if (IS_NEGATIVE32(f)) {
		f += RW_NBIASF;
		RW_ASINT32(f) -= RW_NBIASI;
	} else {
		f += RW_PBIASF;
		RW_ASINT32(f) -= RW_PBIASI;
	}
	return RW_ASINT32(f);
}

[koala01]

Merci beaucou Koala pour ces précisions !

koala01
Ne serait-ce que parce que si, de fait, un double est souvent considéré comme faisant 64 bits, la taille n'est pas définie (comme tous les types primitifs) explicitement dans la norme.

Ha bon ?

hé oui...
le fait a déjà été soulevé bien des fois sur le forum.

Tout ce que la norme dit, c'est

• qu'un caractère utilise un nombre de bit suffisant pour représenter l'ensemble... de la table de caractère choisie pour l'implémentation (ce peut donc etre 6, 7, 8 ou... si on décide d'utiliser la table de caractères issue de la norme iso-8859, 32 )
• que la seule chose dont on soit sur, c'est que sizeof(char) == sizeof(unsigned char) == sizeof(signed char) == 1
• Que tout les types entre dans des tableaux de caractères de telle manière que
  
  • sizeof(char) <= sizeof( short) <= sizeof(int) <= sizeof(long) (<= sizeof(long long)
  • sizeof(signed char) <= sizeof(signed short) <= sizeof(int) <= sizeof(signed long) (<= sizeof(signed long long))
  • sizeof(unsigned signed char) <= sizeof( unsigned signed short) <= sizeof(unsigned signed int) <= sizeof(unsigned signed long) (<= sizeof(unsigned signed long long)
  • sizeof(char)<= sizeof(float) <=sizeof(double) (<= sizeof(long double)
• l'unsigned int est un candidat idéal pour représenter type size_t

Non sans déconner... si il faut vraiment optimiser un bout de code parcequ'on y passe dedans 1 million de fois par frame, qu'il coute 1ns, et qu'on doit conserver du 60fps... crois moi, on se fiche parfaitement que sur Cray-9143 le double ait une représentation en 96 bits....

C'est plus complexe que cela...
Car si même on pouvait *considérer* que la taille des différents types primitifs est *relativement* stable, il reste toujours le problème du boutisme, et le problème des choix d'implémentations (position des bits de signe, taille et position de la mantisse et de l'exposant).

Ainsi, la valeur 0x7FF0000000000000 que tu définis, en étant si sur de ton fait peut très bien avoir une valeur tout à fait aberrante sur un spark, un AS300 ou un... apple(du moins sur ceux qui sont sortis avant leur décision d'utiliser les processeurs intel).

De plus, j'ai pourtant essayé d'être clair sur le fait que, plutôt que d'essayer de gagner un ou deux cycles d'horloge au sein de la boucle, l'idéal reste quand meme toujours de voir s'il n'y a pas moyen de limiter le nombre de fois que la boucle est effectuée.

Car, même en gagnant deux cycles d'horloge par exécution de la boucle (et considérant ici que le problème original du PO n'est jamais qu'une partie de ce que doit faire la boucle, sinon le test en lui-même n'a aucun intérêt), tu gagnera peut être 2 000 000 de cycles si la boucle est effectuée 1 million de fois, mais ce ne sera rien par rapport au gain obtenu si tu arrive à diminuer le nombre d'exécutions de la boucle ne serait-ce que de 10%.

Evidemment, il reste après les "cas particuliers" dans lesquels, bien que l'algorithme soit "le plus efficace qu'il soit effectivement possible d'obtenir", il reste nécessaire d'essayer de grapiller encore un ou deux cycles d'horloge par exécution de la boucle si possible...

Mais ce genre d'optimisation doit venir en toute fin de processus, et après avoir démontré qu'elle est réellement indispensable (pour l'objectif final qui est poursuivi)

On peut prendre par exemple la conversion float<->int (qui est une vraie plaie question rapidité à cause des stalls de FPU que ca engendre)...

Ce bout de code est environ 2 à 3 fois plus rapide que le le cast en int:
<snipped code>

Je n'ai jamais dit le contraire...

Simplement, j'attirais ton attention sur le fait que toute interprétation qui peut concerner la manière dont les types primitifs (et les autres -POD et TAD - d'ailleurs) sont représentés en mémoire ne sera valide que pour la machine, la platforme et avec le compilateur que tu utilises. (ce qui, il faut quand meme l'avouer, place pas mal de restrictions au fait de vouloir déterminer une règle à partir de cette interprétation )