English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
optimization of sequence of List.map and inlining
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2008-06-10 (22:32)
From: Brian Hurt <bhurt@s...>
Subject: Re: [Caml-list] optimization of sequence of List.map and inlining

On Tue, 10 Jun 2008, Charles Hymans wrote:

> Let's say, I have the following code:
>  let f l = List.map succ l
>  ....
>  let l = f l in
>  let l = List.map succ l in
>    do_something_with l
> Is there a way to tell the compiler to optimize it so that it runs as fast
> as this code:
>  let l = List.map (fun x -> succ (succ x)) l in
>    l
> In the first case, there are two passes where succ is applied to 
> each elements of the list. In the second case, there is only one pass 
> that applies succ twice to each element of the list.

The short answer is no- due to the possibility of side effects, it's hard 
(read: in the general case equivelent to the halting problem) to determine 
if that code transformation produces the same result.  Even ignoring 
exceptions and i/o!  As an example of what I mean, consider the code:

let r : ref 1;;

let foo x = r := !r + x; !r;;

let bar x = foo (foo x);;

So now, if we set r to 1, and call List.map foo (List.map foo [1;2;3]), we 
get the return list [9; 13; 20], while List.map bar [1;2;3] returns [4; 
12; 30].  So it's not always the case that you can replace List.map f 
(List.map g lst) with List.map (f . g) lst, and get the same result back.