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]

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

[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