miracle de la récursion

Dans news:m3oeu8fmc8.fsf@uniton.integrable-solutions.net, Gabriel Dos

"Michel Michaud" <mm@gdzid.com> writes:

J'ose une question : est-ce vraiment important ou utile cette
optimisation ? N'y a-t-il pas des choses plus importantes qui
manquent dans gcc (ou g++) ?

Comme ?

Je ne sais pas Gabriel, je ne suis pas un spécialiste de g++,
c'est pourquoi je pose la question. Tiens... export ? :-)

Il me semble que si le compilateur
peut optimiser du code ordinaire, il pourra optimiser du code
où j'aurais enlevé explicitement la récursivité (en tout ou en
partie) et obtenir un résultat meilleur que l'optimisation
complète de la récursivité qu'il aurait pu faire.

Ce raisonnement n'est pas nouveau. Mais le fait est qu'il y a ce
mouvement, donc certains pensent que c'est important -- pusque dans
la liste de ceux que je vois implémenter cela, c'est sur des
contrats spécificques.

Oui, j'ai compris un peu mieux par ton autre message. J'avoue
que si l'on convertit du code d'un autre langage en C et que
cet autre langage met de l'avant un style pro-récursivité, ce
sera pratique.

J'ai peut-être
une mauvaise idée des endroits où la récursivité est utile, mais
il me semble qu'annoncer de l'optimisation de la récursivité par
le compilateur, c'est un peu prendre la chance que les gens
codent récursivement ce qui n'a pas besoin d'être récursif en
pensant faire mieux que la version non récursive...

Ou que les gens codent recursivement pour des besoins de clarté de
correction et veulent que le compilateur se débrouille pour
optimiser.

Je ne dis pas le contraire, je dis que même quand ce n'est pas
pour de bonnes raisons, ça pourrait pousser à en faire.

À quoi sert un compilateur ?
Je ne suis pas sûr, qu'il y a ait Une Seule Réponse,

Non, mais j'ai maintenant compris (par ton autre message),
qu'il y a un intérêt bien réel. Case closed. Merci !

--
Michel Michaud mm@gdzid.com
http://www.gdzid.com
FAQ de fr.comp.lang.c++ :
http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/

"Michel Michaud" <mm@gdzid.com> writes:

Oui, j'ai compris un peu mieux par ton autre message. J'avoue
que si l'on convertit du code d'un autre langage en C et que
cet autre langage met de l'avant un style pro-récursivité, ce
sera pratique.

Je crois que l'optique de gcc est plutot de partager le middle-end
(les optimisations independantes de la cible et du langage) et le
back-end (les optimisations independantes du langage mais dependantes
de la cible et la generation de code) entre les front-end (analyse et
optimisations dependantes du langage). Mais il y a bien des gens qui
generent du C (perso j'aurais meme tendance a generer du C++ --
peut-etre pas a un plus haut niveau d'abstraction que le C mais pour
profiter des exceptions et peut-etre de l'idiome RAII) a partir
d'autres langages.

En ce qui concerne la recursivite terminale, on peut la considerer
comme un cas particulier de chainage des appels, ce qui est
interessant pour le C++ (je ne sais pas si c'est l'approche de gcc ou
pas).

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

"Alain Naigeon" <anaigeon@free.fr> wrote in message
news:<3fdfad7a$0$22330$626a54ce@news.free.fr>...

"Gabriel Dos Reis" <gdr@integrable-solutions.net> a écrit dans le message
news: m3y8tdr3l1.fsf@uniton.integrable-solutions.net...

"Alain Naigeon" <anaigeon@free.fr> writes:

Merci pour ta réponse, il me faut un peu de temps pour
la digérer. Mais j'ai tout de même une question immédiate :

void f()
{
if( false)
{ /*
...
*/
}

Est-ce que le langage autorise une optimisation à :
void f() { }
?

(ou à rien du tout)

Dans quel sens ? Grosso modo, la norme exige deux choses d'un
compilateur : qu'il émet un diagnostique où c'est exigé, et qu'un
programme légal ait le comportement visible (ou un des comportements
visibles) que la norme spécifie.

Ta fonction est légale. Il n'y a donc pas de diagnostique à émettre. Si
en revanche tu mettais quelque chose qui exigeait un diagnostique dans
le if, le compilateur est obligé à l'émettre -- le if fait bien partie
de ton programme.

Ta fonction ne contient pas de comportement visible, et n'influe pas sur
des comportements visibles ailleurs. Le compilateur peut en faire ce
qu'il veut, pourvu que ce qu'il fait n'a pas de comportement visible, et
n'influe pas sur le comportement visible par ailleurs. Il peut donc ôter
la fonction complètement, ou le remplacer par une boucle qui dure une
heure. (Côté qualité de l'implémentation, tous les choix ne sont pas
égaux, mais la norme n'exige pas une qualité minimum.)

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

<kanze@gabi-soft.fr> a écrit
[...]

Ta fonction ne contient pas de comportement visible, et n'influe pas sur
des comportements visibles ailleurs. Le compilateur peut en faire ce
qu'il veut, pourvu que ce qu'il fait n'a pas de comportement visible, et
n'influe pas sur le comportement visible par ailleurs. Il peut donc ôter
la fonction complètement, ou le remplacer par une boucle qui dure une
heure. (Côté qualité de l'implémentation, tous les choix ne sont pas
égaux, mais la norme n'exige pas une qualité minimum.)
J'ai fait des tests avec des fonctions inutiles (compilateur Borland, au

moins):
void f(){}
Ou mieux avec :
int douze(){return 12;}
et l'appel :
...
int VarInt;
int a = 45;
int b = 13;

VarInt = a + (b * douze()) + (b - (douze()*douze()));
...
douze() est définie juste avant le main() d'où se fait l'appel.
Le seul cas où l'appel est remplacé par une valeur immédiate, c'est avec
tous les commutateurs qui vont bien, et si douze est déclarée inline. Dans
tous les autres cas, la fonction est toujours appelée (le code machine est
généré). et je ne me suis pas fait avoir par le mode debug (erreur fréquente
dans les EDI qui fait que certains affirment que la fonction n'est pas
inlinée, alors qu'elle l'est dans la release). Un jour, j'ai même vérifié
avec un debugger code machine.
Je n'ai jamais pu faire disparaitre l'appel à une fonction non inline, aussi
inutile soit-elle. Je n'ai pas testé le if(false)f();. A l'occasion..
Sauf erreur, le Pascal de Delphi est plus radical dans ses optimisations.
J'ai interprété au débuit comme ça :
- si le programmeur demande inline, il ne demande pas un appel.
- dans tous les autres cas, il demande un appel, il faut le respecter.

Et puis m'est venu une autre explication possible : le compilo est flemmard.
Il est muni d'un outil qui lui permet de ne recompiler que ce qui est
nécesaire après une petite modification. C'est semble-t-il très efficace, ça
va plus loin que les simples dépendances d'un makefile. Ce n'est pas lié à
un EDI.
Il est clair que cet outil va être plus simple à concevoir si tous les
appels écrits sont générés. Pour les fonctions inline, le compilo doit de
toutes façons considérer qu'une modif de la fonction est une modif dans le
code de la fonction appelante. Je suis confus ?

Pierre

"Pierre Maurette" <mmaauurreettttttee.ppiieerrrree@@ffrreeee.ffrr> writes:

[...]

| Je n'ai jamais pu faire disparaitre l'appel à une fonction non inline, aussi
| inutile soit-elle.

Normalement, les compilateurs optimisants (quel pléonasme), de nos
jours, savent faire des choses comme ça quand la fonction n'est pas
trop compliquée. Par exemple GCC à -O3 le fait.

| Je n'ai pas testé le if(false)f();. A l'occasion..

C'est possible avec GCC. C'est pour cela que nous avons changé les
règles de codage pour que les gens préfèrent

if (ENABLE_FEATURE) {

à

#if ENABLE_FEATURE == 1
....
#else
....
#endif

-- Gaby

"Michel Michaud" <mm@gdzid.com> writes:

| Dans news:m3oeu8fmc8.fsf@uniton.integrable-solutions.net, Gabriel Dos
| > "Michel Michaud" <mm@gdzid.com> writes:
| >> J'ose une question : est-ce vraiment important ou utile cette
| >> optimisation ? N'y a-t-il pas des choses plus importantes qui
| >> manquent dans gcc (ou g++) ?
| >
| > Comme ?
|
| Je ne sais pas Gabriel, je ne suis pas un spécialiste de g++,
| c'est pourquoi je pose la question. Tiens... export ? :-)

Cela suppose :

(1) qu'il y a un boss qui dit aux développeurs de GCC, « Joe, fais
ceci », « Fred, je veux ceci pour dans deux semaines ».

(2) que les gens qui travaillent sur le middle-end ou le back-end
et implémentent ces optimisations sont aussi en charge du
front-end g++.

aucune de ces hypothèses n'est vraie.

-- Gaby

Jean-Marc Bourguet <jm@bourguet.org> writes:

| En ce qui concerne la recursivite terminale, on peut la considerer
| comme un cas particulier de chainage des appels, ce qui est
| interessant pour le C++ (je ne sais pas si c'est l'approche de gcc ou
| pas).

Si tu parles du « tail call optimization », oui GCC l'implémente.

-- Gaby

Bonjour Gabriel,

Gabriel écrivait le 18 Dec 2003 00:57:39 +0100:

GDR> (1) qu'il y a un boss qui dit aux développeurs de GCC, « Joe, fais
GDR> ceci », « Fred, je veux ceci pour dans deux semaines ».

GDR> (2) que les gens qui travaillent sur le middle-end ou le back-end
GDR> et implémentent ces optimisations sont aussi en charge du
GDR> front-end g++.

GDR> aucune de ces hypothèses n'est vraie.

Il y a une troisième hypothèse possible :
Comme les sources sont disponibles vous pouvez les modifier
en fonction de vos désirs et vous pouvez même en faire profiter
tout le monde.

Bye,
Jean-Louis

"Pierre Maurette" <mmaauurreettttttee.ppiieerrrree@@ffrreeee.ffrr> wrote
in message news:<3fe050d4$0$7141$626a54ce@news.free.fr>...

<kanze@gabi-soft.fr> a écrit
[...]

Ta fonction ne contient pas de comportement visible, et n'influe pas
sur des comportements visibles ailleurs. Le compilateur peut en
faire ce qu'il veut, pourvu que ce qu'il fait n'a pas de
comportement visible, et n'influe pas sur le comportement visible
par ailleurs. Il peut donc ôter la fonction complètement, ou le
remplacer par une boucle qui dure une heure. (Côté qualité de
l'implémentation, tous les choix ne sont pas égaux, mais la norme
n'exige pas une qualité minimum.)
J'ai fait des tests avec des fonctions inutiles (compilateur Borland,

au moins):
void f(){}
Ou mieux avec :
int douze(){return 12;}
et l'appel :
...
int VarInt;
int a = 45;
int b = 13;

VarInt = a + (b * douze()) + (b - (douze()*douze()));
...
douze() est définie juste avant le main() d'où se fait l'appel.

Et l'expression se trouve dans une boucle serrée, et ne peut pas être
enlevée de la boucle sans changer les sorties du programme, j'espère.

Parce que les bons compilateurs aujourd'hui se servent des informations
du profiler pour décider quelles fonctions à générer en ligne. Si tu
n'appelles la fonction qu'une seule fois, ce n'est pas la peine de la
générer en ligne.

Le seul cas où l'appel est remplacé par une valeur immédiate, c'est
avec tous les commutateurs qui vont bien, et si douze est déclarée
inline.

Ça dépend du compilateur. Sans démander une certaine optimisation, c'est
probable qu'elle ne soit jamais générée en ligne. Avec les meilleurs
compilateurs, si le profiler dit que c'est là que ça coince, le
compilateur génèrera la fonction en ligne, même si l'appel est virtuel,
et même si la définition de la fonction se trouve dans une autre module.
(D'accord, d'aussi bons compilateurs sont rares. Mais ils existent.)

Dans tous les autres cas, la fonction est toujours appelée (le code
machine est généré). et je ne me suis pas fait avoir par le mode debug
(erreur fréquente dans les EDI qui fait que certains affirment que la
fonction n'est pas inlinée, alors qu'elle l'est dans la release). Un
jour, j'ai même vérifié avec un debugger code machine.

Qui sont ces certains ? Et comment est-ce qu'il prétend savoir si une
fonction est générée en ligne ou non ? La seule façon certaine que je
connais, c'est en désassemblant l'executable.

Je n'ai jamais pu faire disparaitre l'appel à une fonction non inline,
aussi inutile soit-elle. Je n'ai pas testé le if(false)f();. A
l'occasion.. Sauf erreur, le Pascal de Delphi est plus radical dans
ses optimisations. J'ai interprété au débuit comme ça :

- si le programmeur demande inline, il ne demande pas un appel.
- dans tous les autres cas, il demande un appel, il faut le respecter.

Je crois que tu as mal compris ce que c'est un programme en C++. Un
programme, ce n'est pas une démande au compilateur de générer tel ou tel
code executable. Un programme C++, c'est la spécification d'un certain
comportement visible. Selon la norme, les comportements visibles sont
les entrées/sorties et les accès aux objets déclarés volatile. Le
compilateur a droit de faire ce qu'il veut, dans la mesure que le
résultat respecte la sémantique exigée du programme.

- Le meilleur compilateur possible ignorerait les inline du
programmeur, parce qu'il serait capable de faire mieux. Je dirais
que dans ce cas-ci, il y a intérêt qu'il sache réelement faire
mieux@; de tels compilateurs sont rarissimes, si même ils existent.

- Un bon compilateur traiterait la spécification inline comme une
indication du programmeur que le temps d'appel est critique, et le
respecterait autant que possible. Ce qui ne l'empêchera pas de
générer d'autres appels en ligne aussi, le cas échéant.

En gros, aujourd'hui (au moins pour les systèmes généraux), si le
programmeur démande inline, c'est qu'il ne veut pas l'appel ; s'il ne le
démande pas, c'est que ça lui est indifférent.

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

kanze@gabi-soft.fr wrote:

"Pierre Maurette" <mmaauurreettttttee.ppiieerrrree@@ffrreeee.ffrr> wrote

Le seul cas où l'appel est remplacé par une valeur immédiate, c'est
avec tous les commutateurs qui vont bien, et si douze est déclarée
inline.

Ça dépend du compilateur. Sans démander une certaine optimisation, c'est
probable qu'elle ne soit jamais générée en ligne. Avec les meilleurs
compilateurs, si le profiler dit que c'est là que ça coince, le
compilateur génèrera la fonction en ligne, même si l'appel est virtuel,
et même si la définition de la fonction se trouve dans une autre module.
(D'accord, d'aussi bons compilateurs sont rares. Mais ils existent.)

Est-ce que tu as des exemples de tels compilateurs (juste histoire de
compléter ma culture en la matière) ?

A+

Christophe