Discussion :

[yanndublanche]

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

[rolkA]

Salut.

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...

[Laurent Gomila]

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.

[yanndublanche]

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.

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

[Laurent Gomila]

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.

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 ?

[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 !

[yanndublanche]

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 :

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
 
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 :

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
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

[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)

[yanndublanche]

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?

[rolkA]

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



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.

[yanndublanche]

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



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?

[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.

[yanndublanche]

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?

[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 !

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...

[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 ) :

Code :

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

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 :

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

entityIter++

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

Code :

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

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 :

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

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 :

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

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.

[yanndublanche]

Code :

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

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) ?

Code :

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

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

[rolkA]

Code :

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

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...

[rolkA]

Code :

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

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 :

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

1
2
3
int a;
int b = 2;
a = b++;

Pour réaliser çà, le compilo fait:

Code :

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

1
2
3
4
5
int a;
int b = 2;
int tempo = b;
++b;
a = tempo;

Maintenant, imagine que ce sont des objets

[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.