Différentes lectures m'avaient fait admettre que le reste d'un entier
modulo 2 ie (x % 2) produisait un code équivalent à sa version bit à bit
ie (x & 1).
Avec gcc sous Ubuntu, et si l'option d'optimisation O2 est allumée, les
temps d'exécution sont quasi identiques. Sans option d'optimisation, la
version modulo est 30% moins rapide que la version bit à bit.
Par contre, sous Windows XP et avec MS Visual Express + options
d'optimisation activées, j'obtiens un écart significatif. Ci-dessous, le
code et l'affichage obtenu. Ces écarts m'ont été confirmés par d'autres
utilisateurs. Qu'en pensez-vous ?
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. 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.
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. 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.
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. 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.
Samuel Devulder
candide a é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. 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.
int f1(int n) { return n & 1; } _f1: movl 4(%esp), %eax andl $1, %eax ret
int f2(unsigned int n) { return n%2; } _f2: movl 4(%esp), %eax andl $1, %eax ret
int f3(unsigned int n) { return n & 1; } _f3: movl 4(%esp), %eax andl $1, %eax ret
Bref, on voit que dans le cas int non signé le compilo utilise des bitmasks et les code ASM sont strictement identiques.
En revanche pour les versions signées, le code est plus lourd. En effet comme (-1) & 1 donne 1 et que (-1) % 2 donne -1, le code asm calcule n % 2 ainsi: n - ((n + (n>>31) & -2)
sam.
candide a é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. 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.
int f1(int n) {
return n & 1;
}
_f1:
movl 4(%esp), %eax
andl $1, %eax
ret
int f2(unsigned int n) {
return n%2;
}
_f2:
movl 4(%esp), %eax
andl $1, %eax
ret
int f3(unsigned int n) {
return n & 1;
}
_f3:
movl 4(%esp), %eax
andl $1, %eax
ret
Bref, on voit que dans le cas int non signé le compilo utilise des
bitmasks et les code ASM sont strictement identiques.
En revanche pour les versions signées, le code est plus lourd. En effet
comme (-1) & 1 donne 1 et que (-1) % 2 donne -1, le code asm calcule n %
2 ainsi: n - ((n + (n>>31) & -2)
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. 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.
int f1(int n) { return n & 1; } _f1: movl 4(%esp), %eax andl $1, %eax ret
int f2(unsigned int n) { return n%2; } _f2: movl 4(%esp), %eax andl $1, %eax ret
int f3(unsigned int n) { return n & 1; } _f3: movl 4(%esp), %eax andl $1, %eax ret
Bref, on voit que dans le cas int non signé le compilo utilise des bitmasks et les code ASM sont strictement identiques.
En revanche pour les versions signées, le code est plus lourd. En effet comme (-1) & 1 donne 1 et que (-1) % 2 donne -1, le code asm calcule n % 2 ainsi: n - ((n + (n>>31) & -2)
Vous ne chronométrez pas les instructions que vous voulez tester, ou disons que vous les chronométrez noyées dans le bruit. Votre programme passe tout son temps dans les appels de fonctions, dans une moindre mesure dans les printf(), et quelsues autres trucs. Le fait de passer un pointeur sur fonction en argument empêche l'inlining. Je vous suggère les manips suivantes, l'une après l'autre ou en même temps:
- dans vos fonctions est_pairx(), mettre juste return 0; Si ça se trouve ce sera plus long ;-)
- virer le printf() dans test().
- remplacer le f(i * j) dans test() par l'une ou l'autre de vos instructions.
- Alternativement, écrire une: static int est_pair(int n) // ou static inline etc. { return !(n % 2); } et l'appeler directement dans test().
Puisque vous êtes sur l'optimisation, voyez le f(i*j) en fond de boucle. Ça peut être coûteux et bien plus long (le bruit le bruit) que votre instruction à tester, si le compilateur ne constate pas à votre place que cette multiplication de deux valeurs non constantes n'est en fait qu'un incrément.
-- Pierre Maurette
candide, le 29/10/2009 a écrit :
Bonjour,
[...]
Bonjour,
Vous ne chronométrez pas les instructions que vous voulez tester, ou
disons que vous les chronométrez noyées dans le bruit. Votre programme
passe tout son temps dans les appels de fonctions, dans une moindre
mesure dans les printf(), et quelsues autres trucs.
Le fait de passer un pointeur sur fonction en argument empêche
l'inlining. Je vous suggère les manips suivantes, l'une après l'autre
ou en même temps:
- dans vos fonctions est_pairx(), mettre juste
return 0;
Si ça se trouve ce sera plus long ;-)
- virer le printf() dans test().
- remplacer le f(i * j) dans test() par l'une ou l'autre de vos
instructions.
- Alternativement, écrire une:
static int est_pair(int n) // ou static inline etc.
{
return !(n % 2);
}
et l'appeler directement dans test().
Puisque vous êtes sur l'optimisation, voyez le f(i*j) en fond de
boucle. Ça peut être coûteux et bien plus long (le bruit le bruit) que
votre instruction à tester, si le compilateur ne constate pas à votre
place que cette multiplication de deux valeurs non constantes n'est en
fait qu'un incrément.
Vous ne chronométrez pas les instructions que vous voulez tester, ou disons que vous les chronométrez noyées dans le bruit. Votre programme passe tout son temps dans les appels de fonctions, dans une moindre mesure dans les printf(), et quelsues autres trucs. Le fait de passer un pointeur sur fonction en argument empêche l'inlining. Je vous suggère les manips suivantes, l'une après l'autre ou en même temps:
- dans vos fonctions est_pairx(), mettre juste return 0; Si ça se trouve ce sera plus long ;-)
- virer le printf() dans test().
- remplacer le f(i * j) dans test() par l'une ou l'autre de vos instructions.
- Alternativement, écrire une: static int est_pair(int n) // ou static inline etc. { return !(n % 2); } et l'appeler directement dans test().
Puisque vous êtes sur l'optimisation, voyez le f(i*j) en fond de boucle. Ça peut être coûteux et bien plus long (le bruit le bruit) que votre instruction à tester, si le compilateur ne constate pas à votre place que cette multiplication de deux valeurs non constantes n'est en fait qu'un incrément.
-- Pierre Maurette
-ed-
On 30 oct, 18:13, Vincent Lefevre <vincent+ wrote:
int est_pair2(int n) { return !((unsigned int) n % 2);
}
/* retourne la durée du test en ms */ static double test (unsigned int n, fun_f *f) { unsigned int i, j; int s = 0; clock_t start = clock (); double ms;
for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { s += f (i * j); } } ms = (clock () - start) * 1000 / (double) CLOCKS_PER_SEC; #if 0 printf ("%d/%ldn", s, (long) n*n); #endif return ms; }
#define N 10000 #define NB_TESTS 10 #define NB_ELEM(a) (sizeof(a)/sizeof*(a))
int main (void) { size_t i; fun_f *af[] = { est_pair0, est_pair1, est_pair2};
for (i = 0; i < NB_ELEM(af); i++) { unsigned long duree = 0; int j; for (j = 0; j < NB_TESTS; j++) duree += test (N, af[i]);
int est_pair2(int n)
{
return !((unsigned int) n % 2);
}
/* retourne la durée du test en ms */
static double test (unsigned int n, fun_f *f)
{
unsigned int i, j;
int s = 0;
clock_t start = clock ();
double ms;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
s += f (i * j);
}
}
ms = (clock () - start) * 1000 / (double) CLOCKS_PER_SEC;
#if 0
printf ("%d/%ldn", s, (long) n*n);
#endif
return ms;
}
#define N 10000
#define NB_TESTS 10
#define NB_ELEM(a) (sizeof(a)/sizeof*(a))
int main (void)
{
size_t i;
fun_f *af[] =
{
est_pair0, est_pair1, est_pair2};
for (i = 0; i < NB_ELEM(af); i++)
{
unsigned long duree = 0;
int j;
for (j = 0; j < NB_TESTS; j++)
duree += test (N, af[i]);
int est_pair2(int n) { return !((unsigned int) n % 2);
}
/* retourne la durée du test en ms */ static double test (unsigned int n, fun_f *f) { unsigned int i, j; int s = 0; clock_t start = clock (); double ms;
for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { s += f (i * j); } } ms = (clock () - start) * 1000 / (double) CLOCKS_PER_SEC; #if 0 printf ("%d/%ldn", s, (long) n*n); #endif return ms; }
#define N 10000 #define NB_TESTS 10 #define NB_ELEM(a) (sizeof(a)/sizeof*(a))
int main (void) { size_t i; fun_f *af[] = { est_pair0, est_pair1, est_pair2};
for (i = 0; i < NB_ELEM(af); i++) { unsigned long duree = 0; int j; for (j = 0; j < NB_TESTS; j++) duree += test (N, af[i]);
