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.

[diogene]

Si tes matrices sont grosses (et si l'algorithme le permet) tu peux avoir intérêt à faire varier le deuxième indice dans la boucle la plus intérieure plutôt que le premier (qui est l'adresse d'un tableau de double pour limiter les changements de tableaux dans ton calcul)

[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

[souviron34]

disons que je ne recommande pas la manière d'écrire (présentation) ci-dessus, plutôt "hackeuse" ...

Mais le principe est bien là..

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

disons que pour chaque calcul tu remplaces 2 additions et une multiplication (adrr_départ + i*taille_ligne + j) par une addition addr = adrr_précedente + 1

Et les multiplications sont assez "lentes", ou disons qu'elle ralentissent (moins que les divisions, mais quand même)

[Invité]

disons que pour chaque calcul tu remplaces 2 additions et une multiplication (adrr_départ + i*taille_ligne + j) par une addition addr = adrr_précedente + 1

Il faudrait regarder le code produit, mais il me semble que ca va plus loin... En utilisant des pointeurs que l'on incrémente et déréference (et en les utilisant dans les boucles) on réduit significativement le nombre de variables intermédiaires utilisées et de tests, ce qui réduit la longueur des boucles les plus profondes de l'algorithme.

Dans le cas d'un code un peu compliqué comme le précédent, j'aurais tendance à penser qu'on y gagne plus que sur les cycles d'exécution. Non?

Sur l'aspect hacker, je ne sais pas. Mais je suis preneur de tes commentaires. (je dois avouer que je trouve ces codes utilisant des pointeurs d'une grande élégance et clarté, donc un peu le contraire de l'idée que je me fais d'un hack, mais leur critique m'intéresse)

Edit : en relisant ca ce matin, effectivement... Souviron, un truc comme :

Code :

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

1
2
3
4
5
6
 
int step=(ncol*GForder);
double *beg=&R[l][hij]; // point de départ
double *end=beg+i*step; // point d'arrivée
double *r; // pointeur sur la matrice R
for(r=beg;r<end;r+=step) if(*r) qtemp*= *r;

trouverait il grâce à tes yeux ?

Francois

[souviron34]

eh bien, outre le fait (mais c'était pour la démo de principe) d'avoir ces lignes consécutives sans espacements, j'ajouterais que :

écrire r += ncol*GFolder est strictement équivalent (et moins lisible) que r = r + ncol*GFolder, que ça ne gâte rien de commencer une boucle par l'assignation de départ (qui est faite de toute manière et plus conforme), et que *r étant un double, un test correct est bien if (*r != 0.0) et non if (*r)....

Code :

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

for(;r!=s;r+=ncol*GForder) if(*r) qtemp*= *r;

En bref, ton écriture est sur la bonne voie de l'obfuscation...

[Invité]

Merci du retour...

Pour

que *r étant un double, un test correct est bien if (*r != 0.0) et non if (*r)....

Je suis d'accord, mais j'ai deux questions :

1- cette réprésentation des flottants en zéro n'est elle pas garantie par la norme?
2- le bon test d'égalité sur un flottant n'est il pas if(fabs(*r)<EPSILON) ?

Francois

[souviron34]

1- cette réprésentation des flottants en zéro n'est elle pas garantie par la norme?

je ne le sais pas vraiment, mais si ça l'est, c'est uniquement pour l'assignation..

Pour un test, c'est forcément faux.

De plus, un if teste une valeur logique (booléen).

2- le bon test d'égalité sur un flottant n'est il pas if(fabs(*r)<EPSILON) ?

• Primo ce serait FLT_ESPILON ou DBL_EPSILON
  
  
• Secondo, cet espilon représente la précision (pas la valeur). Attention... Dans le cas de comparaison à zéro, c'est correct. Mais le mieux à garder en mémoire est fabs(valeur - valeur_a_comparer) < DBL_EPSILON, et, vu que cette précision est en général très supérieure aux précisions rencontrées (mesures, calculs, etc), le mieux est encore de définir sa précision (relative ou absolue), par exemple 10-6, et de comparer avec ceci :
  fabs(valeur - valeur_a_comparer) < MA_PRECISION.

[SebastienLeto]

Merci pour vos réponses.
Je viens d'utiliser un profileur, et ce sont les étapes avec les "if" qui sont responsables à plus de 80% du temps d'exécution !

Je vais tenter de procéder aux changements en utilisant des pointeurs, mais il est vrai qu'à la lumière des résultats du profileur, c'est plus comment me débarasser des "if" qui va me faire réfléchir !

Je pense que je vais devoir modifier l'algorithme.

[Invité]

Pour un test, c'est forcément faux.
De plus, un if teste une valeur logique (booléen).

Ceci m'intrigue, parce que je ne crois pas que le booléen existe en C (c'est une innovation du C++), et je suis à peu près sur d'avoir utilisé sans dommage cette instruction (pas très jolie, je le reconnais) dans des programmes C.

Je suis donc allé voir le standard... (http://flash-gordon.me.uk/ansi.c.txt)

3.6.4.1 The if statement

Constraints

The controlling expression of an if statement shall have scalar type.

Semantics

In both forms, the first substatement is executed if the expression
compares unequal to 0. In the else form, the second substatement is
executed if the expression compares equal to 0. If the first
substatement is reached via a label, the second substatement is not
executed.

et l'on précise ailleurs

Integral and floating types are collectively called arithmetic
types. Arithmetic types and pointer types are collectively called
scalar types.

En fait, un if évalue l'expression entre parenthèse comme un scalaire (char, entier, flottant, ou pointeur, sans conversion implicite entre ces types), et vérifie qu'elle est non nulle. Il semblerait donc que les deux expressions

Code :

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

1
2
if(x!=0.0) 
if(x)

soient, du point de vue du standard ANSI, strictement équivalentes. Comme aucun transtypage n'est nécessaire lors de l'évaluation de if(x), elles devraient en fait générer le même code.

En revanche, le standard explique que ce n'est pas vrai pour l'instruction switch() qui nécessite un argument intégral (mais do, while et for acceptent les scalaires).

J'ai appris un truc, aujourd'hui...

Francois

[Invité]

Je vais tenter de procéder aux changements en utilisant des pointeurs, mais il est vrai qu'à la lumière des résultats du profileur, c'est plus comment me débarasser des "if" qui va me faire réfléchir !

Pour les if, il est possible que le ralentissement vienne du fait que ton code crée des défauts de cache (cache miss). Si ta boucle ne tient pas dans le cache d'instructions de ton processeur, un if va causer un rechargement de celui ci, qui le ralentit beaucoup. Normalement ton profileur doit être capable de tester cela...

Essaye les pointeurs, en raccourcissant la taille de ta boucle la plus profonde (celle sur les k, où se trouvent tes if), il est possible qu'elle tienne tout entière dans le cache, et là, ton programme ira beaucoup plus vite. (c'est un peu une règle générale, à complexité égale, la vitesse d'un algorithme dépend de la taille (en code machine) de sa boucle la plus profonde).

Francois

[Sylvain Togni]

Il semblerait donc que les deux expressions

Code :

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

1
2
if(x!=0.0) 
if(x)

soient, du point de vue du standard ANSI, strictement équivalentes.

Oui elles sont équivalentes mais la première est à privilégier pour des questions de lisibilité. La deuxième n'est qu'un hack permis par le C du au fait qu'il ne possède pas de type booléen.

[Sylvain Togni]

Merci pour vos réponses.
Je viens d'utiliser un profileur, et ce sont les étapes avec les "if" qui sont responsables à plus de 80% du temps d'exécution !

Je vais tenter de procéder aux changements en utilisant des pointeurs, mais il est vrai qu'à la lumière des résultats du profileur, c'est plus comment me débarasser des "if" qui va me faire réfléchir !

Je pense que je vais devoir modifier l'algorithme.

Si le nombre de zéros est élevé alors l'utilisation d'une matrice creuse permettra un gain substantiel.

[Invité]

La deuxième n'est qu'un hack permis par le C du au fait qu'il ne possède pas de type booléen.

Ca, c'est pas vrai. Si les créateurs du C l'avaient voulu, ils auraient aisément pu obliger, par standard, if() à prendre un argument intégral (le standard le prévoit pour switch()). Comme x!=0.0 renvoie un int, la première formulation aurait été légitime et pas la seconde.

Mais ce ne serait pas logique. En C, toute expression renvoie une valeur. x!=0.0 renvoie un entier, x (dans ce cas) un flottant. Et if() teste la nullité de son argument (pour tout type scalaire).

(De plus, si on obligeait if() à prendre un int pour argument, je soupconne que l'instruction if(0.5) serait toujours vraie, 0.5 étant converti en int, et donc égal à zéro...)

Personnellement je ne vois pas de problème de lisibilité, if(x) veut juste dire "si x est non nul, quel que soit son type". Je pense en revanche que ce genre de test est potentiellement dangereux, car la représentation flottante des nombres peut introduire des erreurs d'arrondi. Mais, si l'on va par là, il faudrait quasiment abandonner les flottants...

Francois