De la rapidité du code [Trucs & Astuces]

**lepoutho** · 02/08/2005, 17h51

j'ai fait des tests concernant mes précédents posts...
c'est vraiment que des conneries, avec le compilo de
Visual Net ça vaut vraiment pas la peine de jouer au plus
fin, perso code optimisé ou pas je mets le même temps d'execution, va
falloir changer mes habitudes ...

Bonne continuation,

**Rafy** · 04/10/2005, 20h47

Le mieux pour optimiser du code c'est d'utiliser des logiciels adaptés : AQtime est surprennant par ses résultats....
Et vous verrez qu'il n'est pas forcément utile d'optimiser un "if" ou un "for" face à des fonctions beaucoup plus gourmandes.

Je fais allusion à des fonctions qui peuvent ralentir un algorythme.
Le plus important dans la lecture d'une chaine de caractère c'est ce qu'on fait des caractères lu ! Si on écrit chaque caractère dans un fichier, que l'on ouvre le fichier à chaque passage dans la boucle qu'on écrit et qu'on referme ensuite.... Le for avec le strlen ou sans ça ne va même pas se voir... Il ne faut pas se focaliser sur des généralités, mais plutot dire je vais optimiser telle ou telle partie du code pour la rendre aussi rapide que telle autre. Et pas dire je vais optimiser ça pour que ça aille plus vite...

Pour ceux qui programme avec directX, des jeux, par exemple, ils seront d'accord avec moi qu'il faut porter ses effots d'optimisation sur la methode de rendu.... Ca ne sert strictement à rien d'optimiser une pauvre boucle qui n'est parcourue que quand on appuye sur telle touche...

Il faut privillégier ses efforts sur les boucles qui sont appellée souvent, qui sont longue (en temps d'éxectution relatif au temps total)....

**Rafy** · 04/10/2005, 20h51

La methode béton qui marche à chaque fois si on ne veut pas utiliser de logicel d'optimisation, c'est la methode dite "Du test bourin chrono".....

Tu lance ton application avec un certain algorythme, tu regarde le temps d'éxecution, tu change d'algorythme et tu donne au nouvel algorythme le même travail......
Pour plus de précisions tu fais faire différents travaux aux algorythmes, le plus rapide des algorythme est le meilleur.....
Ca marche à chaque coup, mais c'est super long....

**Rafy** · 04/10/2005, 20h57

Ceci dit pour optimiser les boucles ou tres tres tres souvent on fait des additions, des multiplications sur un nombre; il est préfèrable d'utiliser si possible les opérateurs +=, -=, *=, /= car il n'y a pas de copies...
Donc si vous faites des class de base de calculs (vecteurs, matrices) ne pas oublier ces opérateurs....
AQtime dit par exemple, dans un code comme celui ci :

Code :

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

1
2
3
4
5
6
7
8
 
int i = 1;
int j = 1;
for (int k = 0;k < 100000; ++k)
{
    i = i + 15;     // Ligne 1
    j += 15;       // Ligne 2
}

Ligne 1 : 66%
Ligne 2 : 33%

De même, il est préfèrable d'utiliser l'opérateur ++"" à l'opérateur ""++
pour des raisons de copie encore (même remarque qu'au dessus pour les class perso)

**Luc Hermitte** · 05/10/2005, 01h26

Pour les matrices et vecteurs, voir Blitz++, et dérivés comme boost.uBlas, qui profitent de la méta-progammation pour éliminer les temporaires, obtenir une sémantique de déplacement au niveau des retours, et autres calculs retardés.

Pré-incrémentation et compagnie n'avaient pas déjà été signalés ?

Sinon oui, il faut profiter des profileurs de code.

PS à délester: algorithme "vient" (façon de parler) de l'Arabe (cf Al!) et non du Grec.

**Coelacanthe** · 05/01/2006, 02h31

Ce sujet confirme que je suis tombé sur un site de fous furieux...

**Amokrane** · 05/01/2006, 13h30

Envoyé par Luc Hermitte

Pour les matrices et vecteurs, voir Blitz++, et dérivés comme boost.uBlas, qui profitent de la méta-progammation pour éliminer les temporaires, obtenir une sémantique de déplacement au niveau des retours, et autres calculs retardés.

Pré-incrémentation et compagnie n'avaient pas déjà été signalés ?

Sinon oui, il faut profiter des profileurs de code.

PS à délester: algorithme "vient" (façon de parler) de l'Arabe (cf Al!) et non du Grec.

juste un truc , Al khawarizmi est perse , pas arabe non ?

**Rafy** · 02/02/2006, 22h36

Hum j'avais dis ça car je venais de coder une class de vecteur et une class de matrice... Maintenant je vais soit utiliser un type de matrice et de vecteur déjà coder : (D3DXVECTOR3 et D3DXMATRIX) ou bien des insructions 3DNow!

**Charlemagne** · 06/05/2006, 02h55

La discussion est vieille, mais je voudrais y mettre mon grain de sel.

Supposons que je veuille optimiser la boucle suivante:

Code :

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

1
2
3
 
for (int i=0; i<n; ++i)
  z[i]=x[i]+y[i];

Beaucoup de propositions précédentes ne sont que superficielles.
Mais voici les 3 voies principales d'optimisations que je suggère.
Si vous croyez que les compilos les font automatiquement, vous vous trompez (malheureusement).

1) instructions parallèles SIMD (SSE1, SSE2 pour les Pentiums)
Pour les pentium cela permet un gain de:
-char: 16x
-short: 8x
-int, float: 4x
-double: 2x
Il faut faire néanmoins attention aux contraintes d'alignement mémoire et éventuellement prévoir de traiter les éléments restants de la boucle.

Code :

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

1
2
3
4
 
float *px=x, py=y, pz=z;
for (int i=0, imax=n-4; i<imax; px+=4, py+=4, pz+=4, i+=4)
  _mm_store_ps(pz,_mm_add_ps(_mm_load_ps(px),_mm_load_ps(ps)));

2) développer la boucle
Certes un Pentium prédit la plupart du temps correctement le saut conditionnel de la boucle 'for', évitant ainsi de briser le pipeline.
Mais développer la boucle permet un gain important de vitesse, surtout quand les index des tableaux sont constants (instructions plus rapides du Pentium).

Code :

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

1
2
3
4
5
6
7
8
 
for (int i=0, imax=n-16; i<imax; i+=16)
{
  float *px=&x[i], py=&y[i], pz=&z[i];
  pz[0]=px[0]+py[0];
  pz[1]=px[1]+py[1];
  ...
}

3) Garder autant que possible les variables dans les registres.
Ainsi si l'on désire calculer Z1=X+Y et Z2=X-Y, pourquoi ne pas faire qu'une seule boucle:

Code :

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

1
2
3
4
5
6
7
 
for (int i=0; i<n; ++i)
{
  float xi=x[i], yi=y[i];
  z1[i]=xi+yi;
  z2[i]=xi-yi;
}

Il n'est pas interdit de mélanger ces 3 techniques.

Dans un autre ordre d'idées:
-Le processeur prédit qu'un test 'if' est vérifié. Donc pour minimiser les pipeline brisés (destructeur pour la vitesse), placez le code le moins probable après 'else'.
-le mot clé 'restrict' peut supprimer l'aliasing. 'restrict' est dans le C99, mais pas encore officiellement dans le C++. Sinon votre compilateur a surement une option de compilation adéquate.

**Rafy** · 11/05/2006, 23h14

tu as écris += 4, je suppose que ça vient de la taille de l'int enfin tu suppose que sizeof(int) vaut toujours 4... Il faut faire gaffe avec ça....
C'est pas forcement vrai...
Ce qui est vrai c'est :

Code :

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

1
2
3
4
5
6
 
sizeof(char) == 1
et
sizeof(char) <= sizeof(int) <= sizeof(long)
de même
sizeof(float) <= sizeof(double) <= sizeof(long double)

rien n'empêche que les 3 soient égales

**Charlemagne** · 11/05/2006, 23h50

tu as écris += 4, je suppose que ça vient de la taille de l'int enfin tu suppose que sizeof(int) vaut toujours 4... Il faut faire gaffe avec ça....

T'as pas dû comprendre grand chose à mon exemple:
- J'ai pris des floats pour l'exemple, pas des ints
- Il y a bien 4 floats dans un registre SSE = 16 octets

**Luc Hermitte** · 12/05/2006, 01h25

Sa remarque au sujet des constantes magiques reste valide. (Certes dans ton cas, tu vises une archi bien précise, au détriment de la portabilité des perfs.)

**_vince_** · 28/11/2007, 10h24

Envoyé par jfloviou

Bonjour à tous, je suis nouveau sur ce forum et suis à la recherche de tous les trucs et astuces du plus bateau au plus compliqué pour un code plus efficace en vitesse de calcul: ex mieux vaut une boucle FOR ou l'usage du WHILE ? La pile est elle vraiment plus rapide que le tas?
l'usage de inline c'est mieux pour la vitesse?

et tous les autres...

Donc si vous connaissez des sites, ou des astuces, merci!

jaja

Bonjour,

Avant d'optimiser les performances d'execution, il faut d'abord penser a optimiser le code en lecture, i.e. ecrire du code lisible pour les humains.
On ne le repetera jamais assez, les programmes sont d'abord fait pour les humains et ensuite pour les machines.

Pense au programmeur qui reprend le code apres toi et qui passe des heures a comprendre pourquoi l'idiot precedent n'a pas voulu ecrire un code clair, tout ca pour gagner une instruction parmi des millions...

**FloMo** · 28/11/2007, 10h29

Envoyé par _vince_

Bonjour,

Avant d'optimiser les performances d'execution, il faut d'abord penser a optimiser le code en lecture, i.e. ecrire du code lisible pour les humains.
On ne le repetera jamais assez, les programmes sont d'abord fait pour les humains et ensuite pour les machines.

Pense au programmeur qui reprend le code apres toi et qui passe des heures a comprendre pourquoi l'idiot precedent n'a pas voulu ecrire un code clair, tout ca pour gagner une instruction parmi des millions...

Je confirme : un code clair est d'autant plus facile à optimiser que l'on sait immédiatement cibler l'endroit où il y a une perte éventuelle. De plus, si le code est simple, le compilateur saura mieux optimiser sa sortie.

**yan** · 30/11/2007, 14h58

Bonjour,
les trie de la STL utilise pas mal la fonction template std::swap. Il est donc préférable que les class, possedant des variable dynamique(tableau, string, vector ...) stockées dans un contenaire implémente un swap pour optimiser les trie. Cela permet de remplacer un swap constitué de 3 operation égale( donc trois recopie de mémoire) à un échange de memoire

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
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
 
//class qui contient la fonction swap pour éviter des recopie de memoire
class A
{
public :
	A(int a,std::string s) :myString(s),nb(a){ };
 
	const std::string &GetString() {return myString;}
	bool operator<(const A& a)const {return nb<a.nb;}
	A&  operator=(const A& a)
		{
		static int nbegale(0);
		std::cout<<"= : "<<++nbegale<<std::endl;
		nb=a.nb;
		myString=a.myString;
		return (*this);
		}
	void swap(A& a)
		{
			static int nbswap(0);
			std::cout<<"swap : "<<++nbswap<<std::endl;
			std::swap(nb,a.nb);
			myString.swap(a.myString);
		};
private:
        //varible qui "prend du temps" lors d'une recopie 
	std::string myString;
	int nb;
 
};
//specialisation de la fonction std::swap pour la class A
namespace std
{
template<>
inline void swap<A> ( A& a, A& b )
{
	a.swap(b);
};
}
 
int main(int argc, char** argv)
{
	//mon vecteur a trier
	std::vector<A> vect;
       //on remplie de n'importe quoi
      //le but etant quil y en ai assez pour que swap soit appelé
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(2,"deux"));
	vect.push_back(A(15,"quinze"));
	vect.push_back(A(10,"dix"));
	vect.push_back(A(5,"cinq"));
	vect.push_back(A(1,"un"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
	vect.push_back(A(30,"trente"));
 
     //on fait le trie
	std::sort(vect.begin(),vect.end());
	return 0;
}

En posant :
- duré d'un égale = 1s
- durée d'un swap = .5s (echange de la mémoire, donc peut de recopie)

Les résultats que j'obtiens sous visual 20005 sont :
- sans le swap : 234 operation egale = 234s
- avec le swap : 74 operation swap et 72 operation egale = 109 s

Les résultats que j'obtiens avec GCC sous ubuntu sont :
- sans le swap : 361 operation egale = 361s
- avec le swap : 88 operation swap et 185 operation egale = 229 s

voici un lien qui explique un peu :
http://www.tantalon.com/pete/cppopt/...l.htm#Swapping

**zenux** · 08/06/2008, 16h47

J'ai une petite question, qu'est ce qui est le plus rapide :

code 1 :

Code :

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

1
2
for(int i=0;i<vec.size();i++)
  vec[i]->unBool = false;

code 2:

Code :

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

1
2
3
for(int i=0;i<vec.size();i++)
  if(vec[i]->unBool = true)
    vec[i]->unBool = false;

Je me doute bien que si "unBool" est 99% du temps à "true", le premier code sera plus rapide. Mais à partir de quel pourcentage le code numéro 2 sera plus rapide ?

Merci d'avance

**koala01** · 08/06/2008, 17h08

Envoyé par zenux

J'ai une petite question, qu'est ce qui est le plus rapide :

code 1 :

Code :

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

1
2
for(int i=0;i<vec.size();i++)
  vec[i]->unBool = false;

code 2:

Code :

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

1
2
3
for(int i=0;i<vec.size();i++)
  if(vec[i]->unBool = true)
    vec[i]->unBool = false;

Je me doute bien que si "unBool" est 99% du temps à "true", le premier code sera plus rapide. Mais à partir de quel pourcentage le code numéro 2 sera plus rapide ?

Merci d'avance

Déjà, fais attention au test que tu excécute...

En effet, si tu fais un test du genre de

Code :

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

if(test[i]->unBool = true)

tu commence par assigner true à test[i]->unBool... et donc, le test sera toujours vrai...

Pour que ce soit réellement un test, ce serait

Code :

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

if(test[i]->unBool == true)

En outre, il serait peut-être préférable de déclarer i comme étant un size_t, ce qui est le type renvoyé par size

Ceci dit, il faut savoir que, si tu fais un test de manière inopportune, ce sera toujours plus lent que si tu ne le fais pas.

Il n'y a rien à faire, un test demande un certain nombre de cycle d'horloge processeur, et donc, fatalement, cela "ralenti" un peu le code

Pour qu'il présente un avantage, il faudrait que les instructions à effectuer dans le cas où le test est vérifié soient plus nombreuses, de manière, justement, à éviter d'effectuer le nombre d'exécutions quand elles ne sont pas nécessaire.

Ainsi, il devient opportun de placer le test si ton code doit se présenter sous une forme proche de

Code :

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

1
2
3
4
5
6
7
8
9
10
for(size_t i=0;i<test.size();++i)
{
    if(test[i]->unBool == true)
    {
        /* une série d'instructions potentiellement "longue" à l'exécution 
         * mais, en tout cas, plus importante que la simple assignation
         * d'un type primitif
         */
    }
}

De la rapidité du code [Trucs & Astuces]

Contribuez C++

Vue hybride

Discussions similaires

Partager

Partager