Discussion :

[gobelin88]

Bonjour,

Je cherche à optimiser (en terme de rapidité d'execution) au maximum, le code suivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BMes::calc_inter_trilinear(const cv::Vec3d & m,const BOctreeBox & box,const std::vector<BMes *> & B_list , BMes * b_inter)//Fonction de calcul d'un point de mesure
{
    cv::Vec3d Md( (m[0]-box.pos[0])/box.dim[0],
                  (m[1]-box.pos[1])/box.dim[1],
                  (m[2]-box.pos[2])/box.dim[2] );
 
    cv::Vec3d c00 ( B_list[box.id[0]]->B*(1-Md[0]) + B_list[box.id[4]]->B*Md[0] );
    cv::Vec3d c10 ( B_list[box.id[1]]->B*(1-Md[0]) + B_list[box.id[5]]->B*Md[0] );
    cv::Vec3d c11 ( B_list[box.id[2]]->B*(1-Md[0]) + B_list[box.id[6]]->B*Md[0] );
    cv::Vec3d c01 ( B_list[box.id[3]]->B*(1-Md[0]) + B_list[box.id[7]]->B*Md[0] );
    cv::Vec3d c0 ( c00*(1-Md[1]) + c10 * Md[1] );
    cv::Vec3d c1 ( c01*(1-Md[1]) + c11 * Md[1] );
 
    b_inter->B = c0*(1-Md[2]) + c1 * Md[2];
 
    *((cv::Vec3d*)b_inter)=m;
}

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
class BMES : public cv::Vec3d
{
 public:
  cv::Vec3d m;
 .
 .
 .
}

Il s'agit d'une interpolation trilinéaire (http://en.wikipedia.org/wiki/Trilinear_interpolation). j'utilise opencv pour les vecteurs.

Voila, j'ai déjà essayé d'écrire tout en une seule ligne pour supprimer les variables intermédiaires (c00 c10 c11 c 01 c0 c1) mais cela n'a rien changé. le compilateur devait déjà effectué l'optimisation)

C'est le nombre d’opérations flottantes qu'il faudrait réduire.

J’apprécie toutes remarques pour améliorer ce code.

Merci pour votre aide

[Aleph69]

Bonjour,

tu peux promouvoir quelques scalaires : stockes dans des variables locales Md[0], Md[1] et Md[2] pour n'accéder qu'une seule fois à ces valeurs. Pour le moment, tu accèdes 8 fois à Md[0], 4 fois à Md[1] et deux fois à Md[2].

Tu peux essayer de remplacer les calculs du type

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

a*(1-b)+c*b

par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

a+(c-a)*b

ce qui te fait gagner une opération.

[Aleph69]

J'oubliais : ne fais pas d'appels à des constructeurs, c'est-à-dire ne construis pas de vecteurs. Pour un si petit code, tu peux te permettre de ne pas faire d'objet mais de simplement stocker les différentes valeurs de tes vecteurs dans des variables scalaires locales. Ici, le recours à des objets type vecteur n'est pas utile car tu sembles les utiliser comme des tableaux simples.

[Aleph69]

Voici un début :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void BMes::calc_inter_trilinear(const cv::Vec3d & m,const BOctreeBox & box,const std::vector<BMes *> & B_list , BMes * b_inter)//Fonction de calcul d'un point de mesure
{
    // promotion des composantes de Md sans construction explicite de Md
    double Md0 = m[0]-box.pos[0])/box.dim[0];
    double Md1 = m[1]-box.pos[1])/box.dim[1];
    double Md2 = m[2]-box.pos[2])/box.dim[2];
 
    // ici, il ne faudrait pas construire de vecteurs (Vec3d) mais seulement stocker leurs composantes dans des variables scalaires (comme pour Md).
    cv::Vec3d c00 ( B_list[box.id[0]]->B*(1-Md0) + B_list[box.id[4]]->B*Md0 );
    cv::Vec3d c10 ( B_list[box.id[1]]->B*(1-Md0) + B_list[box.id[5]]->B*Md0 );
    cv::Vec3d c11 ( B_list[box.id[2]]->B*(1-Md0) + B_list[box.id[6]]->B*Md0 );
    cv::Vec3d c01 ( B_list[box.id[3]]->B*(1-Md0) + B_list[box.id[7]]->B*Md0 );
    cv::Vec3d c0 ( c00 + (c10-c00) * Md1 );
    cv::Vec3d c1 ( c01 + (c11-c01) * Md1 );
 
    b_inter->B = c0 + (c1-c0) * Md2;
 
    *((cv::Vec3d*)b_inter)=m;
}

Tu peux aussi remarquer que pour calculer b_inter->B tu n'as besoin de connaître que c0 et (c1-c0) : au lieu de calculer c1 à la ligne précédente, tu devrais directement calculer c1-c0. Idem pour le calcul de c1 qui ne nécessite que c01 et c11-c01; celui de c0 ne nécessite que c00 et c10-c00. Inutile de calculer c11 et c10; calcule plutôt directement c11-c01 et c10-c00.

[CedricMocquillon]

Désolé, je ne vais pas vraiment pouvoir t'aider sur les aspects optimisation par contre, j'avais écrit un code permettant de réaliser l'interpolation bilinéaire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
double linearInterpolate(double p[2], double x)
{
	return (1.0 - x)*p[1] + x*p[2];
}
 
 
double bilinearInterpolate(double p[2][2], double x, double y)
{
	double arr[2];
	arr[0] = linearInterpolate(p[0], y);
	arr[1] = linearInterpolate(p[1], y);
	return linearInterpolate(arr, x);
}

Tu dois pouvoir ajouter une "couche" pour exprimer l'interpolation trilinéaire à partir de la bilinéaire, ton code serait je pense un poil plus "digeste" (et souvent un code digeste permet pour toi et le compilo de mieux optimiser).

[gobelin88]

Merci beaucoup

Voici déjà une bonne première étape qui économise 7 multiplications flottantes.

voici le nouveau code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
double Md[3]= {(m[0]-box.pos[0])/box.dim[0],
                   (m[1]-box.pos[1])/box.dim[1],
                   (m[2]-box.pos[2])/box.dim[2] };
 
    cv::Vec3d c00 ( B_list[box.id[0]]->B + ( B_list[box.id[4]]->B - B_list[box.id[0]]->B ) * Md[0] );
    cv::Vec3d c10 ( B_list[box.id[1]]->B + ( B_list[box.id[5]]->B - B_list[box.id[1]]->B ) * Md[0] );
    cv::Vec3d c11 ( B_list[box.id[2]]->B + ( B_list[box.id[6]]->B - B_list[box.id[2]]->B ) * Md[0] );
    cv::Vec3d c01 ( B_list[box.id[3]]->B + ( B_list[box.id[7]]->B - B_list[box.id[3]]->B ) * Md[0] );
 
    cv::Vec3d c0 ( c00 + ( c10-c00 ) * Md[1] );
    cv::Vec3d c1 ( c01 + ( c11-c01 ) * Md[1] );
 
    b_inter->B = c0 + ( c1-c0 ) * Md[2];
 
    *((cv::Vec3d*)b_inter)=m;

[gobelin88]

Merci Aleph69

Tu peux aussi remarquer que pour calculer b_inter->B tu n'as besoin de connaître que c0 et (c1-c0) : au lieu de calculer c1 à la ligne précédente, tu devrais directement calculer c1-c0. Idem pour le calcul de c1 qui ne nécessite que c01 et c11-c01; celui de c0 ne nécessite que c00 et c10-c00. Inutile de calculer c11 et c10; calcule plutôt directement c11-c01 et c10-c00.

Ok je regarde ce que je peux faire

[Aleph69]

Voici déjà une bonne première étape qui économise 7 multiplications flottantes.

Attention, dans le calcul de c00, c01 etc, tu accèdes une fois de trop à Blist. Par exemple, la ligne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

cv::Vec3d c00 ( B_list[box.id[0]]->B + ( B_list[box.id[4]]->B - B_list[box.id[0]]->B ) * Md[0] );

sera plus efficace si tu stockes B_list[box.id[0]]->B une fois pour toutes dans une variable locale. Ainsi, tu n'accèderas qu'une seule fois à B_list[box.id[0]] au lieu de 2 fois.

[gobelin88]

Hum ok, j'ai essayé de calculer avec les différences mais cela ne semble pas factoriser le code, voici ce que j'ai pondu suite à tes suggestions:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
double Md[3]= {(m[0]-box.pos[0])/box.dim[0],
                   (m[1]-box.pos[1])/box.dim[1],
                   (m[2]-box.pos[2])/box.dim[2] };
 
    //Variables pour eviter de recalculer
    cv::Vec3d tmp1= B_list[box.id[4]]->B - B_list[box.id[0]]->B;
    cv::Vec3d tmp2= B_list[box.id[7]]->B - B_list[box.id[3]]->B;
 
    //
    cv::Vec3d c00 ( B_list[box.id[0]]->B + tmp1 * Md[0] );
    cv::Vec3d c01 ( B_list[box.id[3]]->B + tmp2 * Md[0] );
    //cv::Vec3d c10 ( B_list[box.id[1]]->B + ( B_list[box.id[5]]->B - B_list[box.id[1]]->B ) * Md[0] );
    //cv::Vec3d c11 ( B_list[box.id[2]]->B + ( B_list[box.id[6]]->B - B_list[box.id[2]]->B ) * Md[0] );
    cv::Vec3d c10_c00= ( B_list[box.id[1]]->B - B_list[box.id[0]]->B + ( B_list[box.id[5]]->B - B_list[box.id[1]]->B - tmp1 ) * Md[0] ) ; // + 2 soustractions
    cv::Vec3d c11_c01= ( B_list[box.id[2]]->B - B_list[box.id[3]]->B + ( B_list[box.id[6]]->B - B_list[box.id[2]]->B - tmp2 ) * Md[0] ) ; // + 2 soustractions
 
    cv::Vec3d c0 ( c00 + ( c10_c00 ) * Md[1] );
    //cv::Vec3d c1 ( c01 + ( c11_c01 ) * Md[1] );
    cv::Vec3d c1_c0= ( c01_c00 + ( c11_c01 - c10_c00 ) * Md[1] ); //meme nombre d'op
 
    b_inter->B = c0 + ( c1_c0 ) * Md[2]; //- une soustraction
 
    *((cv::Vec3d*)b_inter)=m;

sera plus efficace si tu stockes B_list[box.id[0]]->B une fois pour toutes dans une variable locale. Ainsi, tu n'accèderas qu'une seule fois à B_list[box.id[0]] au lieu de 2 fois.

Ok

[gobelin88]

Du coup le code actuel reste avec dernières recommandations

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void BMes::calc_inter_trilinear(const cv::Vec3d & m,const BOctreeBox & box,const std::vector<BMes *> & B_list , BMes * b_inter)//Fonction de calcul d'un point de mesure
{
    double Md[3]= {(m[0]-box.pos[0])/box.dim[0],
                   (m[1]-box.pos[1])/box.dim[1],
                   (m[2]-box.pos[2])/box.dim[2] };
 
    //
    cv::Vec3d tmp1= B_list[box.id[0]]->B;
    cv::Vec3d tmp2= B_list[box.id[3]]->B;
    cv::Vec3d tmp3= B_list[box.id[1]]->B;
    cv::Vec3d tmp4= B_list[box.id[2]]->B;
 
    //
    cv::Vec3d c00 ( tmp1 + ( B_list[box.id[4]]->B - tmp1 ) * Md[0] );
    cv::Vec3d c01 ( tmp2 + ( B_list[box.id[7]]->B - tmp2 ) * Md[0] );
    cv::Vec3d c10 ( tmp3 + ( B_list[box.id[5]]->B - tmp3 ) * Md[0] );
    cv::Vec3d c11 ( tmp4 + ( B_list[box.id[6]]->B - tmp4 ) * Md[0] );
    //cv::Vec3d c10_c00= ( B_list[box.id[1]]->B - B_list[box.id[0]]->B + ( B_list[box.id[5]]->B - B_list[box.id[1]]->B - tmp1 ) * Md[0] ) ; // + 2 soustractions
    //cv::Vec3d c11_c01= ( B_list[box.id[2]]->B - B_list[box.id[3]]->B + ( B_list[box.id[6]]->B - B_list[box.id[2]]->B - tmp2 ) * Md[0] ) ; // + 2 soustractions
 
    cv::Vec3d c0 ( c00 + ( c10-c00 ) * Md[1] );
    cv::Vec3d c1 ( c01 + ( c11-c01 ) * Md[1] );
    //cv::Vec3d c1_c0= ( c01_c00 + ( c11_c01 - c10_c00 ) * Md[1] ); //meme nombre d'op
 
    b_inter->B = c0 + ( c1-c0 ) * Md[2]; //- une soustraction
 
    *((cv::Vec3d*)b_inter)=m;
}

[gobelin88]

Désolé, je ne vais pas vraiment pouvoir t'aider sur les aspects optimisation par contre, j'avais écrit un code permettant de réaliser l'interpolation bilinéaire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
double linearInterpolate(double p[2], double x)
{
	return (1.0 - x)*p[1] + x*p[2];
}
 
 
double bilinearInterpolate(double p[2][2], double x, double y)
{
	double arr[2];
	arr[0] = linearInterpolate(p[0], y);
	arr[1] = linearInterpolate(p[1], y);
	return linearInterpolate(arr, x);
}

Tu dois pouvoir ajouter une "couche" pour exprimer l'interpolation trilinéaire à partir de la bilinéaire, ton code serait je pense un poil plus "digeste" (et souvent un code digeste permet pour toi et le compilo de mieux optimiser).

Ton code est propre et effectivement adaptable au cas tri_linéaire, tu peux aussi l'optimiser avec ce qu'a proposé Aleph69 cad :

[code]permettant de réaliser l'interpolation bilinéaire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
double linearInterpolate(double p[2], double x)
{
	return p[1] + x*(p[2]-p[1]);
}

[Aleph69]

Hum ok, j'ai essayé de calculer avec les différences mais cela ne semble pas factoriser le code

Oui, il faut faire attention à ne pas augmenter le nombre d'accès aux tableaux et il serait également préférable de ne pas utiliser de vecteurs ou de tableaux quand c'est possible.

Voici quelques modifications :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
// on n'utilise pas de tableau pour ne pas perdre en performance avec des accès inutiles
double Md0 = m[0]-box.pos[0])/box.dim[0];
double Md1 = m[1]-box.pos[1])/box.dim[1];
double Md2 = m[2]-box.pos[2])/box.dim[2];
 
    // stocker les composantes des vecteurs
    cv::Vec3d B = B_list[box.id[0]]->B;
    double b00 = B[0];
    double b01 = B[1];
    double b02 = B[2];
    B = B_list[box.id[1]]->B;
    double b10 = B[0];
    double b11 = B[1];
    double b12 = B[2];
    B = B_list[box.id[2]]->B;
    double b20 = B[0];
    double b21 = B[1];
    double b22 = B[2];
    // ... etc ...
 
 
 
    // on ne passe plus par un vecteur pour le calcul de c00 :
   double c00_0 = b00+(b40-b00)*Md0;
   double c00_1 = b01+(b41-b01)*Md0;
   double c00_1 = b02+(b42-b02)*Md0;
   // ... idem pour les autres vecteurs ...
 
 
   // je ne comprends pas ce que tu fais ici 
    *((cv::Vec3d*)b_inter)=m;

[Bousk]

Oui, il faut faire attention à ne pas augmenter le nombre d'accès aux tableaux et il serait également préférable de ne pas utiliser de vecteurs ou de tableaux quand c'est possible.

Sur quoi tu te bases pour affirmer ça ?
Accéder à un champ de vector ou array se fait en temps constant dû à la contiguité des éléments en mémoire.
Accéder à un champ d'une classe se fait également en temps constant.

Donc tes améliorations n'en sont pas.
Sauf à augmenter la mémoire utilisée en ram avec des variables inutiles.

[CedricMocquillon]

Étant un peu intrigué j'ai tenté une comparaison entre deux codes (je n'ai pas vraiment pu mettre ton code puisque je n'ai pas les structures de données d'opencv et je n'ai pas réimplémenté la partie sur la normalisation de la box):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
double goblinInterpolate(double const p[2][2][2], double const x, double const y, double const z)
{
    double const c00 ( x*(p[1][0][0]-p[0][0][0]) + p[0][0][0] );
    double const c10 ( x*(p[1][1][0]-p[0][1][0]) + p[0][1][0] );
    double const c11 ( x*(p[1][1][1]-p[0][1][1]) + p[0][1][1] );
    double const c01 ( x*(p[1][0][1]-p[0][0][1]) + p[0][0][1] );
 
    double const c0 ( y*(c10-c00) + c00 );
    double const c1 ( y*(c11-c01) + c01 );
 
    return z*(c1-c0) + c0;
}
 
 
double linearInterpolate(double const p[2], double const x)
{
	return x*(p[1] - p[0]) + p[0];
}
 
 
double bilinearInterpolate(double const p[2][2], double const x, double const y)
{
	double const arr[2] = { linearInterpolate(p[0], y), linearInterpolate(p[1], y) };
	return linearInterpolate(arr, x);
}
 
 
double trilinearInterpolate(double const p[2][2][2], double const x, double const y, double const z)
{
	double const arr[2] = { bilinearInterpolate(p[0], y, z), bilinearInterpolate(p[1], y, z) };
	return linearInterpolate(arr, x);
}
 
 
int main()
{
	double p[2][2][2] = { { {0, 1}, {1, 2} }, { {0, 0}, {1, 2} } };
	double const first = trilinearInterpolate(p, 0.5, 0.5, 0.5);
	double const second = goblinInterpolate(p, 0.5, 0.5, 0.5);
	assert(first == second);
}

Le code assembleur généré (sous visual2008 en /Ox) est exactement le même:

?trilinearInterpolate@@YANQAY111$$CBNNNN@Z PROC ; trilinearInterpolate, COMDAT
; _p$ = eax
; Line 367
fld QWORD PTR [eax+8]
fsub QWORD PTR [eax]
fld QWORD PTR _z$[esp-4]
fmul ST(1), ST(0)
fxch ST(1)
fadd QWORD PTR [eax]
fld QWORD PTR [eax+24]
fsub QWORD PTR [eax+16]
fmul ST(0), ST(2)
fadd QWORD PTR [eax+16]
fsub ST(0), ST(1)
fld QWORD PTR _y$[esp-4]
fmul ST(1), ST(0)
fxch ST(1)
faddp ST(2), ST(0)
fld QWORD PTR [eax+40]
fsub QWORD PTR [eax+32]
fmul ST(0), ST(3)
fadd QWORD PTR [eax+32]
fld QWORD PTR [eax+56]
fsub QWORD PTR [eax+48]
fmulp ST(4), ST(0)
fxch ST(3)
fadd QWORD PTR [eax+48]
fsub ST(0), ST(3)
fmulp ST(1), ST(0)
faddp ST(2), ST(0)
; Line 368
fsub ST(1), ST(0)
fxch ST(1)
fmul QWORD PTR _x$[esp-4]
faddp ST(1), ST(0)
; Line 369
ret 0

et

?goblinInterpolate@@YANQAY111$$CBNNNN@Z PROC ; goblinInterpolate, COMDAT
; _p$ = eax
; Line 340
fld QWORD PTR [eax+32]
fsub QWORD PTR [eax]
fld QWORD PTR _x$[esp-4]
fmul ST(1), ST(0)
fxch ST(1)
fadd QWORD PTR [eax]
; Line 343
fld QWORD PTR [eax+40]
fsub QWORD PTR [eax+8]
fmul ST(0), ST(2)
fadd QWORD PTR [eax+8]
fld QWORD PTR [eax+48]
fsub QWORD PTR [eax+16]
fmul ST(0), ST(3)
fadd QWORD PTR [eax+16]
; Line 345
fsub ST(0), ST(2)
fld QWORD PTR _y$[esp-4]
fmul ST(1), ST(0)
fxch ST(1)
faddp ST(3), ST(0)
fld QWORD PTR [eax+56]
fsub QWORD PTR [eax+24]
fmulp ST(4), ST(0)
fxch ST(3)
fadd QWORD PTR [eax+24]
; Line 346
fsub ST(0), ST(1)
fmulp ST(3), ST(0)
faddp ST(2), ST(0)
; Line 348
fsub ST(1), ST(0)
fxch ST(1)
fmul QWORD PTR _z$[esp-4]
faddp ST(1), ST(0)
; Line 349
ret 0

Après ce code d'exemple est relativement simple, il faudrait le templatiser pour qu'il puisse faire l'interpolation sur un ensemble de valeurs (c'est ton cas apparemment puisque tu utilises des cv::Vec3d). Mais au final je pense pas que ça fera une différence sur le code généré (à tester quand même).

[3DArchi]

Sur quoi tu te bases pour affirmer ça ?

J'aurais tendance à penser que c'est la bonne question. Si tu en es à des optimisations aussi localisées, pars du code ASM généré et de la doc de ton compilateur (de la doc du µ?) pour déduire la forme C++ la plus adéquate. Je ne sais pas si, dans ce cas, partir du C++ ne relève pas d'un tatonnement peut être un peu laborieux.

[Aleph69]

Sur quoi tu te bases pour affirmer ça ?
Accéder à un champ de vector ou array se fait en temps constant dû à la contiguité des éléments en mémoire.
Accéder à un champ d'une classe se fait également en temps constant.

Donc tes améliorations n'en sont pas.
Sauf à augmenter la mémoire utilisée en ram avec des variables inutiles.

Depuis quand on optimise des codes avec des accès RAM?

[gbdivers]

@gobelin88
comment mesure tu les améliorations de performances ?
tu as mesuré les gains apportés par les différentes versions du code testé ?
tu as testé avec quel type de données ?

toutes les améliorations proposées ont un sens que si tu as mesuré une différence qui te semble suffisamment significative dans le contexte particulier de ton application. Imagine, si tu fais tes calculs sur des données dont le chargement prend 90% du temps, les améliorations proposées n'auront aucun impact.

Toujours faire du profiling pour optimiser du code

Seul le profiling te dira si tu as des problèmes de cache miss, d'allocation, d'accès, etc. Tout les conseils que l'on t'a donné ne sont que des optimisations théoriques tant que tu n'as pas testé leurs impacts réél. Dis autrement, ça ne sera des améliorations du code que lorsque tu auras prouvé que ce sont des améliorations et pas de la masturbation intellectuelle

[Aleph69]

On doit distinguer deux formes d'optimisation :
1. l'optimisation théorique qui consiste à modifier un algorithme pour obtenir un nouvel algorithme de complexité moindre indépendamment de l'architecture et du processus de compilation;
2. l'optimisation pratique effectuée en fonction de l'architecture et du processus de compilation.
Pour optimiser, on doit d'abord se préoccuper de 1. puis de 2. Le 1. ne nécessite pas l'utilisation d'un profileur tandis que 2. si.

[dourouc05]

Sachant que le compilateur est en général capable d'effectuer pas mal d'optimisations du second type, alors qu'il est incapable de repenser ton algo.

À lire un peu la discussion : lire trente-six fois la même valeur dans un vecteur, le compilateur doit pouvoir l'optimiser, si on lui donne les bonnes hypothèses (pas de modification concurrente, chaque opération de lecture n'altère en rien le contenu), non ?

[gbdivers]

On doit distinguer deux formes d'optimisation :
1. l'optimisation théorique qui consiste à modifier un algorithme pour obtenir un nouvel algorithme de complexité moindre indépendamment de l'architecture et du processus de compilation;

D'accord sans problème. Mais pour le moment, j'ai pas vu de changement d'algo (mais j'ai lu en diagonal) et surtout pas vu de calcul de complexité algorithmique.

Ce que j'ai vu ressemble beaucoup à de la micro optimisation. Et quand on voit la remarque de CedricMocquillon comme quoi le code généré est identique et celle de dourouc05 sur le fait que le compilo fait déjà un gros boulot, ma remarque reste : tant qu'on ne prouve pas l'amélioration (que soit de façon théorique par un calcul de complexité ou pratique par des mesures), ce ne sont pas des améliorations, mais que de la théorie