Je me demande s'il y a des differences de performances entre parcourir
un std::vector avec un iterator ou simplement en utilisant l'operateur[]
et si oui, de quel ordre?
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Alexandre
"benoit le callennec" a écrit dans le message de news:40050177$
Bonjour,
Je me demande s'il y a des differences de performances entre parcourir un std::vector avec un iterator ou simplement en utilisant l'operateur[] et si oui, de quel ordre?
Merci d'avance, Benoit
Normalement, la structure mémoire du vector doit lui garantir une perf équivalente avec [] qu'avec un itérateur. Ce qui, je crois, n'est pas le cas pour deque.
"benoit le callennec" <benoit.lecallennec@epfl.ch> a écrit dans le message
de news:40050177$1@epflnews.epfl.ch...
Bonjour,
Je me demande s'il y a des differences de performances entre parcourir
un std::vector avec un iterator ou simplement en utilisant l'operateur[]
et si oui, de quel ordre?
Merci d'avance,
Benoit
Normalement, la structure mémoire du vector doit lui garantir une perf
équivalente avec [] qu'avec un itérateur.
Ce qui, je crois, n'est pas le cas pour deque.
"benoit le callennec" a écrit dans le message de news:40050177$
Bonjour,
Je me demande s'il y a des differences de performances entre parcourir un std::vector avec un iterator ou simplement en utilisant l'operateur[] et si oui, de quel ordre?
Merci d'avance, Benoit
Normalement, la structure mémoire du vector doit lui garantir une perf équivalente avec [] qu'avec un itérateur. Ce qui, je crois, n'est pas le cas pour deque.
ben_cal
Alexandre wrote:
Normalement, la structure mémoire du vector doit lui garantir une perf équivalente avec [] qu'avec un itérateur. Ce qui, je crois, n'est pas le cas pour deque.
Ok, je vois.
Merci beaucoup, Benoit
Alexandre wrote:
Normalement, la structure mémoire du vector doit lui garantir une perf
équivalente avec [] qu'avec un itérateur.
Ce qui, je crois, n'est pas le cas pour deque.
Normalement, la structure mémoire du vector doit lui garantir une perf équivalente avec [] qu'avec un itérateur. Ce qui, je crois, n'est pas le cas pour deque.
Ok, je vois.
Merci beaucoup, Benoit
kanze
benoit le callennec wrote in message news:<40050177$...
Je me demande s'il y a des differences de performances entre parcourir un std::vector avec un iterator ou simplement en utilisant l'operateur[] et si oui, de quel ordre?
Tout dépend de l'implémentation et du compilateur, mais a priori : si operator[] est plus rapide, rien n'empêche à l'itérateur de l'utiliser. Donc, je dirais que dans une bonne implémentation, operator[] ne peut pas être plus vite que l'itérateur. Sauf qu'en mode debug, il y a plus de choses à vérifier avec l'itérateur.
Dans l'ensemble, j'aurais une tendance à dire que le choix doit se faire plutôt sur la sémantique voulue, et non la vitesse d'une implémentation donnée. Si je veux itérer, j'utilise un itérateur ; si je veux accéder à un élément donné, à partir de son rang, j'utilise l'operator[].
-- James Kanze GABI Software mailto: Conseils en informatique orientée objet/ http://www.gabi-soft.fr Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16
benoit le callennec <benoit.lecallennec@epfl.ch> wrote in message
news:<40050177$1@epflnews.epfl.ch>...
Je me demande s'il y a des differences de performances entre parcourir
un std::vector avec un iterator ou simplement en utilisant
l'operateur[] et si oui, de quel ordre?
Tout dépend de l'implémentation et du compilateur, mais a priori : si
operator[] est plus rapide, rien n'empêche à l'itérateur de l'utiliser.
Donc, je dirais que dans une bonne implémentation, operator[] ne peut
pas être plus vite que l'itérateur. Sauf qu'en mode debug, il y a plus
de choses à vérifier avec l'itérateur.
Dans l'ensemble, j'aurais une tendance à dire que le choix doit se faire
plutôt sur la sémantique voulue, et non la vitesse d'une implémentation
donnée. Si je veux itérer, j'utilise un itérateur ; si je veux accéder à
un élément donné, à partir de son rang, j'utilise l'operator[].
--
James Kanze GABI Software mailto:kanze@gabi-soft.fr
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16
benoit le callennec wrote in message news:<40050177$...
Je me demande s'il y a des differences de performances entre parcourir un std::vector avec un iterator ou simplement en utilisant l'operateur[] et si oui, de quel ordre?
Tout dépend de l'implémentation et du compilateur, mais a priori : si operator[] est plus rapide, rien n'empêche à l'itérateur de l'utiliser. Donc, je dirais que dans une bonne implémentation, operator[] ne peut pas être plus vite que l'itérateur. Sauf qu'en mode debug, il y a plus de choses à vérifier avec l'itérateur.
Dans l'ensemble, j'aurais une tendance à dire que le choix doit se faire plutôt sur la sémantique voulue, et non la vitesse d'une implémentation donnée. Si je veux itérer, j'utilise un itérateur ; si je veux accéder à un élément donné, à partir de son rang, j'utilise l'operator[].
-- James Kanze GABI Software mailto: Conseils en informatique orientée objet/ http://www.gabi-soft.fr Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16
Samuel Krempp
le Thursday 15 January 2004 08:52, écrivit :
benoit le callennec wrote in message news:<40050177$...
Je me demande s'il y a des differences de performances entre parcourir un std::vector avec un iterator ou simplement en utilisant l'operateur[] et si oui, de quel ordre?
Tout dépend de l'implémentation et du compilateur, mais a priori : si operator[] est plus rapide, rien n'empêche à l'itérateur de l'utiliser. Donc, je dirais que dans une bonne implémentation, operator[] ne peut pas être plus vite que l'itérateur. Sauf qu'en mode debug, il y a plus de choses à vérifier avec l'itérateur.
quand j'ai fait des mesures sur une boucle presque vide, la principale différence de temps (jusqu'à un facteur 2 en gros, IIRC) vient de la façon dont on teste la fin de boucle :
for(; it != v.end(); ++it) *it ....
plus lent que : Iter vend = v.end(); for(Iter it=v.begin(); it != vend; ++it) *it ...
qui est vraiment sans différence significative avec sz = v.size(); for(size_t i=0; i <sz; ++i) v[i] ...
C'est dire à quel point l'itération elle même est rapide, et que v[i] / ++i vs *it / ++it a vraiment peu (ou pas) d'impact mesurable.
(faire une copie locale de end() / size() peut avoir des conséquences - si v est modifié dans la boucle par exple. J'ai remarqué que le compilo en général ne fait pas de lui même cette optimisation. D'ailleurs à propos des optimisations permises au compilo : si il est sûr que le contenu de la boucle ne va pas changer le résultat de size() (ou end()) des appels suivant, il a le droit d'utiliser en fait une copie locale, non ? Et pour ça, la possibilité éventuelle de threads concurrents n'a pas à être prise en compte, c'est à l'utilisateur de thread de s'en soucier, c'est bien ça ?)
-- Sam
le Thursday 15 January 2004 08:52, kanze@gabi-soft.fr écrivit :
benoit le callennec <benoit.lecallennec@epfl.ch> wrote in message
news:<40050177$1@epflnews.epfl.ch>...
Je me demande s'il y a des differences de performances entre parcourir
un std::vector avec un iterator ou simplement en utilisant
l'operateur[] et si oui, de quel ordre?
Tout dépend de l'implémentation et du compilateur, mais a priori : si
operator[] est plus rapide, rien n'empêche à l'itérateur de l'utiliser.
Donc, je dirais que dans une bonne implémentation, operator[] ne peut
pas être plus vite que l'itérateur. Sauf qu'en mode debug, il y a plus
de choses à vérifier avec l'itérateur.
quand j'ai fait des mesures sur une boucle presque vide, la principale
différence de temps (jusqu'à un facteur 2 en gros, IIRC) vient de la façon
dont on teste la fin de boucle :
for(; it != v.end(); ++it)
*it ....
plus lent que :
Iter vend = v.end();
for(Iter it=v.begin(); it != vend; ++it)
*it ...
qui est vraiment sans différence significative avec
sz = v.size();
for(size_t i=0; i <sz; ++i)
v[i] ...
C'est dire à quel point l'itération elle même est rapide, et que v[i] / ++i
vs *it / ++it a vraiment peu (ou pas) d'impact mesurable.
(faire une copie locale de end() / size() peut avoir des conséquences - si v
est modifié dans la boucle par exple. J'ai remarqué que le compilo en
général ne fait pas de lui même cette optimisation. D'ailleurs à propos des
optimisations permises au compilo : si il est sûr que le contenu de la
boucle ne va pas changer le résultat de size() (ou end()) des appels
suivant, il a le droit d'utiliser en fait une copie locale, non ?
Et pour ça, la possibilité éventuelle de threads concurrents n'a pas à être
prise en compte, c'est à l'utilisateur de thread de s'en soucier, c'est
bien ça ?)
benoit le callennec wrote in message news:<40050177$...
Je me demande s'il y a des differences de performances entre parcourir un std::vector avec un iterator ou simplement en utilisant l'operateur[] et si oui, de quel ordre?
Tout dépend de l'implémentation et du compilateur, mais a priori : si operator[] est plus rapide, rien n'empêche à l'itérateur de l'utiliser. Donc, je dirais que dans une bonne implémentation, operator[] ne peut pas être plus vite que l'itérateur. Sauf qu'en mode debug, il y a plus de choses à vérifier avec l'itérateur.
quand j'ai fait des mesures sur une boucle presque vide, la principale différence de temps (jusqu'à un facteur 2 en gros, IIRC) vient de la façon dont on teste la fin de boucle :
for(; it != v.end(); ++it) *it ....
plus lent que : Iter vend = v.end(); for(Iter it=v.begin(); it != vend; ++it) *it ...
qui est vraiment sans différence significative avec sz = v.size(); for(size_t i=0; i <sz; ++i) v[i] ...
C'est dire à quel point l'itération elle même est rapide, et que v[i] / ++i vs *it / ++it a vraiment peu (ou pas) d'impact mesurable.
(faire une copie locale de end() / size() peut avoir des conséquences - si v est modifié dans la boucle par exple. J'ai remarqué que le compilo en général ne fait pas de lui même cette optimisation. D'ailleurs à propos des optimisations permises au compilo : si il est sûr que le contenu de la boucle ne va pas changer le résultat de size() (ou end()) des appels suivant, il a le droit d'utiliser en fait une copie locale, non ? Et pour ça, la possibilité éventuelle de threads concurrents n'a pas à être prise en compte, c'est à l'utilisateur de thread de s'en soucier, c'est bien ça ?)
-- Sam
kanze
Samuel Krempp wrote in message news:<4006a4e9$0$29082$...
le Thursday 15 January 2004 08:52, écrivit :
benoit le callennec wrote in message news:<40050177$...
Je me demande s'il y a des differences de performances entre parcourir un std::vector avec un iterator ou simplement en utilisant l'operateur[] et si oui, de quel ordre?
Tout dépend de l'implémentation et du compilateur, mais a priori : si operator[] est plus rapide, rien n'empêche à l'itérateur de l'utiliser. Donc, je dirais que dans une bonne implémentation, operator[] ne peut pas être plus vite que l'itérateur. Sauf qu'en mode debug, il y a plus de choses à vérifier avec l'itérateur.
quand j'ai fait des mesures sur une boucle presque vide, la principale différence de temps (jusqu'à un facteur 2 en gros, IIRC) vient de la façon dont on teste la fin de boucle :
for(; it != v.end(); ++it) *it ....
plus lent que : Iter vend = v.end(); for(Iter it=v.begin(); it != vend; ++it) *it ...
qui est vraiment sans différence significative avec sz = v.size(); for(size_t i=0; i <sz; ++i) v[i] ...
C'est à peu près ce que j'ai trouvé aussi. C'est un peu compréhensible, aussi.
C'est dire à quel point l'itération elle même est rapide, et que v[i] / ++i vs *it / ++it a vraiment peu (ou pas) d'impact mesurable.
J'imagine que c'est le cas sur la plupart des machines et avec la plupart des compilateurs.
(faire une copie locale de end() / size() peut avoir des conséquences - si v est modifié dans la boucle par exple. J'ai remarqué que le compilo en général ne fait pas de lui même cette optimisation.
En principe, il pourrait, dans la mésure qu'on n'appelle pas d'autre fonction dans la boucle, ou que le vector n'est pas visible par ailleurs. Dans la pratique, c'est une optimisation qui exige pas mal d'effort de la part du compilateur (au moins qu'il a une connaissance explicite de vector). Dans le cas où on est dans une fonction, et le vector a été passé comme paramètre en référence (ou qu'il s'agit d'une fonction membre et qu'il soit membre de la classe), il faudrait même un analyse extensif entre-module -- je ne connais pas de compilateurs actuellement qui le font.
D'ailleurs à propos des optimisations permises au compilo : si il est sûr que le contenu de la boucle ne va pas changer le résultat de size() (ou end()) des appels suivant, il a le droit d'utiliser en fait une copie locale, non ?
Dès que le comportement visible du programme (les entrées/sorties et les lectures et les écritures des objets volatiles) ne change pas, le compilateur peut faire ce qu'il veut. En principe, donc, pas de problème. Dans la pratique, en revanche, sauf dans des cas les plus simple, il faut une analyse assez poussé.
Et pour ça, la possibilité éventuelle de threads concurrents n'a pas à être prise en compte, c'est à l'utilisateur de thread de s'en soucier, c'est bien ça ?)
En ce qui concerne la norme, dès qu'il y a plus d'un thread, il y a un comportement indéfini. Ensuite, c'est une question de ce que le vendeur a voulu garantir. Dans la pratique, ce que tu dis vaut bien pour Posix, et étant donné que l'interface de vector expose des références et des pointeurs à de la mémoire interne, je vois mal comment il pourrait en être autrement.
-- James Kanze GABI Software mailto: Conseils en informatique orientée objet/ http://www.gabi-soft.fr Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16
Samuel Krempp <krempp@crans.truc.en.trop.ens-cachan.fr> wrote in message
news:<4006a4e9$0$29082$636a55ce@news.free.fr>...
le Thursday 15 January 2004 08:52, kanze@gabi-soft.fr écrivit :
benoit le callennec <benoit.lecallennec@epfl.ch> wrote in message
news:<40050177$1@epflnews.epfl.ch>...
Je me demande s'il y a des differences de performances entre
parcourir un std::vector avec un iterator ou simplement en
utilisant l'operateur[] et si oui, de quel ordre?
Tout dépend de l'implémentation et du compilateur, mais a priori :
si operator[] est plus rapide, rien n'empêche à l'itérateur de
l'utiliser. Donc, je dirais que dans une bonne implémentation,
operator[] ne peut pas être plus vite que l'itérateur. Sauf qu'en
mode debug, il y a plus de choses à vérifier avec l'itérateur.
quand j'ai fait des mesures sur une boucle presque vide, la principale
différence de temps (jusqu'à un facteur 2 en gros, IIRC) vient de la
façon dont on teste la fin de boucle :
for(; it != v.end(); ++it)
*it ....
plus lent que :
Iter vend = v.end();
for(Iter it=v.begin(); it != vend; ++it)
*it ...
qui est vraiment sans différence significative avec
sz = v.size();
for(size_t i=0; i <sz; ++i)
v[i] ...
C'est à peu près ce que j'ai trouvé aussi. C'est un peu compréhensible,
aussi.
C'est dire à quel point l'itération elle même est rapide, et que v[i]
/ ++i vs *it / ++it a vraiment peu (ou pas) d'impact mesurable.
J'imagine que c'est le cas sur la plupart des machines et avec la
plupart des compilateurs.
(faire une copie locale de end() / size() peut avoir des conséquences
- si v est modifié dans la boucle par exple. J'ai remarqué que le
compilo en général ne fait pas de lui même cette optimisation.
En principe, il pourrait, dans la mésure qu'on n'appelle pas d'autre
fonction dans la boucle, ou que le vector n'est pas visible par
ailleurs. Dans la pratique, c'est une optimisation qui exige pas mal
d'effort de la part du compilateur (au moins qu'il a une connaissance
explicite de vector). Dans le cas où on est dans une fonction, et le
vector a été passé comme paramètre en référence (ou qu'il s'agit d'une
fonction membre et qu'il soit membre de la classe), il faudrait même un
analyse extensif entre-module -- je ne connais pas de compilateurs
actuellement qui le font.
D'ailleurs à propos des optimisations permises au compilo : si il est
sûr que le contenu de la boucle ne va pas changer le résultat de
size() (ou end()) des appels suivant, il a le droit d'utiliser en fait
une copie locale, non ?
Dès que le comportement visible du programme (les entrées/sorties et les
lectures et les écritures des objets volatiles) ne change pas, le
compilateur peut faire ce qu'il veut. En principe, donc, pas de
problème. Dans la pratique, en revanche, sauf dans des cas les plus
simple, il faut une analyse assez poussé.
Et pour ça, la possibilité éventuelle de threads concurrents n'a pas à
être prise en compte, c'est à l'utilisateur de thread de s'en soucier,
c'est bien ça ?)
En ce qui concerne la norme, dès qu'il y a plus d'un thread, il y a un
comportement indéfini. Ensuite, c'est une question de ce que le vendeur
a voulu garantir. Dans la pratique, ce que tu dis vaut bien pour Posix,
et étant donné que l'interface de vector expose des références et des
pointeurs à de la mémoire interne, je vois mal comment il pourrait en
être autrement.
--
James Kanze GABI Software mailto:kanze@gabi-soft.fr
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16
Samuel Krempp wrote in message news:<4006a4e9$0$29082$...
le Thursday 15 January 2004 08:52, écrivit :
benoit le callennec wrote in message news:<40050177$...
Je me demande s'il y a des differences de performances entre parcourir un std::vector avec un iterator ou simplement en utilisant l'operateur[] et si oui, de quel ordre?
Tout dépend de l'implémentation et du compilateur, mais a priori : si operator[] est plus rapide, rien n'empêche à l'itérateur de l'utiliser. Donc, je dirais que dans une bonne implémentation, operator[] ne peut pas être plus vite que l'itérateur. Sauf qu'en mode debug, il y a plus de choses à vérifier avec l'itérateur.
quand j'ai fait des mesures sur une boucle presque vide, la principale différence de temps (jusqu'à un facteur 2 en gros, IIRC) vient de la façon dont on teste la fin de boucle :
for(; it != v.end(); ++it) *it ....
plus lent que : Iter vend = v.end(); for(Iter it=v.begin(); it != vend; ++it) *it ...
qui est vraiment sans différence significative avec sz = v.size(); for(size_t i=0; i <sz; ++i) v[i] ...
C'est à peu près ce que j'ai trouvé aussi. C'est un peu compréhensible, aussi.
C'est dire à quel point l'itération elle même est rapide, et que v[i] / ++i vs *it / ++it a vraiment peu (ou pas) d'impact mesurable.
J'imagine que c'est le cas sur la plupart des machines et avec la plupart des compilateurs.
(faire une copie locale de end() / size() peut avoir des conséquences - si v est modifié dans la boucle par exple. J'ai remarqué que le compilo en général ne fait pas de lui même cette optimisation.
En principe, il pourrait, dans la mésure qu'on n'appelle pas d'autre fonction dans la boucle, ou que le vector n'est pas visible par ailleurs. Dans la pratique, c'est une optimisation qui exige pas mal d'effort de la part du compilateur (au moins qu'il a une connaissance explicite de vector). Dans le cas où on est dans une fonction, et le vector a été passé comme paramètre en référence (ou qu'il s'agit d'une fonction membre et qu'il soit membre de la classe), il faudrait même un analyse extensif entre-module -- je ne connais pas de compilateurs actuellement qui le font.
D'ailleurs à propos des optimisations permises au compilo : si il est sûr que le contenu de la boucle ne va pas changer le résultat de size() (ou end()) des appels suivant, il a le droit d'utiliser en fait une copie locale, non ?
Dès que le comportement visible du programme (les entrées/sorties et les lectures et les écritures des objets volatiles) ne change pas, le compilateur peut faire ce qu'il veut. En principe, donc, pas de problème. Dans la pratique, en revanche, sauf dans des cas les plus simple, il faut une analyse assez poussé.
Et pour ça, la possibilité éventuelle de threads concurrents n'a pas à être prise en compte, c'est à l'utilisateur de thread de s'en soucier, c'est bien ça ?)
En ce qui concerne la norme, dès qu'il y a plus d'un thread, il y a un comportement indéfini. Ensuite, c'est une question de ce que le vendeur a voulu garantir. Dans la pratique, ce que tu dis vaut bien pour Posix, et étant donné que l'interface de vector expose des références et des pointeurs à de la mémoire interne, je vois mal comment il pourrait en être autrement.
-- James Kanze GABI Software mailto: Conseils en informatique orientée objet/ http://www.gabi-soft.fr Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16
