Temps d'execution : theorie et pratique

zwim

24/10/2009 à 20:02

Le Sat, 24 Oct 2009 19:28:19 +0200
candide a écrit

zwim a écrit :

Tandis que naif2 détruit l'optim de registre et est donc plus lent, et
que non_naif détruit le bénéfice du loop unrolling en le remplaçant
par 2 branches de code.

C'est plus contrasté chez moi (gcc sous Ubuntu avec n=1 << 26) :

-- sans option d'optimisation, ton code "non naïf" est plus rapide que
mon code naïf et mon code non naïf ;

-- avec option d'optimisation (O3), ton code "non naïf" est plus lent
que mon code naïf et mon code non naïf.

Bah, j'ai recompilé en -O3 avec gcc et fait la moyenne sur une
vingtaine d'exécutions, la conclusion est inchangée :

naif : 4.846000 s (0.242300)
naif 2 : 8.763000 s (0.438150)
non naif : 8.550000 s (0.427500)
non naif 2 : 4.483000 s (0.224150)

Peux-tu tester avec cette instrumentation du code ?

/* ==================== debut min_max_fclc.c ==================== */

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

void naif(int t[], int n, int *min, int *max)
{
int i;

int mini = t[0], maxi = t[0];

for (i = 0; i < n; i++)
{
if (t[i] < mini)
mini = t[i];
if (t[i] > maxi)
maxi = t[i];
}
*min = mini;
*max = maxi;
}

void naif2(int t[], int n, int *min, int *max)
{
int i;

int mini = t[0], maxi = t[0];

for (i = 0; i < n; i++)
{
if (t[i] < mini)
mini = t[i];
}
for (i = 0; i < n; i++)
{
if (t[i] > maxi)
maxi = t[i];
}
*min = mini;
*max = maxi;
}

void non_naif(int *t, int n, int *min, int *max)
{
int mini = t[0], maxi = t[1];
int k = 0;

for (k = 0; k < n - 1; k += 2)
{
if (t[k] < t[k + 1])
{
if (t[k] < mini)
mini = t[k];
if (t[k + 1] > maxi)
maxi = t[k + 1];
}
else
{
if (t[k + 1] < mini)
mini = t[k + 1];
if (t[k] > maxi)
maxi = t[k];
}
}

*min = mini;
*max = maxi;
}

void non_naif2(int *t, int n, int *min, int *max)
{
int mini = t[0], maxi = t[1];
int k = 0;

for (k = 0; k < n - 1; k += 2)
{
if (t[k] < mini)
mini = t[k];
if (t[k + 1] < mini)
mini = t[k + 1];
if (t[k + 1] > maxi)
maxi = t[k + 1];
if (t[k] > maxi)
maxi = t[k];
}

*min = mini;
*max = maxi;
}

void test(int n)
{
int i;
int *t = malloc(n * sizeof *t);
int min, max;
clock_t now;
double t1,t2,t3,t4;
int nb;

if (t != NULL)
{
t1 = 0.0;
t2 = 0.0;
t3 = 0.0;
t4 = 0.0;

for(nb=0; nb<20; nb++)
{

printf("nb = %dn", nb);

/* Génération d'un tableau aléatoire */
srand(time(NULL));
for (i = 0; i < n; i++)
t[i] = rand();

/* Temps du naif */
now = clock();
naif(t, n, &min, &max);
t1 += (double) (clock() - now) / CLOCKS_PER_SEC;

/* Temps du naif 2 */
now = clock();
naif2(t, n, &min, &max);
t2 += (double) (clock() - now) / CLOCKS_PER_SEC;

/* Temps du non naif */
now = clock();
non_naif(t, n, &min, &max);
t3 += (double) (clock() - now) / CLOCKS_PER_SEC;

/* Temps du non naif 2 */
now = clock();
non_naif2(t, n, &min, &max);
t4 += (double) (clock() - now) / CLOCKS_PER_SEC;
}

free(t);

printf("naif : %f s (%f)n", t1, t1/nb);
printf("naif 2 : %f s (%f)n", t2, t2/nb);
printf("non naif : %f s (%f)n", t3, t3/nb);
printf("non naif 2 : %f s (%f)n", t4, t4/nb);

}
}

int main(void)
{
/* je suppose n pair pour simplifier le code de non_naif() */
test(1 << 26);
return 0;
}

/* ==================== fin min_max_fclc.c ===================== */

--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...

Le Sat, 24 Oct 2009 19:28:19 +0200
candide a écrit

zwim a écrit :

Tandis que naif2 détruit l'optim de registre et est donc plus lent, et
que non_naif détruit le bénéfice du loop unrolling en le remplaçant
par 2 branches de code.

C'est plus contrasté chez moi (gcc sous Ubuntu avec n=1 << 26) :

-- sans option d'optimisation, ton code "non naïf" est plus rapide que
mon code naïf et mon code non naïf ;

-- avec option d'optimisation (O3), ton code "non naïf" est plus lent
que mon code naïf et mon code non naïf.

Bah, j'ai recompilé en -O3 avec gcc et fait la moyenne sur une
vingtaine d'exécutions, la conclusion est inchangée :

naif : 4.846000 s (0.242300)
naif 2 : 8.763000 s (0.438150)
non naif : 8.550000 s (0.427500)
non naif 2 : 4.483000 s (0.224150)

Peux-tu tester avec cette instrumentation du code ?

/* ==================== debut min_max_fclc.c ==================== */

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

void naif(int t[], int n, int *min, int *max)
{
int i;

int mini = t[0], maxi = t[0];

for (i = 0; i < n; i++)
{
if (t[i] < mini)
mini = t[i];
if (t[i] > maxi)
maxi = t[i];
}
*min = mini;
*max = maxi;
}

void naif2(int t[], int n, int *min, int *max)
{
int i;

int mini = t[0], maxi = t[0];

for (i = 0; i < n; i++)
{
if (t[i] < mini)
mini = t[i];
}
for (i = 0; i < n; i++)
{
if (t[i] > maxi)
maxi = t[i];
}
*min = mini;
*max = maxi;
}

void non_naif(int *t, int n, int *min, int *max)
{
int mini = t[0], maxi = t[1];
int k = 0;

for (k = 0; k < n - 1; k += 2)
{
if (t[k] < t[k + 1])
{
if (t[k] < mini)
mini = t[k];
if (t[k + 1] > maxi)
maxi = t[k + 1];
}
else
{
if (t[k + 1] < mini)
mini = t[k + 1];
if (t[k] > maxi)
maxi = t[k];
}
}

*min = mini;
*max = maxi;
}

void non_naif2(int *t, int n, int *min, int *max)
{
int mini = t[0], maxi = t[1];
int k = 0;

for (k = 0; k < n - 1; k += 2)
{
if (t[k] < mini)
mini = t[k];
if (t[k + 1] < mini)
mini = t[k + 1];
if (t[k + 1] > maxi)
maxi = t[k + 1];
if (t[k] > maxi)
maxi = t[k];
}

*min = mini;
*max = maxi;
}

void test(int n)
{
int i;
int *t = malloc(n * sizeof *t);
int min, max;
clock_t now;
double t1,t2,t3,t4;
int nb;

if (t != NULL)
{
t1 = 0.0;
t2 = 0.0;
t3 = 0.0;
t4 = 0.0;

for(nb=0; nb<20; nb++)
{

printf("nb = %dn", nb);

/* Génération d'un tableau aléatoire */
srand(time(NULL));
for (i = 0; i < n; i++)
t[i] = rand();

/* Temps du naif */
now = clock();
naif(t, n, &min, &max);
t1 += (double) (clock() - now) / CLOCKS_PER_SEC;

/* Temps du naif 2 */
now = clock();
naif2(t, n, &min, &max);
t2 += (double) (clock() - now) / CLOCKS_PER_SEC;

/* Temps du non naif */
now = clock();
non_naif(t, n, &min, &max);
t3 += (double) (clock() - now) / CLOCKS_PER_SEC;

/* Temps du non naif 2 */
now = clock();
non_naif2(t, n, &min, &max);
t4 += (double) (clock() - now) / CLOCKS_PER_SEC;
}

free(t);

printf("naif : %f s (%f)n", t1, t1/nb);
printf("naif 2 : %f s (%f)n", t2, t2/nb);
printf("non naif : %f s (%f)n", t3, t3/nb);
printf("non naif 2 : %f s (%f)n", t4, t4/nb);

}
}

int main(void)
{
/* je suppose n pair pour simplifier le code de non_naif() */
test(1 << 26);
return 0;
}

/* ==================== fin min_max_fclc.c ===================== */

--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...

Vous avez filtré cet utilisateur ! Consultez son message

Le Sat, 24 Oct 2009 19:28:19 +0200
candide a écrit

zwim a écrit :

Tandis que naif2 détruit l'optim de registre et est donc plus lent, et
que non_naif détruit le bénéfice du loop unrolling en le remplaçant
par 2 branches de code.

C'est plus contrasté chez moi (gcc sous Ubuntu avec n=1 << 26) :

-- sans option d'optimisation, ton code "non naïf" est plus rapide que
mon code naïf et mon code non naïf ;

-- avec option d'optimisation (O3), ton code "non naïf" est plus lent
que mon code naïf et mon code non naïf.

Bah, j'ai recompilé en -O3 avec gcc et fait la moyenne sur une
vingtaine d'exécutions, la conclusion est inchangée :

naif : 4.846000 s (0.242300)
naif 2 : 8.763000 s (0.438150)
non naif : 8.550000 s (0.427500)
non naif 2 : 4.483000 s (0.224150)

Peux-tu tester avec cette instrumentation du code ?

/* ==================== debut min_max_fclc.c ==================== */

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

void naif(int t[], int n, int *min, int *max)
{
int i;

int mini = t[0], maxi = t[0];

for (i = 0; i < n; i++)
{
if (t[i] < mini)
mini = t[i];
if (t[i] > maxi)
maxi = t[i];
}
*min = mini;
*max = maxi;
}

void naif2(int t[], int n, int *min, int *max)
{
int i;

int mini = t[0], maxi = t[0];

for (i = 0; i < n; i++)
{
if (t[i] < mini)
mini = t[i];
}
for (i = 0; i < n; i++)
{
if (t[i] > maxi)
maxi = t[i];
}
*min = mini;
*max = maxi;
}

void non_naif(int *t, int n, int *min, int *max)
{
int mini = t[0], maxi = t[1];
int k = 0;

for (k = 0; k < n - 1; k += 2)
{
if (t[k] < t[k + 1])
{
if (t[k] < mini)
mini = t[k];
if (t[k + 1] > maxi)
maxi = t[k + 1];
}
else
{
if (t[k + 1] < mini)
mini = t[k + 1];
if (t[k] > maxi)
maxi = t[k];
}
}

*min = mini;
*max = maxi;
}

void non_naif2(int *t, int n, int *min, int *max)
{
int mini = t[0], maxi = t[1];
int k = 0;

for (k = 0; k < n - 1; k += 2)
{
if (t[k] < mini)
mini = t[k];
if (t[k + 1] < mini)
mini = t[k + 1];
if (t[k + 1] > maxi)
maxi = t[k + 1];
if (t[k] > maxi)
maxi = t[k];
}

*min = mini;
*max = maxi;
}

void test(int n)
{
int i;
int *t = malloc(n * sizeof *t);
int min, max;
clock_t now;
double t1,t2,t3,t4;
int nb;

if (t != NULL)
{
t1 = 0.0;
t2 = 0.0;
t3 = 0.0;
t4 = 0.0;

for(nb=0; nb<20; nb++)
{

printf("nb = %dn", nb);

/* Génération d'un tableau aléatoire */
srand(time(NULL));
for (i = 0; i < n; i++)
t[i] = rand();

/* Temps du naif */
now = clock();
naif(t, n, &min, &max);
t1 += (double) (clock() - now) / CLOCKS_PER_SEC;

/* Temps du naif 2 */
now = clock();
naif2(t, n, &min, &max);
t2 += (double) (clock() - now) / CLOCKS_PER_SEC;

/* Temps du non naif */
now = clock();
non_naif(t, n, &min, &max);
t3 += (double) (clock() - now) / CLOCKS_PER_SEC;

/* Temps du non naif 2 */
now = clock();
non_naif2(t, n, &min, &max);
t4 += (double) (clock() - now) / CLOCKS_PER_SEC;
}

free(t);

printf("naif : %f s (%f)n", t1, t1/nb);
printf("naif 2 : %f s (%f)n", t2, t2/nb);
printf("non naif : %f s (%f)n", t3, t3/nb);
printf("non naif 2 : %f s (%f)n", t4, t4/nb);

}
}

int main(void)
{
/* je suppose n pair pour simplifier le code de non_naif() */
test(1 << 26);
return 0;
}

/* ==================== fin min_max_fclc.c ===================== */

--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...

Samuel Devulder

24/10/2009 à 22:03

candide a écrit :

Bonjour

J'ai codé selon deux algorithmes (le naïf et le "non naïf") un problème
classique (expliqué ci-après) et nécessitant de comparer des entiers. Le
naïf effectue 2*n comparaisons et le non naïf en effectue 25% de moins
(ie 1.5*n comparaisons). Les codes C sont simples et très similaires et
pourtant le naïf est plus rapide sur tous les tests que j'ai faits (et
pas qu'un peu : c'est de l'ordre de 50% plus rapide).

Comparer deux algos linéaires n'a pas forcément de sens. Pour les
complexités on travaille en "grand-O", ce qui veut dire qu'on ne se
préoccupe pas spécialement des constantes devant les complexités des
algos. Du coup les deux approches naïve/non-naïce sont strictement
équivalentes du point de vue de leur classe de complexité (linéaire en
la taille des entrées). Après la constante devant les algos dépends de
pleins de params que l'algorithmique ne prétend pas prendre en compte
(optimisations du compilo, possibilité du processeur, etc).

Ainsi, tes deux algos implémentés dans un autre langage ou sur un autre
CPU et/ou avec un autre compilo pourraient avoir un classement différent
l'un par rapport à l'autre.. En revanche quel que soit le langage, le
cpu, le compilo.. quoi qu'on fasse ils resterons linéaires: si tu
doubles le nombre de données à traiter, les deux algos prendront environ
le double de temps.

Bon en plus là tu prends comme critère de perfs le nombre de
comparaisons. Or sur des types simples accessible directement au niveau
CPU (integer, double) cela n'a pas grand sens car le vrai goulet
d'étranglement d'un code n'est pas la comparaison, mais le nombre
d'accès à la mémoire ou de sauts dans le code (à cause de la gestion du
pipeline du CPU). C'est d'ailleurs ce qui doit jouer dans ton
expérimentation car à vue de nez, l'algo "non naif" fait beaucoup de
tests et d'accès mémoire.

Pour optimiser la constante "devant" tes algos, il vaut mieux passer à
l'ASM directement. Ou utiliser un codage C réputé plus performant pour
le code ASM produit (jetter un oeil sur:
http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax).

Nota: c'est de moins en moins "bien vu" de savoir coder des trucs comme
ca de nos jour car finalement ils peuvent être plus lents que ce que le
compilo saurait faire avec un algo propre et simple.

De toute façon les comparaisons de complexité algorithmique ne sont
valable que du point de vue asymptotique, et il est parfois difficile de
savoir à partir de quelle taille d'entrée on est dans le cas
"asymptotique". Par exemple j'ai pas mal travaillé dans le passé dans ce
qu'on appelle la programmation linéaire (c'est plus ou moins de
l'optimisation sous contraintes). Dans ce domaine il existe des
algorithmes prouvés polynomiaux (les méthodes par points intérieures),
et des algos exponentiels (le simplexe).. Or il se trouve en pratique
que les algo polynomiaux sont tellement lourds que pour des tailles de
problèmes que l'on pourrait croire "pas loin de l'infini", ils sont
finalement plus lents que les algo exponentiels.

sam.

candide a écrit :

Bonjour

J'ai codé selon deux algorithmes (le naïf et le "non naïf") un problème
classique (expliqué ci-après) et nécessitant de comparer des entiers. Le
naïf effectue 2*n comparaisons et le non naïf en effectue 25% de moins
(ie 1.5*n comparaisons). Les codes C sont simples et très similaires et
pourtant le naïf est plus rapide sur tous les tests que j'ai faits (et
pas qu'un peu : c'est de l'ordre de 50% plus rapide).

Comparer deux algos linéaires n'a pas forcément de sens. Pour les
complexités on travaille en "grand-O", ce qui veut dire qu'on ne se
préoccupe pas spécialement des constantes devant les complexités des
algos. Du coup les deux approches naïve/non-naïce sont strictement
équivalentes du point de vue de leur classe de complexité (linéaire en
la taille des entrées). Après la constante devant les algos dépends de
pleins de params que l'algorithmique ne prétend pas prendre en compte
(optimisations du compilo, possibilité du processeur, etc).

Ainsi, tes deux algos implémentés dans un autre langage ou sur un autre
CPU et/ou avec un autre compilo pourraient avoir un classement différent
l'un par rapport à l'autre.. En revanche quel que soit le langage, le
cpu, le compilo.. quoi qu'on fasse ils resterons linéaires: si tu
doubles le nombre de données à traiter, les deux algos prendront environ
le double de temps.

Bon en plus là tu prends comme critère de perfs le nombre de
comparaisons. Or sur des types simples accessible directement au niveau
CPU (integer, double) cela n'a pas grand sens car le vrai goulet
d'étranglement d'un code n'est pas la comparaison, mais le nombre
d'accès à la mémoire ou de sauts dans le code (à cause de la gestion du
pipeline du CPU). C'est d'ailleurs ce qui doit jouer dans ton
expérimentation car à vue de nez, l'algo "non naif" fait beaucoup de
tests et d'accès mémoire.

Pour optimiser la constante "devant" tes algos, il vaut mieux passer à
l'ASM directement. Ou utiliser un codage C réputé plus performant pour
le code ASM produit (jetter un oeil sur:
http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax).

Nota: c'est de moins en moins "bien vu" de savoir coder des trucs comme
ca de nos jour car finalement ils peuvent être plus lents que ce que le
compilo saurait faire avec un algo propre et simple.

De toute façon les comparaisons de complexité algorithmique ne sont
valable que du point de vue asymptotique, et il est parfois difficile de
savoir à partir de quelle taille d'entrée on est dans le cas
"asymptotique". Par exemple j'ai pas mal travaillé dans le passé dans ce
qu'on appelle la programmation linéaire (c'est plus ou moins de
l'optimisation sous contraintes). Dans ce domaine il existe des
algorithmes prouvés polynomiaux (les méthodes par points intérieures),
et des algos exponentiels (le simplexe).. Or il se trouve en pratique
que les algo polynomiaux sont tellement lourds que pour des tailles de
problèmes que l'on pourrait croire "pas loin de l'infini", ils sont
finalement plus lents que les algo exponentiels.

sam.

Vous avez filtré cet utilisateur ! Consultez son message

candide a écrit :

Bonjour

J'ai codé selon deux algorithmes (le naïf et le "non naïf") un problème
classique (expliqué ci-après) et nécessitant de comparer des entiers. Le
naïf effectue 2*n comparaisons et le non naïf en effectue 25% de moins
(ie 1.5*n comparaisons). Les codes C sont simples et très similaires et
pourtant le naïf est plus rapide sur tous les tests que j'ai faits (et
pas qu'un peu : c'est de l'ordre de 50% plus rapide).

Comparer deux algos linéaires n'a pas forcément de sens. Pour les
complexités on travaille en "grand-O", ce qui veut dire qu'on ne se
préoccupe pas spécialement des constantes devant les complexités des
algos. Du coup les deux approches naïve/non-naïce sont strictement
équivalentes du point de vue de leur classe de complexité (linéaire en
la taille des entrées). Après la constante devant les algos dépends de
pleins de params que l'algorithmique ne prétend pas prendre en compte
(optimisations du compilo, possibilité du processeur, etc).

Ainsi, tes deux algos implémentés dans un autre langage ou sur un autre
CPU et/ou avec un autre compilo pourraient avoir un classement différent
l'un par rapport à l'autre.. En revanche quel que soit le langage, le
cpu, le compilo.. quoi qu'on fasse ils resterons linéaires: si tu
doubles le nombre de données à traiter, les deux algos prendront environ
le double de temps.

Bon en plus là tu prends comme critère de perfs le nombre de
comparaisons. Or sur des types simples accessible directement au niveau
CPU (integer, double) cela n'a pas grand sens car le vrai goulet
d'étranglement d'un code n'est pas la comparaison, mais le nombre
d'accès à la mémoire ou de sauts dans le code (à cause de la gestion du
pipeline du CPU). C'est d'ailleurs ce qui doit jouer dans ton
expérimentation car à vue de nez, l'algo "non naif" fait beaucoup de
tests et d'accès mémoire.

Pour optimiser la constante "devant" tes algos, il vaut mieux passer à
l'ASM directement. Ou utiliser un codage C réputé plus performant pour
le code ASM produit (jetter un oeil sur:
http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax).

Nota: c'est de moins en moins "bien vu" de savoir coder des trucs comme
ca de nos jour car finalement ils peuvent être plus lents que ce que le
compilo saurait faire avec un algo propre et simple.

De toute façon les comparaisons de complexité algorithmique ne sont
valable que du point de vue asymptotique, et il est parfois difficile de
savoir à partir de quelle taille d'entrée on est dans le cas
"asymptotique". Par exemple j'ai pas mal travaillé dans le passé dans ce
qu'on appelle la programmation linéaire (c'est plus ou moins de
l'optimisation sous contraintes). Dans ce domaine il existe des
algorithmes prouvés polynomiaux (les méthodes par points intérieures),
et des algos exponentiels (le simplexe).. Or il se trouve en pratique
que les algo polynomiaux sont tellement lourds que pour des tailles de
problèmes que l'on pourrait croire "pas loin de l'infini", ils sont
finalement plus lents que les algo exponentiels.

sam.

Éric Lévénez

24/10/2009 à 22:51

zwim a écrit :

Bah, j'ai recompilé en -O3 avec gcc et fait la moyenne sur une
vingtaine d'exécutions, la conclusion est inchangée :

naif : 4.846000 s (0.242300)
naif 2 : 8.763000 s (0.438150)
non naif : 8.550000 s (0.427500)
non naif 2 : 4.483000 s (0.224150)

Peux-tu tester avec cette instrumentation du code ?

naif : 0.000142 s (0.000007)
naif 2 : 0.000011 s (0.000001)
non naif : 0.000015 s (0.000001)
non naif 2 : 0.000014 s (0.000001)

naif : 0.000113 s (0.000006)
naif 2 : 0.000013 s (0.000001)
non naif : 0.000012 s (0.000001)
non naif 2 : 0.000009 s (0.000000)

Les temps de calculs étant trop courts, les résultats sont très
variables d'un essai à l'autre.

Pour un algo de ce type, il faudrait peut-être regarder du côté du
multithreading, car optimiser actuellement sur du monothread, c'est
quand même allez à l'encontre des CPU actuels et futurs, non ? :-)

--
Éric Lévénez
FAQ de fclc : <http://www.levenez.com/lang/c/faq/>

candide

24/10/2009 à 23:04

zwim a écrit :

Bah, j'ai recompilé en -O3 avec gcc et fait la moyenne sur une
vingtaine d'exécutions, la conclusion est inchangée :

naif : 4.846000 s (0.242300)
naif 2 : 8.763000 s (0.438150)
non naif : 8.550000 s (0.427500)
non naif 2 : 4.483000 s (0.224150)

Peux-tu tester avec cette instrumentation du code ?

Grosse surprise en exécutant ton code compilé avec -O3, il m'affiche ceci :

nb = 0
nb = 1
nb = 2
nb = 3
nb = 4
nb = 5
nb = 6
nb = 7
nb = 8
nb = 9
nb = 10
nb = 11
nb = 12
nb = 13
nb = 14
nb = 15
nb = 16
nb = 17
nb = 18
nb = 19
naif : 0.000000 s (0.000000)
naif 2 : 0.000000 s (0.000000)
non naif : 0.000000 s (0.000000)
non naif 2 : 0.000000 s (0.000000)

Je mets une heure à comprendre : carrément -O3 me shunte l'exécution des
fonctions, par contre si je fais précéder le calcul de t1 par exemple
par un

printf("min=%d, max=%dn", min, max);

il entreprend l'exécution de naif().

Par contre, avec -O2, je n'ai pas ce problème et les résultats vont dans
le sens que j'avais indiqué :

nb = 0
nb = 1
nb = 2
nb = 3
nb = 4
nb = 5
nb = 6
nb = 7
nb = 8
nb = 9
nb = 10
nb = 11
nb = 12
nb = 13
nb = 14
nb = 15
nb = 16
nb = 17
nb = 18
nb = 19
naif : 6.270000 s (0.313500)
naif 2 : 11.700000 s (0.585000)
non naif : 8.850000 s (0.442500)
non naif 2 : 10.050000 s (0.502500)

Et, comme indiqué lors de mon premier essai, si je compile sans option
d'optimisation j'obtiens des résultats inverses :

naif : 10.760000 s (0.538000)
naif 2 : 14.850000 s (0.742500)
non naif : 15.390000 s (0.769500)
non naif 2 : 8.980000 s (0.449000)

Ma machine :

Intel Pentium 4, 1600 MHz,
512 Mo (SDRAM)

candide

24/10/2009 à 23:04

Éric Lévénez a écrit :

zwim a écrit :

Bah, j'ai recompilé en -O3 avec gcc et fait la moyenne sur une
vingtaine d'exécutions, la conclusion est inchangée :

naif : 4.846000 s (0.242300)
naif 2 : 8.763000 s (0.438150)
non naif : 8.550000 s (0.427500)
non naif 2 : 4.483000 s (0.224150)

Peux-tu tester avec cette instrumentation du code ?

naif : 0.000142 s (0.000007)
naif 2 : 0.000011 s (0.000001)
non naif : 0.000015 s (0.000001)
non naif 2 : 0.000014 s (0.000001)

naif : 0.000113 s (0.000006)
naif 2 : 0.000013 s (0.000001)
non naif : 0.000012 s (0.000001)
non naif 2 : 0.000009 s (0.000000)

Ta machine a un processeur quantique ;) ?

candide

24/10/2009 à 23:41

Samuel Devulder a écrit :

Comparer deux algos linéaires n'a pas forcément de sens. Pour les
complexités on travaille en "grand-O", ce qui veut dire qu'on ne se
préoccupe pas spécialement des constantes devant les complexités des
algos. Du coup les deux approches naïve/non-naïce sont strictement
équivalentes du point de vue de leur classe de complexité (linéaire en
la taille des entrées). Après la constante devant les algos dépends de
pleins de params que l'algorithmique ne prétend pas prendre en compte
(optimisations du compilo, possibilité du processeur, etc).

Oui, on est bien d'accord, il s'agit de deux algorithmes en theta(n).
Mais les deux codes C sont très très proches, le code non naïf contient
juste une alternative de plus. Dans la pratique, nous avons tous
expérimenté que telle ou telle micro-optimisation de l'algorithme ou du
code C devait intuitivement conduire à une réduction du temps
d'exécution et c'est ce qui se produit le plus souvent. Comme n est très
grand, je pense que le résultat obtenu par le code que j'ai proposé
n'est pas du tout intuitif, en tous cas pour celui qui ne se mêle pas
d'architecture, d'ailleurs il suffit de voir les résultats très
contrastés que l'on obtient en fonction de la présence ou non d'option
de compilation.

Bon en plus là tu prends comme critère de perfs le nombre de
comparaisons. Or sur des types simples accessible directement au niveau
CPU (integer, double) cela n'a pas grand sens car le vrai goulet
d'étranglement d'un code n'est pas la comparaison, mais le nombre
d'accès à la mémoire ou de sauts dans le code (à cause de la gestion du
pipeline du CPU).

Non, tu n'as qu'à faire des tests sur divers algorithmes de tris (par
comparaisons) et tu verras qu'il y a une corrélation directe entre le
nombre de comparaisons effectuées et le temps d'exécution.

C'est d'ailleurs ce qui doit jouer dans ton
expérimentation car à vue de nez, l'algo "non naif" fait beaucoup de
tests et d'accès mémoire.

Non, il ne fait pas plus de tests if, il en fait même moins : le premier
algo fait 2*n tests if tandis que le second en fait (n/2)*2=n.
D'ailleurs, j'ai même fait un essai du 2ème code où je supprimais tous
les "if ... then" et je les transformais en opérations logiques && et ||
et ça n'a rien changé au performances relatives. Quant aux accès
mémoire, il faudrait préciser ce que l'on compte mais, mais au total,
*) le premier en fait 3*n (n fois l'accès à t[i], mini et maxi)
*) le second en fait 2*n (n/2 fois l'accès à t[i], t[i+1], mini et maxi)

L'explication est donc probablement plus compliquée que cette
arithmétique un peu primaire.

Samuel Devulder a écrit :

Comparer deux algos linéaires n'a pas forcément de sens. Pour les
complexités on travaille en "grand-O", ce qui veut dire qu'on ne se
préoccupe pas spécialement des constantes devant les complexités des
algos. Du coup les deux approches naïve/non-naïce sont strictement
équivalentes du point de vue de leur classe de complexité (linéaire en
la taille des entrées). Après la constante devant les algos dépends de
pleins de params que l'algorithmique ne prétend pas prendre en compte
(optimisations du compilo, possibilité du processeur, etc).

Oui, on est bien d'accord, il s'agit de deux algorithmes en theta(n).
Mais les deux codes C sont très très proches, le code non naïf contient
juste une alternative de plus. Dans la pratique, nous avons tous
expérimenté que telle ou telle micro-optimisation de l'algorithme ou du
code C devait intuitivement conduire à une réduction du temps
d'exécution et c'est ce qui se produit le plus souvent. Comme n est très
grand, je pense que le résultat obtenu par le code que j'ai proposé
n'est pas du tout intuitif, en tous cas pour celui qui ne se mêle pas
d'architecture, d'ailleurs il suffit de voir les résultats très
contrastés que l'on obtient en fonction de la présence ou non d'option
de compilation.

Bon en plus là tu prends comme critère de perfs le nombre de
comparaisons. Or sur des types simples accessible directement au niveau
CPU (integer, double) cela n'a pas grand sens car le vrai goulet
d'étranglement d'un code n'est pas la comparaison, mais le nombre
d'accès à la mémoire ou de sauts dans le code (à cause de la gestion du
pipeline du CPU).

Non, tu n'as qu'à faire des tests sur divers algorithmes de tris (par
comparaisons) et tu verras qu'il y a une corrélation directe entre le
nombre de comparaisons effectuées et le temps d'exécution.

C'est d'ailleurs ce qui doit jouer dans ton
expérimentation car à vue de nez, l'algo "non naif" fait beaucoup de
tests et d'accès mémoire.

Non, il ne fait pas plus de tests if, il en fait même moins : le premier
algo fait 2*n tests if tandis que le second en fait (n/2)*2=n.
D'ailleurs, j'ai même fait un essai du 2ème code où je supprimais tous
les "if ... then" et je les transformais en opérations logiques && et ||
et ça n'a rien changé au performances relatives. Quant aux accès
mémoire, il faudrait préciser ce que l'on compte mais, mais au total,
*) le premier en fait 3*n (n fois l'accès à t[i], mini et maxi)
*) le second en fait 2*n (n/2 fois l'accès à t[i], t[i+1], mini et maxi)

L'explication est donc probablement plus compliquée que cette
arithmétique un peu primaire.

Vous avez filtré cet utilisateur ! Consultez son message

Samuel Devulder a écrit :

Comparer deux algos linéaires n'a pas forcément de sens. Pour les
complexités on travaille en "grand-O", ce qui veut dire qu'on ne se
préoccupe pas spécialement des constantes devant les complexités des
algos. Du coup les deux approches naïve/non-naïce sont strictement
équivalentes du point de vue de leur classe de complexité (linéaire en
la taille des entrées). Après la constante devant les algos dépends de
pleins de params que l'algorithmique ne prétend pas prendre en compte
(optimisations du compilo, possibilité du processeur, etc).

Oui, on est bien d'accord, il s'agit de deux algorithmes en theta(n).
Mais les deux codes C sont très très proches, le code non naïf contient
juste une alternative de plus. Dans la pratique, nous avons tous
expérimenté que telle ou telle micro-optimisation de l'algorithme ou du
code C devait intuitivement conduire à une réduction du temps
d'exécution et c'est ce qui se produit le plus souvent. Comme n est très
grand, je pense que le résultat obtenu par le code que j'ai proposé
n'est pas du tout intuitif, en tous cas pour celui qui ne se mêle pas
d'architecture, d'ailleurs il suffit de voir les résultats très
contrastés que l'on obtient en fonction de la présence ou non d'option
de compilation.

Bon en plus là tu prends comme critère de perfs le nombre de
comparaisons. Or sur des types simples accessible directement au niveau
CPU (integer, double) cela n'a pas grand sens car le vrai goulet
d'étranglement d'un code n'est pas la comparaison, mais le nombre
d'accès à la mémoire ou de sauts dans le code (à cause de la gestion du
pipeline du CPU).

Non, tu n'as qu'à faire des tests sur divers algorithmes de tris (par
comparaisons) et tu verras qu'il y a une corrélation directe entre le
nombre de comparaisons effectuées et le temps d'exécution.

C'est d'ailleurs ce qui doit jouer dans ton
expérimentation car à vue de nez, l'algo "non naif" fait beaucoup de
tests et d'accès mémoire.

Non, il ne fait pas plus de tests if, il en fait même moins : le premier
algo fait 2*n tests if tandis que le second en fait (n/2)*2=n.
D'ailleurs, j'ai même fait un essai du 2ème code où je supprimais tous
les "if ... then" et je les transformais en opérations logiques && et ||
et ça n'a rien changé au performances relatives. Quant aux accès
mémoire, il faudrait préciser ce que l'on compte mais, mais au total,
*) le premier en fait 3*n (n fois l'accès à t[i], mini et maxi)
*) le second en fait 2*n (n/2 fois l'accès à t[i], t[i+1], mini et maxi)

L'explication est donc probablement plus compliquée que cette
arithmétique un peu primaire.

Éric Lévénez

24/10/2009 à 23:42

candide a écrit :

Éric Lévénez a écrit :

naif : 0.000142 s (0.000007)
naif 2 : 0.000011 s (0.000001)
non naif : 0.000015 s (0.000001)
non naif 2 : 0.000014 s (0.000001)

naif : 0.000113 s (0.000006)
naif 2 : 0.000013 s (0.000001)
non naif : 0.000012 s (0.000001)
non naif 2 : 0.000009 s (0.000000)

Ta machine a un processeur quantique ;) ?

C'est le -O3 qui donnait cela (optimisation trop abrasive).

Avec -O2, j'ai :

naif : 1.989057 s (0.099453)
naif 2 : 3.584619 s (0.179231)
non naif : 3.322438 s (0.166122)
non naif 2 : 1.837709 s (0.091885)

Et sans optimisation :

naif : 5.227104 s (0.261355)
naif 2 : 7.080845 s (0.354042)
non naif : 6.266246 s (0.313312)
non naif 2 : 4.203295 s (0.210165)

--
Éric Lévénez
FAQ de fclc : <http://www.levenez.com/lang/c/faq/>

Samuel Devulder

25/10/2009 à 02:55

candide a écrit :

En effet j'ai regardé le code ASM et il y a effectivement moins
d'instructions (donc nb de sauts) à executer dans le code non-naïf que
le naïf.. C'est surprenant ce truc.

L'explication est donc probablement plus compliquée que cette
arithmétique un peu primaire.

En regardant le code ASM de près on se rend compte que, contrairement à
ce que je pensais, le compilo ne pénalise pas trop les accès mémoire à
t[k] t[k+1] dans l'algo non-naïf car il arrive à trouver des registres
pour y garder ces valeurs lors des tests internes par rapport à mini et
maxi (qu'il garde aussi dans des registres).

_non_naif:
...
L27:
movl (%edi,%ecx,4), %edx
movl 4(%edi,%ecx,4), %eax
cmpl %eax, %edx
jge L17
cmpl %esi, %edx
jge L18
movl %edx, %esi
L18:
cmpl %ebx, %eax
jle L16
movl %eax, %ebx
L16:
...

Bref du point de vue des accès mémoire, les deux algos sont kif-kif.

Par contre, c'est vachement rigolo ce truc, car cela signifie que
l'autre explication est plus plausible: Les deux algos ne se comportent
pas de la même façon du point de vue du pipeline du CPU.

En fait, l'idée est que les tests
t[k]<t[k+1] (1)
sont infiniment moins prévisibles que
t[k]<mini. (2)
ou
t[k]>maxi (3)

En effet, statistiquement (1) ne reste jamais vrai ou faux trop
longtemps.. Une fois sur 2 on se paye une pénalité au niveau CPU de ce
que le test vient de changer de branche. A l'inverse (2) et (3) sont
beaucoup plus prévisibles. Ils sont quasi tout le temps faux. Du coup
Les pénalité pour saut "non prévus" sont plus rares: on saute quasiment
toujours dans la même branche (celle prévue par les algos de prédiction
de saut). Le pipeline d'instruction n'a pas besoin d'etre flushé et tout
le bazard tourne plein pot.

Si je modifie ton code pour que les valeurs du tableau soient plus
prévisible, par exemple de sorte que t[k]<t[k+1] soit faux tout le temps:

for (i = 0; i < n; i++)
t[i] = -i;

Alors j'obtiens l'exécution suivante (je teste sur 1<<28):

min=-268435455, max=0
Temps CPU naif : 0.44 seconde.

min=-268435455, max=0
Temps CPU non naif : 0.31 seconde.

(ca marche encore si on introduit un peu de bruit dans l'ordre).

A la louche le naïf est à présent 50% plus lent que le non naïf
(0.45secs vs 0.31secs). Ca correspond assez bien aux ratio du nombre de
tests par tour que tu obtiens théoriquement.

Je n'ai pas changé le code, juste les data en entrée pour rendre les
sauts plus prévisibles. Pour bien il faudrait que je fasse tourner le
prog sur un CPU sans prédiction de sauts (rare de nos jours), et là je
pense que c'est encore le non-naïf qui gagne.

Bref: il semblerait que la difference entre théorie et pratique vient du
fait que la prédiction de saut n'a pas été prise en compte dans
l'analyse de l'algo. Le fait que les sauts soient moins prévisible pour
l'un des algos le pénalise fortement par rapport à sont voisin. Je ne
m'attendais pas à une telle conclusion, mais je pense qu'elle s'impose.

CQFD :)

candide a écrit :

En effet j'ai regardé le code ASM et il y a effectivement moins
d'instructions (donc nb de sauts) à executer dans le code non-naïf que
le naïf.. C'est surprenant ce truc.

L'explication est donc probablement plus compliquée que cette
arithmétique un peu primaire.

En regardant le code ASM de près on se rend compte que, contrairement à
ce que je pensais, le compilo ne pénalise pas trop les accès mémoire à
t[k] t[k+1] dans l'algo non-naïf car il arrive à trouver des registres
pour y garder ces valeurs lors des tests internes par rapport à mini et
maxi (qu'il garde aussi dans des registres).

_non_naif:
...
L27:
movl (%edi,%ecx,4), %edx
movl 4(%edi,%ecx,4), %eax
cmpl %eax, %edx
jge L17
cmpl %esi, %edx
jge L18
movl %edx, %esi
L18:
cmpl %ebx, %eax
jle L16
movl %eax, %ebx
L16:
...

Bref du point de vue des accès mémoire, les deux algos sont kif-kif.

Par contre, c'est vachement rigolo ce truc, car cela signifie que
l'autre explication est plus plausible: Les deux algos ne se comportent
pas de la même façon du point de vue du pipeline du CPU.

En fait, l'idée est que les tests
t[k]<t[k+1] (1)
sont infiniment moins prévisibles que
t[k]<mini. (2)
ou
t[k]>maxi (3)

En effet, statistiquement (1) ne reste jamais vrai ou faux trop
longtemps.. Une fois sur 2 on se paye une pénalité au niveau CPU de ce
que le test vient de changer de branche. A l'inverse (2) et (3) sont
beaucoup plus prévisibles. Ils sont quasi tout le temps faux. Du coup
Les pénalité pour saut "non prévus" sont plus rares: on saute quasiment
toujours dans la même branche (celle prévue par les algos de prédiction
de saut). Le pipeline d'instruction n'a pas besoin d'etre flushé et tout
le bazard tourne plein pot.

Si je modifie ton code pour que les valeurs du tableau soient plus
prévisible, par exemple de sorte que t[k]<t[k+1] soit faux tout le temps:

for (i = 0; i < n; i++)
t[i] = -i;

Alors j'obtiens l'exécution suivante (je teste sur 1<<28):

min=-268435455, max=0
Temps CPU naif : 0.44 seconde.

min=-268435455, max=0
Temps CPU non naif : 0.31 seconde.

(ca marche encore si on introduit un peu de bruit dans l'ordre).

A la louche le naïf est à présent 50% plus lent que le non naïf
(0.45secs vs 0.31secs). Ca correspond assez bien aux ratio du nombre de
tests par tour que tu obtiens théoriquement.

Je n'ai pas changé le code, juste les data en entrée pour rendre les
sauts plus prévisibles. Pour bien il faudrait que je fasse tourner le
prog sur un CPU sans prédiction de sauts (rare de nos jours), et là je
pense que c'est encore le non-naïf qui gagne.

Bref: il semblerait que la difference entre théorie et pratique vient du
fait que la prédiction de saut n'a pas été prise en compte dans
l'analyse de l'algo. Le fait que les sauts soient moins prévisible pour
l'un des algos le pénalise fortement par rapport à sont voisin. Je ne
m'attendais pas à une telle conclusion, mais je pense qu'elle s'impose.

CQFD :)

Vous avez filtré cet utilisateur ! Consultez son message

candide a écrit :

En effet j'ai regardé le code ASM et il y a effectivement moins
d'instructions (donc nb de sauts) à executer dans le code non-naïf que
le naïf.. C'est surprenant ce truc.

L'explication est donc probablement plus compliquée que cette
arithmétique un peu primaire.

En regardant le code ASM de près on se rend compte que, contrairement à
ce que je pensais, le compilo ne pénalise pas trop les accès mémoire à
t[k] t[k+1] dans l'algo non-naïf car il arrive à trouver des registres
pour y garder ces valeurs lors des tests internes par rapport à mini et
maxi (qu'il garde aussi dans des registres).

_non_naif:
...
L27:
movl (%edi,%ecx,4), %edx
movl 4(%edi,%ecx,4), %eax
cmpl %eax, %edx
jge L17
cmpl %esi, %edx
jge L18
movl %edx, %esi
L18:
cmpl %ebx, %eax
jle L16
movl %eax, %ebx
L16:
...

Bref du point de vue des accès mémoire, les deux algos sont kif-kif.

Par contre, c'est vachement rigolo ce truc, car cela signifie que
l'autre explication est plus plausible: Les deux algos ne se comportent
pas de la même façon du point de vue du pipeline du CPU.

En fait, l'idée est que les tests
t[k]<t[k+1] (1)
sont infiniment moins prévisibles que
t[k]<mini. (2)
ou
t[k]>maxi (3)

En effet, statistiquement (1) ne reste jamais vrai ou faux trop
longtemps.. Une fois sur 2 on se paye une pénalité au niveau CPU de ce
que le test vient de changer de branche. A l'inverse (2) et (3) sont
beaucoup plus prévisibles. Ils sont quasi tout le temps faux. Du coup
Les pénalité pour saut "non prévus" sont plus rares: on saute quasiment
toujours dans la même branche (celle prévue par les algos de prédiction
de saut). Le pipeline d'instruction n'a pas besoin d'etre flushé et tout
le bazard tourne plein pot.

Si je modifie ton code pour que les valeurs du tableau soient plus
prévisible, par exemple de sorte que t[k]<t[k+1] soit faux tout le temps:

for (i = 0; i < n; i++)
t[i] = -i;

Alors j'obtiens l'exécution suivante (je teste sur 1<<28):

min=-268435455, max=0
Temps CPU naif : 0.44 seconde.

min=-268435455, max=0
Temps CPU non naif : 0.31 seconde.

(ca marche encore si on introduit un peu de bruit dans l'ordre).

A la louche le naïf est à présent 50% plus lent que le non naïf
(0.45secs vs 0.31secs). Ca correspond assez bien aux ratio du nombre de
tests par tour que tu obtiens théoriquement.

Je n'ai pas changé le code, juste les data en entrée pour rendre les
sauts plus prévisibles. Pour bien il faudrait que je fasse tourner le
prog sur un CPU sans prédiction de sauts (rare de nos jours), et là je
pense que c'est encore le non-naïf qui gagne.

Bref: il semblerait que la difference entre théorie et pratique vient du
fait que la prédiction de saut n'a pas été prise en compte dans
l'analyse de l'algo. Le fait que les sauts soient moins prévisible pour
l'un des algos le pénalise fortement par rapport à sont voisin. Je ne
m'attendais pas à une telle conclusion, mais je pense qu'elle s'impose.

CQFD :)

Samuel Devulder

25/10/2009 à 22:55

Samuel Devulder a écrit :

Je n'ai pas changé le code, juste les data en entrée pour rendre les
sauts plus prévisibles. Pour bien il faudrait que je fasse tourner le
prog sur un CPU sans prédiction de sauts (rare de nos jours), et là je
pense que c'est encore le non-naïf qui gagne.

Pour info, j'ai fait tourner le prog sur un vieux pentium de 1999 (peut
être 98. je sais plus tellement) donc avec très peu de cache et aucun
système de prédiction de branchement.

Voici les résultats bruts:

C:>a.exe
min'25, max!47449793
Temps CPU naif : 517.00 seconde.

min'25, max!47449793
Temps CPU non naif : 595.00 seconde.

on voit les deux algos prennent pratiquement le même temps sur ce type
de machines.

En fait ce qu'il se passe sur ce CPU est que la ram est super lente. Les
accès mémoires sont ici le goulet d'étranglement et dans ce cas, les
deux algos sont équivalents. En effet dans l'un comme dans l'autre le
code ASM montre que chaque élément du tableau n'est accédé qu'une fois
et une fois seulement.

Par ailleurs le non-naïf est pénalisé car il y a un accès de plus dans
la pile pour comparer l'indice courant avec la taille du tableau. On
peut sans doute s'abstraire de cet accès mémoire en indexant le tableau
vers le bas:

for (k = n; (k-=2)>0; ) ...

Car ainsi on compare à la constante 0 plutôt qu'à une variable sur la pile.

Bon.. finalement les expérimentations montrent que:

1. Sur les vieux CPU (ou les CPU "low-cost" embarqués), ce sont les
accès mémoires qui sont pénalisant. Le meilleur algo est celui qui
accède le moins souvent en ram. Pour le calcul du min/max aucun n'est
finalement mieux que l'autre.

2. Sur les CPU modernes avec pipelines monstrueux et prédiction de
sauts, c'est plutôt l'aspect "peu-prédictible" des sauts qui sont
pénalisant. Dans ce cas si les data sont déjà plutôt organisées de sorte
que le test t[k]<t[k+1] ait une valeur exceptionnellement variable,
l'algo non-naïf est le meilleur. A l'inverse, si on ne sait rien sur
l'ordre des data, l'algo naïf est meilleur.

Pfew.. a ce niveau d'intrication avec l'architecture CPU mieux vaut
abandonner le C et faire de l'ASM.. on aura meilleur contrôle de
l'implémentation de l'algo et des goulets d'étranglement de
l'architecture matérielle. Mais c'était marrant à évaluer. :)

sam.

Samuel Devulder a écrit :

Je n'ai pas changé le code, juste les data en entrée pour rendre les
sauts plus prévisibles. Pour bien il faudrait que je fasse tourner le
prog sur un CPU sans prédiction de sauts (rare de nos jours), et là je
pense que c'est encore le non-naïf qui gagne.

Pour info, j'ai fait tourner le prog sur un vieux pentium de 1999 (peut
être 98. je sais plus tellement) donc avec très peu de cache et aucun
système de prédiction de branchement.

Voici les résultats bruts:

C:>a.exe
min'25, max!47449793
Temps CPU naif : 517.00 seconde.

min'25, max!47449793
Temps CPU non naif : 595.00 seconde.

on voit les deux algos prennent pratiquement le même temps sur ce type
de machines.

En fait ce qu'il se passe sur ce CPU est que la ram est super lente. Les
accès mémoires sont ici le goulet d'étranglement et dans ce cas, les
deux algos sont équivalents. En effet dans l'un comme dans l'autre le
code ASM montre que chaque élément du tableau n'est accédé qu'une fois
et une fois seulement.

Par ailleurs le non-naïf est pénalisé car il y a un accès de plus dans
la pile pour comparer l'indice courant avec la taille du tableau. On
peut sans doute s'abstraire de cet accès mémoire en indexant le tableau
vers le bas:

for (k = n; (k-=2)>0; ) ...

Car ainsi on compare à la constante 0 plutôt qu'à une variable sur la pile.

Bon.. finalement les expérimentations montrent que:

1. Sur les vieux CPU (ou les CPU "low-cost" embarqués), ce sont les
accès mémoires qui sont pénalisant. Le meilleur algo est celui qui
accède le moins souvent en ram. Pour le calcul du min/max aucun n'est
finalement mieux que l'autre.

2. Sur les CPU modernes avec pipelines monstrueux et prédiction de
sauts, c'est plutôt l'aspect "peu-prédictible" des sauts qui sont
pénalisant. Dans ce cas si les data sont déjà plutôt organisées de sorte
que le test t[k]<t[k+1] ait une valeur exceptionnellement variable,
l'algo non-naïf est le meilleur. A l'inverse, si on ne sait rien sur
l'ordre des data, l'algo naïf est meilleur.

Pfew.. a ce niveau d'intrication avec l'architecture CPU mieux vaut
abandonner le C et faire de l'ASM.. on aura meilleur contrôle de
l'implémentation de l'algo et des goulets d'étranglement de
l'architecture matérielle. Mais c'était marrant à évaluer. :)

sam.

Vous avez filtré cet utilisateur ! Consultez son message

Samuel Devulder a écrit :

Je n'ai pas changé le code, juste les data en entrée pour rendre les
sauts plus prévisibles. Pour bien il faudrait que je fasse tourner le
prog sur un CPU sans prédiction de sauts (rare de nos jours), et là je
pense que c'est encore le non-naïf qui gagne.

Pour info, j'ai fait tourner le prog sur un vieux pentium de 1999 (peut
être 98. je sais plus tellement) donc avec très peu de cache et aucun
système de prédiction de branchement.

Voici les résultats bruts:

C:>a.exe
min'25, max!47449793
Temps CPU naif : 517.00 seconde.

min'25, max!47449793
Temps CPU non naif : 595.00 seconde.

on voit les deux algos prennent pratiquement le même temps sur ce type
de machines.

En fait ce qu'il se passe sur ce CPU est que la ram est super lente. Les
accès mémoires sont ici le goulet d'étranglement et dans ce cas, les
deux algos sont équivalents. En effet dans l'un comme dans l'autre le
code ASM montre que chaque élément du tableau n'est accédé qu'une fois
et une fois seulement.

Par ailleurs le non-naïf est pénalisé car il y a un accès de plus dans
la pile pour comparer l'indice courant avec la taille du tableau. On
peut sans doute s'abstraire de cet accès mémoire en indexant le tableau
vers le bas:

for (k = n; (k-=2)>0; ) ...

Car ainsi on compare à la constante 0 plutôt qu'à une variable sur la pile.

Bon.. finalement les expérimentations montrent que:

1. Sur les vieux CPU (ou les CPU "low-cost" embarqués), ce sont les
accès mémoires qui sont pénalisant. Le meilleur algo est celui qui
accède le moins souvent en ram. Pour le calcul du min/max aucun n'est
finalement mieux que l'autre.

2. Sur les CPU modernes avec pipelines monstrueux et prédiction de
sauts, c'est plutôt l'aspect "peu-prédictible" des sauts qui sont
pénalisant. Dans ce cas si les data sont déjà plutôt organisées de sorte
que le test t[k]<t[k+1] ait une valeur exceptionnellement variable,
l'algo non-naïf est le meilleur. A l'inverse, si on ne sait rien sur
l'ordre des data, l'algo naïf est meilleur.

Pfew.. a ce niveau d'intrication avec l'architecture CPU mieux vaut
abandonner le C et faire de l'ASM.. on aura meilleur contrôle de
l'implémentation de l'algo et des goulets d'étranglement de
l'architecture matérielle. Mais c'était marrant à évaluer. :)

sam.

candide

26/10/2009 à 16:04

Samuel Devulder a écrit :

Pfew.. a ce niveau d'intrication avec l'architecture CPU mieux vaut
abandonner le C et faire de l'ASM.. on aura meilleur contrôle de
l'implémentation de l'algo et des goulets d'étranglement de
l'architecture matérielle. Mais c'était marrant à évaluer. :)

Merci de ces expérimentations. Pour ce qui est de l'assembleur x86 (ou
autre), le problème que nous avons rencontré ne suffira pas à me faire
lancer dans son apprentissage ;)

Temps d'execution : theorie et pratique

10 réponses

Veuillez sélectionner un problème