Optimisation de la division par 2

Le
candide
Bonjour,

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 ?



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

int est_pair0(int n)
{
return !(n & 0x1);
}

int est_pair1(int n)
{
return !(n % 2);
}

double test(unsigned int n, int (*f) (int))
{
unsigned int i, j;
int s = 0;
clock_t now = clock();

for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
s += f(i * j);
printf("%d", s);
return (double) (clock() - now) / CLOCKS_PER_SEC;

}

#define N (unsigned int)10000
#define NB_TESTS 10
int main(void)
{
int i,j;
int (*f[2])(int)={est_pair0, est_pair1};

for (j=0;j<2;j++)
{
double duree=0;
for (i=0;i<NB_TESTS;i++)
duree+=test(N, f[j]);

printf("estpair%d : %.2lf secondes", j, duree/NB_TESTS);
}

return 0;
}
/* */

75000000
75000000
75000000
75000000
75000000
75000000
75000000
75000000
75000000
75000000
estpair0 : 1.03 secondes

75000000
75000000
75000000
75000000
75000000
75000000
75000000
75000000
75000000
75000000
estpair1 : 1.42 secondes
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 5
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Vincent Lefevre
Le #20456331
Dans l'article candide
int est_pair0(int n)
{
return !(n & 0x1);
}



int est_pair1(int n)
{
return !(n % 2);
}



Et que donne ceci?

int est_pair2(int n)
{
return !((unsigned int) n % 2);
}

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

--
Vincent Lefèvre 100% accessible validated (X)HTML - Blog: Work: CR INRIA - computer arithmetic / Arénaire project (LIP, ENS-Lyon)
candide
Le #20457471
Vincent Lefevre a écrit :


Et que donne ceci?

int est_pair2(int n)
{
return !((unsigned int) n % 2);
}





Ah ! bien vu, les temps deviennent identiques :


75000000
75000000
75000000
75000000
75000000
75000000
75000000
75000000
75000000
75000000
estpair0 : 0.91 secondes

75000000
75000000
75000000
75000000
75000000
75000000
75000000
75000000
75000000
75000000
estpair1 : 1.35 secondes

75000000
75000000
75000000
75000000
75000000
75000000
75000000
75000000
75000000
75000000
estpair2 : 0.91 secondes


Merci.
candide
Le #20458111
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.
Samuel Devulder
Le #20458791
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.



Il suffit de jetter un oeil au code ASM.

int f0(int n) {
return n%2;
}
_f0:
movl 4(%esp), %eax
movl %eax, %ecx
shrl $31, %ecx
leal (%eax,%ecx), %edx
andl $-2, %edx
subl %edx, %eax
ret

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.
-ed-
Le #20458951
On 29 oct, 23:14, candide
        printf("estpair%d : %.2lf secondesnn",  j, duree/NB_T ESTS);



N'existe pas. C'est

printf("estpair%d : %.2f secondesnn", j, duree/NB_TESTS);
-ed-
Le #20458941
On 29 oct, 23:14, candide
#define N (unsigned int)10000



Une façon compliqué et erronée

#define N ((unsigned int)10000)

d'écrire

#define N 10000U
Pierre Maurette
Le #20459041
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.


--
Pierre Maurette
-ed-
Le #20459071
On 30 oct, 18:13, Vincent Lefevre
Dans l'article   candide
> int est_pair0(int n)
> {
>     return !(n & 0x1);
> }
> int est_pair1(int n)
> {
>     return !(n % 2);
> }

Et que donne ceci?

int est_pair2(int n)
{
    return !((unsigned int) n % 2);

}

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



Bien vu :

est_pair0() : 0.45 secondes

est_pair1() : 0.47 secondes

est_pair2() : 0.42 secondes


Process returned 0 (0x0) execution time : 13.510 s
Press any key to continue.

Sous Vista avec Code::Blocks.

avec ce code :

/* ======================== =============== */
#include #include
typedef int (fun_f) (int);

static int est_pair0 (int n)
{
return !(n & 1);
}

static int est_pair1 (int n)
{
return !(n % 2);
}

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]);

printf ("est_pair%d() : %.2f secondesnn", i, (double) duree /
(NB_TESTS * 1000));
}

return 0;
}
-ed-
Le #20459061
On 31 oct, 08:23, Samuel Devulder wrote:
Il suffit de jetter un oeil au code ASM.



Ce qui donne une explication pour une implémentation donnée, dans des
conditions données ...
Éric Lévénez
Le #20459711
-ed- a écrit :
On 29 oct, 23:14, candide
printf("estpair%d : %.2lf secondesnn", j, duree/NB_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'écrire "%f".

--
Éric Lévénez
FAQ de fclc :
Publicité
Poster une réponse
Anonyme