Discussion :

[gelam]

Quand on parle d'optimiser du code je sens une crainte... car ce qu'on gagne d'un côté (vitesse) on le perd de l'autre (maintenabilité).
A mon sens c'est la maintenabilité qui doit être notre priorité. Toute optimisation ( taille ou vitesse ) doit être justifié par un gain mesurable. Ici je n'ai rien vu que des affirmations sans preuve (mon algo va plus vite parce que...). On sait et il a été répété ici que l'optimiseur fait un boulot étonnant.
Pour conclure je dirais que :
Toute optimisation de code doit être documentée et accompagnée d'un programme permettant de mesurerle gain de performances par rapport au code maintenable. Si ce n'est pas le cas au prochain cycle de maintenance mon collègue développeur va commencer par corriger mon code optimisé et le remplacer par du code lisible par lui-même. En outre le programme de mesure devra être exécuté à chaque mise à jour du compilateur.

[Matthieu Brucher]

Quand on parle d'optimiser du code je sens une crainte... car ce qu'on gagne d'un côté (vitesse) on le perd de l'autre (maintenabilité).
A mon sens c'est la maintenabilité qui doit être notre priorité. Toute optimisation ( taille ou vitesse ) doit être justifié par un gain mesurable. Ici je n'ai rien vu que des affirmations sans preuve (mon algo va plus vite parce que...). On sait et il a été répété ici que l'optimiseur fait un boulot étonnant.
Pour conclure je dirais que :
Toute optimisation de code doit être documentée et accompagnée d'un programme permettant de mesurerle gain de performances par rapport au code maintenable. Si ce n'est pas le cas au prochain cycle de maintenance mon collègue développeur va commencer par corriger mon code optimisé et le remplacer par du code lisible par lui-même. En outre le programme de mesure devra être exécuté à chaque mise à jour du compilateur.

Ca rejoint ce que j'ai dans mon dernier message, il ya les "optimisations" qui ne sont en fait qu'une utilisation correcte des outils et les hacks. Dans le premier cas, il n'y a aucun problème de maintenance, tandis que dans le deuxième cas, il y en a.

[yan]

Bonjour.
Une chose qui serait super ,se serait de faire des petits programmes qui confrontent les performances de différentes méthode.
Par exemple pour le parcoure d'un vector pour l'initialiser

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
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
 
#include <ctime>
 
#include <math.h>
 
 
 
class Mytimer
    {
    public:
        Mytimer() {Restart();};
        void Restart() {m_start_time = std::clock();}
        double GetTime() {return double(std::clock() - m_start_time) / CLOCKS_PER_SEC;}
    private:
        std::clock_t m_start_time;
    };
 
 
 
 
 
struct MyGenerate
{
explicit MyGenerate()
:count_(0)
{}
 
int operator () () {count_++ ; return static_cast<int> ( sqrt(count_*count_+36) );}
 
private:
int count_;
};
 
 
 
const long int my_vect_size = 300000;
const int nb_compute =50;
 
 
std::vector<int> my_vect;
std::vector<int>::iterator It1;
std::vector<int>::iterator Itend;
 
 
double genTime1;
double genTime2;
double genTime3;
double genTime4;
 
 
void gen1(int n)
    {
    Mytimer time__;
 
    MyGenerate gen;
    It1 = my_vect.begin();
    for (It1 = my_vect.begin();It1!=my_vect.end(); ++It1)
        {
        *It1 = gen();
        }
    genTime1 += time__.GetTime();
    }
 
void gen2(int n)
    {
    Mytimer time__;
 
    MyGenerate gen;
    It1 = my_vect.begin();
    Itend = my_vect.end();
    for (It1 = my_vect.begin();It1!=Itend; ++It1)
        {
        *It1 = gen();
        }
    genTime2 += time__.GetTime();
    }
 
 
void gen3(int n)
    {
    Mytimer time__;
    int i=0;
    MyGenerate gen;
    for(int i=0; i<my_vect.size();++i)
        {
        my_vect[i] = gen();
        }
    genTime3 += time__.GetTime();
    }
 
void gen4(long int n)
{
Mytimer time__;
std::generate( my_vect.begin(), my_vect.end(), MyGenerate() );
genTime4 += time__.GetTime();
}
 
 
int main()
{
 
genTime1 = 0;
genTime2 = 0;
genTime3 = 0;
genTime4 = 0;
my_vect.resize(my_vect_size);
 
 
int i = 0;
 
 
for (i = 0 ; i<nb_compute ; i++)
{
std::cerr<<100.*(static_cast<float>(i)/(nb_compute-1))<<"%                        \r";
gen1(my_vect_size);
gen2(my_vect_size);
gen3(my_vect_size);
gen4(my_vect_size);
}
std::cout <<std::endl;
std::cout << "gen time 1 = " << genTime1/nb_compute << std::endl;
std::cout << "gen time 2 = " << genTime2/nb_compute << std::endl;
std::cout << "gen time 3 = " << genTime3/nb_compute << std::endl;
std::cout << "gen time 4 = " << genTime4/nb_compute << std::endl;
return 0;
}

montre que ces quatres méthode sont quasi aussi performante. Aprés plusieurs lancé, Ce n'est pas toujours le même parcoure qui gagne

[koala01]

J'ai envie de dire que c'est normal:

• le test n'est pas le seul processus à tourner sur la machine et la charge du processeur pour tous les porcessus "externes" à celui que l'on teste vient "fausser" la donne
• Une moyenne n'a déjà un sens que si elle est associée à un "écart type" (c'est ce qui permet de savoir à partir de quelle valeur on obtient une valeur "anormalement élevée" ou "anormalement faible" en statistiques)

C'est la raison pour laquelle j'insiste sur le fait que, bien avant d'essayer d'optimiser les choses via le code, il faut penser à la meilleure structure et au meilleur algorithme...

Un exemple chiffré basé sur ma dernière intervention:

Mettons que les deux premiers exemples prennent 30 périodes par élément testé, et mettons même que la dernière en prenne 50 par élément testé du fait des appels récursifs - à peu de chose près, on devrait tourner dans ces eaux là:

Dans le cas extrème, si l'on recherche un élément parmis 255, c'est le dernier testé qui est celui recherché

Les deux premières possibilités (tableau et liste) prendront au maximum: 255*30 périodes = 7750 périodes processeur.

La dernière (recherche dans un arbre binaire) prendra au maximum: 8*50 périodes = ...400 périodes processeur.

C'est à dire que l'on divise le temps nécessaire pour trouver le dernier élément testé par presque 20 ...Et la différence devient de plus en plus flagrante au fur et à mesure que l'on augmente le nombre d'éléments (le temps est divisé par pres de 2450 pour... 65535 éléments avec 800 périodes contre 1 966 050)

Alors, honnêtement, le fait que la fonction s'effectue en 40 périodes au lieu d'en 50 ne présentera qu'un gain de performance tout à fait marginal, y compris dans le cadre d'un moteur 3D

Par contre, là où je suis d'accord, c'est qu'au niveau de la communication et/ou de la persistance des données, il faudra veiller à ce que les données soient triée dans un ordre compatible avec la structure utilisée au final:

Ce peut etre sous la forme de

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

pour un tableau alors que l'ordre le plus efficace pour un arbre binaire serait de l'ordre de

Code :

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

8 | 4 | 12 | 2 | 6 | 10 | 14 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15

Mais, là encore, un algorithme correct permet de s'en sortir

[yan]

J'ai envie de dire que c'est normal:

• le test n'est pas le seul processus à tourner sur la machine et la charge du processeur pour tous les porcessus "externes" à celui que l'on teste vient "fausser" la donne
• Une moyenne n'a déjà un sens que si elle est associée à un "écart type" (c'est ce qui permet de savoir à partir de quelle valeur on obtient une valeur "anormalement élevée" ou "anormalement faible" en statistiques)

C'est la raison pour laquelle j'insiste sur le fait que, bien avant d'essayer d'optimiser les choses via le code, il faut penser à la meilleure structure et au meilleur algorithme...

J'ai modifier le code pour ce que ca interesse, avec le calcul dumin, max, moyenne et ecart type.

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
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
157
158
159
160
161
162
163
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <numeric>
 
#include <ctime>
 
#include <math.h>
 
 
 
class Mytimer
    {
    public:
        Mytimer() {Restart();};
        void Restart() {m_start_time = std::clock();}
        double GetTime() {return double(std::clock() - m_start_time) / CLOCKS_PER_SEC;}
    private:
        std::clock_t m_start_time;
    };
 
 
 
 
 
struct MyGenerate
{
explicit MyGenerate()
:count_(0)
{}
 
int operator () () {count_++ ; return static_cast<int> ( sqrt(count_*count_+36) );}
 
private:
int count_;
};
 
 
 
const long int my_vect_size = 300000;
const int nb_compute =50;
 
 
std::vector<int> my_vect;
std::vector<int>::iterator It1;
std::vector<int>::iterator Itend;
 
 
std::vector<double> genTime1;
std::vector<double> genTime2;
std::vector<double> genTime3;
std::vector<double> genTime4;
 
 
 
struct ecart_type
{
    ecart_type(double & moyenne): m_moyenne (moyenne),m_somme(0.),m_NbElements(0){};
      void operator()(const double & val )
      {
          double x = val-m_moyenne;
          m_somme+=x*x;
          ++m_NbElements;
      }
 
    double GetEcartType(){return std::sqrt(m_somme/m_NbElements);}
 
    double m_moyenne;
    double m_somme;
    int m_NbElements;
 
};
 
void AFFICHER_resultat(std::vector<double>& vect)
{
    std::cout << "min : "<<*std::min_element(vect.begin(),vect.end())<<std::endl;
    std::cout << "max : "<<*std::max_element(vect.begin(),vect.end())<<std::endl;
    double moyenne = std::accumulate(vect.begin(),vect.end(),0.)/vect.size();
    std::cout << "moyenne : "<<moyenne<<std::endl;
    ecart_type ect = std::for_each(vect.begin(),vect.end(),ecart_type(moyenne));
     std::cout << "ecart type : "<<ect.GetEcartType()<<std::endl;
}
 
void gen1(int n)
    {
    Mytimer time__;
 
    MyGenerate gen;
    It1 = my_vect.begin();
    for (It1 = my_vect.begin();It1!=my_vect.end(); ++It1)
        {
        *It1 = gen();
        }
    genTime1.push_back( time__.GetTime());
    }
 
void gen2(int n)
    {
    Mytimer time__;
 
    MyGenerate gen;
    It1 = my_vect.begin();
    Itend = my_vect.end();
    for (It1 = my_vect.begin();It1!=Itend; ++It1)
        {
        *It1 = gen();
        }
    genTime2 .push_back(  time__.GetTime());
    }
 
 
void gen3(int n)
    {
    Mytimer time__;
    int i=0;
    MyGenerate gen;
    for(int i=0; i<my_vect.size();++i)
        {
        my_vect[i] = gen();
        }
    genTime3 .push_back(  time__.GetTime());
    }
 
void gen4(long int n)
{
Mytimer time__;
std::generate( my_vect.begin(), my_vect.end(), MyGenerate() );
genTime4  .push_back( time__.GetTime());
}
 
 
int main()
{
 
my_vect.resize(my_vect_size);
 
 
int i = 0;
 
 
for (i = 0 ; i<nb_compute ; i++)
{
std::cerr<<100.*(static_cast<float>(i)/(nb_compute-1))<<"%                        \r";
gen1(my_vect_size);
gen2(my_vect_size);
gen3(my_vect_size);
gen4(my_vect_size);
}
std::cout <<std::endl;
std::cout << "gen time 1"  << std::endl;
AFFICHER_resultat(genTime1);
std::cout <<std::endl<< "gen time 2" << std::endl;
AFFICHER_resultat(genTime2);
std::cout << std::endl<<"gen time 3" << std::endl;
AFFICHER_resultat(genTime3);
std::cout << std::endl<<"gen time 4 "  << std::endl;
AFFICHER_resultat(genTime4);
 
 
 
return 0;
}

Mais je suis d'accord avec ton point de vu. C'est pour cela que je proposer des petit main pour démontrer si c'est une vrai optimisation ou non.