Optimisation de la division par 2

Vincent Lefevre

31/10/2009 à 21:48

Dans l'article <4aeb65c0$0$32749$,
candide écrit:

Vincent Lefevre a écrit :

> Tous les compilateurs ne détectent peut-être pas que le signe du "%"
> n'aura aucune influence à cause du "!".

En réalité, je ne pense pas que ce soit l'explication ultime puisque si
je supprime des return des trois fonctions la présence du symbole "!" de
négation, les écarts restent dans le même sens.

Mon explication n'est valable que lorsqu'il y a un "!". Si tu
supprimes le "!", c'est normal que tu obtiennes des temps différents
(le compilateur ne pouvant pas optimiser la version % signée puisque
cela donnerait un résultat différent). En revanche, s'il y a un "!",
les compilateurs les plus avancés vont être capables d'optimiser la
version signée puisque !(-1) == !1; mais d'autres compilateurs n'en
sont pas capables et génèrent du code non optimisé, comme s'il n'y
avait pas de "!". Donc mieux vaut utiliser la version non signée avec
"!" (ou bien le "&"), même si la version signée est sémantiquement
équivalente.

Je pense en fait que, tout simplement, si le compilateur est sûr et
certain que l'on effectue une division entre entiers d'un type non
signé (à cause de la conversion que tu suggères et des règles de
conversion), il tente une division par décalage de bits (j'ai
vérifié que cela marchait aussi pour des puissances de 2 et pas
seulement 2). D'ailleurs, si on écrit plutôt :

int est_pair2(int n)
{
return (n % 2U);
}

le temps est le même que si on faisait n & 1 ou (unsigned int) n % 2.

Oui, car n % 2U est une version non signée du modulo.

--
Vincent Lefèvre - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / Arénaire project (LIP, ENS-Lyon)

Vincent Lefevre

31/10/2009 à 22:00

Dans l'article <4aec7ca8$0$29451$,
Samuel Devulder écrit:

D'ailleurs la représentation en complément à 2 est assez dangereuse dans
le sens ou elle est "asymétrique". La valeur minimale est son propre
inverse (sommée à elle même elle le résultat vaut zéro), donc on ne peut
assumer que l'opposé d'un nombre négatif est toujours positif.

En C ISO, il y a un overflow et c'est un UB. Dans un programme
conforme, l'opposé d'un nombre négatif est toujours positif, et
le compilateur peut faire les optimisations correspondantes (ou
alors, avec gcc, il faut utiliser -fwrapv pour rendre ces UB
définis avec la sémantique du complément à 2, mais c'est une
extension).

--
Vincent Lefèvre - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / Arénaire project (LIP, ENS-Lyon)

Samuel Devulder

01/11/2009 à 00:14

Vincent Lefevre a écrit :

Dans l'article <4aec7ca8$0$29451$,
Samuel Devulder écrit:

D'ailleurs la représentation en complément à 2 est assez dangereuse dans
le sens ou elle est "asymétrique". La valeur minimale est son propre
inverse (sommée à elle même elle le résultat vaut zéro), donc on ne peut
assumer que l'opposé d'un nombre négatif est toujours positif.

En C ISO, il y a un overflow et c'est un UB.

Et oui le fameux UB de la norme. Je l'aime décidément bien cet
argument... Si la norme le dit.. il n'y a rien d'autre à ajouter
finalement :) C'est beau les arguments d'autorités ya rien à discuter ;-)

> Dans un programme

conforme, l'opposé d'un nombre négatif est toujours positif, et

Le truc est qu'à en croire la norme, les programmes conformes ne sont
pas légions. J'ai lu que toutes les addition signed sont un risque
d'overflow et donc d'UB d'après la norme. En revanche les overflow sur
unsigned ne font jammais d'UB et car ils "wrap" automatiquement. J'ai le
sentiment qu'on devrait le plus possible utiliser des unsigned au lieu
de int dans les progs pour ne pas risquer de soucis avec les UB de
l'arithmétique signée.

En plus du fait de l'absence d'UB, il y a des chances que l'optimiseur
fasse un meilleur job. Exemple: en théorie l'addition est associative
avec les unsigned, mais pas avec les signed car l'associativité sur les
signed risque d'introduire des UB.

Y a t'il une raison de favoriser les signed au lieu des unsigned dans
les progs? Des raisons Historique? Pratiques? (on préfère faire un
int i = ...;
while(--i>=0) {...}
plutot qu'un
unsigned i = ...;
while(i-->0) {...}
?)

sam.

candide

01/11/2009 à 00:44

Pierre Maurette a écrit :

Vous m'étonnez. CF plus haut. Rassurez-moi: vous êtes dans l'Education
Nationale ?

Tiens, ça me fait penser à cette phrase de Cocteau qui dit grosso modo :

"Puisque ces évènements nous sont incompréhensibles, feignons d'en être
les organisateurs".

J'ai bien l'impression que vous êtes ce qu'on appelle "un mauvais
perdant". Car en réalité, vous étiez bien incapable de répondre à ma
question, vous ignoriez sans doute ce comportement du compilateur de MS,
vous vous êtes mépris en confondant du bruit et un signal et vous
essayez de cacher ce bruit qui fait mal à vos oreilles en tentant de me
ridiculiser.

Reprenons mon code initial. Avec N000.

1°) Sous gcc, le temps d'un test "bruité" est d'environ 1 s. Si on
détruit le bruit (plus de pointeur de fonction, et même plus de
fonction, affichage réduit au minimum et qu'il ne faut pas complètement
supprimer sous peine que le calcul ne soit pas effectué à cause des
optimisations, suppression de la double boucle) :

#define TEST(f) {
unsigned s = 0;
int i;
s = 0;

for (i = 0; i < 100000000; i++)
s += (unsigned)f(i);
printf("%un",s);
}

on obtient environ 0.2 s. Donc je n'appelle pas ça du bruit ("noyées
dans le bruit" disiez-vous), c'est loin d'être négligeable. Il se trouve
par ailleurs en effet que si dans ma fonction du premier code on
retourne 0 au lieu de !(n%2) le temps est inchangé, je ne me l'explique
pas mais il n'empêche qu'un calcul ou un autre utilise quand même 1/5
incompressible du temps du test.

2°) Mais il n'y avait pas d'interrogations concernant gcc. Le point
portait sur Visual. Les écarts de temps observés devaient au moins
soulever un doute (justifié, comme la suite de la discussion l'a
montré). Mais Monsieur Maurette préfère se dire que ce n'est que du
bruit d'un programmeur du dimanche.

Je débruite le code initial en ceci :

#include <stdio.h>
#include <time.h>

#define f0(n) (!((n) & 0x1))
#define f1(n) (!((n) % 2))
#define f2(n) (!((n) % 2U))
#define f3(n) (42)
#define N 10000

#define TEST(f ) {
clock_t now=clock();
unsigned s = 0;
int i,j;
s = 0;

for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
s += (unsigned)f(i*j);
printf("%un",s);
printf("%.2fn",(double) (clock() - now) / CLOCKS_PER_SEC);}

int main(void)
{
//TEST(f0)
//TEST(f1)
//TEST(f2)
//TEST(f1)

return 0;
}

*) Pour f0, le temps mis en moyenne selon est de 0.16s (au lieu de 1s)
donc effectivement il y avait beaucoup de bruit.
*) Par contre pour f1, le temps mis est en moyenne de 0.75s au lieu
1.42s pour le code initial donc, c'est loin loin d'être du bruit. Même
si je supprime la double boucle par
for (i = 0; i < N*N; i++)
s += (unsigned)f(i);
j'obtiens en moyenne un temps presque équivalent (0.65s).

Une fois de plus, vous n'avez pas su apprécier le problème à sa juste
complexité et vous pouvez même me remercier de vous avoir fait apprendre
quelque chose ;)

Pierre Maurette a écrit :

Vous m'étonnez. CF plus haut. Rassurez-moi: vous êtes dans l'Education
Nationale ?

Tiens, ça me fait penser à cette phrase de Cocteau qui dit grosso modo :

"Puisque ces évènements nous sont incompréhensibles, feignons d'en être
les organisateurs".

J'ai bien l'impression que vous êtes ce qu'on appelle "un mauvais
perdant". Car en réalité, vous étiez bien incapable de répondre à ma
question, vous ignoriez sans doute ce comportement du compilateur de MS,
vous vous êtes mépris en confondant du bruit et un signal et vous
essayez de cacher ce bruit qui fait mal à vos oreilles en tentant de me
ridiculiser.

Reprenons mon code initial. Avec N000.

1°) Sous gcc, le temps d'un test "bruité" est d'environ 1 s. Si on
détruit le bruit (plus de pointeur de fonction, et même plus de
fonction, affichage réduit au minimum et qu'il ne faut pas complètement
supprimer sous peine que le calcul ne soit pas effectué à cause des
optimisations, suppression de la double boucle) :

#define TEST(f) {
unsigned s = 0;
int i;
s = 0;

for (i = 0; i < 100000000; i++)
s += (unsigned)f(i);
printf("%un",s);
}

on obtient environ 0.2 s. Donc je n'appelle pas ça du bruit ("noyées
dans le bruit" disiez-vous), c'est loin d'être négligeable. Il se trouve
par ailleurs en effet que si dans ma fonction du premier code on
retourne 0 au lieu de !(n%2) le temps est inchangé, je ne me l'explique
pas mais il n'empêche qu'un calcul ou un autre utilise quand même 1/5
incompressible du temps du test.

2°) Mais il n'y avait pas d'interrogations concernant gcc. Le point
portait sur Visual. Les écarts de temps observés devaient au moins
soulever un doute (justifié, comme la suite de la discussion l'a
montré). Mais Monsieur Maurette préfère se dire que ce n'est que du
bruit d'un programmeur du dimanche.

Je débruite le code initial en ceci :

#include <stdio.h>
#include <time.h>

#define f0(n) (!((n) & 0x1))
#define f1(n) (!((n) % 2))
#define f2(n) (!((n) % 2U))
#define f3(n) (42)
#define N 10000

#define TEST(f ) {
clock_t now=clock();
unsigned s = 0;
int i,j;
s = 0;

for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
s += (unsigned)f(i*j);
printf("%un",s);
printf("%.2fn",(double) (clock() - now) / CLOCKS_PER_SEC);}

int main(void)
{
//TEST(f0)
//TEST(f1)
//TEST(f2)
//TEST(f1)

return 0;
}

*) Pour f0, le temps mis en moyenne selon est de 0.16s (au lieu de 1s)
donc effectivement il y avait beaucoup de bruit.
*) Par contre pour f1, le temps mis est en moyenne de 0.75s au lieu
1.42s pour le code initial donc, c'est loin loin d'être du bruit. Même
si je supprime la double boucle par
for (i = 0; i < N*N; i++)
s += (unsigned)f(i);
j'obtiens en moyenne un temps presque équivalent (0.65s).

Une fois de plus, vous n'avez pas su apprécier le problème à sa juste
complexité et vous pouvez même me remercier de vous avoir fait apprendre
quelque chose ;)

Vous avez filtré cet utilisateur ! Consultez son message

Pierre Maurette a écrit :

Vous m'étonnez. CF plus haut. Rassurez-moi: vous êtes dans l'Education
Nationale ?

Tiens, ça me fait penser à cette phrase de Cocteau qui dit grosso modo :

"Puisque ces évènements nous sont incompréhensibles, feignons d'en être
les organisateurs".

J'ai bien l'impression que vous êtes ce qu'on appelle "un mauvais
perdant". Car en réalité, vous étiez bien incapable de répondre à ma
question, vous ignoriez sans doute ce comportement du compilateur de MS,
vous vous êtes mépris en confondant du bruit et un signal et vous
essayez de cacher ce bruit qui fait mal à vos oreilles en tentant de me
ridiculiser.

Reprenons mon code initial. Avec N000.

1°) Sous gcc, le temps d'un test "bruité" est d'environ 1 s. Si on
détruit le bruit (plus de pointeur de fonction, et même plus de
fonction, affichage réduit au minimum et qu'il ne faut pas complètement
supprimer sous peine que le calcul ne soit pas effectué à cause des
optimisations, suppression de la double boucle) :

#define TEST(f) {
unsigned s = 0;
int i;
s = 0;

for (i = 0; i < 100000000; i++)
s += (unsigned)f(i);
printf("%un",s);
}

on obtient environ 0.2 s. Donc je n'appelle pas ça du bruit ("noyées
dans le bruit" disiez-vous), c'est loin d'être négligeable. Il se trouve
par ailleurs en effet que si dans ma fonction du premier code on
retourne 0 au lieu de !(n%2) le temps est inchangé, je ne me l'explique
pas mais il n'empêche qu'un calcul ou un autre utilise quand même 1/5
incompressible du temps du test.

2°) Mais il n'y avait pas d'interrogations concernant gcc. Le point
portait sur Visual. Les écarts de temps observés devaient au moins
soulever un doute (justifié, comme la suite de la discussion l'a
montré). Mais Monsieur Maurette préfère se dire que ce n'est que du
bruit d'un programmeur du dimanche.

Je débruite le code initial en ceci :

#include <stdio.h>
#include <time.h>

#define f0(n) (!((n) & 0x1))
#define f1(n) (!((n) % 2))
#define f2(n) (!((n) % 2U))
#define f3(n) (42)
#define N 10000

#define TEST(f ) {
clock_t now=clock();
unsigned s = 0;
int i,j;
s = 0;

for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
s += (unsigned)f(i*j);
printf("%un",s);
printf("%.2fn",(double) (clock() - now) / CLOCKS_PER_SEC);}

int main(void)
{
//TEST(f0)
//TEST(f1)
//TEST(f2)
//TEST(f1)

return 0;
}

*) Pour f0, le temps mis en moyenne selon est de 0.16s (au lieu de 1s)
donc effectivement il y avait beaucoup de bruit.
*) Par contre pour f1, le temps mis est en moyenne de 0.75s au lieu
1.42s pour le code initial donc, c'est loin loin d'être du bruit. Même
si je supprime la double boucle par
for (i = 0; i < N*N; i++)
s += (unsigned)f(i);
j'obtiens en moyenne un temps presque équivalent (0.65s).

Une fois de plus, vous n'avez pas su apprécier le problème à sa juste
complexité et vous pouvez même me remercier de vous avoir fait apprendre
quelque chose ;)

-ed-

01/11/2009 à 10:46

On 31 oct, 12:53, Éric Lévénez wrote:

-ed- a écrit :

>> printf("estpair%d : %.2lf secondesnn", j, duree/N B_TESTS);

> N'existe pas. C'est

> printf("estpair%d : %.2f secondesnn", j, duree/ NB_TESTS);

Non. "%lf" est tout à fait valide, même s'il est plus courant d'écr ire "%f".

Oui, c'est correct en C99, mais pas en C90 (où c'est gentiment toléré
par la plupart des compilateurs).

-ed-

01/11/2009 à 10:56

On 31 oct, 17:58, Pierre Maurette wrote:

Ce que je veux dire, c'est qu'en C, les variables sont signées, et ça
fout un grosse merde.

Les variables sont signée ou non. Question de définition.

Il est probable que sur la plupart des machines, le code de calcul
produit avec des variables signées soit plus complexe qu'avec des
variables non signées.

candide

01/11/2009 à 11:23

Éric Lévénez a écrit :

Non. "%lf" est tout à fait valide, même s'il est plus courant d'écrire
"%f".

Ah oui, tu avais raison, la Norme dit :

7.19.6.1 The fprintf function

p7

l (ell) [...]or has no effect on a following a, A, e, E, f, F, g, or G
conversion specifier.

Par contre pour un long double c'est un L majuscule !

espie

01/11/2009 à 11:56

In article <4aec7ca8$0$29451$,
Samuel Devulder wrote:

Oui, tu veux dire qu'en ASM on doit savoir ce que l'on fait.

<sarcasme>Parce qu'en C, c'est pas la meme chose ? Je croyais que c'etait
reserve a Java, ce genre de souci...</sarcasme>

En fait le soucis est que l'on ne pense pas naturellement en complément à 2.
Je suis persuadé que beaucoup, si
ce n'est tous pensent intuitivement "positif" ou éventuellement avec un
bit de signe séparé du reste comme dans les float IEEE (donc 2 valeurs
de zéro). Cela n'aide pas à écrire des expressions valides
indépendamment du signe.

De toutes facons, le complement a 2 n'est pas garanti, ca n'est jamais
qu'une des representations possibles pour les entiers signes (je te l'accorde,
c'est la plus repandue aujourd'hui).

Si on se pose des questions de micro-optimisation, ca aide de connaitre
l'assembleur. Et le code genere. On pourra, comme le fait candide, regarder
aussi longtemps qu'on veut le code source, modifier les trucs pour essayer
d'obtenir des resultats... ca a a peu pres autant de chance d'aboutir que
l'alchimiste du moyen age essayant d'obtenir la transmutation de la matiere.

Surtout qu'en plus la tres sainte Norme ne dit rien sur les performances du
code, et que les compilo sont vraiment plus ou moins futes...

A cote de ca, meme si c'est pedagogiquement interessant, je me garde en
general de me plonger dans ce niveau de detail. Ca a une tendance naturelle
a obfusquer gravement le code, et a cacher de vraies grosses opportunites
d'optimisations qui elles, ne vont pas se compter en pouiemes de
micro-secondes.

Faire du code qui va vite, c'est un art. Eviter des micro-constructions qui
rament, c'est bien, mais c'est pas avec ca qu'on fait du code rapide, et
tu le sais aussi bien que moi...

espie

01/11/2009 à 12:03

In article <4aecc4e0$0$22236$,
Samuel Devulder wrote:

Le truc est qu'à en croire la norme, les programmes conformes ne sont
pas légions. J'ai lu que toutes les addition signed sont un risque
d'overflow et donc d'UB d'après la norme. En revanche les overflow sur
unsigned ne font jammais d'UB et car ils "wrap" automatiquement. J'ai le
sentiment qu'on devrait le plus possible utiliser des unsigned au lieu
de int dans les progs pour ne pas risquer de soucis avec les UB de
l'arithmétique signée.

En plus du fait de l'absence d'UB, il y a des chances que l'optimiseur
fasse un meilleur job. Exemple: en théorie l'addition est associative
avec les unsigned, mais pas avec les signed car l'associativité sur les
signed risque d'introduire des UB.

Y a t'il une raison de favoriser les signed au lieu des unsigned dans
les progs? Des raisons Historique? Pratiques? (on préfère faire un
int i = ...;
while(--i>=0) {...}
plutot qu'un
unsigned i = ...;
while(i-->0) {...}
?)

Juste, la plupart des gens se gauffrent regulierement avec les comparaisons
en presence d'unsigned, ou utilisent des macros qui vont merder de facon
interessante. Typiquement, comment tu fais pour verifier que deux nombres
sont proches ? Avec des valeurs signees, tu sors abs de ton chapeau, et tu
ecris: if (abs(a-b) < 5)
En non-signe, il faut avoir la presence d'esprit de sortir un:
#define absdiff(a, b) ((a) < (b) ? (b) - (a) : (a) - (b))
if (absdiff(a, b) < 5)

sans compter que la quasi-totalite de la bibliotheque standard et des
bibliotheques que tu peux utiliser bossent avec des entiers signes...
donc ca va se bousculer au balcon cote verification des parametres.

Exception: size_t. C'est impressionnant les bugs lies a size_t. Ca ne fait
guere que quelques annees que les bibliotheques standard embarquent un
calloc() qui fonctionnent... Ben ouais, a la place d'un UB, on obtient
des debordements de capacite parfaitement documentes si on multiplie deux
valeurs trop grandes. C'est un schema d'attaque classique et parfaitement
connu (a l'origine d'un trou dans ssh, et d'un trou dans le flashplayer,
si ma memoire est bonne).

A l'arrivee, plein de gens preferent avoir parfois un UB plutot que des
bugs un peu abscons concernant leurs tests...

In article <4aecc4e0$0$22236$426a74cc@news.free.fr>,
Samuel Devulder <samuel-dot-devulder@geensys.com> wrote:

Le truc est qu'à en croire la norme, les programmes conformes ne sont
pas légions. J'ai lu que toutes les addition signed sont un risque
d'overflow et donc d'UB d'après la norme. En revanche les overflow sur
unsigned ne font jammais d'UB et car ils "wrap" automatiquement. J'ai le
sentiment qu'on devrait le plus possible utiliser des unsigned au lieu
de int dans les progs pour ne pas risquer de soucis avec les UB de
l'arithmétique signée.

En plus du fait de l'absence d'UB, il y a des chances que l'optimiseur
fasse un meilleur job. Exemple: en théorie l'addition est associative
avec les unsigned, mais pas avec les signed car l'associativité sur les
signed risque d'introduire des UB.

Y a t'il une raison de favoriser les signed au lieu des unsigned dans
les progs? Des raisons Historique? Pratiques? (on préfère faire un
int i = ...;
while(--i>=0) {...}
plutot qu'un
unsigned i = ...;
while(i-->0) {...}
?)

Juste, la plupart des gens se gauffrent regulierement avec les comparaisons
en presence d'unsigned, ou utilisent des macros qui vont merder de facon
interessante. Typiquement, comment tu fais pour verifier que deux nombres
sont proches ? Avec des valeurs signees, tu sors abs de ton chapeau, et tu
ecris: if (abs(a-b) < 5)
En non-signe, il faut avoir la presence d'esprit de sortir un:
#define absdiff(a, b) ((a) < (b) ? (b) - (a) : (a) - (b))
if (absdiff(a, b) < 5)

sans compter que la quasi-totalite de la bibliotheque standard et des
bibliotheques que tu peux utiliser bossent avec des entiers signes...
donc ca va se bousculer au balcon cote verification des parametres.

Exception: size_t. C'est impressionnant les bugs lies a size_t. Ca ne fait
guere que quelques annees que les bibliotheques standard embarquent un
calloc() qui fonctionnent... Ben ouais, a la place d'un UB, on obtient
des debordements de capacite parfaitement documentes si on multiplie deux
valeurs trop grandes. C'est un schema d'attaque classique et parfaitement
connu (a l'origine d'un trou dans ssh, et d'un trou dans le flashplayer,
si ma memoire est bonne).

A l'arrivee, plein de gens preferent avoir parfois un UB plutot que des
bugs un peu abscons concernant leurs tests...

Vous avez filtré cet utilisateur ! Consultez son message

In article <4aecc4e0$0$22236$,
Samuel Devulder wrote:

Le truc est qu'à en croire la norme, les programmes conformes ne sont
pas légions. J'ai lu que toutes les addition signed sont un risque
d'overflow et donc d'UB d'après la norme. En revanche les overflow sur
unsigned ne font jammais d'UB et car ils "wrap" automatiquement. J'ai le
sentiment qu'on devrait le plus possible utiliser des unsigned au lieu
de int dans les progs pour ne pas risquer de soucis avec les UB de
l'arithmétique signée.

En plus du fait de l'absence d'UB, il y a des chances que l'optimiseur
fasse un meilleur job. Exemple: en théorie l'addition est associative
avec les unsigned, mais pas avec les signed car l'associativité sur les
signed risque d'introduire des UB.

Y a t'il une raison de favoriser les signed au lieu des unsigned dans
les progs? Des raisons Historique? Pratiques? (on préfère faire un
int i = ...;
while(--i>=0) {...}
plutot qu'un
unsigned i = ...;
while(i-->0) {...}
?)

Juste, la plupart des gens se gauffrent regulierement avec les comparaisons
en presence d'unsigned, ou utilisent des macros qui vont merder de facon
interessante. Typiquement, comment tu fais pour verifier que deux nombres
sont proches ? Avec des valeurs signees, tu sors abs de ton chapeau, et tu
ecris: if (abs(a-b) < 5)
En non-signe, il faut avoir la presence d'esprit de sortir un:
#define absdiff(a, b) ((a) < (b) ? (b) - (a) : (a) - (b))
if (absdiff(a, b) < 5)

sans compter que la quasi-totalite de la bibliotheque standard et des
bibliotheques que tu peux utiliser bossent avec des entiers signes...
donc ca va se bousculer au balcon cote verification des parametres.

Exception: size_t. C'est impressionnant les bugs lies a size_t. Ca ne fait
guere que quelques annees que les bibliotheques standard embarquent un
calloc() qui fonctionnent... Ben ouais, a la place d'un UB, on obtient
des debordements de capacite parfaitement documentes si on multiplie deux
valeurs trop grandes. C'est un schema d'attaque classique et parfaitement
connu (a l'origine d'un trou dans ssh, et d'un trou dans le flashplayer,
si ma memoire est bonne).

A l'arrivee, plein de gens preferent avoir parfois un UB plutot que des
bugs un peu abscons concernant leurs tests...

Vincent Lefevre

01/11/2009 à 13:14

Dans l'article <4aecc4e0$0$22236$,
Samuel Devulder écrit:

Vincent Lefevre a écrit :
> Dans un programme conforme, l'opposé d'un nombre négatif est
> toujours positif, et

Le truc est qu'à en croire la norme, les programmes conformes ne sont
pas légions. J'ai lu que toutes les addition signed sont un risque
d'overflow et donc d'UB d'après la norme. En revanche les overflow sur
unsigned ne font jammais d'UB et car ils "wrap" automatiquement. J'ai le
sentiment qu'on devrait le plus possible utiliser des unsigned au lieu
de int dans les progs pour ne pas risquer de soucis avec les UB de
l'arithmétique signée.

Le fait que ça wrappe n'est pas forcément le comportement voulu par
l'utilisateur. Dans ce cas, la solution n'est pas d'utiliser un type
non signé (sauf si les quelques valeurs positives supplémentaires
suffisent), mais un type plus grand, et de valider son logiciel.
Sinon, ça fait comme Ariane 5.

D'autre part, on a parfois besoin de types signés pour représenter
des valeurs négatives, et mixer les types signés et les types non
signés est dangereux (surtout s'ils sont de tailles différentes) à
cause des conversions implicites.

En plus du fait de l'absence d'UB, il y a des chances que l'optimiseur
fasse un meilleur job.

C'est plutôt l'inverse.

Exemple: en théorie l'addition est associative avec les unsigned,
mais pas avec les signed car l'associativité sur les signed risque
d'introduire des UB.

Non, la notion d'UB existe dans le source C, mais comme en pratique,
le processeur calcule en complément à 2, les optimisations sur les
nombres signés restent valides.

--
Vincent Lefèvre - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / Arénaire project (LIP, ENS-Lyon)

Optimisation de la division par 2

10 réponses

Veuillez sélectionner un problème