Je suis en train d'examiner le code source de différentes tables de
hachage _génériques_ [ie pouvant hacher n'importe quel type de données
(entiers, structures, etc) et pas seulement des chaînes de caractères].
Je suis surpris que les fonctions de hachage de la clé (qui se présenter
typiquement en void *key) se basent sur la seule représentation de
l'objet à hacher plutôt que sur sa valeur.
Voici un cas typique, cf.
https://github.com/cgjones/android-system-core/blob/master/libcutils/hashmap.c
:
int hashmapHash(void* key, size_t keySize) {
int h = keySize;
char* data = (char*) key;
size_t i;
for (i = 0; i < keySize; i++) {
h = h * 31 + *data;
data++;
}
return h;
}
Si la fonction de hachage ci-dessus est appliquée à une chaîne de
caractères, il me semble qu'elle ne pose aucun problème. En revanche si
la clé est d'un autre type comme int ou même unsigned int, il pourrait
en aller autrement. En effet, la norme du langage C n'assure pas du tout
que deux objets ayant même valeur aient nécessairement même
représentation. Si, par exemple, l'entier disons 421, est susceptible
d'avoir deux représentations différentes (autrement dit memcmp ne
renverrait pas 0) deux clés de même valeur, par exemple, 420+1 et 422-1,
pourraient renvoyer des hash différents : catastrophe.
le 22/08/2013 à 11:12, Marc Boyer a écrit dans le message <kv4kma$mf4$ :
Oui, c'est exactement mon souci. Ce qui me gêne, c'est cette note de bas de page de la Norme :
------------------------------------------------------------------------- It is possible for objects x and y with the same effective type T to have the same value when they are accessed as objects of type T, but to have different values in other contexts. In particular, if == is defined for type T, then x == y does not imply that memcmp(&x, &y, sizeof (T)) == 0. -------------------------------------------------------------------------
Oui. Le cas doit être extrèmement rare avec des entiers, plus commun avec les flottants.
Mais ce sont surtout les structures qui sont le cas courant, puisqu'on peut faire x= y et avoir ensuite memcmp(&x, &y, sizeof (T)) != 0.
Il y a un quelque chose qui m'échappe : memcmp() compare après avoir converti en unsigned char, comment est-ce possible que ça diffère sur des int ou float (pour une structure, je comprends bien qu'il peut y avoir du padding) ?
Première hypothèse (théorique): j'ai une machine qui ne sait adresser que des mots de 8 ou 32 bits. Je décide d'encoder des shorts sur 16 bits. Je décide alors de faire sizeof(short)=4 (32 bits) et de n'en utiliser que 16, et je laisse les 16 autre dans un état "indéterminé".
C'est possible de faire ça (mettre autre chose que 0 dans les 2 octets non utilisés) ? Ça ne casse pas l'arithmétique des pointeurs ?
Pour les flottants, je suis incompétent: je sais qu'on peut avoir +0.0 et -0.0 et NaN dans IEEE-754, mais la norme C admet surement d'autres encodages.
Au final, je me méfierais avant d'écrire une table de hash sur des flottants comme clef.
Ce qui me gène c'est pourquoi, dans ce cas, memcmp prend en argument des void* et non des char* ?
-- Benoit Izac
Bonjour,
le 22/08/2013 à 11:12, Marc Boyer a écrit dans le message
<kv4kma$mf4$1@news.cict.fr> :
Oui, c'est exactement mon souci. Ce qui me gêne, c'est cette note de bas
de page de la Norme :
-------------------------------------------------------------------------
It is possible for objects x and y with the same effective type T to
have the same value when they are accessed as objects of type T, but to
have different values in other contexts. In particular, if == is defined
for type T, then x == y does not imply that memcmp(&x, &y, sizeof (T)) == 0.
-------------------------------------------------------------------------
Oui. Le cas doit être extrèmement rare avec des entiers, plus commun
avec les flottants.
Mais ce sont surtout les structures qui sont le cas courant, puisqu'on
peut faire x= y et avoir ensuite memcmp(&x, &y, sizeof (T)) != 0.
Il y a un quelque chose qui m'échappe : memcmp() compare après avoir
converti en unsigned char, comment est-ce possible que ça diffère sur des
int ou float (pour une structure, je comprends bien qu'il peut y avoir
du padding) ?
Première hypothèse (théorique): j'ai une machine qui ne sait adresser
que des mots de 8 ou 32 bits. Je décide d'encoder des shorts sur 16 bits.
Je décide alors de faire sizeof(short)=4 (32 bits) et de n'en utiliser
que 16, et je laisse les 16 autre dans un état "indéterminé".
C'est possible de faire ça (mettre autre chose que 0 dans les 2 octets
non utilisés) ? Ça ne casse pas l'arithmétique des pointeurs ?
Pour les flottants, je suis incompétent: je sais qu'on peut avoir +0.0
et -0.0 et NaN dans IEEE-754, mais la norme C admet surement d'autres
encodages.
Au final, je me méfierais avant d'écrire une table de hash sur
des flottants comme clef.
Ce qui me gène c'est pourquoi, dans ce cas, memcmp prend en argument des
void* et non des char* ?
le 22/08/2013 à 11:12, Marc Boyer a écrit dans le message <kv4kma$mf4$ :
Oui, c'est exactement mon souci. Ce qui me gêne, c'est cette note de bas de page de la Norme :
------------------------------------------------------------------------- It is possible for objects x and y with the same effective type T to have the same value when they are accessed as objects of type T, but to have different values in other contexts. In particular, if == is defined for type T, then x == y does not imply that memcmp(&x, &y, sizeof (T)) == 0. -------------------------------------------------------------------------
Oui. Le cas doit être extrèmement rare avec des entiers, plus commun avec les flottants.
Mais ce sont surtout les structures qui sont le cas courant, puisqu'on peut faire x= y et avoir ensuite memcmp(&x, &y, sizeof (T)) != 0.
Il y a un quelque chose qui m'échappe : memcmp() compare après avoir converti en unsigned char, comment est-ce possible que ça diffère sur des int ou float (pour une structure, je comprends bien qu'il peut y avoir du padding) ?
Première hypothèse (théorique): j'ai une machine qui ne sait adresser que des mots de 8 ou 32 bits. Je décide d'encoder des shorts sur 16 bits. Je décide alors de faire sizeof(short)=4 (32 bits) et de n'en utiliser que 16, et je laisse les 16 autre dans un état "indéterminé".
C'est possible de faire ça (mettre autre chose que 0 dans les 2 octets non utilisés) ? Ça ne casse pas l'arithmétique des pointeurs ?
Pour les flottants, je suis incompétent: je sais qu'on peut avoir +0.0 et -0.0 et NaN dans IEEE-754, mais la norme C admet surement d'autres encodages.
Au final, je me méfierais avant d'écrire une table de hash sur des flottants comme clef.
Ce qui me gène c'est pourquoi, dans ce cas, memcmp prend en argument des void* et non des char* ?
-- Benoit Izac
candide
Le 22/08/2013 17:25, Marc Boyer a écrit :
Juste pour info, c'est une pratique courante que de faire la somme de hashes pour obtenir un nouveau hash ?
C'est je pense assez courant,
Entendu, je m'en inspirerai.
Quelqu'un connaît l'usage pour hacher un point en 3D à coordonnées entières (tableau de trois int) ? Pareil, on fait la somme ?
La somme des 3 entiers ou la somme des trois fonctions de hashages.
La somme des hashes bien sûr.
Le 22/08/2013 17:25, Marc Boyer a écrit :
Juste pour info, c'est une pratique courante que de faire la somme de
hashes pour obtenir un nouveau hash ?
C'est je pense assez courant,
Entendu, je m'en inspirerai.
Quelqu'un connaît l'usage pour hacher un point en 3D à coordonnées
entières (tableau de trois int) ? Pareil, on fait la somme ?
La somme des 3 entiers ou la somme des trois fonctions de hashages.
Juste pour info, c'est une pratique courante que de faire la somme de hashes pour obtenir un nouveau hash ?
C'est je pense assez courant,
Entendu, je m'en inspirerai.
Quelqu'un connaît l'usage pour hacher un point en 3D à coordonnées entières (tableau de trois int) ? Pareil, on fait la somme ?
La somme des 3 entiers ou la somme des trois fonctions de hashages.
La somme des hashes bien sûr.
candide
Le 22/08/2013 11:12, Marc Boyer a écrit :
Première hypothèse (théorique): j'ai une machine qui ne sait adresser que des mots de 8 ou 32 bits. Je décide d'encoder des shorts sur 16 bits. Je décide alors de faire sizeof(short)=4 (32 bits) et de n'en utiliser que 16, et je laisse les 16 autre dans un état "indéterminé".
Ah ok ! donc une même valeur entière pourrait facilement avoir deux représentations différentes.
Bon, et si l'implémentation me dit, cf. gcc concernant les entiers :
------------------------------------------- GCC supports only two’s complement integer types, and all bit patterns are ordinary values. -------------------------------------------
puis-je considérer qu'il y a bijection entre valeurs et représentations ? ce serait tellement plus simple !
Le 22/08/2013 11:12, Marc Boyer a écrit :
Première hypothèse (théorique): j'ai une machine qui ne sait adresser
que des mots de 8 ou 32 bits. Je décide d'encoder des shorts sur 16 bits.
Je décide alors de faire sizeof(short)=4 (32 bits) et de n'en utiliser
que 16, et je laisse les 16 autre dans un état "indéterminé".
Ah ok ! donc une même valeur entière pourrait facilement avoir deux
représentations différentes.
Bon, et si l'implémentation me dit, cf. gcc concernant les entiers :
-------------------------------------------
GCC supports only two’s complement integer types, and all bit patterns
are ordinary values.
-------------------------------------------
puis-je considérer qu'il y a bijection entre valeurs et représentations
? ce serait tellement plus simple !
Première hypothèse (théorique): j'ai une machine qui ne sait adresser que des mots de 8 ou 32 bits. Je décide d'encoder des shorts sur 16 bits. Je décide alors de faire sizeof(short)=4 (32 bits) et de n'en utiliser que 16, et je laisse les 16 autre dans un état "indéterminé".
Ah ok ! donc une même valeur entière pourrait facilement avoir deux représentations différentes.
Bon, et si l'implémentation me dit, cf. gcc concernant les entiers :
------------------------------------------- GCC supports only two’s complement integer types, and all bit patterns are ordinary values. -------------------------------------------
puis-je considérer qu'il y a bijection entre valeurs et représentations ? ce serait tellement plus simple !
[Je reviens à ma petite obsession, mais nous sommes bien d'accord que l'usage de hasmapHash pour hacher un int présente un petit risque, n'est-ce pas ?]
Juste pour info, c'est une pratique courante que de faire la somme de hashes pour obtenir un nouveau hash ?
C'est un point important que beaucoup de monde néglige et qui peut causer des bugs subtils (à cause de la rupture du contrat "equals" dans la table de hachage) ou des performances déplorables à cause de collisions trop nombreuses.
En fait tout si l'ordre de tes entiers compte ou pas, plus généralement parlant si l'ordre de tes valeurs dans la donnée influence le résultat du test "equals".
Si l’ordre n'importe pas, on a affaire à une sorte de Set (à la java), auquel cas si on calcule le hashCode des tableaux {1,2,3} et {3,2,1} on doit avoir la même valeur (car ces deux tableaux répondent equals() du point de vu Set. Dans ce cas l'addition directe des hashCode de chaque élement est parfait car l'addition est commutative.
En revanche si l'ordre importe (le 1er entier est de nature différente du 2eme: ce qui est le cas typique dans une structure avec plusieurs entiers), alors il est important que (1,2,3) ne renvoie pas le même hashCode que (3,1,2) si on veut éviter de se payer une collision dans la table de hachage. Dans ce cas on utilise une forumule du type:
h = hashCode(element1) h = h*31 + hashCode(element2) h = h*31 + hashCode(element3)
Remarque: Multiplier par un nombre premier est important pour éviter les collisions par la suite.
Quelqu'un connaît l'usage pour hacher un point en 3D à coordonnées entières (tableau de trois int) ? Pareil, on fait la somme ?
Tu as donc struct pt3d {int x, y, z;}
Cela semble nécessiter *absolument* un hashCoe qui tienne compte de l'ordre des éléments (3 en x, n'est pas la même chose que 3 pour z). Donc je ferais ainsi:
int h = 0; h = h*31 + hashmapHash( &(point->x), sizeof( point->x ) ); h = h*31 + hashmapHash( &(point->y), sizeof( point->y ) ); h = h*31 + hashmapHash( &(point->z), sizeof( point->z ) );
Nota: dans beaucoup de structures de données, l'ordre des valeurs des éléments importe beaucoup. Aussi tu trouvera souvent le "*31" dans la littérature. C'est typiquement le cas quand on calcule le hashCode d'une chaine de caractère: "abab" ne doit idéalement pas avoir le même hash-code que "aabb" ou "bbaa".
[Je reviens à ma petite obsession, mais nous sommes bien d'accord que
l'usage de hasmapHash pour hacher un int présente un petit risque,
n'est-ce pas ?]
Juste pour info, c'est une pratique courante que de faire la somme de
hashes pour obtenir un nouveau hash ?
C'est un point important que beaucoup de monde néglige et qui peut
causer des bugs subtils (à cause de la rupture du contrat "equals" dans
la table de hachage) ou des performances déplorables à cause de
collisions trop nombreuses.
En fait tout si l'ordre de tes entiers compte ou pas, plus généralement
parlant si l'ordre de tes valeurs dans la donnée influence le résultat
du test "equals".
Si l’ordre n'importe pas, on a affaire à une sorte de Set (à la java),
auquel cas si on calcule le hashCode des tableaux {1,2,3} et {3,2,1} on
doit avoir la même valeur (car ces deux tableaux répondent equals() du
point de vu Set. Dans ce cas l'addition directe des hashCode de chaque
élement est parfait car l'addition est commutative.
En revanche si l'ordre importe (le 1er entier est de nature différente
du 2eme: ce qui est le cas typique dans une structure avec plusieurs
entiers), alors il est important que (1,2,3) ne renvoie pas le même
hashCode que (3,1,2) si on veut éviter de se payer une collision dans la
table de hachage. Dans ce cas on utilise une forumule du type:
h = hashCode(element1)
h = h*31 + hashCode(element2)
h = h*31 + hashCode(element3)
Remarque: Multiplier par un nombre premier est important pour éviter les
collisions par la suite.
Quelqu'un connaît l'usage pour hacher un point en 3D à coordonnées
entières (tableau de trois int) ? Pareil, on fait la somme ?
Tu as donc struct pt3d {int x, y, z;}
Cela semble nécessiter *absolument* un hashCoe qui tienne compte de
l'ordre des éléments (3 en x, n'est pas la même chose que 3 pour z).
Donc je ferais ainsi:
int h = 0;
h = h*31 + hashmapHash( &(point->x), sizeof( point->x ) );
h = h*31 + hashmapHash( &(point->y), sizeof( point->y ) );
h = h*31 + hashmapHash( &(point->z), sizeof( point->z ) );
Nota: dans beaucoup de structures de données, l'ordre des valeurs des
éléments importe beaucoup. Aussi tu trouvera souvent le "*31" dans la
littérature. C'est typiquement le cas quand on calcule le hashCode d'une
chaine de caractère: "abab" ne doit idéalement pas avoir le même
hash-code que "aabb" ou "bbaa".
[Je reviens à ma petite obsession, mais nous sommes bien d'accord que l'usage de hasmapHash pour hacher un int présente un petit risque, n'est-ce pas ?]
Juste pour info, c'est une pratique courante que de faire la somme de hashes pour obtenir un nouveau hash ?
C'est un point important que beaucoup de monde néglige et qui peut causer des bugs subtils (à cause de la rupture du contrat "equals" dans la table de hachage) ou des performances déplorables à cause de collisions trop nombreuses.
En fait tout si l'ordre de tes entiers compte ou pas, plus généralement parlant si l'ordre de tes valeurs dans la donnée influence le résultat du test "equals".
Si l’ordre n'importe pas, on a affaire à une sorte de Set (à la java), auquel cas si on calcule le hashCode des tableaux {1,2,3} et {3,2,1} on doit avoir la même valeur (car ces deux tableaux répondent equals() du point de vu Set. Dans ce cas l'addition directe des hashCode de chaque élement est parfait car l'addition est commutative.
En revanche si l'ordre importe (le 1er entier est de nature différente du 2eme: ce qui est le cas typique dans une structure avec plusieurs entiers), alors il est important que (1,2,3) ne renvoie pas le même hashCode que (3,1,2) si on veut éviter de se payer une collision dans la table de hachage. Dans ce cas on utilise une forumule du type:
h = hashCode(element1) h = h*31 + hashCode(element2) h = h*31 + hashCode(element3)
Remarque: Multiplier par un nombre premier est important pour éviter les collisions par la suite.
Quelqu'un connaît l'usage pour hacher un point en 3D à coordonnées entières (tableau de trois int) ? Pareil, on fait la somme ?
Tu as donc struct pt3d {int x, y, z;}
Cela semble nécessiter *absolument* un hashCoe qui tienne compte de l'ordre des éléments (3 en x, n'est pas la même chose que 3 pour z). Donc je ferais ainsi:
int h = 0; h = h*31 + hashmapHash( &(point->x), sizeof( point->x ) ); h = h*31 + hashmapHash( &(point->y), sizeof( point->y ) ); h = h*31 + hashmapHash( &(point->z), sizeof( point->z ) );
Nota: dans beaucoup de structures de données, l'ordre des valeurs des éléments importe beaucoup. Aussi tu trouvera souvent le "*31" dans la littérature. C'est typiquement le cas quand on calcule le hashCode d'une chaine de caractère: "abab" ne doit idéalement pas avoir le même hash-code que "aabb" ou "bbaa".
sam.
candide
Le 22/08/2013 21:24, Samuel DEVULDER a écrit :
C'est un point important que beaucoup de monde néglige et qui peut causer des bugs subtils (à cause de la rupture du contrat "equals" dans la table de hachage) ou des performances déplorables à cause de collisions trop nombreuses.
Effectivement la somme étant "symétrique" et très "lisse", elle devrait hacher peu et produire plus de collisions mais dans l'exemple de Marc, le premier champ et le deuxième champ sont de types différents.
Remarque: Multiplier par un nombre premier est important pour éviter les collisions par la suite.
Pas forcément, le hash de Bernstein multiplie par 33, cf. http://www.strchr.com/hash_functions
Quelqu'un connaît l'usage pour hacher un point en 3D à coordonnées entières (tableau de trois int) ? Pareil, on fait la somme ?
Tu as donc struct pt3d {int x, y, z;}
Cela semble nécessiter *absolument* un hashCoe qui tienne compte de l'ordre des éléments (3 en x, n'est pas la même chose que 3 pour z). Donc je ferais ainsi:
int h = 0; h = h*31 + hashmapHash( &(point->x), sizeof( point->x ) ); h = h*31 + hashmapHash( &(point->y), sizeof( point->y ) ); h = h*31 + hashmapHash( &(point->z), sizeof( point->z ) );
OK je vois l'idée, c'est probablement mieux que de faire la somme (trop symétrique) et finalement on reprend l'inusable (*) fonction de hachage figurant dans mon message initial.
Merci de ta contribution.
(*) cf. KR2, chapitre 6, page 144
Le 22/08/2013 21:24, Samuel DEVULDER a écrit :
C'est un point important que beaucoup de monde néglige et qui peut
causer des bugs subtils (à cause de la rupture du contrat "equals" dans
la table de hachage) ou des performances déplorables à cause de
collisions trop nombreuses.
Effectivement la somme étant "symétrique" et très "lisse", elle devrait
hacher peu et produire plus de collisions mais dans l'exemple de Marc,
le premier champ et le deuxième champ sont de types différents.
Remarque: Multiplier par un nombre premier est important pour éviter les
collisions par la suite.
Pas forcément, le hash de Bernstein multiplie par 33, cf.
http://www.strchr.com/hash_functions
Quelqu'un connaît l'usage pour hacher un point en 3D à coordonnées
entières (tableau de trois int) ? Pareil, on fait la somme ?
Tu as donc struct pt3d {int x, y, z;}
Cela semble nécessiter *absolument* un hashCoe qui tienne compte de
l'ordre des éléments (3 en x, n'est pas la même chose que 3 pour z).
Donc je ferais ainsi:
int h = 0;
h = h*31 + hashmapHash( &(point->x), sizeof( point->x ) );
h = h*31 + hashmapHash( &(point->y), sizeof( point->y ) );
h = h*31 + hashmapHash( &(point->z), sizeof( point->z ) );
OK je vois l'idée, c'est probablement mieux que de faire la somme (trop
symétrique) et finalement on reprend l'inusable (*) fonction de hachage
figurant dans mon message initial.
C'est un point important que beaucoup de monde néglige et qui peut causer des bugs subtils (à cause de la rupture du contrat "equals" dans la table de hachage) ou des performances déplorables à cause de collisions trop nombreuses.
Effectivement la somme étant "symétrique" et très "lisse", elle devrait hacher peu et produire plus de collisions mais dans l'exemple de Marc, le premier champ et le deuxième champ sont de types différents.
Remarque: Multiplier par un nombre premier est important pour éviter les collisions par la suite.
Pas forcément, le hash de Bernstein multiplie par 33, cf. http://www.strchr.com/hash_functions
Quelqu'un connaît l'usage pour hacher un point en 3D à coordonnées entières (tableau de trois int) ? Pareil, on fait la somme ?
Tu as donc struct pt3d {int x, y, z;}
Cela semble nécessiter *absolument* un hashCoe qui tienne compte de l'ordre des éléments (3 en x, n'est pas la même chose que 3 pour z). Donc je ferais ainsi:
int h = 0; h = h*31 + hashmapHash( &(point->x), sizeof( point->x ) ); h = h*31 + hashmapHash( &(point->y), sizeof( point->y ) ); h = h*31 + hashmapHash( &(point->z), sizeof( point->z ) );
OK je vois l'idée, c'est probablement mieux que de faire la somme (trop symétrique) et finalement on reprend l'inusable (*) fonction de hachage figurant dans mon message initial.
Merci de ta contribution.
(*) cf. KR2, chapitre 6, page 144
Marc Boyer
Le 22-08-2013, Benoit Izac a écrit :
le 22/08/2013 à 11:12, Marc Boyer a écrit dans le message <kv4kma$mf4$ :
Oui, c'est exactement mon souci. Ce qui me gêne, c'est cette note de bas de page de la Norme :
------------------------------------------------------------------------- It is possible for objects x and y with the same effective type T to have the same value when they are accessed as objects of type T, but to have different values in other contexts. In particular, if == is defined for type T, then x == y does not imply that memcmp(&x, &y, sizeof (T)) == 0. -------------------------------------------------------------------------
Oui. Le cas doit être extrèmement rare avec des entiers, plus commun avec les flottants.
Mais ce sont surtout les structures qui sont le cas courant, puisqu'on peut faire x= y et avoir ensuite memcmp(&x, &y, sizeof (T)) != 0.
Il y a un quelque chose qui m'échappe : memcmp() compare après avoir converti en unsigned char, comment est-ce possible que ça diffère sur des int ou float (pour une structure, je comprends bien qu'il peut y avoir du padding) ?
Première hypothèse (théorique): j'ai une machine qui ne sait adresser que des mots de 8 ou 32 bits. Je décide d'encoder des shorts sur 16 bits. Je décide alors de faire sizeof(short)=4 (32 bits) et de n'en utiliser que 16, et je laisse les 16 autre dans un état "indéterminé".
C'est possible de faire ça (mettre autre chose que 0 dans les 2 octets non utilisés) ?
Oui.
Ça ne casse pas l'arithmétique des pointeurs ?
Ben non.
Pour t'en convaincre, dis-toi que c'est la même chose avec les structures et que l'arithmétique des pointeurs y marche très bien.
Pour les flottants, je suis incompétent: je sais qu'on peut avoir +0.0 et -0.0 et NaN dans IEEE-754, mais la norme C admet surement d'autres encodages.
Au final, je me méfierais avant d'écrire une table de hash sur des flottants comme clef.
Ce qui me gène c'est pourquoi, dans ce cas, memcmp prend en argument des void* et non des char* ?
Je ne sais pas ;-)
void* et char* sont très proches, puisqu'ils doivent avoir même représentation et mêmes contraintes d'alignement.
Mais on ne peut pas faire d'arithmétique des pointeurs sur void*, ou déréférencer.
Il y a sûrement être des règles de conversion implicites différentes, mais j'ai la flemme de chercher. Perso, void* me dit bien "mémoire brute, pointeur de type inconnu, faites gaffe" alors que char* me dit juste "pointeur sur char, ou tableau, ou chaine de caractère..."
Par exemple, gcc -Wall -pedantic couine un peu sur une convertion implicite int* -> char* mais pas int* -> void*.
int i; char* c= &i; void* v= &i;
Marc Boyer -- À mesure que les inégalités regressent, les attentes se renforcent. François Dubet
Le 22-08-2013, Benoit Izac <use.reply.to@INVALID.ADDRESS> a écrit :
le 22/08/2013 à 11:12, Marc Boyer a écrit dans le message
<kv4kma$mf4$1@news.cict.fr> :
Oui, c'est exactement mon souci. Ce qui me gêne, c'est cette note de bas
de page de la Norme :
-------------------------------------------------------------------------
It is possible for objects x and y with the same effective type T to
have the same value when they are accessed as objects of type T, but to
have different values in other contexts. In particular, if == is defined
for type T, then x == y does not imply that memcmp(&x, &y, sizeof (T)) == 0.
-------------------------------------------------------------------------
Oui. Le cas doit être extrèmement rare avec des entiers, plus commun
avec les flottants.
Mais ce sont surtout les structures qui sont le cas courant, puisqu'on
peut faire x= y et avoir ensuite memcmp(&x, &y, sizeof (T)) != 0.
Il y a un quelque chose qui m'échappe : memcmp() compare après avoir
converti en unsigned char, comment est-ce possible que ça diffère sur des
int ou float (pour une structure, je comprends bien qu'il peut y avoir
du padding) ?
Première hypothèse (théorique): j'ai une machine qui ne sait adresser
que des mots de 8 ou 32 bits. Je décide d'encoder des shorts sur 16 bits.
Je décide alors de faire sizeof(short)=4 (32 bits) et de n'en utiliser
que 16, et je laisse les 16 autre dans un état "indéterminé".
C'est possible de faire ça (mettre autre chose que 0 dans les 2 octets
non utilisés) ?
Oui.
Ça ne casse pas l'arithmétique des pointeurs ?
Ben non.
Pour t'en convaincre, dis-toi que c'est la même chose avec les structures
et que l'arithmétique des pointeurs y marche très bien.
Pour les flottants, je suis incompétent: je sais qu'on peut avoir +0.0
et -0.0 et NaN dans IEEE-754, mais la norme C admet surement d'autres
encodages.
Au final, je me méfierais avant d'écrire une table de hash sur
des flottants comme clef.
Ce qui me gène c'est pourquoi, dans ce cas, memcmp prend en argument des
void* et non des char* ?
Je ne sais pas ;-)
void* et char* sont très proches, puisqu'ils doivent avoir même
représentation et mêmes contraintes d'alignement.
Mais on ne peut pas faire d'arithmétique des pointeurs sur void*,
ou déréférencer.
Il y a sûrement être des règles de conversion implicites différentes,
mais j'ai la flemme de chercher. Perso, void* me dit bien "mémoire
brute, pointeur de type inconnu, faites gaffe" alors que char*
me dit juste "pointeur sur char, ou tableau, ou chaine de caractère..."
Par exemple, gcc -Wall -pedantic couine un peu sur une convertion
implicite int* -> char* mais pas int* -> void*.
int i;
char* c= &i;
void* v= &i;
Marc Boyer
--
À mesure que les inégalités regressent, les attentes se renforcent.
François Dubet
le 22/08/2013 à 11:12, Marc Boyer a écrit dans le message <kv4kma$mf4$ :
Oui, c'est exactement mon souci. Ce qui me gêne, c'est cette note de bas de page de la Norme :
------------------------------------------------------------------------- It is possible for objects x and y with the same effective type T to have the same value when they are accessed as objects of type T, but to have different values in other contexts. In particular, if == is defined for type T, then x == y does not imply that memcmp(&x, &y, sizeof (T)) == 0. -------------------------------------------------------------------------
Oui. Le cas doit être extrèmement rare avec des entiers, plus commun avec les flottants.
Mais ce sont surtout les structures qui sont le cas courant, puisqu'on peut faire x= y et avoir ensuite memcmp(&x, &y, sizeof (T)) != 0.
Il y a un quelque chose qui m'échappe : memcmp() compare après avoir converti en unsigned char, comment est-ce possible que ça diffère sur des int ou float (pour une structure, je comprends bien qu'il peut y avoir du padding) ?
Première hypothèse (théorique): j'ai une machine qui ne sait adresser que des mots de 8 ou 32 bits. Je décide d'encoder des shorts sur 16 bits. Je décide alors de faire sizeof(short)=4 (32 bits) et de n'en utiliser que 16, et je laisse les 16 autre dans un état "indéterminé".
C'est possible de faire ça (mettre autre chose que 0 dans les 2 octets non utilisés) ?
Oui.
Ça ne casse pas l'arithmétique des pointeurs ?
Ben non.
Pour t'en convaincre, dis-toi que c'est la même chose avec les structures et que l'arithmétique des pointeurs y marche très bien.
Pour les flottants, je suis incompétent: je sais qu'on peut avoir +0.0 et -0.0 et NaN dans IEEE-754, mais la norme C admet surement d'autres encodages.
Au final, je me méfierais avant d'écrire une table de hash sur des flottants comme clef.
Ce qui me gène c'est pourquoi, dans ce cas, memcmp prend en argument des void* et non des char* ?
Je ne sais pas ;-)
void* et char* sont très proches, puisqu'ils doivent avoir même représentation et mêmes contraintes d'alignement.
Mais on ne peut pas faire d'arithmétique des pointeurs sur void*, ou déréférencer.
Il y a sûrement être des règles de conversion implicites différentes, mais j'ai la flemme de chercher. Perso, void* me dit bien "mémoire brute, pointeur de type inconnu, faites gaffe" alors que char* me dit juste "pointeur sur char, ou tableau, ou chaine de caractère..."
Par exemple, gcc -Wall -pedantic couine un peu sur une convertion implicite int* -> char* mais pas int* -> void*.
int i; char* c= &i; void* v= &i;
Marc Boyer -- À mesure que les inégalités regressent, les attentes se renforcent. François Dubet
Pour les entiers, les archi ou ce n'est pas le cas sont rarissimes.
(En fait, je ne vois comme candidats que les machines d'Unisys, ou il y a des machines en complement a un -- et donc deux representations pour 0, je ne sais pas a quel point -0 est considere comme totalement equivalent a +0 -- et des machines avec tags -- et je ne suis pas sur que les bits qui ne participent pas a la valeur ne sont pas fixes)
A+
-- Jean-Marc FAQ de fclc: http://www.levenez.com/lang/c/faq Site de usenet-fr: http://www.usenet-fr.news.eu.org
Pour les entiers, les archi ou ce n'est pas le cas sont rarissimes.
(En fait, je ne vois comme candidats que les machines d'Unisys, ou il y
a des machines en complement a un -- et donc deux representations pour
0, je ne sais pas a quel point -0 est considere comme totalement
equivalent a +0 -- et des machines avec tags -- et je ne suis pas sur
que les bits qui ne participent pas a la valeur ne sont pas fixes)
A+
--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Pour les entiers, les archi ou ce n'est pas le cas sont rarissimes.
(En fait, je ne vois comme candidats que les machines d'Unisys, ou il y a des machines en complement a un -- et donc deux representations pour 0, je ne sais pas a quel point -0 est considere comme totalement equivalent a +0 -- et des machines avec tags -- et je ne suis pas sur que les bits qui ne participent pas a la valeur ne sont pas fixes)
A+
-- Jean-Marc FAQ de fclc: http://www.levenez.com/lang/c/faq Site de usenet-fr: http://www.usenet-fr.news.eu.org
Tonton Th
On 2013-08-22, Marc Boyer wrote:
Pour les flottants, je suis incompétent: je sais qu'on peut avoir +0.0 et -0.0 et NaN dans IEEE-754, mais la norme C admet surement d'autres encodages.
Il me semble même que l'état "NaN" n'est encodé que sur quelques bits de la représentation mémoire :)
On 2013-08-22, Marc Boyer <Marc.Boyer@cert.onera.fr.invalid> wrote:
Pour les flottants, je suis incompétent: je sais qu'on peut avoir +0.0
et -0.0 et NaN dans IEEE-754, mais la norme C admet surement d'autres
encodages.
Il me semble même que l'état "NaN" n'est encodé que sur quelques
bits de la représentation mémoire :)
Pour les flottants, je suis incompétent: je sais qu'on peut avoir +0.0 et -0.0 et NaN dans IEEE-754, mais la norme C admet surement d'autres encodages.
Il me semble même que l'état "NaN" n'est encodé que sur quelques bits de la représentation mémoire :)
Question interessante, est-ce que NaN est considere comme une valeur ou plusieurs? De toute maniere le fait que x != x si x est un NaN offre pas mal de possibilites de foutre le bazard si on cherche a les mettre dans des conteneurs associatifs.
A+
-- Jean-Marc FAQ de fclc: http://www.levenez.com/lang/c/faq Site de usenet-fr: http://www.usenet-fr.news.eu.org
Tonton Th <tth@nowhere.invalid> writes:
On 2013-08-22, Marc Boyer <Marc.Boyer@cert.onera.fr.invalid> wrote:
Question interessante, est-ce que NaN est considere comme une valeur ou
plusieurs? De toute maniere le fait que x != x si x est un NaN offre
pas mal de possibilites de foutre le bazard si on cherche a les mettre
dans des conteneurs associatifs.
A+
--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Question interessante, est-ce que NaN est considere comme une valeur ou plusieurs? De toute maniere le fait que x != x si x est un NaN offre pas mal de possibilites de foutre le bazard si on cherche a les mettre dans des conteneurs associatifs.
A+
-- Jean-Marc FAQ de fclc: http://www.levenez.com/lang/c/faq Site de usenet-fr: http://www.usenet-fr.news.eu.org
Question interessante, est-ce que NaN est considere comme une valeur ou plusieurs?
Si j'ai bonne memoire, la norme definit assez precisement que c'est l'argument qui est conserve (je ne sais plus ce qui se passe pour les operations a plusieurs arguments)
-- Jean-Marc FAQ de fclc: http://www.levenez.com/lang/c/faq Site de usenet-fr: http://www.usenet-fr.news.eu.org
Jean-Marc Bourguet <jm@bourguet.org> writes:
Tonton Th <tth@nowhere.invalid> writes:
On 2013-08-22, Marc Boyer <Marc.Boyer@cert.onera.fr.invalid> wrote:
Question interessante, est-ce que NaN est considere comme une valeur ou
plusieurs?
Si j'ai bonne memoire, la norme definit assez precisement que c'est
l'argument qui est conserve (je ne sais plus ce qui se passe pour les
operations a plusieurs arguments)
--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Question interessante, est-ce que NaN est considere comme une valeur ou plusieurs?
Si j'ai bonne memoire, la norme definit assez precisement que c'est l'argument qui est conserve (je ne sais plus ce qui se passe pour les operations a plusieurs arguments)
-- Jean-Marc FAQ de fclc: http://www.levenez.com/lang/c/faq Site de usenet-fr: http://www.usenet-fr.news.eu.org
