Les templates et les performances.

**deubelte** · 27/10/2010, 22h38

Bonjour,
j'ai tenté de comparer les performances d'algorithmes basés sur l'utilisation de template.
J'ai voulu comparer le temps de calcul basés sur de prog différents qui font la même chose: on a un vecteur de paire<int,int> aléatoires. Le but est de compter le nombres de paires dont la première coordonnées est inférieur à 10. Ce vecteur contient 1000000 paires.

Le premier utilise les templates de la STL:

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
 
for(int od=0;od<10;od++)
	{
	time_t start,end;
	double dif;
	int o=0;
	time (&start);
for(int r=1;r<5;r++){
 
	std::vector<pair<int,int>> VN;
	fff(VN);// Cette fonction génère le vecteur aléatoire. 
o=o+ count_if(VN.begin(), VN.end(),bind(tr1::cref(bind1st(less<int>(), 10))  ,(std::bind<int&>(std::get<0, int , int>, _1))));
 
}	 
 
}
 
	time (&end);
    dif = difftime (end,start);
	fffd=fffd+dif;
}

Le deuxième utilise une bonne vieille boucle if et for:

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
 
for(int od=0;od<10;od++)
	{
	time_t start,end;
	double dif;
	int o=0;
	time (&start);
for(int r=1;r<5;r++){
 
	std::vector<pair<int,int>> VN;
	fff(VN);// Cette fonction génère le vecteur aléatoire. 
 for(iterator k=VN.begin();k!=VN.end();k++){
if((*k).first<10) o=o+1;
}	 
 
}
 
	time (&end);
    dif = difftime (end,start);
	fffd=fffd+dif;
}

Hé bien malgré l'utilisation de ces templates, la boucle for-if reste supérieure en performances, puisque fffd dans le premier cas vaut 160, alors que dans le deuxième il faut 140.
Je pense que c'est l'utilisation des 3 bind qui fait que cela ralenti le calcul.
Je ne suis pas assez calé pour améliorer mon code, mais si vous avez des idées.

**Joel F** · 28/10/2010, 07h50

vu que bind fais des copies de pointeur de fonction et qu'un pointeur de fonction n'est pas inlinable, ca me parait raisonnable comme résultat.

- les pb de pefs vient de bind et non de vector :o
- comment mesures tu ton temps d'execution, tu prends bien entendu le temps médian de 10^4+ executions.
- je pense aussi que tu bench le temps d'allocation de ton vector dans ta boucle interne :o
- Essaye avec boost.lambda ou phoenix qui eux devrait s'inliner.
- que dit gprof ?

**JolyLoic** · 28/10/2010, 08h37

Envoyé par Joel F

- Essaye avec boost.lambda ou phoenix qui eux devrait s'inliner.

Deux autres essais intéressants sont avec les lambdas de c++0x, et avec un foncteur fait à la main.

**deubelte** · 28/10/2010, 09h32

les pb de pefs vient de bind et non de vector :o

C'est ce que je pense. Mais je pense quisi qu'il doit y avoir moyen de supprimer un peu le nombre de bind. Il y en a trois. Ca fait bcp.

Essaye avec boost.lambda ou

hmm. C'est deja plus difficile a utiliser.

phoenix qui eux devrait s'inliner.

connais pas

- que dit gprof ?

connais pas

**Joel F** · 28/10/2010, 09h39

Envoyé par deubelte

hmm. C'est deja plus difficile a utiliser.

Guere , ca permet deja de faire sauter le bind sur less

Envoyé par deubelte

connais pas

http://www.boost.org/doc/libs/1_44_0...tml/index.html

Envoyé par deubelte

connais pas

le profiler de gcc quoi ...
man gprof :o

**Joel F** · 28/10/2010, 09h45

Envoyé par JolyLoic

Deux autres essais intéressants sont avec les lambdas de c++0x, et avec un foncteur fait à la main.

Je t'avoue que la, je ferais effectivement un foncteur

Code :

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

1
2
3
4
5
6
7
8
9
 
struct compare_first
{
  compare_first(int v) : value(v) {}
  bool operator()( std::pair<int,in> const& p )  { return p.first<value; }
  int value;
};
 
count_if(VN.begin(), VN.end(), compare_first(10) );

**deubelte** · 28/10/2010, 09h51

Je t'avoue que la, je ferais effectivement un foncteur

Le but etait d'utiliser le plus possible de fonctions déjà implémentées. Enfin, de réduire au plus possible le code. De tout internatiliser

**Joel F** · 28/10/2010, 10h09

vu le truc, ca mange pas beaucoup :€
Tu colles ça dans un namespace details et hop

**deubelte** · 28/10/2010, 10h51

vu le truc, ca mange pas beaucoup :€
Tu colles ça dans un namespace details et hop

De toute facon, j'ai essayé avec un foncteur, ca ne change pas grand chose, même inliné

**Joel F** · 28/10/2010, 11h25

tu ne m'as toujours pas dit comment tu bench

**deubelte** · 28/10/2010, 11h36

c'est dans mon code.
Je fais la différence entre start et end:

dif = difftime (end,start);

qu'appelles tu par bencher?

**Arzar** · 28/10/2010, 11h38

Envoyé par deubelte

De toute facon, j'ai essayé avec un foncteur, ca ne change pas grand chose, même inliné

Ce qui veut dire que tu t'es gouré en mesurant.

L'implémentation de count_if étant simplissime, il est quasi impossible d'avoir une différence de perf entre une boucle à la main ou un count_if+foncteur, vu que le code est identique...

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
 
// count_if (un poil simplifié) de vs2010)
template<class _InIt,class _Pr> 
int _Count_if(_InIt _First, _InIt _Last, _Pr _Pred)
{	// count elements satisfying _Pred
   int _Count = 0;
 
   for (; _First != _Last; ++_First)
      if (_Pred(*_First))
         ++_Count;
   return (_Count);
 
// ta boucle
   int o=0;
   for(iterator k=VN.begin();k!=VN.end();k++){
      if((*k).first<10) 
         o=o+1;
}

Ceci-dit, perso, count_if fait parti de la liste des algo que je n'utilise jamais (avec for_each et transform) car la boucle écrite à la main est plus courte et tout aussi claire à mon gout.

**nikko34** · 28/10/2010, 14h35

transform, for_each, c'est quand même bien utile. Enfin quand on a pris goût aux algorithmes.

**poukill** · 28/10/2010, 14h41

Envoyé par nikko34

transform, for_each, c'est quand même bien utile. Enfin quand on a pris goût aux algorithmes.

Surtout quand on commence à toucher aux expression template. Quand on ne manipule plus que des foncteurs, std::for_each, std::transform & Co sont plutot pas mal !

**deubelte** · 28/10/2010, 14h55

Ce qui veut dire que tu t'es gouré en mesurant.

Perso, je vois pas ou je me suis planté. Peut etre que l'inlining à un effet, mais il est tres faible.

**yan** · 28/10/2010, 15h07

Envoyé par Arzar

il est quasi impossible d'avoir une différence de perf entre une boucle à la main ou un count_if+foncteur, vu que le code est identique...

Normalement pas forcement.
La boucle à la main est au mieux aussi rapide. Mais suivant le type du conteneur, les algo peuvent aller plus vite car la STL connait la meilleur façon de parcourir.
Sous visual, normalement le foreach n'utilise pas vraiment les iterateur.
[edit]
un peu de lecture
http://www.drdobbs.com/184401446

**deubelte** · 28/10/2010, 17h55

La boucle à la main est au mieux aussi rapide.

C'est ce que je croyais. D'un autre coté, les compilos savent etllement bien optimiser que je me demande vraiment si on va voir une différence ou non.
Estce que cela vaut le coup de se casser le ... à faire des trucs compliqués??

N'empeche que j'ai testé avec un vector de doubles et un count_if qui regarde si oui ou non les chifres sont > à un certain seuil. Hé bien le programme allait un peu plus vite.

**yan** · 28/10/2010, 20h48

Faut ce mefier de ce type de bench. Je me suis fait avoir plus d'une fois où en regardant de plus prêt, je ne comparai pas la même choses..
Dans ton cas, si j'ai bien compris, c'est les bind qui ralentit un peu. Sans compter que mesure le temps d'allocation de ton vecteur. Ce qu'il faut éviter.

Si tu cherche sur le forum je pense que tu devrais retrouver facilement mes postes avec des bench bancale