[C++]vitesse et optimisation

Version imprimable

18/03/2005, 11h46
yanndublanche

[C++]vitesse et optimisation

Bonjour,

Je suis en train d'essayer d'optimiser au maximum mon code et de l'accelerer le plus possible (en utilisant Visual C++) et pour cela j'aurai certaines questions a vous poser:
- entre * et ->
pour acceder a un element d'un pointeur, vaut il mieux faire (*toto).getName() ou bien toto->getName()?

- affectation dans une map
vaut il mieux faire un maMap[key] = value ou maMap.insert(pair<key, value>(key, value))?

- stockage dans une map ou un vecteur
vaut il mieux stocker un element ou un pointeur sur un element dans une map ou un vecteur?

- stockage
quels sont les structures de donnees a privilegie pour accelerer le programme (map, hashmap, vector, set, list, array....)?

Merci pour votre aide et vos conseils

Yann
18/03/2005, 11h54
rolkA

Re: [C++]vitesse et optimisation

Salut.

Citation:

Envoyé par yanndublanche

Je suis en train d'essayer d'optimiser au maximum mon code et de l'accelerer le plus possible (en utilisant Visual C++)

... Alors tes optimisations, si tu ne changes aucun algorithme ni méthode générale d'implémentation, seront négligeables par rapport aux optimisations de Visual C++. Pour savoir comment accélérer ton programme, tu dois savoir ce qui prend le plus de temps, et travailler uniquement sur "cette fichue fonction qui prend 98% du temps".

Pour le stockage, çà dépend ce que tu veux faire: une list est meilleure qu'un vector si tu fais beaucoup de suppressions et d'ajouts.. Un vector sera meilleur qu'une list si tu as besoin d'un accès aléatoire (récupérer le 3000ème élément, puis le 40ième, puis le 20ième, etc). Une hastable est intéressante si tu as beaucoup d'enregistrements (> 1000)... Bref il n'y a pas de solution plus rapide "dans l'absolu", car si c'était le cas, tu te doutes bien que ce serait la seule disponible...
18/03/2005, 12h12
Laurent Gomila

Citation:

1 - entre * et ->
pour acceder a un element d'un pointeur, vaut il mieux faire (*toto).getName() ou bien toto->getName()?

2- affectation dans une map
vaut il mieux faire un maMap[key] = value ou maMap.insert(pair<key, value>(key, value))?

3- stockage dans une map ou un vecteur
vaut il mieux stocker un element ou un pointeur sur un element dans une map ou un vecteur?

4- stockage
quels sont les structures de donnees a privilegie pour accelerer le programme (map, hashmap, vector, set, list, array....)?

1- Absolument aucune, c'est juste une histoire de syntaxe.

2- Map.insert je pense. La version avec opérateur [] va créer une valeur par défaut puis la réaffecter. Mais bon, on parle de pouillièmes là...

3- Ca n'a pas la même utilité. Une map est une table associative, et va donc associer une clé à chaque élément. Une map est également triée selon les clés et ne comporte pas de doublon.

4- Tout dépend des besoins... Si c'était si simple il n'y aurait pas autant de structures de données différentes.

Bon mais ce n'était que pour préciser, tu ne devrais pas t'embêter avec ce genre de considérations. Tu auras bien d'autres choses à optimiser avant ça.
18/03/2005, 12h18
yanndublanche

Citation:

3- stockage dans une map ou un vecteur
vaut il mieux stocker un element ou un pointeur sur un element dans une map ou un vecteur?

J'ai mal pose ma question, je voulais savoir si il vaut mieux mettre l'element ou le pointeur.

Citation:

Bon mais ce n'était que pour préciser, tu ne devrais pas t'embêter avec ce genre de considérations. Tu auras bien d'autres choses à optimiser avant ça.

Le probleme est que j'ai deja beaucoup optimiser et que je ne vois plus trop quoi faire.

Merci

Yann
18/03/2005, 12h29
Laurent Gomila

Citation:

Envoyé par yanndublanche

J'ai mal pose ma question, je voulais savoir si il vaut mieux mettre l'element ou le pointeur.

Etant donné que le vecteur effectue des recopies, si c'est vraiment des gros objets tu peux peut-être gagner avec des pointeurs.

Citation:

Envoyé par yanndublanche

Le probleme est que j'ai deja beaucoup optimiser et que je ne vois plus trop quoi faire.

A mon avis ce n'est pas ce genre de consideration qui ralentit ton programme... As-tu fais quelques mesures de performances pour isoler les fonctions qui prennent le plus de temps ? As-tu vérifié tes algorithmes ? C'est quel genre d'application ?
18/03/2005, 12h30
Ti-R

La plus grosse optimisation, l'architecture du programme.

Je dirais que parfois éviter des listes déjà toutes faites, si tu as des besoins bien spécifiques et que tu peux écrire exactement pour.... par exemple, un tableau avec un pointeur dessus… rien de + rapide !

Citation:

C'est quel genre d'application ?

C'est une application de simulation d'evenement stockastique.
Mon algorithme semble optimise donc il faut juste maintenant essayer de gagner quelques secondes sur une simu de quelques minutes ce qui representera quelques heures ensuite vu que nos simulations finales prennent plusieurs jours
J'ai fait des profiles avec AQTime et il semble que seul 2 ou 3 fonctions prennent quasiment tout le temps de simulations mais je ne vois pas trop comment l'optimiser.

Voici la premiere fonction (150/500):

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
unsigned int* getEntityCopyNumber(string a_entityName){
    vector<Entity*>::iterator entityIter;
    for(entityIter = m_entities.begin(); entityIter != m_entities.end(); entityIter++){
        if(*((*entityIter)->getEntityName()) == a_entityName){
            return((*entityIter)->getCopyNumberPtr());
        }
    }
    assert(false);
}
 
bool getEntityCopyNumber(string a_entityName, unsigned int* *a_entityCopyNumber){
    vector<Entity*>::iterator entityIter;
    for(entityIter = m_entities.begin(); entityIter != m_entities.end(); entityIter++){
        if(*((*entityIter)->getEntityName()) == a_entityName){
            *a_entityCopyNumber = &(*((*entityIter)->getCopyNumberPtr()));
            return true;
        }
    }
    return false;
}

Voici la seconde (140/500):

Code:

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
double DimensionalVoxelElement::evalPropensity(Event* veIter, double a_time, LatticeModel& a_latticeModel){
	// Iterator of propensity
	Expression::const_iterator node = veIter->getPropensityBegin();
 
	// Init value stack
	int top(0);
	int top2(0);
 
	while(node->m_type != ExprNode::END){
		switch(node->m_type){
			case ExprNode::CONSTANT:
			{
				if(top == c_propensitystackSize)
					throw;
				propensitystack[top++] = node->m_constant;
				break;
			}
			case ExprNode::UNARY_OP:
			{
				top--;
				if(top < 0)
					throw;
				switch(node->m_unaryOp){
					case ExprNode::DGRAD:
					{
						assert(veIter->getIsDiffusion());
						if(veIter->getIsExact()){
							// Accuracy High
							propensitystack[top] = propensitystack[top]*(veIter)->getNeighbourNumber();
						}
						else{
							// Accuracy Low
							vector<DimensionalVoxelElement*>::iterator vdveIter;
							unsigned int tmp = propensitystack[top];
							propensitystack[top] = 0;
							Expression::const_iterator oldnode = node;
							oldnode--;
							for(vdveIter = (veIter)->getNeighbourBegin(); vdveIter != (veIter)->getNeighbourEnd(); vdveIter++){
								unsigned int dest = *((*vdveIter)->getEntityCopyNumber(oldnode->m_entityRef));
								if(tmp > dest){
									propensitystack[top] += (tmp - dest);
								}
							}
						}
						break;
				}
				case ExprNode::UNARY_MINUS:
					propensitystack[top] = -propensitystack[top];
					break;
				case ExprNode::EXP:
					propensitystack[top] = exp(propensitystack[top]);
					break;
				case ExprNode::LOG:
					propensitystack[top] = log(propensitystack[top]);
					break;
				case ExprNode::SIN:
					propensitystack[top] = sin(propensitystack[top]);
					break;
				case ExprNode::COS:
					propensitystack[top] = cos(propensitystack[top]);
					break;
				case ExprNode::SQRT:
					propensitystack[top] = sqrt(propensitystack[top]);
					break;
				case ExprNode::HSTEP:
					assert(propensitystack[top] == 0 || propensitystack[top] == 1);
					break;
				default:
					throw;
						}
						top++;
						break;
			}
			case ExprNode::VOXELENTITYREF:
			{
				if(top == c_propensitystackSize)
					throw;
 
				assert(node->m_voxelRef == m_dimensionalVoxelElement_name);
				int counter = 0;
				for(int i = 0; i < top2; i++){
					if(entities_in_expr[i]->m_entityPtr == node->m_entityPtr){
						counter++;
					}
				}
				entities_in_expr[top2++] = node;
				assert(top2 < 5);
 
				// Search the number of species
				propensitystack[top++] = *(node->m_entityCopyNumberPtr) - counter;
				break;
			}
			case ExprNode::STD_VARIABLE:
			{
				if(top == c_propensitystackSize)
					throw;
				switch(node->m_varIdx){
					case STDPARM_TIME:
						propensitystack[top++] = a_time;
						break;
					case STDPARM_LATTICEUNIT:
						propensitystack[top++] = a_latticeModel.getLatticeUnit() * (1e-5);
						break;
					case STDPARM_LATTICEUNIT_UM:
						propensitystack[top++] = a_latticeModel.getLatticeUnit();
						break;
					case STDPARM_NA:
						propensitystack[top++] = N_AVOGADRO;
						break;
					case STDPARM_PI:
						propensitystack[top++] = PI;
						break;
					default:
						throw LatticeModelException(LatticeModelException::PARAMETER_UNDEFINED);
				}
				break;
			}
			case ExprNode::BINARY_OP:
			{
				top--;
				if(top < 1)
					throw;
				switch(node->m_binaryOp){
					case ExprNode::PLUS:
						propensitystack[top-1] += propensitystack[top];
						break;
					case ExprNode::MINUS:
						propensitystack[top-1] -= propensitystack[top];
						break;
					case ExprNode::TIMES:
						propensitystack[top-1] *= propensitystack[top];
						break;
					case ExprNode::DIVIDE:
						propensitystack[top-1] /= propensitystack[top];
						break;
					case ExprNode::POWER:
						if(propensitystack[top] == 2.0)
							propensitystack[top-1] *= propensitystack[top-1];
						else
							propensitystack[top-1] = pow(propensitystack[top-1], propensitystack[top]);
						break;
					default:
						throw;
				}
				break;
			}
			default:
			{
				cout << "Throws: no suitable node\n" << endl;
				throw;
			}
		}
		node++;
	}
	return propensitystack[0];
}

Merci encore pour vos conseils,

Yann

18/03/2005, 12h51
rolkA

Règle AQTime pour qu'il profile ligne par ligne, pour savoir quelles lignes prennent le plus de temps dans les fonctions ;) ("Full check by lines" dans le Performance Profiler)
18/03/2005, 12h57
yanndublanche

Citation:

Envoyé par rolkA

Règle AQTime pour qu'il profile ligne par ligne, pour savoir quelles lignes prennent le plus de temps dans les fonctions ;) ("Full check by lines" dans le Performance Profiler)

Je suis desole mais je n'arrive pas a trouver cette option. Tu utilises quelles version d'aqtiime et comment as tu trouve l'option?
18/03/2005, 13h01
rolkA

Mais c'est moi qui suis désolé :wink:
Sur la page principale du Performance Profiler, j'ai ceci avec AQTime 4 :

http://membres.lycos.fr/rolka/pics/aqtime.JPG

Ceci permet d'ouvrir chaque source à partir d'AQTime et d'obtenir un affichage avec le pourcentage pris par chaque ligne sur le temps d'exécution de la fonction dans laquelle se trouve la ligne.
18/03/2005, 13h22
yanndublanche

Citation:

Envoyé par rolkA

Mais c'est moi qui suis désolé :wink:
Sur la page principale du Performance Profiler, j'ai ceci avec AQTime 4 :

http://membres.lycos.fr/rolka/pics/aqtime.JPG

Ceci permet d'ouvrir chaque source à partir d'AQTime et d'obtenir un affichage avec le pourcentage pris par chaque ligne sur le temps d'exécution de la fonction dans laquelle se trouve la ligne.

Merci beaucoup, je n'avais jamais fait tres attention a cette option. Je vais la tester maintenant, mais j'ai peur que le profiling soit beaucoup plus long, non?
18/03/2005, 13h52
Troll

Pour la première fonction (La fonction de recherche), je te suggère de remplacer ton vector (vector<Entity*>) par une map (map<string,Entity*>

La map implémente une fonction de recherche sur les clef qui est de l'ordre de log de N alors que ta recherche linéaire sur ton vector est potentielement N.

Evidement il y a le revert de la médaille : l'insertion dans une map est plus couteuse(réorganisation) que le push_back d'un vecteur.
Mais si tu fais beaucoup de recherches, privilégie la map, tu gagneras beaucoup de temps.
18/03/2005, 13h54
yanndublanche

Citation:

Envoyé par Troll

Pour la première fonction (La fonction de recherche), je te suggère de remplacer ton vector (vector<Entity*>) par une map (map<string,Entity*>

La map implémente une fonction de recherche sur les clef qui est de l'ordre de log de N alors que ta recherche linéaire sur ton vector est potentielement N.

Evidement il y a le revert de la médaille : l'insertion dans une map est plus couteuse(réorganisation) que le push_back d'un vecteur.
Mais si tu fais beaucoup de recherches, privilégie la map, tu gagneras beaucoup de temps.

J'avais essaye une fois mais je peux reessayer. Le probleme c'est que mon vecteur a une taille d'une dizaine d'element environ donc est ce que c'est vraiment bien d'utiliser une map?
18/03/2005, 14h05
Troll

En effet, si tu as peu d'éléments le gain ne sera peut-être pas très intéressant.

Déjà le problème du coût de l'insertion devient négligeable, pour la recherche je ne sais pas trop;
Comme tu passes beaucoup de temps dans cette fonction, ça vaut le coup d'essayer ! :wink:

Est ce que AQTime donne le nombre de passage dans ces méthodes.
Le problème est peut-être dû au fait qu'elles sont appelé trop souvent...
18/03/2005, 14h44
Laurent Gomila
Toi qui cherchait de petites optimisations, en voici quelques unes (et encore, celles-ci sont déjà plus couteuses que celles que tu citais au début :wink:) :
Code:

1 2 unsigned int* getEntityCopyNumber(string a_entityName) bool getEntityCopyNumber(string a_entityName, unsigned int* *a_entityCopyNumber)
Toujours prendre les gros paramètres par référence constante, pour éviter une recopie inutile.

Code:

entityIter++

++entityIter sera potentiellement plus rapide sur des types non primitifs.
Code:

1 2 if(*((*entityIter)->getEntityName()) == a_entityName){ return((*entityIter)->getCopyNumberPtr());
Récupérer *entityIter dans une variable temporaire une bonne fois pour toute permettrait d'y gagner un peu je pense.
Code:

1 2 if(top == c_propensitystackSize) throw;
Si réellement ton code doit être très très très rapide, à la limite tu peux désactiver le mécanisme d'exceptions. Enfin à voir, peut-être que ça t'embêterait pour rien du tout. (d'ailleurs, tu throw quoi là ? throw tout seul est utilisé pour relancer une exception précédemment rattrapée)

Code:

exp log sin ...

Si ces fonctions prennent trop de temps et que tu ne souhaites pas une précision au pouillème, tu peux utiliser des tables précalculées.

Après effectivement il faut voir si certaines structures de données ne seraient pas plus efifcaces que d'autres, et surtout voir encore plus précisément ce qui ralentit ton appli.
18/03/2005, 15h15
yanndublanche
Citation:
Code:

1 2 unsigned int* getEntityCopyNumber(string a_entityName) bool getEntityCopyNumber(string a_entityName, unsigned int* *a_entityCopyNumber)

Toujours prendre les gros paramètres par référence constante, pour éviter une recopie inutile.
tu passerais donc getEntityCopyNumber(const string a_entityName, unsigned int* *a_entityCopyNumber) ?

Citation:

Code:

entityIter++

++entityIter sera potentiellement plus rapide sur des types non primitifs.

je ne savais pas qu'il y avait une reel difference entre ces 2 versions
18/03/2005, 15h18
rolkA
Citation:
Envoyé par yanndublanche

Citation:

Code:

1 2 unsigned int* getEntityCopyNumber(string a_entityName) bool getEntityCopyNumber(string a_entityName, unsigned int* *a_entityCopyNumber)

Toujours prendre les gros paramètres par référence constante, pour éviter une recopie inutile.

tu passerais donc getEntityCopyNumber(const string a_entityName, unsigned int* *a_entityCopyNumber) ?
Non, const string & a_entityName...
18/03/2005, 15h22
rolkA
Citation:

Envoyé par yanndublanche

Citation:

Code:

entityIter++

++entityIter sera potentiellement plus rapide sur des types non primitifs.

je ne savais pas qu'il y avait une reel difference entre ces 2 versions

La version postfixe crée une copie.
Par exemple, à la fin du code suivant, a vaut 2 et b vaut 3:
Code:

1 2 3 int a; int b = 2; a = b++;
Pour réaliser çà, le compilo fait:
Code:

1 2 3 4 5 int a; int b = 2; int tempo = b; ++b; a = tempo;
Maintenant, imagine que ce sont des objets :wink:
18/03/2005, 23h46
Luc Hermitte

Côté optimisation, premier truc à changer : la référence constante pour les paramètres. Ensuite, tous ces begin() end() dans les boucles se remplacent par des find_if est autres algos génériques.

Ensuite, bien plus important: la fonction est beaucoup, beaucoup trop grosse. Découpe là. En ce qui me concerne un truc pareil n'est pas maintenable.