Perf de parcours vector : iterator vs index

hello,
quelqu'un d'autre a surement deja du se poser la question, mais n'ayant pu trouver ni sur google ni dans la recherche de ce forum je me lance :

d'un point de vue performance du code assembleur généré pur (ie pas d'un point de vue lisibilité du code C++ ni rien) qu'est-il préférable pour parcourir un std::vector :

Code:

---

1 2 3 4 5 6

for(unsigned int i=0; i<vector.size(); ++i) { element& el = vector[i]; //process on el... }

---

ou

Code:

---

1 2 3 4 5 6

for(vector::iterator it=vector.begin(); it!=vector.end(); ++it) { elemnt& el = *it; //process on el... }

---

Merci d'avance pour vos avis d'experts.

C'est du pareil au même... En tout cas pour des vector de POD.

Par contre sortir l'évaluation de end()/size() de la boucle peut parait-il avoir un effet dans certains cas.

Citation:

---

Envoyé par JolyLoic

Par contre sortir l'évaluation de end()/size() de la boucle peut parait-il avoir un effet dans certains cas.

---

Quand on ne modifie pas le vecteur pendant le parcours, ça a effectivement un sens car ce sont deux éléments censés être constants pendant toute la boucle.

L'optimisation "Invariant code motion" (ou autres dénominations similaires) le fait déjà la plupart du temps, mais cela peut être utile également pour avoir un mode Debug un poil plus réactif ou pour forcer ceci si on commence à devenir limite en nombre de registres (cas relativement fréquent sur les x86, qui ont assez peu de registres généraux par rapport à des CPU RISC).

Citation:

---

Envoyé par Lavock

C'est du pareil au même... En tout cas pour des vector de POD.

---

ok. et pour des non POD ?

J'ai pas vérifier, mais à priori, y a pas de raison pour que se soit différent.

J'aurais quand même tendance à préférer la deuxième écriture.
Avec vector[i] on prend le "risque" d'avoir une addition (et peut-être même une multiplication) en plus.
Cependant, en mode debug la première écriture sera plus performante je pense. Avec les itérateurs il y a souvent un sacré "chipotage" ;)

Citation:

---

Envoyé par codnob

hello,
quelqu'un d'autre a surement deja du se poser la question, mais n'ayant pu trouver ni sur google ni dans la recherche de ce forum je me lance :

d'un point de vue performance du code assembleur généré pur (ie pas d'un point de vue lisibilité du code C++ ni rien) qu'est-il préférable pour parcourir un std::vector :

Code:

---

1 2 3 4 5 6

for(unsigned int i=0; i<vector.size(); ++i) { element& el = vector[i]; //process on el... }

---

ou

Code:

---

1 2 3 4 5 6

for(vector::iterator it=vector.begin(); it!=vector.end(); ++it) { elemnt& el = *it; //process on el... }

---

Merci d'avance pour vos avis d'experts.

---

(M-x mode-rant-on)
Je vais sûrement passer pour un rabat-joie - c'est normal, je suis fatigué, donc je suis un peu cassant - mais tu ne peux vérifier ce que tu obtiens par toi même ? L'implémentation des itérateurs dépends fortement du compilateur sélectionné, de même que le code généré. Il y a peu de chance que tu obtiennes une seule réponse à une question aussi large. Le mieux est encore de vérifier ce que ton compilateur génère comme code asm.

Et puis franchement, pourquoi poser une question sur un forum lorsque tu peux trouver la solution très simplement par toi même ? Ca n'a pas vraiment de sens...
(M-x mode-rant-off)

@camboui : +1
@Emmanuel : +2

Code:

---

gcc -S fichier.cpp | less

---

ça casse pas trois patte à un canard >< !

Tiens d'ailleurs il faudrait mettre une entrée dans la faq pour se genre de question :

Citation:

---

Qu'est-ce qui est plus performant entre ... et ... ?

Tout d'abord, il suffit de taper le code dans un éditeur quelconque. Puis, aller dans le dossier en mode console et taper : ( cf. plus haut )
Et constater par vous-même !!!

---

Bon j'avoue, y a moyen de tourner ça plus sympathiquement >< !

Citation:

---

Envoyé par Emmanuel Deloget

(M-x mode-rant-on)
Je vais sûrement passer pour un rabat-joie - c'est normal, je suis fatigué, donc je suis un peu cassant - mais tu ne peux vérifier ce que tu obtiens par toi même ? L'implémentation des itérateurs dépends fortement du compilateur sélectionné, de même que le code généré. Il y a peu de chance que tu obtiennes une seule réponse à une question aussi large. Le mieux est encore de vérifier ce que ton compilateur génère comme code asm.

Et puis franchement, pourquoi poser une question sur un forum lorsque tu peux trouver la solution très simplement par toi même ? Ca n'a pas vraiment de sens...
(M-x mode-rant-off)

---

Sans compter qu'un code aura probablement des problèmes de perfs pour d'autres raisons (par exemple ... un algo mal ficelé). Ce genre de chose produit rarement du gain significatif.

et vous, vous utilisez quoi comme notation ? pourquoi ? :mrgreen:

La deuxième car elle est plus dans les "habitudes" de la STL. Les exemples, la documentation, les bouquins, etc, sur la STL utilisent cette écriture. On finit par l'adopter.
Si j'avais à utiliser la première écriture je ferais plutôt:

Code:

---

1 2 3 4 5

for(unsigned int u=vector.size(); u>0; ) { element& el = vector[--u]; //process on el... }

---

Et si le sens d'itération est important alors se serait:

Code:

---

1 2 3 4 5 6

vector::iterator it=vector.begin(); for(unsigned int u=vector.size(); u>0; --u) { element& el = *it++; //process on el... }

---

Salut,
En l'absence d'une mesure montrant explicitement que le coût le plus important est lié au parcours de la boucle, j'utilise sans même me poser de question la version avec les itérateurs, voir carrément des algos STL ou les nouvelles boucles C++0x.

Si je devais écrire la boucle sans les itérateurs, de vieilles habitudes de C me feraient varier un pointeur et non utiliser un accès [] :

Code:

---

1 2 3 4 5 6

// std::vector<TYPE> vect; TYPE *p_cur = &vect[0]; for(int loop = vect.size();loop>0;--loop,++p_cur) { do_someting(p_cur); }

---

Mais, j'avoue que je ne sais même pas si ce genre de pratique est encore intéressante en C ?

Citation:

---

Envoyé par 3DArchi

Salut,
En l'absence d'une mesure montrant explicitement que le coût le plus important est lié au parcours de la boucle, j'utilise sans même me poser de question la version avec les itérateurs, voir carrément des algos STL ou les nouvelles boucles C++0x.

Si je devais écrire la boucle sans les itérateurs, de vieilles habitudes de C me feraient varier un pointeur et non utiliser un accès [] :

Code:

---

1 2 3 4 5 6

// std::vector<TYPE> vect; TYPE *p_cur = &vect[0]; for(int loop = vect.size();loop>0;--loop,++p_cur) { do_someting(p_cur); }

---

Mais, j'avoue que je ne sais même pas si ce genre de pratique est encore intéressante en C ?

---

Quitte à utiliser un pointeur/iterateur, autant utiliser dans le même temps une comparaison de pointeurs/iterateurs pour marquer la fin de la boucle plutôt qu'une variable qui n'a pas de lien véritable.

Code:

---

1 2 3 4 5 6

// std::vector<TYPE> vect; TYPE* p_end = &vect.back() for (TYPE* p_cur = &vect.front(); p_cur != p_end; ++p_cur) { do_something(p_cur); }

---

(accessoirement, std::vector<>::size() renvoie une std::size_t qui n'est pas garanti du tout d'avoir la même taille qu'un int).

Mais on entre vraiment dans le domaine de le micro-optimisation - qui n'a de sens que si il est prouvé par une mesure qu'elle a un intérêt quelconque. Le lecteur principal du code est humain - ce n'est pas une machine - il est donc logique de s'intéresser avant tout à la lisibilité du code, et non pas à ses effets supposés (notamment lorsque ces effets sont négligeable dans la plupart des cas).

Si on prends ton exemple, le simple fait d'appeler la fonction do_something() va provoquer le stockage sur la pile de plusieurs valeurs - il y a fort à parier que les instruction d'itération et de comparaison de la variable itérée à une constante ou à une autre valeur soit déjà presque négligeable à coté de l'appel de fonction. Complique encore le code, et là tu seras sûr que c'est vraiment négligeable.

Citation:

---

Envoyé par Emmanuel Deloget

Quitte à utiliser un pointeur/iterateur, autant utiliser dans le même temps une comparaison de pointeurs/iterateurs pour marquer la fin de la boucle plutôt qu'une variable qui n'a pas de lien véritable.

(accessoirement, std::vector<>::size() renvoie une std::size_t qui n'est pas garanti du tout d'avoir la même taille qu'un int).

---

Comme je l'ai dit, ce sont surtout des vieux réflexes de C :oops:

Citation:

---

Envoyé par Emmanuel Deloget

Mais on entre vraiment dans le domaine de le micro-optimisation - qui n'a de sens que si il est prouvé par une mesure qu'elle a un intérêt quelconque. Le lecteur principal du code est humain - ce n'est pas une machine - il est donc logique de s'intéresser avant tout à la lisibilité du code, et non pas à ses effets supposés (notamment lorsque ces effets sont négligeable dans la plupart des cas).

Si on prends ton exemple, le simple fait d'appeler la fonction do_something() va provoquer le stockage sur la pile de plusieurs valeurs - il y a fort à parier que les instruction d'itération et de comparaison de la variable itérée à une constante ou à une autre valeur soit déjà presque négligeable à coté de l'appel de fonction. Complique encore le code, et là tu seras sûr que c'est vraiment négligeable.

---

C'est à peu près le fond de ma pensé. Je suis aussi d'avis que dans 99% des cas les problèmes de perfs du parcours sont négligeables face aux autres traitements dans la boucle.

Citation:

---

Envoyé par MenshaKaine

et vous, vous utilisez quoi comme notation ? pourquoi ? :mrgreen:

---

Ca varie, selon :

• Le fait que je veuille attiré l'attention sur une chose ou une autre
• Le problème du chainage d'opérateur (ça arrive parfois de devoir se retouver à écrire it.operator->() == machin (ou it->operator==(machin)) si on fait pas gaffe).
• Mon humeur
• L'esthétique

sur un std::vector ou autre conteneur de la STL?

iterator et algorithme adapté à ce que je veux faire ( std::for_each, std::transform, copy etc.. ) .

du point de vue de esthétisme et de la lisibilité plusieurs de mes collègues préfère l'accès par index.

moi j'utilise par habitude les itérateurs, surtout qu'ils semblent entrée plus dans la logique d'utilisation de la STL ... Mais après avoir parler avec mes collègues, je suis en plein questionnement. :roll:

Salut,
J'aurais tendance à penser le contraire : esthétiquement (:aie:), les itérateurs offrent une meilleure abstraction que les index.

Je suis pas sûr que "l'esprit" STL soit de sélectionné un outils plutôt qu'un autre, mais la finalité.

Et puis j'ai quand même classé mes choix par ordre d'importance.

Par exemple, si je fais des opération sur les éléments d'un vecteur, j'utilise []. Pas que cela me déplait de faire autrement, mais j'attire l'attetion sur le fait que je fais des opération vectorisé.
A l'inverse, si je parcours pour faire un teste quelconque, ou toute chose ou l'identité de l'élément est plus importante que le fait qu'il soit dans un vecteur, j'utilise les itérateurs.

En gros, dit toi que c'est comme le passif :
Le chat a mangé la souris ! <=> La souris a été mangée par le chat ! (Stricto-sensu, cependant, on pourrait y voir de subtil distinction, notamment en fonction du contexte).

Salut,

A titre personnel, j'utiliserais volontiers les itérateurs lorsque je dois parcourir, peu ou prou, l'ensemble du vecteur, et l'index lorsque je veux accéder à un élément donné de celui-ci et que... j'en connais l'index...

Par exemple, si je veux faire une recherche dichotomique, ou si je veux accéder précisément à l'élément se trouvant à l'indice N (quelle que soit la manière dont cet indice a été évalué), j'utiliserai l'indice, car cela me semble plus facile à lire.

Par contre, s'il s'agit de mettre une logique "incrémentale" en oeuvre, de parcourir tout ou partie du vecteur afin, pourquoi pas, de sélectionner un élément donné en fonction de paramètres donnés, sans avoir d'autre précision que le fait qu'il se trouve "entre tel et tel élément" (pouvant être représenté par begin() et end()... ou non...), j'utiliserai les itérateurs.