Re: compilation

Re: compilation

[Franck Cassez]

Bonjour Jean-Christophe,

	concernant les evaluations a la compilation,
j'avais pose une question similaire a Pierre Weis 
l'annee derniere (mon but etait
d'``accelerer'' un programme): je pense que l'exemple suivant
peut t'interesser.

A+

Franck.

- Franck.Cassez@univ-brest.fr - Departement d'Informatique  - 
-- Universite de Bretagne Occidentale  6, Avenue Le Gorgeu --
----   BP 809  ----   29285 Brest Cedex  ----   FRANCE   ----
-- tel: (+33) 02 98 01 69 59 -- fax: (+33) 02 98 01 69 56  --

dixit Pierre :
Je m'explique soit la fonction f:

let f a x = if a then (x + 1) else (x - 1);;

alors f true est la fonction x -> if true then (x + 1) else (x - 1) et non
pas la fonction x -> x + 1

On obtient une petite acce'le'ration en e'crivant:

let f a = if a then (fun x -> x + 1) else (fun x -> x - 1);;

car alors f true est (fun x -> x + 1). Cependant cette propagation des
constantes par le compilateur du (me'ta)-langage n'est pas de bonne
me'thodologie (elle n'est pas efficace). Pour beaucoup gagner il faut
re'aliser un ve'ritable compilateur qui analyse les programmes sources
du langage a` compiler et les optimise lui-me^me.

compilation

[Jean-Christophe Filliatre]

[english translation at the end of this mail]

Bonjour,

1. J'aimerai savoir si :

	let b = true
	let f = if b then f1 else f2

   est compilé en f1, c'est-à-dire si la branche d'un "if" est
   directement sélectionnée lorsque le booléen est "true" ou "false"
   (sans l'évaluer, bien sûr ; simplement directement égal à "true" ou
   "false" au moment de la compilation)
   La raison de ma question est que cela permettrait d'avoir des options
   de compilation directement en Caml sans perdre d'efficacité.

2. de la même manière, est-ce que 

	let f = ...
	let f1 = f
	
   est compilé en remplaçant tout appel à f1 par un appel à f ?
   Ma question est, là encore, de savoir si on ne perd pas
   d'efficacité en renommant des fonctions.

Merci.
--Jean-Christophe.
  email: Jean-Christophe.Filliatre@ens-lyon.fr
  WWW  : http://www.ens-lyon.fr/~jcfillia

 
=english=====================================================================

1. I would like to know if

	let b = true
	let f = if b then f1 else f2

is compiled as f1, that is if the branch of an "if" expression is
directly selected when the boolean expression is "true" or "false"
(without performing any computation on it, of course; just directly
equal to the constructor "true" or "false").
The reason of this question is that it would allow compile options in
Caml without any loss of efficiency.

2. the same way, is

	let f = ...
	let f1 = f

compiled by replacing any call to f1 by a call to f ? 
The question is still to known if we don't loose efficiency by
renaming functions.

Thank you,
--Jean-Christophe.

Re: compilation

[David Monniaux]

[ENGLISH FURTHER IN THE TEXT]

On Thu, 13 Feb 1997, Jean-Christophe Filliatre wrote:

> 1. J'aimerai savoir si :
> 
> 	let b = true
> 	let f = if b then f1 else f2
> 
>    est compilé en f1, c'est-à-dire si la branche d'un "if" est
>    directement sélectionnée lorsque le booléen est "true" ou "false"
>    (sans l'évaluer, bien sûr ; simplement directement égal à "true" ou
>    "false" au moment de la compilation)
>    La raison de ma question est que cela permettrait d'avoir des options
>    de compilation directement en Caml sans perdre d'efficacité.

A ma connaissance, le compilateur ne fait pas de réductions même
triviales... Par exemple
let f=5;;
let g () = 3 * f;;
compile g vers une fonction qui est sémantiquement une constante, mais qui
en pratique prend f (lié =3), le multiplie par 3...

Un bon compilateur C, par contre, simplifierait les expressions...
Cela dit, les systèmes d'analyse de flot et d'optimizations des
compilateurs C réellement utilisés sont énormes...

> =english=====================================================================
> 
> 1. I would like to know if
> 
> 	let b = true
> 	let f = if b then f1 else f2
> 
> is compiled as f1, that is if the branch of an "if" expression is
> directly selected when the boolean expression is "true" or "false"
> (without performing any computation on it, of course; just directly
> equal to the constructor "true" or "false").
> The reason of this question is that it would allow compile options in
> Caml without any loss of efficiency.

To my knowledge, the Ocaml compiler doesn't perform any kind of reduction,
even trivial. For instance,

let f=3;;
let g () = f*4;;
compiles g to a function that is semantically a constant, but that in
effect takes f (lié =3) and multiplies it by 4.

A good C compiler, nevertheless, would simplify those expressions... But
the flow analysis and optimization part of a "real" C compiler is huge...

"Si l'informatique marchait, cela se saurait."
http://www.ens-lyon.fr/~dmonniau

Re: compilation

[Xavier Leroy]

> [english summary at the end of this mail]

> 1. J'aimerai savoir si :
>
> 	let b = true
> 	let f = if b then f1 else f2
>
>    est compilé en f1, c'est-à-dire si la branche d'un "if" est
>    directement sélectionnée lorsque le booléen est "true" ou "false"
>    (sans l'évaluer, bien sûr ; simplement directement égal à "true" ou
>    "false" au moment de la compilation)

Non, il n'y a pas de propagation des constantes dans le compilateur
Objective Caml. Cependant, b n'est teste qu'une seule fois, et non pas
a chaque appel de f, qui se branche directement sur le code de f1
(voir question suivante).

>    La raison de ma question est que cela permettrait d'avoir des options
>    de compilation directement en Caml sans perdre d'efficacité.

C'est possible, a condition de bien sortir les tests des
fonctions. P.ex. ne pas ecrire

        let f x           if debug then ...;
          ...

(test a chaque appel de f), mais plutot

        let f           if debug then fun x -> ...; ...
                   else fun x -> ...

> 2. de la même manière, est-ce que
>
> 	let f = fun x -> e
> 	let f1 = f
> 	
>    est compilé en remplaçant tout appel à f1 par un appel à f ?

Oui. En fait, les identificateurs f et f1 ont la meme valeur
fonctionnelle, qui est une fermeture du code de fun x -> e.

>    Ma question est, là encore, de savoir si on ne perd pas
>    d'efficacité en renommant des fonctions.

Il n'y a pas de surcout a l'appel de fonction.

- Xavier Leroy

> =english====================================================================>
> 1. I would like to know if
>
> 	let b = true
> 	let f = if b then f1 else f2
>
> is compiled as f1, that is if the branch of an "if" expression is
> directly selected when the boolean expression is "true" or "false"
> (without performing any computation on it, of course; just directly
> equal to the constructor "true" or "false").

No, there's no constant folding in the compiler. However, b will be
tested only once, not at each call to f, so that's still fairly efficient.

> 2. the same way, is
>
> 	let f = fun x -> e
> 	let f1 = f
>
> compiled by replacing any call to f1 by a call to f ?

No, f and f1 have the same functional value: a closure of the code for
fun x -> e.

> The question is still to known if we don't loose efficiency by
> renaming functions.

We don't.