OVH Cloud OVH Cloud

Evaluation boucle for

21 réponses
Avatar
PurL
boujour,

Dans une boucle for comme celle ci :

for (int i = 0; i < 5 + toto; i++)
{
...
}

est-ce que 5+toto est évalué à chaque boucle, ou le compilateur est
assez malin pour faire l'évaluation au debut et stocker le resultat dans
une variable temporaire ?

Merci,

PurL

10 réponses

1 2 3
Avatar
Jean-Marc Bourguet
PurL writes:

boujour,

Dans une boucle for comme celle ci :

for (int i = 0; i < 5 + toto; i++)
{
...
}

est-ce que 5+toto est évalué à chaque boucle, ou le compilateur est
assez malin pour faire l'évaluation au debut et stocker le resultat
dans une variable temporaire ?


Le comportement doit etre comme si l'expression etait evaluee a chaque
fois. Mais l'optimisation qui consiste a sortir des expressions
constantes d'une boucle est un grand classique. Reste a t'assurer que
l'optimiseur peut detecter que l'expression est constante.

Si tu veux etre sur pour un cas particulier: mesure ou regarde
l'assembleur.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Avatar
Samuel Krempp
(02 May 2005 15:29, ) a

PurL writes:

boujour,

Dans une boucle for comme celle ci :

for (int i = 0; i < 5 + toto; i++)


Le comportement doit etre comme si l'expression etait evaluee a chaque
fois. Mais l'optimisation qui consiste a sortir des expressions
constantes d'une boucle est un grand classique. Reste a t'assurer que
l'optimiseur peut detecter que l'expression est constante.


est-ce que le compilateur doit se soucier d'éventuelles modifications de
toto par d'éventuels autres threads ? comme la norme ne connait rien des
threads, je considère que le compilo a le droit d'analyser le code dans le
modèle 'standard' de flot d'éxécution (mono-thread). Mais dans la
pratique ?

Si on imagine le fichier suivant :

int toto;

void modifToto(int n) {
toto = n;
}

void foo() {
for (int i = 0; i < 500000/toto; i++) {
cout << i << endl;
}

est-ce que les compilos usuels évalueraient 500000/toto une seule fois, ou
pas (et alors, c'est en prévision de possibles threads, ou pour d'autres
raisons ?)

--
Sam


Avatar
Pierre Maurette
boujour,

Dans une boucle for comme celle ci :

for (int i = 0; i < 5 + toto; i++)
{
...
}

est-ce que 5+toto est évalué à chaque boucle, ou le compilateur est assez
malin pour faire l'évaluation au debut et stocker le resultat dans une
variable temporaire ?
Un bon compilateur devrait toujours le faire dans les cas exigés par le

bon sens. Ce qui peut exclure, sans être exhaustif:
- toto est déclarée dans le même bloc que le for, mais volatile.
- toto est externe à ce bloc (disons globale ou externe), et des
fonctions sont appelées dans le bloc for. Là, ça peut dépendre de la
qualité de l'optimiseur. Avec avantage à une optimisation globale qui
prend en compte le lieur.
- Dans le même genre, &toto a été passé à une fonction qui attend un
int* non constant, idem pour une reference.
- toto ne devrait pas pouvoir être être modifiée dans le for, mais
celui-ci contient un __asm. Tous les compilos n'étudient pas le
comportement sous ce mot clé (ou _asm ou asm).

J'en oublie sans doute par ignorance du C++ ...

--
Pierre

Avatar
Jean-Marc Bourguet
Samuel Krempp writes:

Si on imagine le fichier suivant :

int toto;

void modifToto(int n) {
toto = n;
}

void foo() {
for (int i = 0; i < 500000/toto; i++) {
cout << i << endl;
}

est-ce que les compilos usuels évalueraient 500000/toto
une seule fois, ou pas (et alors, c'est en prévision de
possibles threads, ou pour d'autres raisons ?)


J'espère qu'ils l'évalueraient à chaque fois. Quelqu'un
peut avoir fait un cout.rbuf(mybuffer) avec streambuf qui
modifie toto. En gros je m'attends que dès qu'il y a appel
à une fonction qui n'est pas définie localement, la plupart
des compilateurs supposent qu'elle peut modifier toto (il y
en a quelques uns qui sont capables de faire de l'analyse
inter-fichier si on leur demande et donc vont pousser plus
loin dans ces cas).

Ils peuvent aussi constater que garder 500000/toto à travers
les appels aux operateurs << est plus coûteux que de
réévaluer l'expression.

Il n'y a pas pour le moment de modèle mémoire standard pour
le multi-thread mais il y en a un en préparation. Je doute
qu'il demande de considérer que toto puisse être modifié
sans marquage spécial (du genre toto marqué comme volatile,
accès à une autre variable volatile).

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Avatar
adebaene
Samuel Krempp wrote:
(02 May 2005 15:29,
) a


PurL writes:

boujour,

Dans une boucle for comme celle ci :

for (int i = 0; i < 5 + toto; i++)


Le comportement doit etre comme si l'expression etait evaluee a
chaque


fois. Mais l'optimisation qui consiste a sortir des expressions
constantes d'une boucle est un grand classique. Reste a t'assurer
que


l'optimiseur peut detecter que l'expression est constante.


est-ce que le compilateur doit se soucier d'éventuelles
modifications de

toto par d'éventuels autres threads ? comme la norme ne connait rien
des

threads, je considère que le compilo a le droit d'analyser le code
dans le

modèle 'standard' de flot d'éxécution (mono-thread). Mais dans la
pratique ?


Si toto est accédée par plusieurs threads, il y a de fortes chances
que le programme est un comportement indéfini (à moins que l'accès
à toto soit garanti atomique en lecture), donc la question ne se pose
pas vraiment...

Arnaud



Avatar
kanze
Samuel Krempp wrote:
(02 May 2005 15:29,

PurL writes:

Dans une boucle for comme celle ci :

for (int i = 0; i < 5 + toto; i++)


Le comportement doit etre comme si l'expression etait
evaluee a chaque fois. Mais l'optimisation qui consiste a
sortir des expressions constantes d'une boucle est un grand
classique. Reste a t'assurer que l'optimiseur peut detecter
que l'expression est constante.


est-ce que le compilateur doit se soucier d'éventuelles
modifications de toto par d'éventuels autres threads ? comme
la norme ne connait rien des threads, je considère que le
compilo a le droit d'analyser le code dans le modèle
'standard' de flot d'éxécution (mono-thread). Mais dans la
pratique ?


Selon la norme C++, comme tu dis, dès qu'il y a des threads, tu
as un comportement indéfini. Il faut donc chercher ailleurs.

Selon Posix, si plusieurs threads peuvent accéder à une
variable, et au moins un d'entre eux risque de la modifier, il
faut que l'utilisateur s'assure la synchronisation
explicitement. Donc, dans la mésure qu'il n'y a pas de lock dans
le code, le compilateur a le droit de supposer qu'aucun autre
thread ne le modifie.

Dans la pratique, évidemment, très peu de compilateurs vont
jusqu'à analyser l'assembleur dans les fichiers objets que tu
linkes, pour voir qu'ils ne connaissent pas la variable. Si donc
la variable est visible ailleurs, ils supposent qu'elle peut
être modifiée dans n'importe quelle fonction externe. Qu'elle
s'appelle pthread_mutex_lock ou autre.

Si on imagine le fichier suivant :

int toto;

void modifToto(int n) {
toto = n;
}

void foo() {
for (int i = 0; i < 500000/toto; i++) {
cout << i << endl;
}

est-ce que les compilos usuels évalueraient 500000/toto une
seule fois, ou pas (et alors, c'est en prévision de possibles
threads, ou pour d'autres raisons ?)


Ils y sont obligé. Parce que dans le main, j'ai installé un
streambuf dans cout qui appelle modifToto chaque fois qu'on sort
un 'n'.

En général : dès que l'expression contient une variable globale,
ou une variable dont on a pris l'adresse (y compris en forme de
référence), et que la boucle contient le moindre appel à une
fonction dont le compilateur ne voit pas l'implémentation, le
compilateur est obligé à supposer que cette fonction change la
valeur de la variable.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34



Avatar
Pierre Maurette
[...]
En général : dès que l'expression contient une variable globale,
ou une variable dont on a pris l'adresse (y compris en forme de
référence), et que la boucle contient le moindre appel à une
fonction dont le compilateur ne voit pas l'implémentation, le
compilateur est obligé à supposer que cette fonction change la
valeur de la variable.
http://minilien.com/?sQNnEIKr4V

http://minilien.com/?6C5JzGmym5

--
Pierre

Avatar
kanze
Pierre Maurette wrote:
[...]

En général : dès que l'expression contient une variable
globale, ou une variable dont on a pris l'adresse (y compris
en forme de référence), et que la boucle contient le moindre
appel à une fonction dont le compilateur ne voit pas
l'implémentation, le compilateur est obligé à supposer que
cette fonction change la valeur de la variable.


http://minilien.com/?sQNnEIKr4V
http://minilien.com/?6C5JzGmym5


En somme, Microsoft te donne la possibilité de dire
explicitement ce qu'il ne pourrait pas déduire (parce que
l'information se trouve dans une autre unité de compilation).

La norme C donne aussi une possibilité de declarer certains
paramètres « restrict » -- grosso modo, c'est une promesse que
l'objet désigné par un pointeur n'est pas accédé autrement que
par ce pointeur.

Je ne suis pas expert dans la matière, mais les deux solutions
me semblent surtout ajouter aux risques d'un comportement
indéfini. J'aurais tendance à les éviter sauf en cas de
nécessité.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


Avatar
Pierre Maurette
[...]
http://minilien.com/?sQNnEIKr4V
http://minilien.com/?6C5JzGmym5


En somme, Microsoft te donne la possibilité de dire
explicitement ce qu'il ne pourrait pas déduire (parce que
l'information se trouve dans une autre unité de compilation).
Je m'étais gourré dans mon minilien, il y avait également /Og, mais il

reprend simplement /Oa /Ow.

La norme C donne aussi une possibilité de declarer certains
paramètres « restrict » -- grosso modo, c'est une promesse que
l'objet désigné par un pointeur n'est pas accédé autrement que
par ce pointeur.
Vous expliquez mieux que la norme C ...


Je ne suis pas expert dans la matière, mais les deux solutions
me semblent surtout ajouter aux risques d'un comportement
indéfini. J'aurais tendance à les éviter sauf en cas de
nécessité.
Cette option, elle signifie en gros: "Compilo, nom ami, je te jure que

ne fais pas l'abruti en modifiant en loucedé mes variable par des
pointeurs occultes (et des __asm ?), optimise à ta guise".
L'exemple donné n'est pas convaincant (il suffit de faire l'addition
avant la boucle). Mais dans d'autres cas, pourquoi pas ?. En #pragma,
bien sûr.

--
Pierre


Avatar
kanze
Pierre Maurette wrote:
[...]
http://minilien.com/?sQNnEIKr4V
http://minilien.com/?6C5JzGmym5




[...]
Je ne suis pas expert dans la matière, mais les deux
solutions me semblent surtout ajouter aux risques d'un
comportement indéfini. J'aurais tendance à les éviter sauf
en cas de nécessité.


Cette option, elle signifie en gros: "Compilo, nom ami, je te
jure que ne fais pas l'abruti en modifiant en loucedé mes
variable par des pointeurs occultes (et des __asm ?), optimise
à ta guise". L'exemple donné n'est pas convaincant (il suffit
de faire l'addition avant la boucle). Mais dans d'autres cas,
pourquoi pas ?. En #pragma, bien sûr.


Si tu parles de l'exemple dans la doc Microsoft dont tu as posté
le lien, il est bien convaincant. L'expression dans la boucle,
c'est : « *p = x + y ». Et justement, si p pointe à x ou à y, il
faut que le compilateur fasse l'addition chaque fois dans la
boucle ; ce n'est que dans l'absence établie (par preuve ou par
déclaration sur l'honneur du programmeur) de cette possibilité
que le compilateur peut enlever l'addition de la boucle.

Au fur et à mésure que le parallelisme des processeurs augmente,
le problème devient plus aigu. Considérons la boucle suivante :

for ( int i = 0 ; i < 1000000 ; ++ i ) {
a[ i ] = b[ i ] + c[ i ] ;
}

Sur un processeur hyperthreadé, un compilateur Java ou Ada
pourrait splitter la boucle en deux, en l'exécutant pour les
indices paires dans un thread, et pour les indices impaires dans
l'autre. Si la boucle est dans une fonction, et a, b et c sont
en fait des pointeurs, un compilateur C ou C++ ne peut pas le
faire, parce qu'on aurait pu appeler la fonction avec quelque
chose comme (tab + 1, tab, tab).

Note bien que ni restrict, ni les options Microsoft n'aide ici,
parce qu'ils interdisent aussi l'appel (tab, tab, tab), qu'on
veut permettre.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34



1 2 3