optimization of sequence of List.map and inlining

optimization of sequence of List.map and inlining

[Charles Hymans]

[-- Attachment #1: Type: text/plain, Size: 492 bytes --]

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.

Thank you,

[-- Attachment #2: Type: text/html, Size: 778 bytes --]

Re: [Caml-list] optimization of sequence of List.map and inlining

[Jon Harrop]

On Tuesday 10 June 2008 20:01:12 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.

In MLs, you deforest by hand. You might like to use a function composition 
operator like << from F#:

  let lst = map (f << f) lst

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

Re: [Caml-list] optimization of sequence of List.map and inlining

[Richard Jones]

On Tue, Jun 10, 2008 at 08:21:36PM +0100, Jon Harrop wrote:
> In MLs, you deforest by hand. You might like to use a function composition 
> operator like << from F#:
> 
>   let lst = map (f << f) lst

One word of caution from someone who redefined << and >> as shift
operators in thousands of lines of code, then had to convert them back
again: << and >> aren't a good choice for operator name because they
clash with the quotation system in camlp4.  So the original poster
might want to choose another name if they're using camlp4 :-)

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] optimization of sequence of List.map and inlining

[Peng Zang]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

ExtLib has an Enum module.  It has lazy maps among other things.  This means I 
can perform multiple maps and it will not create intermediate data 
structures.  Example (++ is function composition and $ is function 
application):

  Enum.fold (+) 0
  ++ Enum.map (( * ) 2)
  ++ Enum.map ((+) 1)
  $ List.enum [1;2;3;4;5]

Will add one to everything in the list, double it and then sum the list, which 
yields 40.

Peng

On Tuesday 10 June 2008 03:01:12 pm 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.
>
> Thank you,
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFITvu+fIRcEFL/JewRAqmMAJ9rWadpHtt2ZiE8EDn4iIKoASDPegCgi0mM
p8iIohGVfxAXXOboMiiNKI4=
=XALu
-----END PGP SIGNATURE-----

Re: [Caml-list] optimization of sequence of List.map and inlining

[Brian Hurt]

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.

Brian

Re: [Caml-list] optimization of sequence of List.map and inlining

[Jon Harrop]

On Tuesday 10 June 2008 20:01:12 Charles Hymans wrote:
> Thank you for your answer.
> 
>> In MLs, you deforest by hand. You might like to use a function
>> composition
> 
> Unfortunately, in the case from which my example is extracted, I
> believe I can't do that:
> The several List.maps, even though they are executed in sequence, are
> not in the same module. In order to deforest by hand, I have to break
> the module interface, do some function inlining and then do the
> function composition.
> Something I don't want to do, because it would make the code difficult
> to read and to maintain.

Perhaps you could use something like the following abstract lazy sequence 
implementation:

  module Seq : sig
    type ('a, 'b) t
    val of_list : 'a list -> ('a, 'a) t
    val map : ('a -> 'b) -> ('c, 'a) t -> ('c, 'b) t
    val to_list : ('a, 'b) t -> 'b list
  end = struct
    type ('a, 'b) t = ('a -> 'b) * 'a list
    let of_list list = (fun x -> x), list
    let map f (g, list) = (fun x -> f(g x)), list
    let to_list (f, list) = List.map f list
  end

Where your existing implementation exposes an 'a list you now expose an 
('b, 'a) Seq.t instead.

# let a = Seq.of_list [1];;
val a : (int, int) Seq.t = <abstr>
# let b = Seq.map float a;;
val b : (int, float) Seq.t = <abstr>
# let c = Seq.map string_of_float b;;
val c : (int, string) Seq.t = <abstr>
# Seq.to_list c;;
- : string list = ["1."]

> That's why I wondered if there was a way to tell the compiler to do it
> for me. Or maybe some incantation with ocamlp4?

I would not recommend pursuing that line of thought under any circumstances. 
Even if this problem is a critical showstopper for you, I would always 
recommend uglier code over camlp4 hacks.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e