Discussion :

[SebastienLeto]

Bonjour,

Mon programme calcule pour des matrices de grande tailles (ici Q), une mise à jour de ses valeurs non nulles, via le produit d'éléments contenus dans une autre matrice R.
Q et R comptent de l'ordre de 500 lignes et 250 colonnes. Or j'utilise ce programme de nombreuses fois et je me suis rendu compte que si je souhaite obtenir un gain de temps d'exécution, il faut que j'optimise ce programme.
Avez-vous des techniques ou conseils ?
En particulier, je sais que les "if" sont à éviter, cependant je ne sais pas par quoi les remplacer. J'ai entendu parler de la possibilité d'intégrer la condition du "if" dans une boucle "for" précédente, sans succès.
Quelques valeurs :
M=252;
N=504;
GForder=8;
Code->rowDegree[i] contient des valeurs entre 3 et 5.

Merci d'avance,

Ci-dessous mon programme :

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
 
int i = 0;
	int j = 0;
	int l = 0;
	int k = 0 ;
	const int M = Code->M; 
	const int N = Code->N; 
	const int GForder = GF->M; 
 
  for ( i = 0; i < M; i++){
	  for ( l = 0 ; l < GForder; l++){
		  for ( j = 0 ; j < Code->rowDegree[i] ; j++){
			  Q[i*GForder+l][(Code->H[i][j]-1)] = Qinit[i*GForder+l][(Code->H[i][j]-1)];
			  for (k = 0; k < i ; k++){
				   if ( R[k*GForder+l][(Code->H[i][j]-1)] != 0 )
					   Q[i*GForder+l][(Code->H[i][j]-1)] *= R[k*GForder+l][(Code->H[i][j]-1)] ;
			   }
			  for ( k = i+1 ; k < M ; k++){
				  if ( R[k*GForder+l][(Code->H[i][j]-1)] != 0 )
					  Q[i*GForder+l][(Code->H[i][j]-1)] *= R[k*GForder+l][(Code->H[i][j]-1)] ;
			  }
 
		  }
	  }
 }

[Sylvain Togni]

Code :

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

1
2
3
4
		  for (k = 0; k < i ; k++){
				   if ( R[k*GForder+l][(Code->H[i][j]-1)] != 0 )
					   Q[i*GForder+l][(Code->H[i][j]-1)] *= R[k*GForder+l][(Code->H[i][j]-1)] ;
			   }

Tu peux commencer par sortir de la boucle tout ce qui ne dépend pas de k, et mettre dans une variable l'expression R[k*GForder+l][(Code->H[i][j]-1)] pour ne pas la recalculer deux fois.

[Invité]

Comme dit précédemment, essaye déjà d'utiliser davantage de variables locales dans tes boucle, (pour éviter de recalculer des gros machins comme Q[i*GForder+l][(Code->H[i][j]-1)] ), et precalcule tout ce que tu peux

En supposant que tes matrices soient des doubles, je ferais quelque chose comme ca (j'espère ne m'être pas trop trompé dans les simplifications...)

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
 
int i = 0;
int j = 0;
int l = 0;
int k = 0 ;
 
double qtemp;
double rtemp;
 
int deg;
int codehij;
int igl=0;
int kgl;
 
const int M = Code->M; 
const int N = Code->N; 
const int GForder = GF->M; 
 
  for ( i = 0; i < M; i++){
          deg=Code->rowDegree[i];
	  for ( l = 0 ; l < GForder; l++,igl++){
		  for ( j = 0 ; j < deg ; j++){
                          codehij=Code->H[i][j]-1;
                          qtemp= Qinit[igl][codehij];
                          kgl=l;
			  for (k = 0; k < i ; k++,kgl+=GForder){
                              rtemp=R[kgl][codehij];
		                if (rtemp  != 0 ) qtemp *= rtemp;
			   }
                               kgl+=GForder;
			  for ( k = i+1 ; k < M ; k++,kgl+=GForder){
                                rtemp=R[kgl][codehij];
				  if ( rtemp != 0 )
					  qtemp *= rtemp ;
			  }
                          Q[igl][codehij]=qtemp;
		  }
	  }
 }

Ca devrait déjà aller un peu plus vite... Pour aller plus loin, faudrait regarder la représentation de tes matrices, si ce sont en fait des tableaux de mémoire contigue, tu peux sans doute utiliser des pointeurs à la place des R, des QInit et des Q, et remplacer la plupart des indirections par des sommes et des déréferencements.

Encore plus loin, il faut voir si tes matrices R ont beaucoup d'éléments nuls, et si oui, utiliser une représentation différente de tes matrices...

Francois

[aoyou]

Quelque chose qui ne coûte pas cher et qui donne de bons résultats.
Laisser faire le compilo en compilant en -O3.
Il est souvent meilleur que nous celui-là pour des petites optimisations bien fines. Mais attention, si l'algorithme est mauvais à la base, le compilo n'y pourra rien.

[souviron34]

Quelque chose qui ne coûte pas cher et qui donne de bons résultats.
Laisser faire le compilo en compilant en -O3.
Il est souvent meilleur que nous celui-là pour des petites optimisations bien fines. Mais attention, si l'algorithme est mauvais à la base, le compilo n'y pourra rien.

c'est vrai, mais au vu de ces calculs de boucles et d'indices et d'adresses, il y a déjà du boulot à faire...

en plus, c'est un bon exercice pour voir ce qui accèlère ou ralenti...

[SebastienLeto]

J'ai apporté des corrections à mon algorithme pour tenir compte de vos remarques :
*variables locales
*précalcul
Voila ce que ça donne :

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
 
 
	int i = 0;
	int j = 0;
	int l = 0;
	int k = 0 ;
	int igl = 0;
	int kgl = 0;
	int hij = 0;
	const int M = Code->M;
	const int N = Code->N;
	const int GForder = GF->M;
	const int *rowDegree = Code->rowDegree;
	const int **H = Code->H;
 
	double qtemp = 0;
	double rtemp = 0;
 
  for ( i = 0; i < M; i++){
	  for ( l = 0 ; l < GForder; l++){
		  igl = i*GForder+l;
		  for ( j = 0 ; j < rowDegree[i] ; j++){
			  hij = H[i][j]-1;
			  qtemp = Qinit[igl][hij];
			  for (k = 0; k < i ; k++){
				  kgl = k*GForder+l;
				  rtemp = R[kgl][hij];
				  if ( rtemp != 0 )			  
					  qtemp *= rtemp ;	  
			   }
			  for ( k = i+1 ; k < M ; k++){
				  kgl = k*GForder+l;
				  rtemp = R[kgl][hij];
				  if ( rtemp != 0 )
					 qtemp *= rtemp ;
			  }
			  Q[igl][hij] = qtemp ;
 
		  }
	  }
 }
}

Ceci étant dit, j'ai utilisé un timer pour chronométrer les temps de calcul, avant et après modifications, et je n'ai constaté aucune différence !

Pour ce qui est de l'allocation de mes matrices, elles suivent le modèle 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
 
	Q = (double**) calloc(nbLine,sizeof(double*));
  if(Q == NULL){
	  printf("Error in Allocation of Q %s:%d\n",__FILE__,__LINE__);
	  exit(-1);
  }
	Q[0] = (double*) calloc(nbColumn*nbLine,sizeof(double));
   if(Q[0] == NULL){
	  printf("Error in Allocation of Q[0] %s:%d\n",__FILE__,__LINE__);
	  exit(-1);
   }
   for(i = 1; i < nbLine ; i++){
		Q[i] = Q[0] + i*nbColumn;
   }

Je n'ai pas compris la remarque au sujet des pointeurs et déférencements, s'il y a quelque chose à lire, je suis prêt à le faire, pour peu que tu m'indiques ce dont il s'agit.

Au sujet du compilateur, je travaille sous Visual C++, et dans les options du projet, j'avais déjà selectionné comme options :
* Maximize Speed /O2
* Favor Fast Code
Je ne trouve pas de /O3. Où est-ce situé ?

Pour ce qui est de la représentation des matrices, en effet, elles contiennent de nombreux zéros, ceci étant, mon algorithme ne fait les calculs que sur les éléments non nuls dans la matrice. C'est-à-dire que je connais à l'avance les colonnes contenant des éléments non nuls dans mes matrices Q et R. Ma boucle sur les colonnes (j allant de 0 jusqu'à rowDegree) tient compte de cela.

Je vous remercie pour vos commentaires. Voyez-vous d'autres pistes pour optimiser le code ?

[Médinoc]

Il n'y a pas de /O3 sous Visual: Il y a confusion avec le -O3 de gcc.

[Invité]

Je n'ai pas compris la remarque au sujet des pointeurs et déférencements, s'il y a quelque chose à lire, je suis prêt à le faire, pour peu que tu m'indiques ce dont il s'agit.

Comme tes matrices sont représentées comme des blocs contigus de mémoire (toutes les lignes écrites à la queue leu leu), tu peux, au lieu d'écrire des choses comme R[klp][hij] et d'incrémenter les indices, les représenter comme des pointeurs, que tu incrémentes.

Dans ta boucle :

Code :

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

1
2
3
4
5
for (k = 0; k < i ; k++){
	kgl = k*GForder+l;
	rtemp = R[kgl][hij];
	if ( rtemp != 0 ) qtemp *= rtemp ;	  
}

tu te déplaces verticalement de GForder lignes à chaque incrémentation de k. Si ton tableau à n_col colonnes, ca veut dire que tu te déplaces (dans ta représentation "vectorielle" de la matrice) de n_col*GForder cases, en partant de R[l][hij].

Donc, si tu écris quelquechose comme

Code :

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

1
2
3
4
 
double *r=&R[l][hij]; // ton point de départ
double *s=r+i*(ncol*GForder); // ton point d'arrivée
for(;r!=s;r+=ncol*GForder) if(*r) qtemp*= *r;

tu élimines tous les indices de tes tableaux... (et, bien sur, tu peux faire ca pour toutes tes matrices).

Maintenant, si tes matrices sont très grosses, très creuses, et contiennent beaucoup de lignes vides, tu devrais essayer de les représenter différemment. Cherche sur l'internet sous les mots "sparse matrix", et tu devrais trouver ton bonheur...

Egalement, avant de te lancer là dedans, tu ferais peut être bien d'utiliser un profileur, pour savoir exactement où le temps est passé. D'expérience, ce n'est pas toujours là où l'on croit...

Francois