Discussion :

[ooxoo]

Bonjour
Voila un petit moment que je me pose cette question.
Question peut être stupide ou classique, mais je n'ai curieusement trouvé de réponse nulle part.
Imaginons qu'on veuille parcourir un vector.
Y a t il une différence entre utiliser un iterator ou l'op []
concrètement quelle est la différence entre les boucles:

Code :

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

1
2
3
4
5
std::vector<int> monvector;
....
 
for(int i = 0; i < monvector.size();i++)
{...}

et

Code :

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

1
2
for(std::vector<int>::iterator it = monvector.begin(); it != monvector.end(); it++)
{...}

L'une est elle plus rapide que l'autre? Pourquoi?

Merci d'éclairer ma lanterne

[loufoque]

La version itérateur pourrait être plus rapide, mais en pratique les compilateurs sont pas stupides et c'est pareil.

[Frifron]

De plus la version avec itérateur a l'avantage d'exister pour tous les conteneurs de la STL. Les itérateurs offrent une méthode uniformisée pour parcourir un conteneur quelqu'il soit. Ce qui n'est pas le cas de l'opérateur [].

D'un autre coté avec la version [] tu connais l'indice de l'objet que tu manipules.

Apres pour un vecteur, ca doit être plus ou moins la même chose pour la machine : les 2 versions ne sont que des pointeurs déguisés (avec déréférencement pour l'un).

[3DArchi]

L'idéal serait plutôt std::for_each(monvector.begin(),monvector.end(),...) ou toute autre fonction de la STL adapté à ton cas. A ce moment, la STL est supposé t'offrir le parcours le plus optimisé pour ton conteneur. Je dirais que le principe serait d'invoquer au max les conteneurs/algo de la STL lorsque cela est possible car ils ont été fait pour ça.

[ooxoo]

merci pour vos réponses.

donc pas vraiment de différence entre les deux.. je vais continuer de mettre 50% de l'un et 50% de l'autre

je retiens le for_each !

[yan]

J'avais fait des essaye avec visual.
Avec un vector :
un parcoure par iterateur avec un for est 2% moins rapide qu'avec le foreach. (Le foreach est équivalent au parcoure avec [])

Par contre avec d'autre conteneur le gain est énorme. Avec une list, le foreach est 50%-60% plus rapide qu'avec le for.

[HanLee]

J'avais fait des essaye avec visual.
Avec un vector :
un parcoure par iterateur avec un for est 2% moins rapide qu'avec le foreach. (Le foreach est équivalent au parcoure avec [])

Par contre avec d'autre conteneur le gain est énorme. Avec une list, le foreach est 50%-60% plus rapide qu'avec le for.

J'ai du mal à voir pourquoi...
Peut-être que le .end() n'a pas été inliné, mais j'en doute...

[JolyLoic]

J'ai du mal à voir pourquoi...
Peut-être que le .end() n'a pas été inliné, mais j'en doute...

Ce n'est pas forcément le fait qu'il soit inliné, mais le fait qu'il soit recalculé à chaque fois ? Il serait intéressant de comparer avec un

Code :

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

1
2
3
4
list<T>::iterator end = maListe.end();
for (list<T>::iterator it = maListe.begin() ; it !=end ; ++it)
{
}

[yan]

J'ai du mal à voir pourquoi...

Tu parle pour le vector ou tous les conteneur??

Peut-être que le .end() n'a pas été inliné, mais j'en doute...

J'avais fait un iterator end.

r0d dans tuto sur la STL trouve en gros là même chose
http://r0d.developpez.com/articles/algos-stl/#LI-E-2

C'est une différence qui est constante dans le temps.
Dans les algorithm de visual, ils transforme l'itérateur. Je ne sait plus si c'est le cas avec Gcc.

[yan]

voila le code où j'ai réussi à empêcher certaine optimization :
1- vire les boucles ou l'on ne fait rien : enlever la récuperation du resultat du for_each et le for_each n'est plus appelé dans visual

2- un peut d'aléatoire pour être sur qu'il n'optimise pas trop les boucles

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
#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <algorithm>
#include <ctime>
#include <cmath>
using namespace std;
 
#define CONTENAIRE vector
const int num =10000;
struct func
{
    func():res(0){};
    void operator()(int i)
    {
      res +=  2.*sqrt((double)i)*sqrt((double)i);
    }
    double res;
};
 
struct gen
{
    gen():i(0){};
    int operator()()
    {
        return ++i;
    }
    int i;
};
 
struct parcour
{
    parcour(std::CONTENAIRE<int>::iterator iit,
        const std::CONTENAIRE<int>::iterator eend)
        :it(iit),end(eend)
    {}
    void next(){++it;};
    bool notfin()const{return it !=end;}
 
 
    std::CONTENAIRE<int>::iterator it;
    const std::CONTENAIRE<int>::iterator end;
};
 
 
int main(int argc, char* argv[])
{
 
    vector<int> tmp(10000+rand()%100);
    std::generate(tmp.begin(),tmp.end(),gen());
    CONTENAIRE<int> ensemble;
    std::copy(tmp.begin(),tmp.end(),std::inserter(ensemble,ensemble.begin()));
    double resultat;
 
 
 
    while(1)
    {
    clock_t t0 = clock();
 
    for (int i =0;i<num;++i)
    {
        std::CONTENAIRE<int>::iterator it = ensemble.begin();
        const std::CONTENAIRE<int>::iterator end = ensemble.end();
        double res(0);
        while(it!=end)
        {
           res += 2.*sqrt((double)*it)*sqrt((double)*it);
           ++it;
        }
        resultat =res;
    }
    double tempA = double(clock()-t0)/num;
    std::cout<<"A"<<" "<<resultat<<" "<<tempA <<std::endl;
 
    t0 = clock();
    for (int i =0;i<num;++i)
    {
        parcour p(ensemble.begin(),ensemble.end());
        double res(0);
        while(p.notfin())
        {
           res += 2.*sqrt((double)*p.it)*sqrt((double)*p.it);
           p.next();
        }
        resultat =res;
    }
    double tempB = double(clock()-t0)/num;
    std::cout<<"B"<<" "<<resultat<<" "<< tempB<<std::endl;
 
    t0 = clock();
    for (int i =0;i<num;++i)
    {
      resultat = std::for_each(ensemble.begin(),ensemble.end(),func()).res;
 
    }
    double tempC = double(clock()-t0)/num;
    std::cout<<"C"<<" "<<resultat<<" "<< tempC<<std::endl;
 
    std::cout<<"C/A"<<" "<<100*(1.-tempC/tempA)<<"%"<<std::endl;
    std::cout<<"C/B"<<" "<<100*(1.-tempC/tempB)<<"%"<<std::endl<<std::endl;
    }
 
	return 0;
}

A : utilise une structure pour parcourir
B : boucle for sur les iterateur
C : for_each

pour un vector je me suis trompé :
visual : pareil
mingw : foreach 2-3% plus rapide que for.

pour une list :
visual : foreach 50% plus rapide que le for.
mingw : assez identique [edit] un peu moins bon de 1-2% avec le foreach[/edit]

[HanLee]

Ce n'est pas forcément le fait qu'il soit inliné, mais le fait qu'il soit recalculé à chaque fois ? Il serait intéressant de comparer avec un

Code :

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

1
2
3
4
list<T>::iterator end = maListe.end();
for (list<T>::iterator it = maListe.begin() ; it !=end ; ++it)
{
}

Oui en fait je supposais qu'inliner le .end() impliquait que le compilateur reconnaisse que l'expression est constante.
Mais oui je me suis mal exprimé.

pour une list :
visual : foreach 50% plus rapide que le for.
mingw : assez identique [edit] un peu moins bon de 1-2% avec le foreach[/edit]

Justement, je me demande si là visual a triché, en désactivant les guards qu'il applique sur ses itérateurs, qui restent activés même en release, à moins d'activer un certain #define.

[Sylvain Togni]

pour une list :
visual : foreach 50% plus rapide que le for.

Avec Visual 2005 for_each est 2-3% plus lent que les deux autres, dans les deux cas. Avec Visual 6, c'est plus rapide effectivement mais cela vient du double déférencement de l'itérateur, si tu remplace :

Code :

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

1
2
3
4
5
while(it!=end)
        {
           res += 2.*sqrt((double)*it)*sqrt((double)*it);
           ++it;
        }

par

Code :

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

1
2
3
4
5
6
while(it!=end)
        {
           int x = *it;
           res += 2.*sqrt((double)x)*sqrt((double)x);
           ++it;
        }

il n'y a plus de différence.

[yan]

Avec Visual 2005 for_each est 2-3% plus lent que les deux autres, dans les deux cas.

Au taf j'utilise visual 2005 et chez moi visual 2008 express.
Merci beaucoup pour la correction, ça change les résultats.
Maintenant pour 2005 j'ai :
vector : gain de 5-6% avec le for_each
list : gain de 8-10% avec le for_each

voici le code corrigé, j'ai peut être faire une autre erreur

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
#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <algorithm>
#include <ctime>
#include <cmath>
using namespace std;
 
#define CONTENAIRE vector
const int num =10000;
struct func
{
    func():res(0){};
    void operator()(int i)
    {
        double x = i;
      res +=  2.*sqrt(x)*sqrt(x);
    }
    double res;
};
 
struct gen
{
    gen():i(0){};
    int operator()()
    {
        return ++i;
    }
    int i;
};
 
struct parcour
{
    parcour(std::CONTENAIRE<int>::iterator iit,
        const std::CONTENAIRE<int>::iterator eend)
        :it(iit),end(eend)
    {}
    void next(){++it;};
    bool notfin()const{return it !=end;}
 
 
    std::CONTENAIRE<int>::iterator it;
    const std::CONTENAIRE<int>::iterator end;
};
 
 
int main(int argc, char* argv[])
{
 
    vector<int> tmp(10000+rand()%100);
    std::generate(tmp.begin(),tmp.end(),gen());
    CONTENAIRE<int> ensemble;
    std::copy(tmp.begin(),tmp.end(),std::inserter(ensemble,ensemble.begin()));
    double resultat;
 
 
 
    while(1)
    {
    clock_t t0 = clock();
 
    for (int i =0;i<num;++i)
    {
        std::CONTENAIRE<int>::iterator it = ensemble.begin();
        const std::CONTENAIRE<int>::iterator end = ensemble.end();
        double res(0);
        while(it!=end)
        {
           double x =*it;
           res += 2.*sqrt(x)*sqrt(x);
           ++it;
        }
        resultat =res;
    }
    double tempA = double(clock()-t0)/num;
    std::cout<<"A"<<" "<<resultat<<" "<<tempA <<std::endl;
 
    t0 = clock();
    for (int i =0;i<num;++i)
    {
        parcour p(ensemble.begin(),ensemble.end());
        double res(0);
        while(p.notfin())
        {
           double x =*p.it;
           res += 2.*sqrt(x)*sqrt(x);
           p.next();
        }
        resultat =res;
    }
    double tempB = double(clock()-t0)/num;
    std::cout<<"B"<<" "<<resultat<<" "<< tempB<<std::endl;
 
    t0 = clock();
    for (int i =0;i<num;++i)
    {
      resultat = std::for_each(ensemble.begin(),ensemble.end(),func()).res;
 
    }
    double tempC = double(clock()-t0)/num;
    std::cout<<"C"<<" "<<resultat<<" "<< tempC<<std::endl;
 
    std::cout<<"C/A"<<" "<<100*(1.-tempC/tempA)<<"%"<<std::endl;
    std::cout<<"C/B"<<" "<<100*(1.-tempC/tempB)<<"%"<<std::endl<<std::endl;
    }
 
	return 0;
}

[edit]
pour ceux qui veulent tester :
si le résultat est positif c'est un gain.
si le résultat est négatif c'est une perte.

[yan]

Justement, je me demande si là visual a triché, en désactivant les guards qu'il applique sur ses itérateurs, qui restent activés même en release, à moins d'activer un certain #define.

Y as de forte chance oui.
Visual transforme les iterator

Code :

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

1
2
3
4
5
6
7
8
9
10
template<class _InIt,
	class _Fn1> inline
	_Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
	{	// perform function for each element
	_CHECKED_BASE_TYPE(_InIt) _ChkFirst(_CHECKED_BASE(_First));
	_CHECKED_BASE_TYPE(_InIt) _ChkLast(_CHECKED_BASE(_Last));
	for (; _ChkFirst != _ChkLast; ++_ChkFirst)
		_Func(*_ChkFirst);
	return (_Func);
	}

[Sylvain Togni]

Pour info, avec Visual 2005, le code assembleur généré est strictement identique pour les trois boucles.

[yan]

Pour info, avec Visual 2005, le code assembleur généré est strictement identique pour les trois boucles.

ok, bizarre alors cette différence. Pourtant elle est assez constante.

[yan]

J'ai réussi a trouver le for_each, mais pas la boucle....

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
push	ecx
	push	esi
; Line 26
	mov	esi, DWORD PTR __First$[esp+8]
	push	edi
; Line 28
	mov	edi, DWORD PTR __Last$[esp+12]
	cmp	esi, edi
	je	SHORT $LN1@for_each
	npad	1
$LL3@for_each:
; Line 29
	fild	DWORD PTR [esi]
	call	__CIsqrt
	fld	ST(0)
	fadd	ST(0), ST(1)
	add	esi, 4
	cmp	esi, edi
	fmulp	ST(1), ST(0)
	fadd	QWORD PTR __Func$[esp+8]
	fstp	QWORD PTR __Func$[esp+8]
	jne	SHORT $LL3@for_each
$LN1@for_each:
; Line 30
	mov	eax, DWORD PTR __Func$[esp+8]
	mov	ecx, DWORD PTR __Func$[esp+12]
; Line 31
	pop	edi
	mov	DWORD PTR [ebx], eax
	mov	DWORD PTR [ebx+4], ecx
	mov	eax, ebx
	pop	esi
	pop	ecx
	ret	0

es ce que tu pourrais me donner la boucle en asm?
ps : c'est le code que j'ai avec visual 2005

[yan]

J'ai trouvé la boucle (je pense)
y as des call ebx et des test en plus

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
	mov	esi, eax
	jbe	SHORT $LN179@main
	call	ebx
	mov	edi, DWORD PTR _ensemble$[esp+204]
	mov	eax, DWORD PTR _ensemble$[esp+200]
$LN179@main:
	cmp	eax, edi
	mov	ebp, edi
	jbe	SHORT $LN191@main
	call	ebx
	mov	edi, DWORD PTR _ensemble$[esp+204]
$LN191@main:
	fldz
	fstp	QWORD PTR _res$25137[esp+196]
	npad	4
$LL11@main:
; Line 71
	cmp	esi, ebp
	je	SHORT $LN10@main
; Line 73
	cmp	esi, edi
	jb	SHORT $LN206@main
	call	ebx
	mov	edi, DWORD PTR _ensemble$[esp+204]
$LN206@main:
	fild	DWORD PTR [esi]
; Line 74
	call	__CIsqrt
	fld	ST(0)
; Line 75
	cmp	esi, edi
	fadd	ST(0), ST(1)
	fmulp	ST(1), ST(0)
	fadd	QWORD PTR _res$25137[esp+196]
	fstp	QWORD PTR _res$25137[esp+196]
	jb	SHORT $LN212@main
	call	ebx
	mov	edi, DWORD PTR _ensemble$[esp+204]
$LN212@main:
	add	esi, 4
; Line 76
	jmp	SHORT $LL11@main

[yan]

J'ai trouvé un bench appelé C/C++ Program Perfometer.
http://alexvn.freeservers.com/s1/perfometer.html

Et des résultats entre le for et le for_each :
http://groups.google.com/group/misc....f01397021dadbe
(a la fin y as des résultats)

: for_action : t_for.cpp #102 : for-loop - vector (size = 10) -> 13
: for_action : t_for.cpp #102 : for-loop - vector (size = 100) -> 124
: for_action : t_for.cpp #102 : for-loop - vector (size = 1000) -> 1225
: for_action : t_for.cpp #114 : for-loop - string (size = 10) -> 14
: for_action : t_for.cpp #114 : for-loop - string (size = 100) -> 120
: for_action : t_for.cpp #114 : for-loop - string (size = 1000) -> 1189
: for_action : t_for.cpp #126 : for-loop - list (size = 10) -> 15
: for_action : t_for.cpp #126 : for-loop - list (size = 100) -> 133
: for_action : t_for.cpp #126 : for-loop - list (size = 1000) -> 1330
: for_action : t_for.cpp #138 : for-loop - set (size = 10) -> 13
: for_action : t_for.cpp #138 : for-loop - set (size = 100) -> 129
: for_action : t_for.cpp #138 : for-loop - set (size = 1000) -> 1311
: for_action : t_for.cpp #152 : for_each - vector (size = 10) -> 10
: for_action : t_for.cpp #152 : for_each - vector (size = 100) -> 92
: for_action : t_for.cpp #152 : for_each - vector (size = 1000) -> 915
: for_action : t_for.cpp #160 : for_each - string (size = 10) -> 10
: for_action : t_for.cpp #160 : for_each - string (size = 100) -> 93
: for_action : t_for.cpp #160 : for_each - string (size = 1000) -> 917
: for_action : t_for.cpp #167 : for_each - list (size = 10) -> 9
: for_action : t_for.cpp #167 : for_each - list (size = 100) -> 78
: for_action : t_for.cpp #167 : for_each - list (size = 1000) -> 773
: for_action : t_for.cpp #174 : for_each - set (size = 10) -> 12
: for_action : t_for.cpp #174 : for_each - set (size = 100) -> 104
: for_action : t_for.cpp #174 : for_each - set (size = 1000) -> 1070

on peut constater que apparemment le for_each est plus rapide que le for.
[edit]}
ça date de 2003 alors c'est peut être un peu trop vieux

[Sylvain Togni]

Ah ouais, ce qui se passe c'est que j'avais enlevé les vérifications que rajoute visual par défaut même en release (_SECURE_SCL=0). Comme ça les 3 boucles génèrent le même code asm et sont donc aussi rapides.

En laissant les vérifications, par contre, for_each est un peu plus rapide car les vérifications de validité des itérateurs sont effectuées qu'une fois au début de la fonction (sur begin et end) pour for_each mais une fois par itération (sur it) pour les deux boucles.