tail-recursion vs. no tail-recursion in list functions

[sebastian.egner@philips.com]

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

Just to chime in on this...

Did anybody every consider the following simple solution for the 'map' 
problem?

let unbreakable_map f xs =
    let rec 
      map limit f xs = (* recursion depth limited to limit *)
        match xs with
          []                   -> []
        | x::xs when limit > 0 -> let f_x = f x in f_x::(map (limit-1) f 
xs)
        | _                    -> List.rev_append (List.rev_map f xs) []
    in  map 512 f xs;;

The function is not tail-recursive for lists of length up to 512---at 
which point it
switches to a tail-recursive algorithm and uses the heap instead of the 
stack
to keep track of structural recursion.

The overhead introduced is counting down and comparing an int-counter.

Clearly, this solution is applicable to most other structural operations 
on lists
and it gets rid of many stack overflows nicely. 

Since the "magic number" 512 necessarily represents a trade-off, I would 
like
to see it being chosen at the time the Ocaml compiler is constructed for a 
specific
target architecture, i.e. at the time somebody more or less knows the 
stack size.

Cheers,

Sebastian.


----
Dr. Sebastian Egner
Senior Scientist Channel Coding & Modulation
Philips Research Laboratories
Prof. Holstlaan 4 (WDC 1-051, 1st floor, room 51)
5656 AA Eindhoven
The Netherlands
tel:       +31 40 27-43166   *** SINCE 10-Feb-2005 ***
fax:      +31 40 27-44004
email: sebastian.egner@philips.com









Jon Harrop <jon@ffconsultancy.com>
Sent by: 
caml-list-admin@yquem.inria.fr
16-03-2005 20:51
 
        To:     caml-list@yquem.inria.fr
        cc:     (bcc: Sebastian Egner/EHV/RESEARCH/PHILIPS)
        Subject:        Re: [Caml-list] OCaml troll on Slashdot
        Classification: 




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


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