Discussion :

[bertry]

Salut à tous,

J'ai récemment créé un classe ( en natif ) dont l'un des membres donnée est un tableau 2d du type vector<vector<double> >. L'une des fonction membre fais l'addition membre à membre de trois de ces tableaux et là : c'est horriblement lent!

Dans mes essais, le tableau fais environ 500*400, et le traitement de celui-ci prend facilement0,2 à 0,3 secondes!!. Et il faut réitérer le calcul des centaines et des milliers de fois! ( C'est une simulation de diffusion osmotique en milieux 2d, pour chaque 'pixel' on détermine quelle quantité de 'produit' est ( ou pas ) transférée aux 'pixels' voisins )

Puisque le PC sur lequel je fais tourner ce code est capable de faire tourner un simulateur de vol en temps réel, j'imagine que le problème ne vient pas du PC mais du programmeur!

Quels sont les "trucs et astuces" pour pouvoir demander au PC de traiter plus rapidement une partie du code. J'ai lu sur certains posts des histoires de "cache" : un développer de jeux disait qu'il faut savoir l'utiliser pour que ça tourne vite, mais ça dépasse mes connaissances. Pouvez-vous me mettre sur la ou les bonnes pistes?

PS : Le PC en question est monoprocesseur, inutile donc de me parler de parallélisation

[screetch]

un vecteur de vecteur est horriblement lent.
montre le code qui fait l'addition pour avoir plus d'idées.
Dans vector il y a une fonction "resize" qui pourrait t'aider aussi:

Code :

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

1
2
3
4
5
6
7
8
9
10
vector<vector<double> > result;
result.resize(input.size());
for(int i = 0; i < input1.size(); ++i)
{
  result[i].resize(input[i].size());
  for(int j = 0; j < input[i].size(); ++j)
  {
    result[i][j] = input[i][j] + input2[i][j];
  }
}

c'est deja un début.

[bertry]

un vecteur de vecteur est horriblement lent

Alors que puis-je utiliser à la place d'un vecteur de vecteur?
Pourquoi 'resize'?

Ca fait plusieurs jours que je met au point et que j'optimise mon code ( ce morceau n'en est qu'une partie ). Mais j'ai commis une grosse erreur de débutant : c'est de ne pas faire un template dès le début ! Je me rends compte en testant mon programme que je n'ai pas forcément besoin de la précision d'un double. Je réécris actuellement ma class sous forme de template

Voici des extraits : la déclaration de mon class template et la définition de la fonction Diffuse:

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
template <typename T, typename U> class Terrain
{
protected:
	unsigned int Width;
	unsigned int Height;
	std::vector<std::vector<T> > Sol;
	T CoefficientDeDiffusion;
	T CoefficientDEvaporation;
public:
	Terrain ( const unsigned int l, const unsigned int h );
	Terrain ( const Terrain<T,U>& ter );
	~Terrain ();
	Terrain<T,U>& operator = ( Terrain<T,U> &ter );
 
	void affiche () const;
 
	void SetSol ( const unsigned int l, const unsigned int h, T valeur );
	void SetCoefficientDeDiffusion ( T coeffDiff );
	void SetCoefficientDEvaporation ( T coeffEvap );
 
	void Diffuse ( U dT );
};
 
template <typename T, typename U> void Terrain<T,U>::Diffuse ( U dT )
{
	std::vector<std::vector<T> > flux;
	std::vector<std::vector<T> > pertes;
	T courant;			//Valeur du pixel courant
	T vh, vb, vg, vd;	//Valeurs des pixels voisins
	T p, pTempo;			//Variables auxiliaires
	const T zero = static_cast<T>( 0 );
 
	//flux et pertes sont initialisée pour faire sx de large et sy de haut
	for ( unsigned int y = 0; y < Height; y++ )
	{
		flux.push_back ( std::vector<T> ( Width,  zero ) );
		pertes.push_back ( std::vector<T> ( Width,  zero ) );
	}
 
	//Calcule de diffusion
	for ( unsigned int y = 0; y < Height; ++y )
	{
		for ( unsigned int x = 0; x < Width; ++x )
		{
			vh = zero;	vb = zero;	vg = zero;	vd = zero;	p = zero;
			courant = Sol[y][x];
 
			//Calcul de flux : ce que gagne chaques pixels voisins
			if ( y )			//Si on est pas à la première ligne
			{
				vh = Sol[y-1][x];
				if ( courant > vh )
				{
					pTempo = dT * CoefficientDeDiffusion * ( courant - vh );
					flux[y-1][x] = pTempo;
					p += pTempo;
				}
			}
			if ( y < Height-1 )	//Si on est pas à la dernière ligne
			{
				vb = Sol[y+1][x];
				if ( courant > vb )
				{
					pTempo = dT * CoefficientDeDiffusion * ( courant - vb );
					flux[y+1][x] = pTempo;
					p += pTempo;
				}
			}
			if ( x )			//Si on est pas à la première colonne
			{
				vg = Sol[y][x-1];
				if ( courant > vg )
				{
					pTempo = dT * CoefficientDeDiffusion * ( courant - vg );
					flux[y][x-1] = pTempo;
					p += pTempo;
				}
			}
			if ( x < Width-1 )	//Si on est pas à la dernière colonne
			{
				vd = Sol[y][x+1];
				if ( courant > vd )
				{
					pTempo = dT * CoefficientDeDiffusion * ( courant - vd );
					flux[y][x+1] = pTempo;
					p += pTempo;
				}
			}
 
			//Calcul de pertes : ce que perd ce pixel
			pertes[y][x] = p + dT * CoefficientDEvaporation;
		}
	}
 
	//Calcul final : On additionne au tableau d'origine le tableau des flux
	//				et on y soustrait celui des pertes
	for ( unsigned int y = 0; y < Height; ++y )
		for ( unsigned int x = 0; x < Width; ++x )
			Sol[y][x] += flux[y][x] - pertes[y][x];
}

[pyros]

Salut,

Première chose, débrouille toi pour organiser tes données de manière à ce qu'elles soit à la suite dans la mémoire. Par exemple, n'utilise qu'un seul tableau comme ceci:

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
 
int largeur = 500;
int hauteur = 800;
std::vector<double> tableau(largeur*hauteur);
// acceder a la valeur (i, j):
tableau[j * largeur + i];
 
// parcourir tous les points:
// Attention, la boucle du i doit être à l'interieur, de manière a ce que
// lorsque tu parcour ton tableau, tu ne fasse pas de "saut" dans la mémoire
for ( int j = 0; j < hauteur; ++j )
{
  for ( int i = 0; i < largeur; ++i )
  {
     tableau[j * largeur + i];
  }
}

C'est moins claire, mais diablement plus rapide

[screetch]

dans ton code:

Code :

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

1
2
3
4
5
	for ( unsigned int y = 0; y < Height; y++ )
	{
		flux.push_back ( std::vector<T> ( Width,  zero ) );
		pertes.push_back ( std::vector<T> ( Width,  zero ) );
	}

je parie c'est ca qui est lent
push_back peut réallouer le vector
en réallouant le vector il doit recopier tous les vector qu'il contient
c'est exactement pour ca que vector<vector> c'est nul niveau perfs
resize visait justement a éviter ca.

la différence entre float et double se fera peut etre meme pas sentir... la regle si on veut améliorer les perfs est de voir ou l'on passe du temps.
si tu ne sais pas ce qu'est un profiler:
* soit c'est le bon moment pour apprendre
* soit tu mets des timer dans ton code pour calculer combien de temps prennent les opérations

sinon tu optimises a l'aveugle et ca c'est un peu naze

[bertry]

Merci pour les réponses screetch et pyros

@Pyros : Je vais tester cette façon de procéder en tenant bien compte du fait que

la boucle du i doit être à l'interieur, de manière a ce que lorsque tu parcour ton tableau, tu ne fasse pas de "saut" dans la mémoire

, ça permettra de virer les "push_back ( std::vector<T> ( Width, zero )" sur lesquels Screetch attire mon attention

@Screetch : En effet, je ne connais pas les "profilers" ( C'est le problème quand on est autodidacte dans un domaine, on ne connais que ce dont on a eu besoin ( moi je suis ingénieur en mécanique à la base, et il y a 15 ans dans mon école, la formation en informatique était assez limitée : quelques heures de pascal tout au plus!!! ) ). Je vais tester la méthode des timers, et regarder ce qu'est un "profiler" dès que j'en ai le temps.

Merci encore à vous deux, donc.

Je coche ce post comme résolu, mais si quelqu'un a d'autres piste, qu'il n'hésite pas.