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)