Discussion :

[Laugilus]

Bonjour,

Je suis en train d'implémenter le radix sort en C++, et j'aimerais bien l'implémenter pour trier des nombres flottants.
Ce n'est pas une question d'algorithmie que je vous demande, mais j'ai plutôt un problème avec le langage.

Pour trier les float, je dois lire les valeurs de chaque bit du float (L'algorithme fonctionnera pour les float enregistrés selon la norme IEEE). Je voulais donc utiliser les opérateurs bitwise (& logique), mais le langage interdit de faire un & entre un float et un int (3.f & 1 est interdit).

La solution que j'ai implémentée me retourne un warning que je ne comprends pas.

Code :

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

1
2
float f = /* something */;
int a = *reinterpreter_cast<int*>(&f);

De cette façon là, je récupère les bits de "f" et je peux les lire via "a". Lorsque ce code s'exécute, il a déjà été vérifié que sizeof(int) == sizeof(float) (Si la taille est différente, l'algorithme sera faux, mais est-ce que ça peut mener à un crash du programme ?).
Le problème de cette méthode est que j'obtiens un warning :
warning: dereferencing type-punned pointer will break strict-aliasing rules [-Wstrict-aliasing] (GCC 4.6.x)
Je ne comprends pas que ça veut dire. Néanmoins, si je fais :

Code :

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

1
2
3
float f = /* something */;
int* pa = reinterpreter_cast<int*>(&f);
int a = *pa;

Le warning disparait. (Pourtant les deux codes ont l'air équivalents...)

Ma première question est : y a-t-il un moyen simple de contourner la limitation (& logique interdit entre float et int) ?
Ensuite : ma solution est-elle dangereuse ? (sinon laquelle préférer entre les deux ?)

[JolyLoic]

Je te conseille la lecture de https://svn.boost.org/trac/boost/wik...ingsGuidelines (ça commence en milieu de page) qui décrit bien le problème, sa cause, et des solutions.

Ton code n'est formellement pas correct. Rien ne garanti que la valeur dans le int est une valeur valide pour un int. Seul les trois types char ont la garanti que tous leurs bits ont du sens. En pratique, je pense que ton code ne pose pas de soucis particuliers, et tu fais déjà d'autres suppositions sur la représentation des flaots qui me semblent encore plus risquées. Par contre, par principe, pour manipuler des bits, j'aurais plutôt tendance à utiliser des types unsigned, et en particulier chars.

[Laugilus]

Ton code n'est formellement pas correct. Rien ne garanti que la valeur dans le int est une valeur valide pour un int. Seul les trois types char ont la garanti que tous leurs bits ont du sens.

Il me semblait bien qu'il y avait un truc comme ça, d'où ma question^^.

tu fais déjà d'autres suppositions sur la représentation des flaots qui me semblent encore plus risquées.

Mouais, je ne sais pas à quel point la norme IEEE est suivi, mais je n'ai pas d'autres choix de toute façon. Il y a une norme plus suivie ? (Ca peut paraitre étrange, mais l'algorithme se fiche bien de savoir sur combien de bits sont codés l'exposant et la mantisse, donc si ces données changent, ça n'a aucune conséquence).

Je te conseille la lecture de https://svn.boost.org/trac/boost/wik...ingsGuidelines (ça commence en milieu de page) qui décrit bien le problème, sa cause, et des solutions.

Merci! C'est ce qu'il me fallait! Je ne pensais plus aux unions.

La solution :

Code :

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

1
2
3
4
5
6
union {
	float f;
	int i;
} data;
data.f = /* some float */;
data.i; // Access to the integer representation;

Merci encore!

[3DArchi]

Salut,
Comme c'est rappelé dans la doc boost proposée par Loic, l'utilisation de l'union n'est pas garantie en C++ (on n'a pas de garantie lorsqu'on accède à un autre membre que celui initialisé).

[Joel F]

Pour info:

Code :

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

1
2
3
4
5
6
7
 
float f = 1.f;
boost::int32_t i;
char* pf = &f;
char* pi = &i;
 
memcpy(pi, pf, siozef(float));

Fait exactement ce qu'il faut, ne fait pas de warning *et* est optimisé sur tout les compilos par un simple MOV.

[Laugilus]

Ah, j'ai lu trop vite...

Comme c'est rappelé dans la doc boost proposée par Loic, l'utilisation de l'union n'est pas garantie en C++ (on n'a pas de garantie lorsqu'on accède à un autre membre que celui initialisé).

Je ne comprends pourquoi. Tant que float et int ont la même taille. L'intérêt de l'union est justement qu'ils partagent la même mémoire. (je suppose que c'est encore un problème d'alignement^^)

Je trouve que c'est quand même assez décevant que l'on doive passer par des mécanismes aussi "complexes" pour simplement lire les bits d'un float...

Code :

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

1
2
3
4
5
6
float f = 1.f;
boost::int32_t i;
char* pf = &f;
char* pi = &i;
 
memcpy(pi, pf, siozef(float));

Dans le site, il est marqué que l'appel à memcpy est optimisé, mais est-ce aussi rapide que les solutions que j'ai proposé auparavant (union ou reinterpreter_cast).
La vitesse d'exécution est tout de même importante (ce code sera exécuté n*k fois, où n est la taille du tableau à trier, k la taille en bit d'un float.)

Je viens de penser à une autre solution :

Code :

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

1
2
float f = /* something */;
int i = *(new (&f) int);

Je n'ai jamais utilisé l'opérateur new (*), donc je ne sais pas ce que ça vaut.

La solution de JoelF me semble bien, je l'adopterais s'il n'y a pas de solutions plus simples/rapides. (merci!)

Merci encore de vos réponses.