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.

[Joel F]

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).

c'est la seule correcte qui ne plantera pas en -O3 en production un vendredi soir a 23h54. DOnc y a pas de question a ce poser.

Je m'en sert dans une lib de calcul parallele, jamais eu a m'en plaindre.

[Laugilus]

Ok merci, je vais sûrement adopter ça.

Cependant, juste par curiosité, ma dernière solution ne marche pas non plus ?

[Ekleog]

Non, le new (*) est le placement new, et va donc remplir f de zéros.

Pourquoi ne pas tester ?

[EDIT : Apparemment, ça *semble* fonctionner chez moi (en tout cas la récupération du float semble marcher) ... Quelqu'un peut m'expliquer ?]

[Laugilus]

J'ai testé, et ça marche. Ce n'est pas ça le problème. (Le placement new doit sûrement appeler le constructeur par défaut. Comme c'est un int, il n'y en a pas vraiment (je ne sais pas ce que dit la norme là-dessus. En tout cas, ça ne le remplit pas de 0).

Toutes mes autres solutions marchent (reinterpreter_cast, union). Mes vous dites qu'elles ne sont pas sûres. Je voulais savoir si c'est aussi le cas avec le placement new.

[loufoque]

Il y a 2 alternatives qui marchent :
1) recopier les données via des char* ou une union (ce dernier n'étant pas strictement conforme au standard, mais marche en pratique et génère du meilleur code sur certains compilos)
2) aliaser les données avec un attribut spécial, mais y'a plein de bugs dans le compilo avec la gestion de cet attribut et on peut très facilement l'enlever sans faire exprès et rendre le code invalide