OVH Cloud OVH Cloud

[STL] vector et boucle for

7 réponses
Avatar
BlueR
Bonjour

Petite question simple (niveau débutant STL) concernant la rapidité d'une
boucle for sur les éléments d'un vecteur, par exemple :

//********************************
class objet
{ int d;
bool vrai;
string nom;
vector<int> numeros;
// constructeur, constructeur de copie, etc...
}

vector<objet> toto;
// je le remplis

vector<objet>::iterator iobj;

for (iobj = toto.begin(); iobj < toto.end(); iobj++)
{
// je fais quelque chose qui ne modifie pas le vecteur (pas d'ajout
d'éléments, suppression, ni tri, etc...) mais qui peut modifier les
valeurs contenuesdans les objets "objet", dont le nombre d'éléments du
vecteur numeros contenu dans chaque objet.
}

//********************************
Est-ce que la valeur d'arrêt de la boucle, toto.end(), est calculée à
chaque à chaque itération ou une seule fois à l'entrée de la boucle ?

Merci.
--
BlueR

7 réponses

Avatar
Guillaume Brocker
Est-ce que la valeur d'arrêt de la boucle, toto.end(), est calculée à
chaque à chaque itération ou une seule fois à l'entrée de la boucle ?


Et bien, vu que tu testes la fin du vecteur en écrivant "iobj <
toto.end()", tu vas intérroger le vecteur sur sa fin. On peut donc
considérer que l'iterateur de fin est calculé à chaque fois.

Maintenant, pour un vecteur, cela n'est pas très couteux. Le plus long
dans l'histoire sera l'appel de la fonction "end".

Guillaume Brocker

Avatar
Loïc Joly
BlueR wrote:


for (iobj = toto.begin(); iobj < toto.end(); iobj++)
{
// je fais quelque chose qui ne modifie pas le vecteur (pas d'ajout
d'éléments, suppression, ni tri, etc...) mais qui peut modifier les
valeurs contenuesdans les objets "objet", dont le nombre d'éléments du
vecteur numeros contenu dans chaque objet.
}

//********************************
Est-ce que la valeur d'arrêt de la boucle, toto.end(), est calculée à
chaque à chaque itération ou une seule fois à l'entrée de la boucle ?


Les optimisation, c'est avant tout une histoise de "comme si", après le
compilateur fait ce qu'il veut.

Ici, tout doit se passer "comme si" la valeur était lue à chaque fois.
Maintenant, le compilateur a plusieurs choix :
- La lire à chaque fois
- La lire au début après avoir vérifié que ça revenait au même (pas
trivial du tout à vérifier pour le compilo, à ce qu'il paraît)
- La lire une foi sur 42 après avoir vérifié que ça ne posait pas de
problème
- ...

Le première possibilité est la plus probable.

--
Loïc

Avatar
Alexandre
"Guillaume Brocker" a écrit dans le message de
news:4027ed50$0$28129$
Est-ce que la valeur d'arrêt de la boucle, toto.end(), est calculée à
chaque à chaque itération ou une seule fois à l'entrée de la boucle ?


Et bien, vu que tu testes la fin du vecteur en écrivant "iobj <
toto.end()", tu vas intérroger le vecteur sur sa fin. On peut donc
considérer que l'iterateur de fin est calculé à chaque fois.

Maintenant, pour un vecteur, cela n'est pas très couteux. Le plus long
dans l'histoire sera l'appel de la fonction "end".


Qui est peut-être écrite inline, donc pas de temps à l'appel...
Sinon, si le vecteur n'est pas modifié, il suffit de la stocker avant...
std::vector<truc>::iterator Fin = Vecteur.end();
for(std::vector<truc>::iterator i = Vecteur.begin(); i!=Fin;++i)
...


Guillaume Brocker



Avatar
kanze
Loïc Joly wrote in message
news:<c08tvm$n07$...
BlueR wrote:

for (iobj = toto.begin(); iobj < toto.end(); iobj++)
{
// je fais quelque chose qui ne modifie pas le vecteur (pas d'ajout
d'éléments, suppression, ni tri, etc...) mais qui peut modifier les
valeurs contenuesdans les objets "objet", dont le nombre d'éléments du
vecteur numeros contenu dans chaque objet.
}

//********************************
Est-ce que la valeur d'arrêt de la boucle, toto.end(), est calculée à
chaque à chaque itération ou une seule fois à l'entrée de la boucle ?


Les optimisation, c'est avant tout une histoise de "comme si", après
le compilateur fait ce qu'il veut.

Ici, tout doit se passer "comme si" la valeur était lue à chaque fois.
Maintenant, le compilateur a plusieurs choix :
- La lire à chaque fois
- La lire au début après avoir vérifié que ça revenait au même (pas
trivial du tout à vérifier pour le compilo, à ce qu'il paraît)
- La lire une foi sur 42 après avoir vérifié que ça ne posait pas de
problème
- ...

Le première possibilité est la plus probable.


C'est de loin la plus simple pour l'auteur du compilateur. Si end()
n'est pas inline, il y a actuellement fort peu de compilateurs qui
pourrait sortir l'appel de la boucle. Si il est inline, tout
dépend. L'optimisation s'appelle lever l'invariant de la boucle, et
c'est une optimisation très courante QUAND le compilateur en reconnaît
la possibilité -- que le changement ne modifie en rien la sémantique du
programme. Dans le cas de end() (ou son expansion inline), ce n'est pas
du tout évident de le reconnaître.

Mais la vraie question est : qu'importe ? Typiquement, la première chose
qu'on veut, c'est que la sémantique du programme soit respectée. C'est
le problème du compilateur. La deuxième, parfois, c'est d'avoir une
performance suffisante. Et si la performance n'est pas suffisante, ce
qu'on peut en faire. À ce moment-là, et seulement alors, on peut faire
un profiling. Si on trouve que c'est réelement cette boucle qui cause le
problème, on peut essayer de stocker la valeur de retour de end() dans
une variable locale, et de faire la comparaison avec la variable locale.
Les benchmarks que j'ai fais montre que ça donne bien un programme plus
rapide, avec tous les compilateurs auxquels j'ai actuellement accès, en
tout cas. (Ce qui suggère fortement qu'il ne lève pas le calcul de la
boucle.)

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


Avatar
BlueR
Bonjour

Merci pour vos réponses.

J'utilise la STLport 4.5, end() est inline, je n'avais pas eu le réflexe de
regarder.
iterator end() { return this->_M_finish; }

Donc effectivement je ne dois pas perdre grand chose.

Pour le moment, sur ce que je fais pas de problème de performance. Mais
c'est quand même pas une raison pour perdre du temps gratuitement surtout
que ce programme peut être utilisé sur des machines moins puissantes.

--
BlueR
Avatar
kanze
BlueR wrote in message
news:...

J'utilise la STLport 4.5, end() est inline, je n'avais pas eu le réflexe de
regarder.
iterator end() { return this->_M_finish; }


C'est prèsque toujours le cas. Pas que ça change forcement quelque
chose@; il y des compilateurs qui ne mettent pas en ligne ce qu'on a
démandé en ligne, et il y en a d'autres (fort rares, malheureusement)
qui mettent en ligne même les fonctions qui ne sont pas déclarées
inline, pour peu que le profiler montre que c'est là que ça coince.

Donc effectivement je ne dois pas perdre grand chose.


Ça dépend de la qualité de l'optimisateur. Il y a une indirection en
plus ; un bon optimisateur pourrait l'éliminer, mais l'indirection
introduit des alias possibles, et ajoute à la complexité de l'analyse.
Je ne me suis jamais perdu le temps à régarder le généré, mais d'après
mes mésures, au moins avec g++ sur Sparc, on perd bien un petit peu par
rapport à une lecture explicite vers une variable locale avant l'entrée
dans la boucle.

Pour le moment, sur ce que je fais pas de problème de performance.
Mais c'est quand même pas une raison pour perdre du temps gratuitement
surtout que ce programme peut être utilisé sur des machines moins
puissantes.


Ça veut dire quoi, perdre du temps gratuitement ? Si tu écris une
bibliothèque d'utilisation générale, où tu n'aurais jamais accès aux
programmes qui l'utilisent, à la rigueur, il faut y penser. Sinon, la
perte de temps gratuite, c'est la perte de ton temps à y penser.

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

Avatar
BlueR
Bonjour

Ça veut dire quoi, perdre du temps gratuitement ?
Ici ça voulait simplement dire : perdre du temps parce que j'aurai eu la

flemme de me poser la question et d'optimiser un peu le code.

Le temps que je prends pour y penser, franchement c'est pas perdu.
Et tu vois tes explications sur les compilateurs, inline qui n'est pas
forcément mis inline, je l'avais complètement oublié, les questions
d'optimisation par le compilateur, je n'y connais rien, j'apprécie de
comprendre un peu mieux ce qui se joue la dessous. Même si ça ne me sert
pas ici, ça me servira plus tard.
Merci.

--
BlueR