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).
Le problème dont je parlais est le suivant : on a un tableau t de n
entiers et on veut retourner _à la fois_ le minimum et le maximum de t.
*) la méthode naïve consiste à parcourir t et
1) à comparer le minimum courant m de t à l'élément courant t[i] à
mettre à jour m si besoin
1) à comparer le maximum courant M de t à l'élément courant t[i] à
mettre à jour M si besoin
Cela fait 2 comparaisons d'entiers faites n fois donc 2*n comparaisons.
Cela fait aussi 2*n affectations au pire (en fait, n au pire).
*) la méthode astucieuse consiste à regrouper les éléments de t par
paires de deux éléments successifs, disons t[2*i] et t[2*i+1] puis
1) à comparer t[2*i] et t[2*i+1] ce qui permet de déterminer le plus
petit (mini) et le plus grand (maxi) des deux ;
2) à comparer le minimum courant m de t à mini et à mettre à jour m s'il
est "amélioré" ;
3) à comparer le maximum courant M de t à maxi et à mettre à jour M
s'il est "amélioré".
Cela fait 3 comparaisons faites n/2 fois donc 1.5*n comparaisons. Cela
fait aussi 2*n/2=n affectations au pire.
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 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 test(int n)
{
int i;
int *t = malloc(n * sizeof *t);
int min, max;
clock_t now;
if (t != NULL)
{
/* 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);
printf("min=%d, max=%d\n", min, max);
printf("Temps CPU naif : %.2lf seconde.\n\n",
(double) (clock() - now) / CLOCKS_PER_SEC);
/* Temps du non naif */
now = clock();
non_naif(t, n, &min, &max);
printf("min=%d, max=%d\n", min, max);
printf("Temps CPU non naif : %.2lf seconde.\n",
int main(void)
{
/* je suppose n pair pour simplifier le code de non_naif() */
test(1 << 26);
return 0;
}
/* ==================== fin min_max_fclc.c ===================== */
Voici la compilation et l'exécution :
$ gcc -O2 -W -Wall -std=c99 -pedantic -o x min_max_fclc.c
$ ./x
min=9, max=2147483640
Temps CPU naif : 0.28 seconde.
min=9, max=2147483640
Temps CPU non naif : 0.44 seconde.
$
Qui pourrait m'expliquer pourquoi le premier code est pas loin de 50%
plus rapide que le second alors que ce dernier effectue 25% de moins de
comparaisons et pas plus d'affectations (et qu'il n'y a rien d'autre
comme opérations, par exemple le nombre d'instructions if est moindre
dans le 2ème algo que dans le premier) ?
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; }
Variables utilisees dans la boucle: i, n, mini, maxi, t[i] -> 5 registres.
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; }
Variables utilisees dans la boucle: k, n, mini, maxi, t[k], t[k+1] (en etant gentil et en supposant que le compilo voit la reduction) -> 6 registres
longueur du code dans la boucle: environ le double.
Ca va dependre de ton processeur, mais soit tu debordes en nombre de registres, soit tu debordes du cache d'instructions.
Le nombre de comparaisons n'est qu'une mesure de ton algo.
Essaie eventuellement:
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;) { int a = t[k++]; int b = t[k++]; if (a < b) { if (a < mini) mini = a; if (b > maxi) maxi = b; } else if (b < mini) mini = a; if (a > maxi) maxi = b; } *min = mini; *max = maxi; }
ou meme: void non_naif3(int *t, int n, int *min, int *max) { int mini = t[0], maxi = t[1]; int k = 0;
for (k = 0; k < n;) { int a = t[k++]; int b = t[k++]; if (a < b) { int c = a; a = b; b =c; } if (b < mini) mini = a; if (a > maxi) maxi = b; } *min = mini; *max = maxi; }
selon l'intelligence de ton compilo, il est possible que l'une de ces variantes donne des resultats meilleurs. ;-)
In article <4ae2d7d2$0$409$426a74cc@news.free.fr>,
candide <candide@free.invalid> wrote:
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;
}
Variables utilisees dans la boucle:
i, n, mini, maxi, t[i]
-> 5 registres.
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;
}
Variables utilisees dans la boucle:
k, n, mini, maxi, t[k], t[k+1] (en etant gentil et en supposant que le compilo
voit la reduction) -> 6 registres
longueur du code dans la boucle: environ le double.
Ca va dependre de ton processeur, mais soit tu debordes en nombre de
registres, soit tu debordes du cache d'instructions.
Le nombre de comparaisons n'est qu'une mesure de ton algo.
Essaie eventuellement:
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;)
{
int a = t[k++];
int b = t[k++];
if (a < b) {
if (a < mini)
mini = a;
if (b > maxi)
maxi = b;
} else
if (b < mini)
mini = a;
if (a > maxi)
maxi = b;
}
*min = mini;
*max = maxi;
}
ou meme:
void non_naif3(int *t, int n, int *min, int *max)
{
int mini = t[0], maxi = t[1];
int k = 0;
for (k = 0; k < n;)
{
int a = t[k++];
int b = t[k++];
if (a < b) {
int c = a;
a = b;
b =c;
}
if (b < mini)
mini = a;
if (a > maxi)
maxi = b;
}
*min = mini;
*max = maxi;
}
selon l'intelligence de ton compilo, il est possible que l'une de ces
variantes donne des resultats meilleurs. ;-)
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; }
Variables utilisees dans la boucle: i, n, mini, maxi, t[i] -> 5 registres.
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; }
Variables utilisees dans la boucle: k, n, mini, maxi, t[k], t[k+1] (en etant gentil et en supposant que le compilo voit la reduction) -> 6 registres
longueur du code dans la boucle: environ le double.
Ca va dependre de ton processeur, mais soit tu debordes en nombre de registres, soit tu debordes du cache d'instructions.
Le nombre de comparaisons n'est qu'une mesure de ton algo.
Essaie eventuellement:
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;) { int a = t[k++]; int b = t[k++]; if (a < b) { if (a < mini) mini = a; if (b > maxi) maxi = b; } else if (b < mini) mini = a; if (a > maxi) maxi = b; } *min = mini; *max = maxi; }
ou meme: void non_naif3(int *t, int n, int *min, int *max) { int mini = t[0], maxi = t[1]; int k = 0;
for (k = 0; k < n;) { int a = t[k++]; int b = t[k++]; if (a < b) { int c = a; a = b; b =c; } if (b < mini) mini = a; if (a > maxi) maxi = b; } *min = mini; *max = maxi; }
selon l'intelligence de ton compilo, il est possible que l'une de ces variantes donne des resultats meilleurs. ;-)
candide
Marc Espie a écrit :
Variables utilisees dans la boucle: k, n, mini, maxi, t[k], t[k+1] (en etant gentil et en supposant que le compilo voit la reduction) -> 6 registres
longueur du code dans la boucle: environ le double.
Ca va dependre de ton processeur, mais soit tu debordes en nombre de registres, soit tu debordes du cache d'instructions.
Le nombre de comparaisons n'est qu'une mesure de ton algo.
OK mais je pensais que c'était prépondérant (avec le nombre d'affectations ici). Je ne pensais pas que la longueur du code ou juste 1 registre d'écart pouvait autant jouer.
Essaie eventuellement:
Ne change pas grand chose chez moi (et c'est même pire sans compter que les valeurs mini et maxi ne correspondent pas avec celles obtenues par mes deux fonctions). J'ai essayé aussi avec Visual C++ Express + optimisations, l'écart est moins flagrant qu'avec gcc mais le naïf l'emporte encore largement.
Marc Espie a écrit :
Variables utilisees dans la boucle:
k, n, mini, maxi, t[k], t[k+1] (en etant gentil et en supposant que le compilo
voit la reduction) -> 6 registres
longueur du code dans la boucle: environ le double.
Ca va dependre de ton processeur, mais soit tu debordes en nombre de
registres, soit tu debordes du cache d'instructions.
Le nombre de comparaisons n'est qu'une mesure de ton algo.
OK mais je pensais que c'était prépondérant (avec le nombre
d'affectations ici). Je ne pensais pas que la longueur du code ou juste
1 registre d'écart pouvait autant jouer.
Essaie eventuellement:
Ne change pas grand chose chez moi (et c'est même pire sans compter que
les valeurs mini et maxi ne correspondent pas avec celles obtenues par
mes deux fonctions). J'ai essayé aussi avec Visual C++ Express +
optimisations, l'écart est moins flagrant qu'avec gcc mais le naïf
l'emporte encore largement.
Variables utilisees dans la boucle: k, n, mini, maxi, t[k], t[k+1] (en etant gentil et en supposant que le compilo voit la reduction) -> 6 registres
longueur du code dans la boucle: environ le double.
Ca va dependre de ton processeur, mais soit tu debordes en nombre de registres, soit tu debordes du cache d'instructions.
Le nombre de comparaisons n'est qu'une mesure de ton algo.
OK mais je pensais que c'était prépondérant (avec le nombre d'affectations ici). Je ne pensais pas que la longueur du code ou juste 1 registre d'écart pouvait autant jouer.
Essaie eventuellement:
Ne change pas grand chose chez moi (et c'est même pire sans compter que les valeurs mini et maxi ne correspondent pas avec celles obtenues par mes deux fonctions). J'ai essayé aussi avec Visual C++ Express + optimisations, l'écart est moins flagrant qu'avec gcc mais le naïf l'emporte encore largement.
Pierre Maurette
candide, le 24/10/2009 a écrit :
[...]
Ne change pas grand chose chez moi (et c'est même pire sans compter que les valeurs mini et maxi ne correspondent pas avec celles obtenues par mes deux fonctions). J'ai essayé aussi avec Visual C++ Express + optimisations, l'écart est moins flagrant qu'avec gcc mais le naïf l'emporte encore largement.
Le rôle d'un bon compilateur est d'optimiser du code naïf, en fait lisible, mais bien écrit.
Je ne sais ce que peut "penser" un bon compilateur de:
if (t[i] < mini) mini = t[i]; if (t[i] > maxi) maxi = t[i];
par rapport à
if (t[i] < mini) mini = t[i]; else if (t[i] > maxi) maxi = t[i];
-- Pierre Maurette
candide, le 24/10/2009 a écrit :
[...]
Ne change pas grand chose chez moi (et c'est même pire sans compter que
les valeurs mini et maxi ne correspondent pas avec celles obtenues par
mes deux fonctions). J'ai essayé aussi avec Visual C++ Express +
optimisations, l'écart est moins flagrant qu'avec gcc mais le naïf
l'emporte encore largement.
Le rôle d'un bon compilateur est d'optimiser du code naïf, en fait
lisible, mais bien écrit.
Je ne sais ce que peut "penser" un bon compilateur de:
if (t[i] < mini)
mini = t[i];
if (t[i] > maxi)
maxi = t[i];
par rapport à
if (t[i] < mini)
mini = t[i];
else if (t[i] > maxi)
maxi = t[i];
Ne change pas grand chose chez moi (et c'est même pire sans compter que les valeurs mini et maxi ne correspondent pas avec celles obtenues par mes deux fonctions). J'ai essayé aussi avec Visual C++ Express + optimisations, l'écart est moins flagrant qu'avec gcc mais le naïf l'emporte encore largement.
Le rôle d'un bon compilateur est d'optimiser du code naïf, en fait lisible, mais bien écrit.
Je ne sais ce que peut "penser" un bon compilateur de:
if (t[i] < mini) mini = t[i]; if (t[i] > maxi) maxi = t[i];
par rapport à
if (t[i] < mini) mini = t[i]; else if (t[i] > maxi) maxi = t[i];
-- Pierre Maurette
espie
In article <4ae307cf$0$20053$, candide wrote:
Marc Espie a écrit :
Variables utilisees dans la boucle: k, n, mini, maxi, t[k], t[k+1] (en etant gentil et en supposant que le compilo voit la reduction) -> 6 registres
longueur du code dans la boucle: environ le double.
Ca va dependre de ton processeur, mais soit tu debordes en nombre de registres, soit tu debordes du cache d'instructions.
Le nombre de comparaisons n'est qu'une mesure de ton algo.
OK mais je pensais que c'était prépondérant (avec le nombre d'affectations ici). Je ne pensais pas que la longueur du code ou juste 1 registre d'écart pouvait autant jouer.
Ah, les mefaits des cours d'algorithmique theoriques...
Non, sur les processeurs recents, ce qui domine, c'est la vitesse d'acces a la memoire, ton proc pedale bien plus vite que ta memoire.
Des que tu sors des registres, ou que tu grimpes d'un niveau de cache, tu le sens passer, et pas qu'un peu...
Evidemment, les ordres de grandeur sont toujours bons: un algo en O(n log n) sera meilleur qu'un O(n^2), a la longue... mais il faut vraiment regarder attentivement ce qui se passe cote acces memoire pour avoir une intuition.
In article <4ae307cf$0$20053$426a74cc@news.free.fr>,
candide <candide@free.invalid> wrote:
Marc Espie a écrit :
Variables utilisees dans la boucle:
k, n, mini, maxi, t[k], t[k+1] (en etant gentil et en supposant que le compilo
voit la reduction) -> 6 registres
longueur du code dans la boucle: environ le double.
Ca va dependre de ton processeur, mais soit tu debordes en nombre de
registres, soit tu debordes du cache d'instructions.
Le nombre de comparaisons n'est qu'une mesure de ton algo.
OK mais je pensais que c'était prépondérant (avec le nombre
d'affectations ici). Je ne pensais pas que la longueur du code ou juste
1 registre d'écart pouvait autant jouer.
Ah, les mefaits des cours d'algorithmique theoriques...
Non, sur les processeurs recents, ce qui domine, c'est la vitesse
d'acces a la memoire, ton proc pedale bien plus vite que ta memoire.
Des que tu sors des registres, ou que tu grimpes d'un niveau de cache,
tu le sens passer, et pas qu'un peu...
Evidemment, les ordres de grandeur sont toujours bons: un algo en O(n log n)
sera meilleur qu'un O(n^2), a la longue... mais il faut vraiment regarder
attentivement ce qui se passe cote acces memoire pour avoir une intuition.
Variables utilisees dans la boucle: k, n, mini, maxi, t[k], t[k+1] (en etant gentil et en supposant que le compilo voit la reduction) -> 6 registres
longueur du code dans la boucle: environ le double.
Ca va dependre de ton processeur, mais soit tu debordes en nombre de registres, soit tu debordes du cache d'instructions.
Le nombre de comparaisons n'est qu'une mesure de ton algo.
OK mais je pensais que c'était prépondérant (avec le nombre d'affectations ici). Je ne pensais pas que la longueur du code ou juste 1 registre d'écart pouvait autant jouer.
Ah, les mefaits des cours d'algorithmique theoriques...
Non, sur les processeurs recents, ce qui domine, c'est la vitesse d'acces a la memoire, ton proc pedale bien plus vite que ta memoire.
Des que tu sors des registres, ou que tu grimpes d'un niveau de cache, tu le sens passer, et pas qu'un peu...
Evidemment, les ordres de grandeur sont toujours bons: un algo en O(n log n) sera meilleur qu'un O(n^2), a la longue... mais il faut vraiment regarder attentivement ce qui se passe cote acces memoire pour avoir une intuition.
espie
In article , Pierre Maurette wrote:
candide, le 24/10/2009 a écrit :
[...]
Ne change pas grand chose chez moi (et c'est même pire sans compter que les valeurs mini et maxi ne correspondent pas avec celles obtenues par mes deux fonctions). J'ai essayé aussi avec Visual C++ Express + optimisations, l'écart est moins flagrant qu'avec gcc mais le naïf l'emporte encore largement.
Le rôle d'un bon compilateur est d'optimiser du code naïf, en fait lisible, mais bien écrit.
Je ne sais ce que peut "penser" un bon compilateur de:
if (t[i] < mini) mini = t[i]; if (t[i] > maxi) maxi = t[i];
par rapport à
if (t[i] < mini) mini = t[i]; else if (t[i] > maxi) maxi = t[i];
Il y a peu de chance ici qu'il transforme le premier en le deuxieme. Il faudrait qu'il sache suffisamment de choses sur les comparaisons d'entiers pour pouvoir affirmer que mini <= maxi.
Si tu ecris ceci:
assert(mini <= maxi); if (t[i] < mini) mini = t[i]; if (t[i] > maxi) maxi = t[i];
ca pourrait eventuellement l'aider (puisque assert fait partie de la bibliotheque standard, et donc que le compilo a le droit de faire de la magie avec, et donc de marquer la branche "mini > maxi" comme non prise, et donc de "voir" la suite.... ;-)
In article <mn.c3ef7d9ac3d6ce4c.79899@wanadoo.fr>,
Pierre Maurette <maurettepierre@wanadoo.fr> wrote:
candide, le 24/10/2009 a écrit :
[...]
Ne change pas grand chose chez moi (et c'est même pire sans compter que
les valeurs mini et maxi ne correspondent pas avec celles obtenues par
mes deux fonctions). J'ai essayé aussi avec Visual C++ Express +
optimisations, l'écart est moins flagrant qu'avec gcc mais le naïf
l'emporte encore largement.
Le rôle d'un bon compilateur est d'optimiser du code naïf, en fait
lisible, mais bien écrit.
Je ne sais ce que peut "penser" un bon compilateur de:
if (t[i] < mini)
mini = t[i];
if (t[i] > maxi)
maxi = t[i];
par rapport à
if (t[i] < mini)
mini = t[i];
else if (t[i] > maxi)
maxi = t[i];
Il y a peu de chance ici qu'il transforme le premier en le deuxieme.
Il faudrait qu'il sache suffisamment de choses sur les comparaisons d'entiers
pour pouvoir affirmer que mini <= maxi.
Si tu ecris ceci:
assert(mini <= maxi);
if (t[i] < mini)
mini = t[i];
if (t[i] > maxi)
maxi = t[i];
ca pourrait eventuellement l'aider (puisque assert fait partie de la
bibliotheque standard, et donc que le compilo a le droit de faire de la
magie avec, et donc de marquer la branche "mini > maxi" comme non prise,
et donc de "voir" la suite.... ;-)
Ne change pas grand chose chez moi (et c'est même pire sans compter que les valeurs mini et maxi ne correspondent pas avec celles obtenues par mes deux fonctions). J'ai essayé aussi avec Visual C++ Express + optimisations, l'écart est moins flagrant qu'avec gcc mais le naïf l'emporte encore largement.
Le rôle d'un bon compilateur est d'optimiser du code naïf, en fait lisible, mais bien écrit.
Je ne sais ce que peut "penser" un bon compilateur de:
if (t[i] < mini) mini = t[i]; if (t[i] > maxi) maxi = t[i];
par rapport à
if (t[i] < mini) mini = t[i]; else if (t[i] > maxi) maxi = t[i];
Il y a peu de chance ici qu'il transforme le premier en le deuxieme. Il faudrait qu'il sache suffisamment de choses sur les comparaisons d'entiers pour pouvoir affirmer que mini <= maxi.
Si tu ecris ceci:
assert(mini <= maxi); if (t[i] < mini) mini = t[i]; if (t[i] > maxi) maxi = t[i];
ca pourrait eventuellement l'aider (puisque assert fait partie de la bibliotheque standard, et donc que le compilo a le droit de faire de la magie avec, et donc de marquer la branche "mini > maxi" comme non prise, et donc de "voir" la suite.... ;-)
Pierre Maurette
Marc Espie, le 24/10/2009 a écrit :
In article , Pierre Maurette wrote:
candide, le 24/10/2009 a écrit :
[...]
Ne change pas grand chose chez moi (et c'est même pire sans compter que les valeurs mini et maxi ne correspondent pas avec celles obtenues par mes deux fonctions). J'ai essayé aussi avec Visual C++ Express + optimisations, l'écart est moins flagrant qu'avec gcc mais le naïf l'emporte encore largement.
Le rôle d'un bon compilateur est d'optimiser du code naïf, en fait lisible, mais bien écrit.
Je ne sais ce que peut "penser" un bon compilateur de:
if (t[i] < mini) mini = t[i]; if (t[i] > maxi) maxi = t[i];
par rapport à
if (t[i] < mini) mini = t[i]; else if (t[i] > maxi) maxi = t[i];
Il y a peu de chance ici qu'il transforme le premier en le deuxieme. Il faudrait qu'il sache suffisamment de choses sur les comparaisons d'entiers pour pouvoir affirmer que mini <= maxi.
Si tu ecris ceci:
assert(mini <= maxi); if (t[i] < mini) mini = t[i]; if (t[i] > maxi) maxi = t[i];
ca pourrait eventuellement l'aider (puisque assert fait partie de la bibliotheque standard, et donc que le compilo a le droit de faire de la magie avec, et donc de marquer la branche "mini > maxi" comme non prise, et donc de "voir" la suite.... ;-)
C'est exactement ce que je voulais exprimer. La base de l'optimisation en LHN, à part de ne pas écrire des trucs trop débiles, c'est précisément de donner au compilateur des connaissances que nous avons et qu'il n'a pas nécessairement. Le double if sans else est un truc /trop débile/. Après, ça se complique. Comment en LHN faire passer l'information que tel ou tel test sera /le plus souvent/ positif [ou négatif] ? "register" ? Faut parvenir également en LHN à égaliser les branches, donc à faire péter les tests. Quand on y parvient, c'est efficace. Mais ce n'est pas toujours le cas, et alors l'algo assembleur s'impose.
Sinon, je suis assez impressionné par les optimisations mises en place par le compilo Microsoft. Sur un bench /à-la-con/ je ne suis jamais parvenu à faire un truc rapide que MSVC.
-- Pierre Maurette
Marc Espie, le 24/10/2009 a écrit :
In article <mn.c3ef7d9ac3d6ce4c.79899@wanadoo.fr>,
Pierre Maurette <maurettepierre@wanadoo.fr> wrote:
candide, le 24/10/2009 a écrit :
[...]
Ne change pas grand chose chez moi (et c'est même pire sans compter que
les valeurs mini et maxi ne correspondent pas avec celles obtenues par
mes deux fonctions). J'ai essayé aussi avec Visual C++ Express +
optimisations, l'écart est moins flagrant qu'avec gcc mais le naïf
l'emporte encore largement.
Le rôle d'un bon compilateur est d'optimiser du code naïf, en fait
lisible, mais bien écrit.
Je ne sais ce que peut "penser" un bon compilateur de:
if (t[i] < mini)
mini = t[i];
if (t[i] > maxi)
maxi = t[i];
par rapport à
if (t[i] < mini)
mini = t[i];
else if (t[i] > maxi)
maxi = t[i];
Il y a peu de chance ici qu'il transforme le premier en le deuxieme.
Il faudrait qu'il sache suffisamment de choses sur les comparaisons d'entiers
pour pouvoir affirmer que mini <= maxi.
Si tu ecris ceci:
assert(mini <= maxi);
if (t[i] < mini)
mini = t[i];
if (t[i] > maxi)
maxi = t[i];
ca pourrait eventuellement l'aider (puisque assert fait partie de la
bibliotheque standard, et donc que le compilo a le droit de faire de la
magie avec, et donc de marquer la branche "mini > maxi" comme non prise,
et donc de "voir" la suite.... ;-)
C'est exactement ce que je voulais exprimer. La base de l'optimisation
en LHN, à part de ne pas écrire des trucs trop débiles, c'est
précisément de donner au compilateur des connaissances que nous avons
et qu'il n'a pas nécessairement.
Le double if sans else est un truc /trop débile/.
Après, ça se complique. Comment en LHN faire passer l'information que
tel ou tel test sera /le plus souvent/ positif [ou négatif] ?
"register" ?
Faut parvenir également en LHN à égaliser les branches, donc à faire
péter les tests. Quand on y parvient, c'est efficace. Mais ce n'est pas
toujours le cas, et alors l'algo assembleur s'impose.
Sinon, je suis assez impressionné par les optimisations mises en place
par le compilo Microsoft. Sur un bench /à-la-con/ je ne suis jamais
parvenu à faire un truc rapide que MSVC.
Ne change pas grand chose chez moi (et c'est même pire sans compter que les valeurs mini et maxi ne correspondent pas avec celles obtenues par mes deux fonctions). J'ai essayé aussi avec Visual C++ Express + optimisations, l'écart est moins flagrant qu'avec gcc mais le naïf l'emporte encore largement.
Le rôle d'un bon compilateur est d'optimiser du code naïf, en fait lisible, mais bien écrit.
Je ne sais ce que peut "penser" un bon compilateur de:
if (t[i] < mini) mini = t[i]; if (t[i] > maxi) maxi = t[i];
par rapport à
if (t[i] < mini) mini = t[i]; else if (t[i] > maxi) maxi = t[i];
Il y a peu de chance ici qu'il transforme le premier en le deuxieme. Il faudrait qu'il sache suffisamment de choses sur les comparaisons d'entiers pour pouvoir affirmer que mini <= maxi.
Si tu ecris ceci:
assert(mini <= maxi); if (t[i] < mini) mini = t[i]; if (t[i] > maxi) maxi = t[i];
ca pourrait eventuellement l'aider (puisque assert fait partie de la bibliotheque standard, et donc que le compilo a le droit de faire de la magie avec, et donc de marquer la branche "mini > maxi" comme non prise, et donc de "voir" la suite.... ;-)
C'est exactement ce que je voulais exprimer. La base de l'optimisation en LHN, à part de ne pas écrire des trucs trop débiles, c'est précisément de donner au compilateur des connaissances que nous avons et qu'il n'a pas nécessairement. Le double if sans else est un truc /trop débile/. Après, ça se complique. Comment en LHN faire passer l'information que tel ou tel test sera /le plus souvent/ positif [ou négatif] ? "register" ? Faut parvenir également en LHN à égaliser les branches, donc à faire péter les tests. Quand on y parvient, c'est efficace. Mais ce n'est pas toujours le cas, et alors l'algo assembleur s'impose.
Sinon, je suis assez impressionné par les optimisations mises en place par le compilo Microsoft. Sur un bench /à-la-con/ je ne suis jamais parvenu à faire un truc rapide que MSVC.
-- Pierre Maurette
espie
In article , Pierre Maurette wrote:
Sinon, je suis assez impressionné par les optimisations mises en place par le compilo Microsoft. Sur un bench /à-la-con/ je ne suis jamais parvenu à faire un truc rapide que MSVC.
C'est facile de faire un compilo rapide quand tu mets des oeilleres. Typiquement, MSVC a deux avantages par rapport a, par exemple, gcc: - un seul processeur cible - la possibilite d'utiliser des algorithmes brevetes pour les affectations optimales de registres.
Si on arrive a faire abolir cette connerie de brevets logiciels, peut-etre que les compilos libres seront vaguement plus a armes egales, au moins sur ce plan...
In article <mn.c4267d9a38119f3d.79899@wanadoo.fr>,
Pierre Maurette <maurettepierre@wanadoo.fr> wrote:
Sinon, je suis assez impressionné par les optimisations mises en place
par le compilo Microsoft. Sur un bench /à-la-con/ je ne suis jamais
parvenu à faire un truc rapide que MSVC.
C'est facile de faire un compilo rapide quand tu mets des oeilleres.
Typiquement, MSVC a deux avantages par rapport a, par exemple, gcc:
- un seul processeur cible
- la possibilite d'utiliser des algorithmes brevetes pour les affectations
optimales de registres.
Si on arrive a faire abolir cette connerie de brevets logiciels, peut-etre
que les compilos libres seront vaguement plus a armes egales, au moins sur
ce plan...
Sinon, je suis assez impressionné par les optimisations mises en place par le compilo Microsoft. Sur un bench /à-la-con/ je ne suis jamais parvenu à faire un truc rapide que MSVC.
C'est facile de faire un compilo rapide quand tu mets des oeilleres. Typiquement, MSVC a deux avantages par rapport a, par exemple, gcc: - un seul processeur cible - la possibilite d'utiliser des algorithmes brevetes pour les affectations optimales de registres.
Si on arrive a faire abolir cette connerie de brevets logiciels, peut-etre que les compilos libres seront vaguement plus a armes egales, au moins sur ce plan...
espie
J'ajouterais que c'est un truc qui me desole toujours dans les soit-disant "progres" de l'informatique: on te sort regulierement des langages soit-disant plus evolues, a la java ou C#. Mais jamais des trucs plus "corrects". Les gens qui font de l'interpretation abstraite et de la semantique ont quand meme fait des trucs interessants. On sait depuis pas mal d'annees qu'on ne va deboucher que sur des problemes indecidables (ou a combinatoire abominablement elevee). Mais a cote de ca, je ne comprend pas pourquoi on n'a toujours pas de langage "annotable", avec des assertions qu'on pourrait rajouter, qui seraient prouvees par le compilo, et qui pourraient servir a faire du code plus optimal.
Dans le cas qui nous concerne, c'est enervant que le compilo ne puisse pas, en meme temps qu'il cree le code, prouver que mini <= maxi, et donc qu'on peut evacuer des bouts de code... je ne dis pas qu'il doit le faire tout seul, ca serait un peu cher dans tous les cas. Mais avec une ou deux annotations du programmeur, qui sait tres bien ce qu'il est en train de calculer, ca ne me parait pas du tout deraisonnable...
bref, je ne comprend pas pourquoi ce type de technologie n'est pas sortie des labos.
J'ajouterais que c'est un truc qui me desole toujours dans les soit-disant
"progres" de l'informatique: on te sort regulierement des langages
soit-disant plus evolues, a la java ou C#. Mais jamais des trucs plus
"corrects". Les gens qui font de l'interpretation abstraite et de la
semantique ont quand meme fait des trucs interessants. On sait depuis pas
mal d'annees qu'on ne va deboucher que sur des problemes indecidables (ou a
combinatoire abominablement elevee). Mais a cote de ca, je ne comprend pas
pourquoi on n'a toujours pas de langage "annotable", avec des assertions
qu'on pourrait rajouter, qui seraient prouvees par le compilo, et qui
pourraient servir a faire du code plus optimal.
Dans le cas qui nous concerne, c'est enervant que le compilo ne puisse pas,
en meme temps qu'il cree le code, prouver que mini <= maxi, et donc qu'on
peut evacuer des bouts de code... je ne dis pas qu'il doit le faire tout
seul, ca serait un peu cher dans tous les cas. Mais avec une ou deux
annotations du programmeur, qui sait tres bien ce qu'il est en train de
calculer, ca ne me parait pas du tout deraisonnable...
bref, je ne comprend pas pourquoi ce type de technologie n'est pas sortie
des labos.
J'ajouterais que c'est un truc qui me desole toujours dans les soit-disant "progres" de l'informatique: on te sort regulierement des langages soit-disant plus evolues, a la java ou C#. Mais jamais des trucs plus "corrects". Les gens qui font de l'interpretation abstraite et de la semantique ont quand meme fait des trucs interessants. On sait depuis pas mal d'annees qu'on ne va deboucher que sur des problemes indecidables (ou a combinatoire abominablement elevee). Mais a cote de ca, je ne comprend pas pourquoi on n'a toujours pas de langage "annotable", avec des assertions qu'on pourrait rajouter, qui seraient prouvees par le compilo, et qui pourraient servir a faire du code plus optimal.
Dans le cas qui nous concerne, c'est enervant que le compilo ne puisse pas, en meme temps qu'il cree le code, prouver que mini <= maxi, et donc qu'on peut evacuer des bouts de code... je ne dis pas qu'il doit le faire tout seul, ca serait un peu cher dans tous les cas. Mais avec une ou deux annotations du programmeur, qui sait tres bien ce qu'il est en train de calculer, ca ne me parait pas du tout deraisonnable...
bref, je ne comprend pas pourquoi ce type de technologie n'est pas sortie des labos.
zwim
Le Sat, 24 Oct 2009 12:32:50 +0200 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).
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; }
J'ai ajouté un algo naif2 pour illustrer le problème. C'est juste la séparation de naif en 2 boucles.
Le nombre de comparaisons reste le même (presque, car en fait i<n est fait 2 fois).
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; }
Et j'ai fait de même avec non_naif, cette fois en retirant l'overhead dû aux branchements conditionnels.
Cette boucle semble vraiment faire du travail inutile, et pourtant...
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; }
Voici la compilation et l'exécution :
$ gcc -O2 -W -Wall -stdÉ9 -pedantic -o x min_max_fclc.c $ ./x min=9, max!47483640 Temps CPU naif : 0.28 seconde.
min=9, max!47483640 Temps CPU non naif : 0.44 seconde. $
Qui pourrait m'expliquer pourquoi le premier code est pas loin de 50% plus rapide que le second alors que ce dernier effectue 25% de moins de comparaisons et pas plus d'affectations (et qu'il n'y a rien d'autre comme opérations, par exemple le nombre d'instructions if est moindre dans le 2ème algo que dans le premier) ?
Et voilà, le résultat est sans appel :
$ ./a.exe min=3, max!47483577 Temps CPU naif : 0.22 seconde.
min=3, max!47483577 Temps CPU naif2 : 0.44 seconde.
min=3, max!47483577 Temps CPU non naif : 0.42 seconde.
min=3, max!47483577 Temps CPU non naif2 : 0.20 seconde.
Tu vois clairement que naif prend 2 fois moins de temps que naif2, ce qui laisse supposer que le compilo fait de l'optimisation sur les registres quand il execute ce petit bout de code du fait que la valeur t[i] est réutilisée 4 fois.
if (t[i] < mini) mini = t[i]; if (t[i] > maxi) maxi = t[i];
Et finalement c'est non_naif2 qui semble codé avec les pieds qui est finalement le plus rapide... En fait non_naif2 bénéficie d'un loop_unrolling + l'optimisation de registres de naif, et il est ainsi plus rapide.
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.
-- zwim. Rien n'est impossible que la mesure de la volonté humaine...
Le Sat, 24 Oct 2009 12:32:50 +0200
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).
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;
}
J'ai ajouté un algo naif2 pour illustrer le problème.
C'est juste la séparation de naif en 2 boucles.
Le nombre de comparaisons reste le même (presque, car en fait i<n est
fait 2 fois).
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;
}
Et j'ai fait de même avec non_naif, cette fois en retirant l'overhead
dû aux branchements conditionnels.
Cette boucle semble vraiment faire du travail inutile, et pourtant...
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;
}
Voici la compilation et l'exécution :
$ gcc -O2 -W -Wall -stdÉ9 -pedantic -o x min_max_fclc.c
$ ./x
min=9, max!47483640
Temps CPU naif : 0.28 seconde.
min=9, max!47483640
Temps CPU non naif : 0.44 seconde.
$
Qui pourrait m'expliquer pourquoi le premier code est pas loin de 50%
plus rapide que le second alors que ce dernier effectue 25% de moins de
comparaisons et pas plus d'affectations (et qu'il n'y a rien d'autre
comme opérations, par exemple le nombre d'instructions if est moindre
dans le 2ème algo que dans le premier) ?
Et voilà, le résultat est sans appel :
$ ./a.exe
min=3, max!47483577
Temps CPU naif : 0.22 seconde.
min=3, max!47483577
Temps CPU naif2 : 0.44 seconde.
min=3, max!47483577
Temps CPU non naif : 0.42 seconde.
min=3, max!47483577
Temps CPU non naif2 : 0.20 seconde.
Tu vois clairement que naif prend 2 fois moins de temps que naif2, ce
qui laisse supposer que le compilo fait de l'optimisation sur les
registres quand il execute ce petit bout de code du fait que la valeur
t[i] est réutilisée 4 fois.
if (t[i] < mini)
mini = t[i];
if (t[i] > maxi)
maxi = t[i];
Et finalement c'est non_naif2 qui semble codé avec les pieds qui est
finalement le plus rapide... En fait non_naif2 bénéficie d'un
loop_unrolling + l'optimisation de registres de naif, et il est ainsi
plus rapide.
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.
--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...
Le Sat, 24 Oct 2009 12:32:50 +0200 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).
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; }
J'ai ajouté un algo naif2 pour illustrer le problème. C'est juste la séparation de naif en 2 boucles.
Le nombre de comparaisons reste le même (presque, car en fait i<n est fait 2 fois).
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; }
Et j'ai fait de même avec non_naif, cette fois en retirant l'overhead dû aux branchements conditionnels.
Cette boucle semble vraiment faire du travail inutile, et pourtant...
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; }
Voici la compilation et l'exécution :
$ gcc -O2 -W -Wall -stdÉ9 -pedantic -o x min_max_fclc.c $ ./x min=9, max!47483640 Temps CPU naif : 0.28 seconde.
min=9, max!47483640 Temps CPU non naif : 0.44 seconde. $
Qui pourrait m'expliquer pourquoi le premier code est pas loin de 50% plus rapide que le second alors que ce dernier effectue 25% de moins de comparaisons et pas plus d'affectations (et qu'il n'y a rien d'autre comme opérations, par exemple le nombre d'instructions if est moindre dans le 2ème algo que dans le premier) ?
Et voilà, le résultat est sans appel :
$ ./a.exe min=3, max!47483577 Temps CPU naif : 0.22 seconde.
min=3, max!47483577 Temps CPU naif2 : 0.44 seconde.
min=3, max!47483577 Temps CPU non naif : 0.42 seconde.
min=3, max!47483577 Temps CPU non naif2 : 0.20 seconde.
Tu vois clairement que naif prend 2 fois moins de temps que naif2, ce qui laisse supposer que le compilo fait de l'optimisation sur les registres quand il execute ce petit bout de code du fait que la valeur t[i] est réutilisée 4 fois.
if (t[i] < mini) mini = t[i]; if (t[i] > maxi) maxi = t[i];
Et finalement c'est non_naif2 qui semble codé avec les pieds qui est finalement le plus rapide... En fait non_naif2 bénéficie d'un loop_unrolling + l'optimisation de registres de naif, et il est ainsi plus rapide.
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.
-- zwim. Rien n'est impossible que la mesure de la volonté humaine...
candide
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.
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.
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.
