différence entre itérateur et indice ( [] )

Version imprimable

17/09/2008, 22h54
ooxoo

différence entre itérateur et indice ( [] )
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:

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

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
17/09/2008, 23h46
loufoque

La version itérateur pourrait être plus rapide, mais en pratique les compilateurs sont pas stupides et c'est pareil.
18/09/2008, 03h12
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).
18/09/2008, 09h34
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.
18/09/2008, 18h19
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 :lol:

je retiens le for_each !
18/09/2008, 19h27
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.
18/09/2008, 21h16
HanLee

Citation:

Envoyé par Mongaulois

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...
18/09/2008, 21h20
JolyLoic
Citation:

Envoyé par HanLee

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:

1 2 3 4 list<T>::iterator end = maListe.end(); for (list<T>::iterator it = maListe.begin() ; it !=end ; ++it) { }
18/09/2008, 21h29
yan

Citation:

Envoyé par HanLee

J'ai du mal à voir pourquoi...

Tu parle pour le vector ou tous les conteneur??

Citation:

Envoyé par HanLee

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.

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:

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]

19/09/2008, 09h41
HanLee
Citation:
Envoyé par JolyLoic

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:

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é.

Citation:

Envoyé par Mongaulois

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.
19/09/2008, 10h59
Sylvain Togni
Citation:

Envoyé par Mongaulois

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:

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

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.

Citation:

Envoyé par Sylvain Togni

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:

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.

Citation:

Envoyé par HanLee

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:

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); }

19/09/2008, 12h29
Sylvain Togni

Pour info, avec Visual 2005, le code assembleur généré est strictement identique pour les trois boucles.
19/09/2008, 13h28
yan

Citation:

Envoyé par Sylvain Togni

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

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

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

Code:

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

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

Code:

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

19/09/2008, 14h27
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)

Citation:

: 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
19/09/2008, 16h16
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.
19/09/2008, 16h21
yan

Citation:

Envoyé par 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.

Ceci explique cela, merci.
A mon avis visual ne doit pas être le seul compilateur qui fait cela.
Malgré tout, je resterais sur l'idée de privilégier les algo pour être tranquille.
19/09/2008, 19h15
yan

:koi:
je viens de tester le code corrigé sous mingw.
pour un vector et une liste, for_each est 50% plus rapide que la boucle for...
j'ai beau vérifier, le résultat ne change pas.
Quelqu'un aurais un explication?

Avec visual express 2008, c'est pareil sans désactiver les sécurités.
19/09/2008, 23h45
loufoque

Mouarf, des tests de perf avec le mode debug de ta bibliothèque standard activé...

Les benchmarks ça se fait avec toutes optimisations activées. (-O3 -march=native -fomit-frame-pointer -DNDEBUG pour GCC, par exemple)
20/09/2008, 00h03
yan

Citation:

Envoyé par loufoque

Mouarf, des tests de perf avec le mode debug de ta bibliothèque standard activé...

Les benchmarks ça se fait avec toutes optimisations activées. (-O3 -march=native -fomit-frame-pointer -DNDEBUG pour GCC, par exemple)

J'en suis pas encore à faire des bench en debug...
Pour mingw, j'utilise code::block.
Par defaut, il utilise -02.
J'ai modifié pour qu'il utilise -03 et -fomit-frame-pointer et défini DNDEBUG
Ça ne change rien...
20/09/2008, 00h13
loufoque

Pour MSVC, il faut désactiver SECURE_SCL machin truc.
20/09/2008, 00h24
yan

Je veins d'essayer avec g++ 4.1 sous ubuntu, les temps sont pareil entre les trois methode.

Y as que mingw...Peut être parce qu'il est basé sur gcc 3??
20/09/2008, 00h44
JolyLoic

Citation:

Envoyé par loufoque

Pour MSVC, il faut désactiver SECURE_SCL machin truc.

Hélas, c'est une variable que Microsoft préconise de garder, même en release. Et donc on risque d'être obligé de l'utiliser dans des projets (qui utilisent des bibliothèques externes pré-compilées avec ce flag), alors qu'il est nocif sur les performances. L'utiliser pour des benchs ne me semble donc pas idiot.

Je me demande ce qui a motivé Microsoft à brider les performances de son compilateur, surtout quand on sait l'influence que des benchs de ce type peut avoir sur les développeurs C++.

Le pire, c'est que sur un prétexte de sécurité, cette option va pousser les gens n'ayant pas le choix à utiliser des tableaux à la C plutôt que des vectors, car la différence de perfs est significative, et donc à choisir une solution bien moins sûre...
20/09/2008, 11h53
loufoque

C'est comme décider de ne pas désactiver les asserts (définir NDEBUG) en release. Certains ne le font pas, tout simplement parce que le code n'a pas été suffisamment testé pour montrer que ces assertions n'arrivent jamais.
21/09/2008, 18h30
ooxoo

merci pour les tests, c'est intéressants.

Si je comprends bien le _SECURE_SCL vérifie à chaque appel de l'iterator, que celui n'a pas dépassé les limites du conteneur, dans le cas d'une boucle for.
Dans le cas d'un for_each, le compilateur ne fait pas cette vérification.
c'est ça?
21/09/2008, 18h52
yan

Citation:

Envoyé par ooxoo

Si je comprends bien le _SECURE_SCL vérifie à chaque appel de l'iterator, que celui n'a pas dépassé les limites du conteneur, dans le cas d'une boucle for.
Dans le cas d'un for_each, le compilateur ne fait pas cette vérification.
c'est ça?

En gros oui.
Le for_each utilise une autre forme de l'iterateur et le compilateur ne fait le test que pour le premier et le dernier iterateur avant la boucle.

Après, il y as l'optimisation qui peut changer la donne.
Sous visual 2008 express, le code corrigé donne les même perf pour les trois boucle sur une list ou un vector.