IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

SL & STL C++ Discussion :

Perf de parcours vector : iterator vs index


Sujet :

SL & STL C++

  1. #1
    Membre du Club
    Inscrit en
    Juillet 2009
    Messages
    7
    Détails du profil
    Informations forums :
    Inscription : Juillet 2009
    Messages : 7
    Par défaut 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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    for(unsigned int i=0; i<vector.size(); ++i)
    {
           element& el = vector[i];
           //process on el...
    }
    ou

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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.

  2. #2
    Membre chevronné Avatar de Lavock
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    560
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 560
    Par défaut
    C'est du pareil au même... En tout cas pour des vector de POD.

  3. #3
    Rédacteur/Modérateur
    Avatar de JolyLoic
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2004
    Messages
    5 463
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Août 2004
    Messages : 5 463
    Par défaut
    Par contre sortir l'évaluation de end()/size() de la boucle peut parait-il avoir un effet dans certains cas.
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

  4. #4
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 50
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    Par défaut
    Citation Envoyé par JolyLoic Voir le message
    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).
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

  5. #5
    Membre du Club
    Inscrit en
    Juillet 2009
    Messages
    7
    Détails du profil
    Informations forums :
    Inscription : Juillet 2009
    Messages : 7
    Par défaut
    Citation Envoyé par Lavock Voir le message
    C'est du pareil au même... En tout cas pour des vector de POD.
    ok. et pour des non POD ?

  6. #6
    Membre chevronné Avatar de Lavock
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    560
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 560
    Par défaut
    J'ai pas vérifier, mais à priori, y a pas de raison pour que se soit différent.

  7. #7
    Membre éclairé
    Inscrit en
    Avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : Avril 2005
    Messages : 1 110
    Par défaut
    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"

  8. #8
    Membre Expert

    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2007
    Messages
    1 895
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Septembre 2007
    Messages : 1 895
    Par défaut
    Citation Envoyé par codnob Voir le message
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    for(unsigned int i=0; i<vector.size(); ++i)
    {
           element& el = vector[i];
           //process on el...
    }
    ou

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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)
    [FAQ des forums][FAQ Développement 2D, 3D et Jeux][Si vous ne savez pas ou vous en êtes...]
    Essayez d'écrire clairement (c'est à dire avec des mots français complets). SMS est votre ennemi.
    Evitez les arguments inutiles - DirectMachin vs. OpenTruc ou G++ vs. Café. C'est dépassé tout ça.
    Et si vous êtes sages, vous aurez peut être vous aussi la chance de passer à la télé. Ou pas.

    Ce site contient un forum d'entraide gratuit. Il ne s'use que si l'on ne s'en sert pas.

  9. #9
    Membre chevronné Avatar de Lavock
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    560
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 560
    Par défaut
    @camboui : +1
    @Emmanuel : +2
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 :

    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 >< !

  10. #10
    Rédacteur
    Avatar de 3DArchi
    Profil pro
    Inscrit en
    Juin 2008
    Messages
    7 634
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2008
    Messages : 7 634
    Par défaut
    Citation Envoyé par Emmanuel Deloget Voir le message
    (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.

  11. #11
    Membre confirmé Avatar de MenshaKaine
    Inscrit en
    Juin 2009
    Messages
    68
    Détails du profil
    Informations personnelles :
    Âge : 48

    Informations forums :
    Inscription : Juin 2009
    Messages : 68
    Par défaut
    et vous, vous utilisez quoi comme notation ? pourquoi ?

  12. #12
    Membre éclairé
    Inscrit en
    Avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : Avril 2005
    Messages : 1 110
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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...
    }

  13. #13
    Rédacteur
    Avatar de 3DArchi
    Profil pro
    Inscrit en
    Juin 2008
    Messages
    7 634
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2008
    Messages : 7 634
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 ?

  14. #14
    Membre Expert

    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2007
    Messages
    1 895
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Septembre 2007
    Messages : 1 895
    Par défaut
    Citation Envoyé par 3DArchi Voir le message
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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.
    [FAQ des forums][FAQ Développement 2D, 3D et Jeux][Si vous ne savez pas ou vous en êtes...]
    Essayez d'écrire clairement (c'est à dire avec des mots français complets). SMS est votre ennemi.
    Evitez les arguments inutiles - DirectMachin vs. OpenTruc ou G++ vs. Café. C'est dépassé tout ça.
    Et si vous êtes sages, vous aurez peut être vous aussi la chance de passer à la télé. Ou pas.

    Ce site contient un forum d'entraide gratuit. Il ne s'use que si l'on ne s'en sert pas.

  15. #15
    Rédacteur
    Avatar de 3DArchi
    Profil pro
    Inscrit en
    Juin 2008
    Messages
    7 634
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2008
    Messages : 7 634
    Par défaut
    Citation Envoyé par Emmanuel Deloget Voir le message
    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
    Citation Envoyé par Emmanuel Deloget Voir le message
    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.

  16. #16
    Membre chevronné Avatar de Lavock
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    560
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 560
    Par défaut
    Citation Envoyé par MenshaKaine Voir le message
    et vous, vous utilisez quoi comme notation ? pourquoi ?
    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

  17. #17
    Membre émérite
    Profil pro
    Inscrit en
    Mai 2006
    Messages
    780
    Détails du profil
    Informations personnelles :
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Mai 2006
    Messages : 780
    Par défaut
    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.. ) .

  18. #18
    Membre confirmé Avatar de MenshaKaine
    Inscrit en
    Juin 2009
    Messages
    68
    Détails du profil
    Informations personnelles :
    Âge : 48

    Informations forums :
    Inscription : Juin 2009
    Messages : 68
    Par défaut
    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.

  19. #19
    Rédacteur
    Avatar de 3DArchi
    Profil pro
    Inscrit en
    Juin 2008
    Messages
    7 634
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2008
    Messages : 7 634
    Par défaut
    Salut,
    J'aurais tendance à penser le contraire : esthétiquement (), les itérateurs offrent une meilleure abstraction que les index.

  20. #20
    Membre chevronné Avatar de Lavock
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    560
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 560
    Par défaut
    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).

Discussions similaires

  1. vector : iterator.. besoins d'une petite précision
    Par italiasky dans le forum SL & STL
    Réponses: 2
    Dernier message: 18/11/2008, 10h37
  2. Réponses: 10
    Dernier message: 30/06/2008, 19h59
  3. pair, vector, iterator et type_traits
    Par NiamorH dans le forum SL & STL
    Réponses: 7
    Dernier message: 21/02/2008, 18h56
  4. Réponses: 2
    Dernier message: 07/12/2007, 02h19
  5. Template - vector - iterator
    Par jmeuf dans le forum Langage
    Réponses: 6
    Dernier message: 30/03/2007, 13h42

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo