Discussion :

[tnarol]

Salut,

J'ai quelques questions qui me turlupinent à chaque fois que j'écris du code avec des impératifs de performance :

- est ce qu'une variable déclarée localement dans une boucle a un risque d'être moins rapide qu'une variable déclarée à l'extérieur.

- dans une boucle for (i = 0; i < monVecteur.size(); i++) est ce qu'on perd un peu de temps à évaluer la fonction size() par rapport à la mettre dans une variable (si elle ne varie pas) ?

- de manière plus générale si j'utilise plusieurs fois une valeur de variable constante que j'obtiens avec un appel de fonction et/ou une indirection dois-je stocker localement cette variable ?

Merci !

[koala01]

Salut,

La méthode size() est de toutes manières faite pour être en temps d'exécution constant, ce qui fait que je peux déjà t'assurer que tu ne prend pas plus de temps à obtenir le résultat avec 100 000 éléments qu'avec 10.

Et il me semble même que la méthode est déclarée inline (bien que je ne puisse en jurer), et, si c'est bel et bien le cas, il n'y aura pas de différences entre le fait de prendre la valeur une fois pour toute en dehors de la boucle et celui de rappeler la méthode à chaque fois.

Quoi qu'il en soit, faut il rappeler que dans plus de 90% des cas, ce genre d'optimisation arrive trop tôt et qu'il vaut mieux commencer par voir s'il n'y a pas moyen d'optimiser l'algorithme/les structures de manière a s'éviter des itérations inutiles

[tnarol]

Quoi qu'il en soit, faut il rappeler que dans plus de 90% des cas, ce genre d'optimisation arrive trop tôt et qu'il vaut mieux commencer par voir s'il n'y a pas moyen d'optimiser l'algorithme/les structures de manière a s'éviter des itérations inutiles

Certes, mais quitte à écrire quelque chose, autant que ce soit pas trop mal la première fois...

[koala01]

Certes, mais quitte à écrire quelque chose, autant que ce soit pas trop mal la première fois...

Oui, si par "pas trop mal" tu envisages les choses sous l'angle de l'algorithme.

Si tu fais bien ton travail en utilisant des noms de variables non concurrents et explicites, et que tu te rend compte que, malgré le fait que ton algorithme est "aussi optimisé que faire se peut", il faut encore essayer de grapiller quelques cycles d'horloges, le fait de sortir la fonction de la boucle ne devrait pas poser de problème, et tu sera libre de faire les tests de perfs pour t'assurer du fait que cela change quelque chose ou non

[themadmax]

Bonne question, et d'après la littérature il est conseillé de déclarer une variable au plus tard dans le code.

Testons :

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
#include <iostream>
#include <windows.h>
 
#define COUNT 100
int tab[COUNT];
 
void func1()
{
	for (int i=0; i<COUNT; i++)
	{
		int b = tab[i];
		if ( b == 0 )
			b++;
	}
}
 
void func2()
{
	int b;
	for (int i=0; i<COUNT; i++)
	{
		b = tab[i];
		if ( b == 0 )
			b++;
	}
}
 
int main()
{
	memset( tab, 0, COUNT );
	__int64 start, stop;
 
	QueryPerformanceCounter((LARGE_INTEGER*)&start);
	func1();
	QueryPerformanceCounter((LARGE_INTEGER*)&stop);
	std::cout << (stop - start) << std::endl;
 
	QueryPerformanceCounter((LARGE_INTEGER*)&start);
	func2();
	QueryPerformanceCounter((LARGE_INTEGER*)&stop);
	std::cout << ( stop - start ) << std::endl;
}

J'ai fait plusieurs tests avec VS2005 (Release) et c'est a peut prés pareil, pour les deux fonctions !
Il faudrai jeter un coup d'oeil dans le code ASM généré.

[Invité]

J'ai fait le même test chez moi :

Code c++ :

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
#include <iostream>
#include <time.h>
 
#define COUNT 100000000
int tab[COUNT];
 
void func1()
{
    for (int i=0; i<COUNT; i++)
    {
        int b = tab[i];
        if ( b == 0 )
            b++;
    }
}
 
void func2()
{
    int b;
    for (int i=0; i<COUNT; i++)
    {
        b = tab[i];
        if ( b == 0 )
            b++;
    }
}
 
int main()
{
    memset( tab, 0, COUNT );
 
    clock_t start, stop;
 
    start = clock();
    func1();
    stop = clock();
    std::cout << (unsigned int)(stop - start) << std::endl;
 
    start = clock();
    func2();
    stop = clock();
    std::cout << (unsigned int)( stop - start ) << std::endl;
 
    return 0;
}

Avec g++ 4.2.3, les résultats sont les suivants:
func1 -> 1090000
func2 -> 790000

[koala01]

Héhé...

La première règle est de ne jamais faire confiance à un benchmark que l'on n'a pas trafiqué soi même...

En plus, la question ici porte précisément sur l'évaluation de size() comme condition d'arrêt de la boucle, ce que le code ne met pas en valeur

De plus, il n'est pas bon de se contenter de tester les choses une seule fois, étant donné qu'un tas de circonstances externes sont de nature à fausser les résultats.

J'ai donc modifié les deux fonctions pour que elles nous testent exactement ce que le PO demande en:

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
 
void func1(std::vector<size_t>& v)
{
    for (size_t i=0; i<v.size(); i++)
    {
        v[i]=i;
    }
}
 
void func2(std::vector <size_t>& v)
{
    size_t max=v.size();
    size_t i;
    for (i=0; i<max; i++)
    {
       v[i]=i;
    }
}

et j'ai bien sur adapté un peu la fonction main en

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
 
int main()
{
    std::vector<size_t> t;
    for(size_t i=0;i<10000000;++i)
        t.push_back(i);
 
    clock_t start, stop;
 
    for(size_t i=0;i<10; ++i)
    {
        start = clock();
        func1(t);
        stop = clock();
        std::cout <<i<<" func1 "<< (unsigned int)(stop - start) <<"  ";
 
        start = clock();
        func2(t);
        stop = clock();
        std::cout <<" func2 "<< (unsigned int)( stop - start ) << std::endl;
    }
    return 0;
}

Et là, apparaissent certaines divergences apparaissent.

En mode Debug, func1 est globalement plus lente que func2 ainsi que le montre la sortie ci-dessous:

Code :

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

1
2
3
4
5
6
7
8
9
10
0 func1 218   func2 188
1 func1 219   func2 172
2 func1 218   func2 188
3 func1 219   func2 187
4 func1 219   func2 172
5 func1 218   func2 188
6 func1 234   func2 172
7 func1 219   func2 187
8 func1 219   func2 172
9 func1 234   func2 172

En mode Relase (compilé avec -O2) les résultats sont plus nuancés...

Allez savoir pourquoi, lors de la première exécution, alors que les 5 premiers passages montrent que func2 est plus rapide, les 5 suivants montraient exactement le contraire:

Code :

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

1
2
3
4
5
6
7
8
9
10
0 func1 156   func2 141
1 func1 156   func2 141
2 func1 156   func2 141
3 func1 156   func2 140
4 func1 141   func2 140
5 func1 141   func2 156
6 func1 140   func2 156
7 func1 140   func2 157
8 func1 140   func2 157
9 func1 141   func2 156

et les exécutions suivantes donnaient, parfois, un avantage à func2 (de l'ordre de 156 contre 148 pour les 10 passages), parfois un avantage à func1 (avec une différence du même ordre pour les 10 passages), et parfois un avantage à func1 (ou à func2) pour les (quelques) premier passages, un avantage exactement inversé pour les suivants.

Bref, je crois sincèrement qu'il est - à tout prendre - plus intéressant:

1. de déclarer la variable servant compteur pour la boucle dans la boucle (afin d'éviter les conflits de noms de variables)
2. d'utiliser la méthode size() dans la boucle, afin que le lecteur puisse se faire une idée de la condition de sortie à la seule lecture de la boucle

Et ce, sous réserve d'un benchmark qui montre une réelle constance dans les différences.

Maintenant, c'est peut être du à ma situation personnelle, et donc, voici avec quoi j'ai travaillé:

• Athlon 1700XP, 512Mb RAM (SD-RAM)
• Code::Blocks, SVN Build Rev 5010
• Gcc-4.3.0

[three minute hero]

À mon avis, c'est tout simplement le compilateur qui optimise (O2) pour donner un binaire équivalent à celui résultant d'un code où la variable aurait été déclarée en dehors de la boucle.

[koala01]

À mon avis, c'est tout simplement le compilateur qui optimise (O2) pour donner un binaire équivalent à celui résultant d'un code où la variable aurait été déclarée en dehors de la boucle.

Ce n'est pas impossible, et c'est même fort vraisemblable...

Cependant, cela confirme ce que je dit bien haut depuis toujours: attendez d'avoir la preuve qu'un "sucre syntaxique" quelconque ait effectivement en phase de distribution un impact sur le résultat, commencez par optimiser votre algorithme, et remettez vous en au compilateur pour savoir comment créer au mieux le binaire.

Si, par la suite, il apparait à coup de benchmarks qu'une optimisation est nécessaire et utile, elle ne devrait être tentée que dans les circonstances qui seront celle de la compilation avant distribution.

[three minute hero]

Le mieux serait de sortir les codes assembleurs générés.

De toute façon, tout ceci n'est que de la masturbation intellectuelle. C'est bien de comprendre ce qui se passe, mais en pratique perdre du temps à « optimiser » le code de cette façon est antiproductif. Il vaut mieux s'intéresser à la complexité algorithmique et privilégier avant tout la lisibilité du code.

[koala01]

Le mieux serait de sortir les codes assembleurs générés.

De toute façon, tout ceci n'est que de la masturbation intellectuelle. C'est bien de comprendre ce qui se passe, mais en pratique perdre du temps à « optimiser » le code de cette façon est antiproductif. Il vaut mieux s'intéresser à la complexité algorithmique et privilégier avant tout la lisibilité du code.

Heuuu... As tu remarqué que c'était le sens de ma toute première intervention

Si, par la suite, je me suis amusé à faire quelques mesures, c'était pour:

1. Démontrer que l'optimisation de l'algorithme importe plus que celle du code
2. Démontrer qu'il ne faut pas se fier à un bench que l'on n'a pas truqué soi-même
3. Démontrer que, si sur certains points, il faut prendre le compilateur pour un c, on peut par contre lui faire parfaitement confiance pour optimiser le binaire
4. Démontrer enfin que le résultat sera fortement dépendant des options de compilation passées

[Emmanuel Deloget]

Bonne question, et d'après la littérature il est conseillé de déclarer une variable au plus tard dans le code.

Ca n'a pas grand chose à voir avec un problème de rapidité d'exécution du cycle normal.

Par contre, si tu fais:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
void f1(params..)
{
  MaClasseQuiPrendsDuTempsALaConstruction c(params..)
  if (test_sur_une_valeur_indep_de_c) return;
  ...
}
 
void f2(params..)
{
  if (test_sur_une_valeur_indep_de_c) return;
  MaClasseQuiPrendsDuTempsALaConstruction c(params..)
  ...
}

Alors f2 est plus rapide que f1, qui exécute un constructeur et un destructeur en plus. Par contre, si c est un int, le temps d'exécution sera probablement identique (car un int est simplement réservé sur la pile - il n'y a ni constructeur ni destructeur à appeler).

De manière générale, plus tu attends pour déclarer une variable, plus tu a de chance que cette déclaration ne soit pas nécessaire - d'où la recommandation de la déclarer le plus tard possible.

[Emmanuel Deloget]

Allez savoir pourquoi, lors de la première exécution, alors que les 5 premiers passages montrent que func2 est plus rapide, les 5 suivants montraient

et les exécutions suivantes donnaient, parfois, un avantage à func2 (de l'ordre de 156 contre 148 pour les 10 passages), parfois un avantage à func1 (avec une différence du même ordre pour les 10 passages), et parfois un avantage à func1 (ou à func2) pour les (quelques) premier passages, un avantage exactement inversé pour les suivants.

Scheduler, task switch sont les premiers mots qui me viennent à l'esprit. Sous Windows, une différence de 10/20ms n'est pas significative, surtout sur un test qui dure 150ms (parce que ce sont bien des ms, n'est-ce pas?)

Tu sais que un v.resize() au début te permet de gagner un peu de temps au setup ? puisque tu te moques des valeurs présentes dans le vecteur, les initialiser ne sert pas à grand chose

[three minute hero]

Heuuu... As tu remarqué que c'était le sens de ma toute première intervention

Oui oui, j'appuyais tes propos

[themadmax]

J'ai essayé de regarder le code ASM généré par VS2005, mais celui-ci a bien voulu me le générer juste pour le mode Debug (voir pièce jointe).
Pour conclure, j'aimerai conseiller au développeur C++ ayant un passé C, de ne plus déclarer leur variable en début de fonction.
Et d'utiliser les fonctions "size()", mise à part pour une recherche profonde d'optimisation ( pas encore prouvé plus rapide ).

J'aime bien ce genre de poste qui traite de la "beauté" du développement, et hélas très difficile à trouver sur le net/cours. Peut-être serai-t-il intéressant d'avoir un petit coin où l'on référence tous ces conseils, avec surtout leurs argumentations.

[Emmanuel Deloget]

J'ai essayé de regarder le code ASM généré par VS2005, mais celui-ci a bien voulu me le générer juste pour le mode Debug (voir pièce jointe).

Pour *voir* le code asm généré en mode release, tu peux mettre un point d'arrêt en début de fonction (si si, ça marche), debugger le programme et visualiser la fenêtre assembleur. Ce n'est pas très pratique, je te l'accorde.

Pour *générer* du code asm directement, il faut passer par les options de compilation. Dans les propriétés de ton projet,
[C++ -> Output Files --> Assembler Output]: choisir l'option qui te conviens le mieux (presonnellement, c'est le listing assembleur simple).
[C++ -> Output Files --> ASM List Location]: mettre le path ou tu va stocker les fichiers ASM

Pour conclure, j'aimerai conseiller au développeur C++ ayant un passé C, de ne plus déclarer leur variable en début de fonction.
Et d'utiliser les fonctions "size()", mise à part pour une recherche profonde d'optimisation ( pas encore prouvé plus rapide ).

La fonction size() est plus que probablement inlinée, donc elle est équivalente à une soustraction dans la plupart des cas (l'équivalent de end() - begin(), mais en plus intelligent). Si le compilateur n'est pas capable de détecter que le vecteur n'a aucune chance d'avoir été modifié entre deux appels successifs à size(), il effectuera systématiquement la soustraction. Autant ne la faire qu'une seule fois

J'aime bien ce genre de poste qui traite de la "beauté" du développement, et hélas très difficile à trouver sur le net/cours. Peut-être serai-t-il intéressant d'avoir un petit coin où l'on référence tous ces conseils, avec surtout leurs argumentations.

Ah, et sur l'optimisation, en voici des bons: The Fallacy of Premature Optimization, par Randall Hyde.

Un extrait:

As you can probably tell, this article is not "yet another article warning beginning programmers to avoid premature optimization." The purpose of this article is to examine how software engineers have (incorrectly) applied Hoare's statement as a way of avoiding the effort necessary to produce a well-performing application. Hopefully, this article can encourage many software engineers to change their views on application performance.

(PS: c'est Hoare et non Knuth qui a lancé la célèbre phrase "premature optimization is the root of all evil").

[loufoque]

Un bon compilateur pourrait optimiser votre code pour qu'il ne fasse rien du tout.
En effet, il ne fait rien de visible.

[Charlemagne]

J'apporte mon petit grain de sel:

- est ce qu'une variable déclarée localement dans une boucle a un risque d'être moins rapide qu'une variable déclarée à l'extérieur.

Je ne pense pas. En tout cas, c'est tellement plus pratique et élégant de déclarer une variable locale à l'intérieur.
Exception plus que probable: si cette variable locale est une classe avec un constructeur...

- dans une boucle for (i = 0; i < monVecteur.size(); i++) est ce qu'on perd un peu de temps à évaluer la fonction size() par rapport à la mettre dans une variable (si elle ne varie pas) ?

J'avais fait des essais du genre y'a quelques années (principalement avec le compilateur Intel sous Windows, plus rapide que GCC ou Visual d'après mes benchs).
J'en étais venu à la conclusion, qu'il valait mieux stocker le résultat dans une variable. J'aurais pensé le contraire, car j'estimais que l'inline jouerait à plein pour des fonctions du genre de size ou une simple addition, et pourtant...
Depuis j'ai pris l'habitude d'écrire les boucles dans le genre

Code :

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

1
2
for (int i=0, imax=vec.size(); i<imax; ++i) ...
for (int i=0, imax=n+10;       i<imax; ++i) ...

[koala01]

J'apporte mon petit grain de sel:

Tant qu'il ne fait pas gripper la machine...

Je ne pense pas. En tout cas, c'est tellement plus pratique et élégant de déclarer une variable locale à l'intérieur.
Exception plus que probable: si cette variable locale est une classe avec un constructeur...

Et encore...

Il est peut être alors utile de savoir si la variable "temporaire" utilise tout le temps les mêmes valeurs ou non, et, dans la négative, il faut alors comparer les performances des constructions/destructions successives avec celles des (ré)initialisations à envisager pour permettre à cette variable de fonctionner avec les bonnes valeurs...

Et je parle ici de performances uniquement, car, en ce qui concerne le code à utiliser pour la réinitialisation, je préférerais me contenter d'un appel au constructeur et de la destruction automatique de la variable

Quand on dit que rien n'est blanc ou noir

J'avais fait des essais du genre y'a quelques années (principalement avec le compilateur Intel sous Windows, plus rapide que GCC ou Visual d'après mes benchs).
J'en étais venu à la conclusion, qu'il valait mieux stocker le résultat dans une variable. J'aurais pensé le contraire, car j'estimais que l'inline jouerait à plein pour des fonctions du genre de size ou une simple addition, et pourtant...
Depuis j'ai pris l'habitude d'écrire les boucles dans le genre

Code :

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

1
2
for (int i=0, imax=vec.size(); i<imax; ++i) ...
for (int i=0, imax=n+10;       i<imax; ++i) ...

Cela implique de se poser quelques questions de base (du fait qu'il ne faut jamais se fier à un bench que l'on n'a pas truqué soi-même )

• Pourrais-tu, ne serait-ce qu'approximativement, nous dire il y a combien de temps
• Quelle était la version du compilateur intel
• As tu réeffectué les tests avec la version actuelle
• Etait-ce suffisemment significatif que pour justifier l'utilisation en dehors de situations où les temps d'exécutions sont réellement critiques (AKA ou le moindre cycle d'horloge compte)
• sans doute une ou l'autre à laquelle je n'ai pas pensé...

EDIT par contre, j'ai toujours eu horreur de rencontrer deux instructions différentes dans l'une des parties des boucles...

[Charlemagne]

Cela implique de se poser quelques questions de base (du fait qu'il ne faut jamais se fier à un bench que l'on n'a pas truqué soi-même )

• Pourrais-tu, ne serait-ce qu'approximativement, nous dire il y a combien de temps
• Quelle était la version du compilateur intel
• As tu réeffectué les tests avec la version actuelle
• Etait-ce suffisemment significatif que pour justifier l'utilisation en dehors de situations où les temps d'exécutions sont réellement critiques (AKA ou le moindre cycle d'horloge compte)
• sans doute une ou l'autre à laquelle je n'ai pas pensé...

Y'a peut-être environ 3-4 ans, plus que probablement avec la version 8.0.X ou 8.1.X du compilateur d'Intel (ICL).
Intel a certes sorti les version 9 et 10 depuis, mais ça ne fait probablement aucune différence. Je préfère a propos la version 8.1 aux récentes, car la version 8.1 obéit au doigt et à l'oeil aux consignes inline, alors que depuis les autres versions ne font que ce qu'elles veulent.
Dans mes tests, c'était pas négligeable pour des boucles à petit contenu. C'est clair qu'il y'a d'autres moyens autrement plus efficaces pour optimiser les boucles (déroulement bien pensé, calculs SIMD...)

EDIT par contre, j'ai toujours eu horreur de rencontrer deux instructions différentes dans l'une des parties des boucles...

Faut pas en abuser de la double instruction, mais je trouve ça sympa dans certains cas pour pas surcharger le contenu de la boucle, du genre:

Code :

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

1
2
3
4
5
6
7
8
 
for (iterator it=X.begin(), end=X.end(); it!=end; ++it) ...
 
for (int i=0, j=n-1; i<n; ++i, --j) ...//double balayage avant-arrière
 
//copie
for (float *p=&X[0], *q=&Y[0], *end=X[n]; p!=end; ++p, ++q)
  *q=*p;

Déclarer une variable imax comme dans l'exemple de mon message précédent, ne mange pas de pain, alors dans le doute sur la performance, autant aider le ou les compilateurs.
Car on est sûrement d'accord pour dire qu'au moins ça ne nuira pas aux performances...