* Re: [Caml-list] optimization of sequence of List.map and inlining
2008-06-10 19:01 optimization of sequence of List.map and inlining Charles Hymans
@ 2008-06-10 19:21 ` Jon Harrop
2008-06-10 20:55 ` Richard Jones
2008-06-10 22:10 ` Peng Zang
` (2 subsequent siblings)
3 siblings, 1 reply; 6+ messages in thread
From: Jon Harrop @ 2008-06-10 19:21 UTC (permalink / raw)
To: caml-list
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] optimization of sequence of List.map and inlining
2008-06-10 19:21 ` [Caml-list] " Jon Harrop
@ 2008-06-10 20:55 ` Richard Jones
0 siblings, 0 replies; 6+ messages in thread
From: Richard Jones @ 2008-06-10 20:55 UTC (permalink / raw)
To: Jon Harrop; +Cc: caml-list
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] optimization of sequence of List.map and inlining
2008-06-10 19:01 optimization of sequence of List.map and inlining Charles Hymans
2008-06-10 19:21 ` [Caml-list] " Jon Harrop
@ 2008-06-10 22:10 ` Peng Zang
2008-06-10 23:07 ` Brian Hurt
2008-06-17 14:36 ` Jon Harrop
3 siblings, 0 replies; 6+ messages in thread
From: Peng Zang @ 2008-06-10 22:10 UTC (permalink / raw)
To: caml-list; +Cc: Charles Hymans
-----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-----
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] optimization of sequence of List.map and inlining
2008-06-10 19:01 optimization of sequence of List.map and inlining Charles Hymans
2008-06-10 19:21 ` [Caml-list] " Jon Harrop
2008-06-10 22:10 ` Peng Zang
@ 2008-06-10 23:07 ` Brian Hurt
2008-06-17 14:36 ` Jon Harrop
3 siblings, 0 replies; 6+ messages in thread
From: Brian Hurt @ 2008-06-10 23:07 UTC (permalink / raw)
To: Charles Hymans; +Cc: caml-list
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] optimization of sequence of List.map and inlining
2008-06-10 19:01 optimization of sequence of List.map and inlining Charles Hymans
` (2 preceding siblings ...)
2008-06-10 23:07 ` Brian Hurt
@ 2008-06-17 14:36 ` Jon Harrop
3 siblings, 0 replies; 6+ messages in thread
From: Jon Harrop @ 2008-06-17 14:36 UTC (permalink / raw)
To: caml-list
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
^ permalink raw reply [flat|nested] 6+ messages in thread