Re: [Caml-list] OCaml troll on Slashdot

[brogoff <brogoff@speakeasy.net>]

I just ran your counterexample and the tail recursive code was faster
for each. I used native code compilation.

Byte code compilation gives similar results to yours, except that as I ran the
test on "ye olde SPARC machine", it took a hell of a lot longer.

I'll try on a few different architectures later.

Anyways, long lists do occur, and Stack_overflow at the customer site sucketh
bigtime.

-- Brian

On Wed, 16 Mar 2005, Jon Harrop wrote:

> On Wednesday 16 March 2005 17:43, brogoff wrote:
> > On Wed, 16 Mar 2005, Jacques Garrigue wrote:
> > > Because tail-recursive versions do some extra work to ensure
> > > tail-recursiveness. For instance building a list in reverse order, and
> > > converting it back with List.rev at the end. This only pays off for
> > > huge lists.
> >
> > No doubt the implementors will want me guillotined for bringing this up
> > again, but using the (still functional!) set_cdr! tail recursive functions,
> > which do *not* reverse the list, are always faster than the non tail
> > recursive list functions, even for small lists, at least in my experience.
> > So I suspect that your "for instance" is in fact the only reason for the
> > disparity. I'd welcome a counterexample.
>
> Here is one of the counterexamples given in my book, two implementations of a
> fold_right function over an implicit semi-inclusive range of integers [l..u):
>
> # let rec fold_right1 f accu l u =
>     if l < u then f (fold_right1 f accu (l + 1) u) l else accu;;
> val fold_right1 : ('a -> int -> 'a) -> 'a -> int -> int -> 'a = <fun>
> # let rec fold_right2 f accu l u =
>     if l < u then let u = u - 1 in fold_right2 f (f accu u) l u else accu;;
> val fold_right2 : ('a -> int -> 'a) -> 'a -> int -> int -> unit = <fun>
>
> (A program for timing is at the end of this e-mail).
>
> Here, the non-tail-recursive fold_left function is significantly faster on
> smaller lists and the tail-recursive fold_right functions is much faster in
> larger lists.
>
> I believe there are many other counterexamples. Indeed, I would even say that
> most functions are counterexamples. Perhaps the reason is that non-tail
> recursion is used when it is natural for a given task, and transforming into
> tail-recursive form is then necessarily more complicating the function.
>
> > Those Obj based List functions are what ExtLib provides, I think, and there
> > are even ways to get this optimization neatly into ML style languages.
> > Maybe in ML 20XY this will be addressed.
>
> I don't know what the performance of such transformed code would be. Perhaps
> the transformation would slow code down. Consequently, it may be early days
> to call it an "optimisation".
>
> Here's the timing program:
>
> let rec fold_right1 f accu l u =
>   if l < u then f (fold_right1 f accu (l + 1) u) l else accu
> let rec fold_right2 f accu l u =
>   if l < u then let u = u - 1 in fold_right2 f (f accu u) l u else accu
>
> let rec test f n = if n>0 then (f (); test f (n-1))
>
> let _ =
>   let t = Unix.gettimeofday () in
>   test (fun () -> ignore (fold_right1 ( + ) 0 1 5000)) 10000;
>   Printf.printf "Non-tail-recursive took: %fs\n"
>     (Unix.gettimeofday () -. t);
>   let t = Unix.gettimeofday () in
>   test (fun () -> ignore (fold_right2 ( + ) 0 1 5000)) 10000;
>   Printf.printf "Tail-recursive took: %fs\n\n"
>     (Unix.gettimeofday () -. t);
>   let t = Unix.gettimeofday () in
>   test (fun () -> ignore (fold_right1 ( + ) 0 1 50000)) 1000;
>   Printf.printf "Non-tail-recursive took: %fs\n"
>     (Unix.gettimeofday () -. t);
>   let t = Unix.gettimeofday () in
>   test (fun () -> ignore (fold_right2 ( + ) 0 1 50000)) 1000;
>   Printf.printf "Tail-recursive took: %fs\n"
>     (Unix.gettimeofday () -. t)
>
> $ ./test
> Non-tail-recursive took: 0.513307s
> Tail-recursive took: 0.582472s
>
> Non-tail-recursive took: 1.950229s
> Tail-recursive took: 0.590756s
>
> --
> Dr Jon D Harrop, Flying Frog Consultancy Ltd.
> Objective CAML for Scientists
> http://www.ffconsultancy.com/products/ocaml_for_scientists
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>