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
Pierre Maurette
Pierre Maurette wrote:
[...]

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.
Nous sommes d'accord. L'exemple est explicite *du danger*.

Je voulais dire qu'il ne l'est pas de l'utilité de /Oa. Si l'on est sûr
de soi, on pourra toujours faire, *ici*:

i = -100;
const type t = x + y; // C++ et C99
t = x + y; /* Cpré99 */
while( i < 0 )
{
i += t;
*p = i;
}



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.
Chez Microsoft, restera plus que les intrinsics sur 128 bits /16 ou 32

en parallèle, ou un coup de __asm selon les versions ;-)
On pourra faire (tab, tab, tab) mais on aura des contraintes
d'alignement.

--
Pierre


Avatar
Samuel Krempp
(10 May 2005 11:51,

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


le compilateur ne pourrait-il pas générer le code pour les 2 cas (suppose
aucun alias // aucune supposition), lorsque la fonction est appelée faire
un branchement selon qu'il peut utiliser le code optimisé ou non ?

ça me semble simple et guère moins efficace même lorsque l'on pourrait
utiliser un /Og

--
Sam

Avatar
Pierre Maurette
[...]
le compilateur ne pourrait-il pas générer le code pour les 2 cas (suppose
aucun alias // aucune supposition), lorsque la fonction est appelée faire
un branchement selon qu'il peut utiliser le code optimisé ou non ?

ça me semble simple et guère moins efficace même lorsque l'on pourrait
utiliser un /Og
Ça pourrait générer des surprises lors d'un débogage, surtout crapuleux

;-)
J'ai vu un truc comme ça sous VC7. C'était au cours de tests dont j'ai
parlé ici, voir si on pouvait par 'register' favoriser une branche que
le programmeur sait être prise presqu'à chaque fois, alors que le
compilateur ne peut pas le supposer. VC7 était le plus rapide, et
'register' ne changeait rien. Le code objet semblait bien compliqué, et
de toute évidence des blocs entiers étaient dupliqués.
Mais j'ai réfléchi plus tard qu'il n'est pas certain que le code
exécutable soit dupliqué lui aussi. Le code objet était obtenu par
/FAs, et il est possible que le bloc soit choisi à l'édition de liens
et non à l'exécution. Faudrait que je ressorte ce truc, surtout que
j'ai depuis découvert WinDbg...

Puisqu'on est là dessus, je me pose une question : j'avais pour
habitude, parce que ça m'a paru plus facile pour les makefile et
fichiers de commande, de compiler sans lier, puis de lier. Je me
demande si cette manie peut empêcher des optimisations ...

--
Pierre

Avatar
kanze
Samuel Krempp wrote:
(10 May 2005 11:51,

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


le compilateur ne pourrait-il pas générer le code pour les 2
cas (suppose aucun alias // aucune supposition), lorsque la
fonction est appelée faire un branchement selon qu'il peut
utiliser le code optimisé ou non ?


Tout à fait. Je crois même que certains compilateurs le font. Au
moins si les informations en provenance du profiling indique ce
c'est dans un chemin critique, et que les recouverements sont en
fait très rare.

De même, un compilateur qui fait un analyse inter-modules
pourrait, en théorie, en tout cas, determiner qu'en fait, la
fonction ne serait jamais appelée avec des tableaux qui
s'échevauchent, et faire l'optimisation. J'ai même vaguement
entendu parler d'un tel compilateur, mais je ne sais pas dans
quelle mésure la personne qui en parlait parler de la réalité,
ou de ses souhaits.

ça me semble simple et guère moins efficace même lorsque l'on
pourrait utiliser un /Og


Tout à fait.

N'oublions pas qu'on parle ici surtout des compilateurs pour des
processeurs parallels. Il y a peu, ça signifiait des Cray et
companie. Depuis peu, en revanche, il y a du hyper-threading sur
des PC. Il va falloir que les implémenteurs de compilateur s'y
mettent.

--
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
kanze
Pierre Maurette wrote:
[...]
le compilateur ne pourrait-il pas générer le code pour les 2
cas (suppose aucun alias // aucune supposition), lorsque la
fonction est appelée faire un branchement selon qu'il peut
utiliser le code optimisé ou non ?

ça me semble simple et guère moins efficace même lorsque
l'on pourrait utiliser un /Og


Ça pourrait générer des surprises lors d'un débogage, surtout
crapuleux ;-)

J'ai vu un truc comme ça sous VC7. C'était au cours de tests
dont j'ai parlé ici, voir si on pouvait par 'register'
favoriser une branche que le programmeur sait être prise
presqu'à chaque fois, alors que le compilateur ne peut pas le
supposer.


Je ne vois pas ce que register pourrait avoir à faire dans
l'écoulement du programme. En fait, en général, le compilateur
(quand on veut de l'optimisation, évidemment) sait pertinemment
bien quelles branches sont les plus fréquents, parce qu'il a
accès aux informations du profileur. (Je ne sais pas pour VC++,
mais il me semble en avoir entendu parler. C'est bien le cas de
tous les compilateurs Unix, en tout cas.)

[...]

Puisqu'on est là dessus, je me pose une question : j'avais
pour habitude, parce que ça m'a paru plus facile pour les
makefile et fichiers de commande, de compiler sans lier, puis
de lier. Je me demande si cette manie peut empêcher des
optimisations ...


L'optimisation finale aujourd'hui se fait lors de l'édition des
liens, sur tout le programme. Mais de toute façon, que tu
invoques « cl /Tp a.cc /Tp b.cc », ou que tu invoques le
compilateur deux fois, puis l'éditeur de liens, le programme
pilot (parce que c'est ce que c'est en réalité) appelle le
compilateur deux fois, et l'éditeur de liens une fois. Dans les
deux cas, exactement pareil.

--
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
[...]
Je ne vois pas ce que register pourrait avoir à faire dans
l'écoulement du programme. En fait, en général, le compilateur
(quand on veut de l'optimisation, évidemment) sait pertinemment
bien quelles branches sont les plus fréquents, parce qu'il a
accès aux informations du profileur. (Je ne sais pas pour VC++,
mais il me semble en avoir entendu parler. C'est bien le cas de
tous les compilateurs Unix, en tout cas.)
Pourtant, ça le fait, et ça optimise clairement avec gcc 3.2. Le

processus: je lis un flux de char, disons un fichier. Je teste chaque
valeur:
#define MAGIC 154
int a1, b1, c1, d1;
int a1, b1, c1, d1;
if(val == MAGIC)
{
// boucle 1
}
else
{
// boucle 2
}




[...]

Puisqu'on est là dessus, je me pose une question : j'avais
pour habitude, parce que ça m'a paru plus facile pour les
makefile et fichiers de commande, de compiler sans lier, puis
de lier. Je me demande si cette manie peut empêcher des
optimisations ...


L'optimisation finale aujourd'hui se fait lors de l'édition des
liens, sur tout le programme. Mais de toute façon, que tu
invoques « cl /Tp a.cc /Tp b.cc », ou que tu invoques le
compilateur deux fois, puis l'éditeur de liens, le programme
pilot (parce que c'est ce que c'est en réalité) appelle le
compilateur deux fois, et l'éditeur de liens une fois. Dans les
deux cas, exactement pareil.


--
Pierre


Avatar
Pierre Maurette
[...]
Je ne vois pas ce que register pourrait avoir à faire dans
l'écoulement du programme. En fait, en général, le compilateur
(quand on veut de l'optimisation, évidemment) sait pertinemment
bien quelles branches sont les plus fréquents, parce qu'il a
accès aux informations du profileur. (Je ne sais pas pour VC++,
mais il me semble en avoir entendu parler. C'est bien le cas de
tous les compilateurs Unix, en tout cas.)
Pourtant, ça le fait, et ça optimise clairement avec gcc 3.2.

Le processus, de mémoire, je retrouve les fichiers de test, mais j'ai
écrasé le code :-( :
Je lis un flux de char, disons un fichier, dont je teste chaque valeur:
#define MAGIC 154
/* register */ int a1, b1, c1, d1;
/* register */ int a2, b2, c2, d2;
if(val == MAGIC)
{
// utilise a1, b1, c1, d1;
}
else
{
// utilise a2, b2, c2, d2;
}
Le fichier (disons 30 ko) ne contient que des octets à 154, sauf un.
Par exemple.
Si je déclare:
register int a1, b1, c1, d1;
int a2, b2, c2, d2;
ce sera meilleur que
int a1, b1, c1, d1;
int a2, b2, c2, d2;
et encore plus que
int a1, b1, c1, d1;
register int a2, b2, c2, d2;

Bien sûr, ce n'est pas du code naturel. Je ne sais même plus si c'était
bien 4 variables dans chaque boucle.

--
Pierre

Avatar
Pierre THIERRY
Le Wed, 11 May 2005 09:42:50 -0700, kanze a écrit :
N'oublions pas qu'on parle ici surtout des compilateurs pour des
processeurs parallels. Il y a peu, ça signifiait des Cray et companie.


Je croyais qu'il y avait pas mal de SMP dans les stations Alpha, c'est
quand même des machines un tantinet plus répandues que les Cray, non ?
Ou on optimise simplement pas la compilation pour les SMP Alpha/Intel ?
(ce serait con, quand même)

Curieusement,
Nowhere man
--

OpenPGP 0xD9D50D8A

Avatar
Richard Delorme

N'oublions pas qu'on parle ici surtout des compilateurs pour des
processeurs parallels. Il y a peu, ça signifiait des Cray et
companie. Depuis peu, en revanche, il y a du hyper-threading sur
des PC. Il va falloir que les implémenteurs de compilateur s'y
mettent.


Ce n'est pas si récent. A ma connaissance, les machines multiprocesseurs
se sont démocratisées vers 1995, avec des cartes mères supportants de 2
à 4 pentium-pro. Les premiers processeurs à supporter efficacement le
multitâche (de type hyperthreading) sont apparues en 2001 (RS64 IV), et
des processeurs multi-cores existent depuis la même époque (POWER4) :
http://www-128.ibm.com/developerworks/library/l-powhist/

--
Richard

Avatar
kanze
Pierre THIERRY wrote:
N'oublions pas qu'on parle ici surtout des compilateurs pour
des processeurs parallels. Il y a peu, ça signifiait des
Cray et companie.


Je croyais qu'il y avait pas mal de SMP dans les stations
Alpha, c'est quand même des machines un tantinet plus
répandues que les Cray, non ? Ou on optimise simplement pas
la compilation pour les SMP Alpha/Intel ? (ce serait con,
quand même)


Je ne connais pas trop la situation des Alphas. Chez Sun, ça
fait longtemps qu'on a des configurations multiprocesseurs. Mais
j'ai l'impression, au moins chez Sun, que le but visé n'est pas
une rapidité de calcul numérique, en soi, mais une responsivité,
par exemple, quand la machine executue beaucoup de petits
programmes, par exemple des scripts CGI, ou quand on a d'une
part une activité graphique et de l'autre des calculs.

En tout cas, autant que je sache, le système Solaris n'offre pas
réelement du support pour le genre de multithreading voulu ici,
et les compilateurs Sun n'ont jamais essayé de faire de la
parallelisation automatiquement. Les systèmes Unix ont
typiquement pas mal de chose qui se passent déjà en parallel,
dans de différents processus, et on arrive à exploiter un
certain nombre de processeurs sans parallelisme dans les
applications mêmes.

J'avoue que, étant donné que la recherche sur la parallelisation
automatique que je connais date des années 80, et j'ai entendu
parler justement du compilateur C++ qui faisait l'analyse global
pour détecter ce genre de chose au début des années 90, il
m'étonne un peu que les compilateurs sur des machines actuelles
semblent l'ignorer complétement. Et que quelqu'un comme Herb
Sutter pourrait écrire un article (dans CUJ, il y a quelques
mois) pour expliquer comment l'hyperthreading va changer notre
façon de penser -- depuis la nuit du temps, il y a eu des
applications où les performances linéaires disponibles à
l'époque ne suffisaient pas, et qu'on récherche une solution qui
met des processeurs en parallel pour aller plus vite.

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