Discussion :

[alexIsBack]

Bonjour à tous, je vous propose un petit challenge de programmation la plus efficace possible,
le but est de partager ses connaissances et montrer à tous des méthodes de programmation performantes

la règle du jeux est la suivante, à partir d'un code simple de filtrage d'image par exemple, tout candidat peut proposer ses propres modifications
et montrer à tous le gain en performance qu'il a pu noter. présentez les gains de vitesse chiffrés et proposez un code clair (et commenté) pour que chacun puisse le comprendre aisément.

Sont autorisés tout changement du code d'origine qui ne modifie pas le résultat final, à partir de là, toute optimisation est possible
pointeurs/registres, fonction intrinsics (SSE2 etc), threads etc tout est envisageable, mais doit rester portable (linux et windows, restons en là)
les shaders peuvent aussi être proposés.

Le code simple de base est présenté ci dessous, Bon courage à tous.

l'exemple proposé ici réalise un filtrage sur une image en NIVEAUX DE GRIS (donc, pas en RGB ou autre, juste sur un calque), ligne par ligne, de la gauche vers la droite, il s'agit en fait d'un filtrage passe bas (lissage des contours) assymétrique couramment utilisé en traitement d'image.

dans le code proposé, les calculs sont effectués sur une image de taille _NBrows par _NBcolumns
le résultat final est stocké dans le tableau 'outputFrame', en entrée on a le tableau outputFrame (résultat de la frame précédente par exemple que l'on va écraser après calcul), l'image d'entrée 'inputFrame' (de même taille que la sortie) et une autre image de paramètres 'window' de même taille que l'image de sortie), une variable temporaire 'value' permet d'inclure dans le calcul du pixel courant, le résultat du calcul du pixel précédent.

TOUS LES CALCULS SONT EFFECTUES EN TYPE DOUBLE

voici le code non optimisé :

%%%%%%%%%%%%%%%%%%%%%%%%%%

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
43
44
45
46
47
#include <iostream.h>
#include <time.h>
 
unsigned int _NBcolumns=640; // nombre de colonnes des buffers
unsigned int _NBrows=480; // nombre de lignes des buffers
 
 
// Entry point
int main(int argc, char *argv[])
{
 
// buffers d'entrée et de sortie
double outputFrame[480][640], inputFrame[480][640], windowfilter[480][640];
// variables/buffers utilisés dans les boucles:
double value, tau=10.0;
unsigned int IDrow, IDcolumn, NBloops=100;
 
cout<<"loop started"<<endl;
 
int startTime=clock();
//appel de la fonction de filtrage 10 fois
for (unsigned int i=0; i<NBloops; ++i)
	// def des variables de taille des buffers
 
 
{
 
	/* PARTIE A OPTIMISER */
 
	// boucle appelée pour toute nouvelle image d'entrée (inputFrame) on retyrouve le code suivant :
   for (IDrow=0; IDrow <_NBrows;  ++IDrow)
   {          
        value=0; // initialize la variable pour chaque nouvelle ligne traitée
          for (IDcolumn=0; IDcolumn<_NBcolumns ; ++IDcolumn)
       {
           value = outputFrame[IDrow][IDcolumn]*tau + inputFrame[IDrow][IDcolumn] +  windowfilter[IDrow][IDcolumn]* value;
           outputFrame[IDrow][IDcolumn] = value;
       }
   }
 
   /* FIN DE LA PARTIE A OPTIMISER  */
}
 
int endTime=clock();
cout<<"filtering finished, time elapsed="<<(endTime-startTime)/(NBloops)<<"clocks"<<endl;
return 0;
}

%%%%%%%%%%%%%

merci pour vos contributions, pour toute les personnes intéressés par l'optimisation de code et les novices désireux de progresser (moi compris)

++
ALex :

[Volune]

Concept intéressant.
Bien que l'énoncé ne soit pas très clair, et le code incomplet. Il aurait été appréciable de voir les définitions des variables/constantes. Tout comme avoir un programme de test pour évaluer les performances des solutions proposées.

C'est dommage qu'en lisant tes précédants messages, j'ai la désagréable sensation que ce n'est là qu'une manière détournée de demander aux lecteurs du forum de te faire ton travail ...


Et en passant :

[alexIsBack]

salut, j'ai remis à jour certaines parties de l'idée.

j'utilise ce code en ce moment même, pour mes programmes 'amateurs', mais comme moi et bien d'autres personnes ne sommes pas des développeurs expérimentés, voila l'occasion de partager ses connaissances, chacun peut y trouver son compte, ce forum se veut pédagogique/informatif et que chacun trouve là de quoi améliorer son code/progresser.

Avis aux intéressés

++
Alex

[moldavi]

'exemple proposé ici réalise un filtrage sur une image, ligne par ligne, de la gauche vers la droite, il s'agit en fait d'un filtrage passe bas (lissage des contours) assymétrique couramment utilisé en traitement d'image.

Salut.

C'est intéressant comme challenge.

Si tu travailles sur des pixels, donnes le format aussi (RGBA?). Vu que c'est du traitement d'image, je ferais faire le travail par la carte graphique en utilisant les pixels shaders. Mais bon tout dépend du contexte, et je trouve que le tien n'est pas bien définit:

par exemple, tu devrais donner un code complet, compilable qui incluerait les tests de performance (un timer genre Queryperformancecounter) et les conditions de test (processeur, ram, etc...). Il n'y aurait plus qu'à modifier la boucle.

[alexIsBack]

j'ai remis à jour le message de base, cela convient il mieux?
faut il que je relance un nouveau thread ou on reste sur celui là?
++

[Alp]

Moi je rejoins le premier avis, le coup du j'aimerai qu'on améliore mon code, mais bon
Et puis des balises code ne seraient pas de trop en effet!

[Volune]

j'ai remis à jour le message de base, cela convient il mieux?
faut il que je relance un nouveau thread ou on reste sur celui là?
++

Ajoute la balise code dans le message de base
Je ne pense pas qu'il faille ouvrir un nouveau thread, et ça ressemble d'avantage à un challenge maintenant :p

Edition/pour en dessous :

[alexIsBack]

salut, bon, pour info, ce code je l'utilise, mais entre autre j'essaye d'apprendre et si ca sert à d'autres que moi, c'est bon pour tout le monde.

le premier essai, le plus efficace jusque là était de déclarer la valiable 'value' en register, ca me permet d'avoir un gain en vitesse de 2 ce qui est déjà pas mal, apparemment, ca permet de déclarer cette variable dans le registre du proc, donc, accès plus rapide etc

Code :

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

=> 'register double value;' au lieu de 'double value;'

mais si on met plus de variables en register, ca ralentit ...certainement du au fait que les registres sont vite remplis (il y en a peu, et l'OS et mange une bonne partie aussi)

pour info, j'ai essayé aussi avec les fonctions intrinsics avec par exemple pour un code similaire :

avec le

Code :

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

#include <emmintrin.h>

voila le code utilisé, ca permet de charger 2 données au format double dans les registres du pentium 4 et on fait les mêmes opérations en parallèles sur ces 2 données indépendantes, mais perso, c'est plus lent avec cet essai, donc, je ne dois pas avoir la bonne stratégie, et si quelqu'un voit l'astuce, oui, je suis preneur et les intéressés aussi bien évidemment.

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
 
       // déclaration des variables/registres qui vont contenir 2 variables au format double pour effectuer 2 opérations en parallèle
       __m128d  currentPixel, tempValue, oldValue;
	__m128d Va,  Vgain, Vtau;
	Va=_mm_set1_pd(a); //charge le vecteur avec 2 variables idntiques égales à a
	Vgain=_mm_set1_pd(gain);//charge le vecteur avec 2 variables idntiques égales à gain
	Vtau =_mm_set1_pd(tau);//charge le vecteur avec 2 variables idntiques égales à gain
	double returnData[2]; // un tableau à "2 cases" doubles qui servira à récupérer les données après calcul
 
	register unsigned int firstloopSTOP=_NBrows-1;  // le mot register indiqu au compilateur qu'il serait préférable que cette variable soit stockée en registre...si c'est possible
 
 
	for (IDrow=0; IDrow<firstloopSTOP ; IDrow+=2 ) // on va de 2 lignes en 2 lignes maintenant
	{	
		// set init value
		//value=0;
		tempValue=_mm_setzero_pd(); // on initialise la double valriable à 0
 
		for (IDcolumn=0; IDcolumn<_NBcolumns ; ++IDcolumn)
		{
			// pack to values : __m128d  _mm_set_pd( double x, double y ); => méthode pour remplir le vecteur par 2 valeurs type double
			oldValue = _mm_set_pd( outputFrame[IDrow][IDcolumn], outputFrame[IDrow+1][IDcolumn]);
			currentPixel = _mm_set_pd(inputFrame[IDrow][IDcolumn], inputFrame[IDrow+1][IDcolumn]);
			// calcul du filtre=> j'ai tout mis d'un coup ensemble, quelle est la meilleure méthode?
			tempValue = _mm_add_pd(currentPixel,_mm_add_pd(_mm_mul_pd(Vtau, oldValue), _mm_mul_pd(Va, tempValue)));
			//on récupère/reconvertit les données calculées au format double
			_mm_store_pd (returnData, tempValue); //write result in the buffer
// finalement, on réécrit dans le buffer de sortie...hem, ca en fait des transfert mémoire, ca devient lourd, il doit y avoir moyen de faire mieux...
			outputFrame[IDrow][IDcolumn]=returnData[0];
			outputFrame[IDrow+1][IDcolumn]=returnData[1];
 
 
// ancienne version de code simple
//value = outputFrame[IDrow][IDcolumn]*tau + inputFrame[IDrow][IDcolumn] +  a* value;
			//outputFrame[IDrow][IDcolumn] = value;
		}
	}

Pour finir, une petite remarque concernant "tu veux que l'on te fasse ton travail", remarque que je ne prend pas mal mais que je tiens à clarifier, restons positifs et constructifs

=> 1. c'est du code pour mon propre compte amateur, donc, c'est de la curiosité de nouvelles connaissances et non pas "mon prof m'a dit de faire ci et ca alors fate le pour moi"... d'ailleurs, je ne suis plus étudiant mais je n'ai pas perdu ma soif de connaissances
=> 2. si ca peut servir à d'autres personnes que moi c'est parfait, tout le monde en profite et PROGRESSE, ce qui est mon but aussi.

=>3. le fait de proposer ceci sous forme de challenge permet à tous d'apporter sa contribution de manière un peu plus ludique et c'est bien le but

@++

[Matthieu Brucher]

Intéressant.
Mais je citerai Sutter qui disait qu'il vaut mieux ne pas optimiser que mal optimiser. Donc je rajouterai une règle à ton exercice, celle de justifier l'optimisation par des chiffres. Et ne pas oublier de garder le code clair et lisible.

[alexIsBack]

effectivement, je modifie les règles