Recherche optimisation de code

Version imprimable

Bonjour,

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

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:

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

24/08/2012, 09h52
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:

a*(1-b)+c*b

par

Code:

a+(c-a)*b

ce qui te fait gagner une opération.
24/08/2012, 10h00
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.

Voici un début :

Code:

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.

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:

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).

Merci beaucoup

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

voici le nouveau code:

Code:

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;

24/08/2012, 10h46
gobelin88

Merci Aleph69

Citation:

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 ;)
24/08/2012, 11h23
Aleph69

Citation:

Envoyé par gobelin88

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

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

Code:

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.

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:

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;

Citation:

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.

Du coup le code actuel reste avec dernières recommandations

Code:

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;
}

Citation:
Envoyé par 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:

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:

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

Citation:

Envoyé par gobelin88

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:

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;

24/08/2012, 13h15
Bousk

Citation:

Envoyé par Aleph69

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. :aie:
Sauf à augmenter la mémoire utilisée en ram avec des variables inutiles.

É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:

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:

Citation:

?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

Citation:

?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).

24/08/2012, 17h14
3DArchi

Citation:

Envoyé par Bousk

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.
24/08/2012, 22h30
Aleph69

Citation:

Envoyé par Bousk

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. :aie:
Sauf à augmenter la mémoire utilisée en ram avec des variables inutiles.

Depuis quand on optimise des codes avec des accès RAM? :koi:
25/08/2012, 21h05
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
25/08/2012, 22h20
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.
25/08/2012, 22h33
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 ?
25/08/2012, 22h39
gbdivers

Citation:

Envoyé par 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;

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
25/08/2012, 22h41
Aleph69

Citation:

Envoyé par dourouc05

À 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 ?

Sur un code manipulant peu de données comme celui-là, j'imagine que c'est possible mais je ne peux pas l'affirmer (on peut pas tester toutes les configurations possibles de compilation) donc je préfère faire le boulot (simple et rapide) moi-même en promouvant quelques scalaires. Sur un plus grand nombre de données, l'argument du temps d'accès constant en RAM pour une zone mémoire contigüe ne tient plus car l'ordre d'accès a directement un impact sur la réutilisation des caches (principe de localité).
25/08/2012, 22h48
Aleph69

Citation:

Envoyé par gbdivers

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.

Dès le départ, une modification a été proposée pour réduire le nombre d'opérations. Et pour effectuer ce changement de manière explicite, j'ai besoin de détruire la structuration des données imposée par les conteneurs.

Citation:

Envoyé par gbdivers

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

Non, si tu testes une optimisation théorique avec un profileur ou tout autre chose dépendant de l'architecture, tu biaises de facto les résultats. Ce n'est pas parce que sur ta machine, avec ton compilateur et tes options de compilation, les optimisations sont faites automatiquement (même code assembleur qu'avec le codage manuel) que cela sera vrai en modifiant l'un de ces paramètres. Le test de CedricMocquillon n'est plus nécessairement vrai sur la machine de Gobelin88 (principe de reproductibilité de l'expérience violé) et en plus, dans ce cas particulier, l'implémentation est différente (non utilisation des cv:Vec3d).
25/08/2012, 23h12
gbdivers

Attend, on est bien d'accord qu'il s'agit simplement de restructuration du code, pas d'un changement d'algorithme. Ou alors montre moi les calculs de complexité pour prouver que tu gagnes quelques chose en terme de complexité algorithmique.

Et si ce n'est pas un changement de complexité algorithmique, alors ça doit être prouvé en pratique par des tests et profiling. Par exemple, ta "promotion" de variables, rien de dit que le compilateur ne fait déjà pas ce boulot (mise en cache ? en registre ?)

Bref, je suis d'accord avec toi que ce sont des améliorations que l'on peut proposer. Mais sans validation pratique par des tests, pour moi, ça n'a pas de valeur
25/08/2012, 23h41
Aleph69

Citation:

Envoyé par gbdivers

Attend, on est bien d'accord qu'il s'agit simplement de restructuration du code, pas d'un changement d'algorithme. Ou alors montre moi les calculs de complexité pour prouver que tu gagnes quelques chose en terme de complexité algorithmique.

Je t'assure que l'algorithme a bien été modifié. C'est la deuxième partie du deuxième message de cette discussion. Je n'ai pas développé le calcul de complexité puisqu'il est trivial. J'ai simplement indiqué qu'on gagnait une opération à chaque fois.

Citation:

Envoyé par gbdivers

Et si ce n'est pas un changement de complexité algorithmique, alors ça doit être prouvé en pratique par des tests et profiling.

La limite c'est que tu ne peux pas généraliser à partir de ta validation statistique. Si tu gagnes en rapidité, cela n'induit rien quant aux autres architectures/compilations. Idem si tu perds en rapidité. L'inférence est purement transductive : tu dois tout reprendre si tu changes les conditions de l'expérience. C'est d'ailleurs pour cette raison qu'il y a tant de recherches sur la transformation automatique de programme (génération de code optimisé en fonction de l'architecture à partir de tests statistiques).

Citation:

Envoyé par gbdivers

Par exemple, ta "promotion" de variables, rien de dit que le compilateur ne fait déjà pas ce boulot (mise en cache ? en registre ?)

Effectivement, rien ne le dit. D'ailleurs, beaucoup sont capables de le faire dans les cas simples comme celui-ci. Je dis juste que lorsque c'est si simple et rapide à faire, je préfère le faire moi-même pour que mon optimisation soit la mieux portée possible sur d'autres couples (architecture, compilation). Je préfère miser sur ce que je sais faire plutôt que sur ce que je "crois" que "tout" compilateur "devrait" savoir faire.
27/08/2012, 16h58
gobelin88

Citation:

Envoyé par 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):

...

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).

Peut etre que dans mon cas le compilateur de visual que j'utilise n'a pas su faire la simplification arithmétique :roll: (peut etre pk j'utilise cv::Vec3d... je sais pas...)

En tout cas dans mon cas, le fait de supprimer explicitement 7*3 (j'ai des vecteurs) multiplications, constitue la meilleure optimisation effectuée.
27/08/2012, 17h02
gobelin88

Citation:

Envoyé par 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

J'utilise un timer précis de opencv pour mesurer une différence de temps .

Je n'ai pas d'autre outils à ma disposition pour faire du profiling, mais la solution précédente me semble viable.
27/08/2012, 17h28
white_tentacle

Citation:

Envoyé par Aleph69

Je t'assure que l'algorithme a bien été modifié. C'est la deuxième partie du deuxième message de cette discussion. Je n'ai pas développé le calcul de complexité puisqu'il est trivial. J'ai simplement indiqué qu'on gagnait une opération à chaque fois.

En général, on n’appelle pas ce type d’optimisations modification de l’algorithme. C’est une optimisation purement calculatoire (factorisation), l’algorithme n’a pas changé d’un pouce. Ça ne veut pas dire qu’elle ne sert à rien (et il semble bien qu’elle serve !), mais ce n’est pas ce qu’on entend usuellement par modification de l’algorithme.

Citation:

La limite c'est que tu ne peux pas généraliser à partir de ta validation statistique. Si tu gagnes en rapidité, cela n'induit rien quant aux autres architectures/compilations. Idem si tu perds en rapidité. L'inférence est purement transductive : tu dois tout reprendre si tu changes les conditions de l'expérience. C'est d'ailleurs pour cette raison qu'il y a tant de recherches sur la transformation automatique de programme (génération de code optimisé en fonction de l'architecture à partir de tests statistiques).

À ce niveau là, tu optimises forcément pour une archi et un compilateur donné. Quitte à user du préprocesseur si tu as des comportements différents.

Après, j’ai du mal à imaginer des cas ou tes modifications rendraient le code plus lent que l’original (saturation des registres ? je n’y crois pas trop…). Du coup, je ne peux difficilement te donner tort de les faire, tant que la lisibilité du code n’en pâtit pas :).

edit : je n’avais pas fait gaffe, mais combien est sizeof(cv::vec3d) ? Parce que là, tu échanges des accès à un tableau (donc des calculs d’adresse) contre des copies d’objet, du coup, pas étonnant qu’on semble ne rien gagner sur ce point. Il faudrait peut-être plutôt utiliser des références peur les tmp, non ?
27/08/2012, 18h07
gobelin88

Citation:

Envoyé par white_tentacle

edit : je n’avais pas fait gaffe, mais combien est sizeof(cv::vec3d) ? Parce que là, tu échanges des accès à un tableau (donc des calculs d’adresse) contre des copies d’objet, du coup, pas étonnant qu’on semble ne rien gagner sur ce point. Il faudrait peut-être plutôt utiliser des références peur les tmp, non ?

Right

sizeof(cv::Vec3d)==24 --> references utiles pour les tmp
27/08/2012, 20h09
Aleph69

Bonjour white_tentacle,

Citation:

Envoyé par white_tentacle

En général, on n’appelle pas ce type d’optimisations modification de l’algorithme. C’est une optimisation purement calculatoire (factorisation), l’algorithme n’a pas changé d’un pouce. Ça ne veut pas dire qu’elle ne sert à rien (et il semble bien qu’elle serve !), mais ce n’est pas ce qu’on entend usuellement par modification de l’algorithme.

Je tellement surpris parce ce que tu affirmes que je me dis qu'on ne doit sûrement pas parler de la même chose. Pour être clair, remplacer les opérations écrites

Code:

a*(1-b)+c*b

par

Code:

a+(c-a)*b

c'est bien changer d'algorithme. Outre le fait que la complexité temporelle soit réduite, la stabilité numérique est également améliorée. Il existe un exemple historique d'une modification aussi simple que celle-ci qui conduit à une stabilisation fondamentale du procédé d'orthonormalisation de Gram-Schmidt : en précision finie la perte d'orthogonalité est arbitrairement grande pour l'algorithme de Gram-Schmidt classique (CGS) tandis qu'elle est bornée pour l'algorithme de Gram-Schmidt modifié (MGS). Affirmer qu'on est en présence du même algorithme me paraît exagéré : en analyse numérique, personne ne le fait et on distingue bien les deux algorithmes. Pourtant, dans ce cas, même la complexité temporelle est la même : on a juste modifié l'ordre des opérations. Un algorithme est aussi défini par son comportement en précision finie (stabilité numérique).

EDIT : mais dans le cadre de discussion, réduire la complexité spatiale ou temporelle d'un algorithme suffit pour dire qu'on a changé d'algorithme. De même, améliorer la stabilité numérique d'un algorithme suffit pour dire qu'on a changé d'algorithme. Ce n'est d'ailleurs pas pour rien si on apprend aux étudiants à faire des calculs de complexité dans les cours d'algorithmique. En revanche, c'est dommage qu'on les fasse rarement analyser numériquement des algorithmes.

Citation:

Envoyé par white_tentacle

Du coup, je ne peux difficilement te donner tort de les faire, tant que la lisibilité du code n’en pâtit pas :).

Effectivement, personne n'a parlé de la lisibilité du code; tu fais bien de le mentionner! :ccool:
27/08/2012, 20h33
Aleph69

Citation:

Envoyé par gobelin88

En tout cas dans mon cas, le fait de supprimer explicitement 7*3 (j'ai des vecteurs) multiplications, constitue la meilleure optimisation effectuée.

Super! Je suis content si j'ai pu t'aider! :D
27/08/2012, 21h17
CedricMocquillon

Ce qui n'était pas très clair (et que ne l'est pas encore pour moi) c'est ce que tu cherches à interpoler: généralement le but est de déterminer la valeur d'une fonction partiellement connues en certains point en un point inconnu. Généralement les points connus constituent une grille; dans le cas tri-linéaire, on se place dans le cas 3d, tu as donc besoin des points encadrant le point cherché et des valeurs de la fonction à interpoler sur ces 8 points.

A priori ta fonction est à valeurs dans R^3 ce qui créer un peu de confusion (avec les coordonnées de l'espace 3d); la plupart du temps c'est une fonction à valeurs dans R d'où le code que j'ai proposé et l'un des premiers d'Aleph69 à base de double et le fait qu'on ait pas pensé tout de suite aux références.

Après dans les quelques tests que j'avais effectué, visual n'arrivait pas à optimiser la partie proposée par Aleph69 (le gain d'une multiplication par interpolation linéaire).

Enfin pour ce qui est de la partie sur la complexité, tout dépend à quel niveau on se place: dans mon domaine, ce qui nous intéresse c'est la complexité en O() (on cherche principalement le comportement lorsque n tends vers l'infini) après il y a des domaines où on se bat sur la complexité "précise" de l'algo (il me semble dans ce cas qu'on utilise la notation o()) ce qui est le cas ici. C'est vrai que naturellement pour moi on change pas la complexité de l'algo car j'entends O mais si on parle de la complexité o y'a pas à discuter, le complexité est bien différente (et meilleure dans la solution proposée par Aleph)
27/08/2012, 21h26
Aleph69

Citation:

Envoyé par CedricMocquillon

Enfin pour ce qui est de la partie sur la complexité, tout dépend à quel niveau on se place: dans mon domaine, ce qui nous intéresse c'est la complexité en O() (on cherche principalement le comportement lorsque n tends vers l'infini) après il y a des domaines où on se bat sur la complexité "précise" de l'algo (il me semble dans ce cas qu'on utilise la notation o()) ce qui est le cas ici. C'est vrai que naturellement pour moi on change pas la complexité de l'algo car j'entends O mais si on parle de la complexité o y'a pas à discuter, le complexité est bien différente (et meilleure dans la solution proposée par Aleph)

Tu ne peux pas raisonner asymptotiquement dans ce cas précis car le nombre d'opérations est en O(1).
27/08/2012, 21h34
CedricMocquillon

Complètement d'accord mais je finis par être "formaté" (je ne me préoccupe que très rarement de la complexité en o() ). Dans tous les cas, en notation O() la complexité des deux algos est identique (en temps constant comme tu l'as indiqué : O(1) ) Mais différente en o() (sans parler des aspects de stabilité numérique)
27/08/2012, 23h15
Aleph69
Citation:

Envoyé par CedricMocquillon

Dans tous les cas, en notation O() la complexité des deux algos est identique (en temps constant comme tu l'as indiqué : O(1) ) Mais différente en o() (sans parler des aspects de stabilité numérique)

Cela n'a pas beaucoup de sens de raisonner ainsi car si l'une des deux constantes explose, la différence est notoire. C'est une erreur classique quand on manipule les notations de Landau de ne pas prendre en compte les constantes et cela a conduit à pas mal d'erreurs d'interprétation en recherche mathématique, en particulier sur les estimations d'erreur et de vitesse de convergence en analyse numérique, mais je ne vais pas entrer dans les détails car cela va devenir technique et pas forcément compréhensible pour le néophyte. Je peux toutefois te faire sentir les choses sur un exemple. Si on suit ton raisonnement, les deux algorithmes suivants ont la même complexité :
Code:

1 2 3 double optimal_millionTimes(double x){return x*1e6;} double naive_millionTimes(double x) {return x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+...+x;} // ici, x apparaît 1 million de fois
Les deux algorithmes sont en O(1) mais le premier nécessite une opération flottante (multiplication) et sa constante vaut 1, tandis que l'autre en nécessite 1E6-1 (additions) et sa constante vaut 1E6-1.
28/08/2012, 08h44
CedricMocquillon

Pour revenir sur le problème de gobelin88, si ta fonction à interpoler est bien définie sur R^3 et à valeurs dans R^3 (et non pas à valeurs dans R), tu devrais regarder du côté des expressions template: lorsque tu fais un calcul (par exemple) :

Code:

cv::Vec3d c0 ( c00 + (c10-c00) * Md1 );

tu vas avoir des créations d'objets temporaires (à moins que cv n'implémente déjà les expressions template) ce qui risque d'être la partie la plus coûteuse de ta fonction.

Citation:

Envoyé par CedricMocquillon

Pour revenir sur le problème de gobelin88, si ta fonction à interpoler est bien définie sur R^3 et à valeurs dans R^3 (et non pas à valeurs dans R), tu devrais regarder du côté des expressions template: lorsque tu fais un calcul (par exemple) :

Code:

cv::Vec3d c0 ( c00 + (c10-c00) * Md1 );

tu vas avoir des créations d'objets temporaires (à moins que cv n'implémente déjà les expressions template) ce qui risque d'être la partie la plus coûteuse de ta fonction.

Je confirme que opencv utilise les expressions templates, j'ai regardé dans le code d' OpenCV:
Code:

1 2 3 4 5 6 7 8 9 10 struct CV_EXPORTS Matx_AddOp {}; struct CV_EXPORTS Matx_SubOp {}; struct CV_EXPORTS Matx_ScaleOp {}; struct CV_EXPORTS Matx_MulOp {}; struct CV_EXPORTS Matx_MatMulOp {}; struct CV_EXPORTS Matx_TOp {}; template<typename _Tp, int m, int n> class CV_EXPORTS Matx { ...
Vec est typedef de Matx ... OpenCV c genial :P

28/08/2012, 14h14
white_tentacle

Citation:

Envoyé par Aleph69

Affirmer qu'on est en présence du même algorithme me paraît exagéré : en analyse numérique, personne ne le fait et on distingue bien les deux algorithmes. Pourtant, dans ce cas, même la complexité temporelle est la même : on a juste modifié l'ordre des opérations. Un algorithme est aussi défini par son comportement en précision finie (stabilité numérique).

Peut-être que je ne fais pas assez de numérique, ce qui explique ma vision. Mais tes arguments sont convaincants :).
28/08/2012, 20h37
Aleph69

Citation:

Envoyé par white_tentacle

Peut-être que je ne fais pas assez de numérique, ce qui explique ma vision. Mais tes arguments sont convaincants :).

Un grand merci pour ton honnêteté intellectuelle! :ccool:
31/08/2012, 07h26
Joel F

Citation:

Envoyé par gobelin88

Je confirme que opencv utilise les expressions templates.

Apres au vu de la manière dont il s'en servent, ils pourraient juste ne rien faire ca serait pareil :aie:
31/08/2012, 16h58
Aleph69

[HS]
Salut Joel,
je suis tombé sur un truc intéressant à propos des E.T. dernièrement, je me suis dit que cela pourrait t'intéresser. Dans le dernier NA Digest a été annoncée la publication d'une nouvelle bibliothèque de calcul, Blaze de son petit nom, qui, au vu des benchmarks, semble plutôt efficace :
http://code.google.com/p/blaze-lib/
L'article associé chez SIAM est assez intéressant mais je l'ai juste survolé :
http://blogs.fau.de/hager/files/2012...berger2012.pdf
Il y a quand même des choses qui me chiffonnent. Je compte refaire moi-même quelques tests de vérification; je les posterai dans le forum à cette occasion.
A noter qu'il il existe un second article dans IEEE mais je n'ai pas vu de preprint.
[/HS]

Fuseau horaire GMT +2. Il est actuellement 14h07.