OCaml troll on Slashdot

Karl Zilles

Oliver Bandel

Michael Vanier

Jon Harrop

Yoann Padioleau
 Jon Harrop
 Paul Argentoff
 Paul Argentoff

Yoann Padioleau

Jon Harrop
 Yoann Padioleau

Michael Vanier
 Richard Jones

Oliver Bandel
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  sebastian.egner@p... 
Subject:  tailrecursion vs. no tailrecursion in list functions 
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 (limit1) f xs)  _ > List.rev_append (List.rev_map f xs) [] in map 512 f xs;; The function is not tailrecursive for lists of length up to 512at which point it switches to a tailrecursive algorithm and uses the heap instead of the stack to keep track of structural recursion. The overhead introduced is counting down and comparing an intcounter. 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 tradeoff, 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 1051, 1st floor, room 51) 5656 AA Eindhoven The Netherlands tel: +31 40 2743166 *** SINCE 10Feb2005 *** fax: +31 40 2744004 email: sebastian.egner@philips.com Jon Harrop <jon@ffconsultancy.com> Sent by: camllistadmin@yquem.inria.fr 16032005 20:51 To: camllist@yquem.inria.fr cc: (bcc: Sebastian Egner/EHV/RESEARCH/PHILIPS) Subject: Re: [Camllist] OCaml troll on Slashdot Classification: On Wednesday 16 March 2005 17:43, brogoff wrote: > On Wed, 16 Mar 2005, Jacques Garrigue wrote: > > Because tailrecursive versions do some extra work to ensure > > tailrecursiveness. 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 semiinclusive 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 email). Here, the nontailrecursive fold_left function is significantly faster on smaller lists and the tailrecursive 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 nontail recursion is used when it is natural for a given task, and transforming into tailrecursive 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 (n1)) let _ = let t = Unix.gettimeofday () in test (fun () > ignore (fold_right1 ( + ) 0 1 5000)) 10000; Printf.printf "Nontailrecursive took: %fs\n" (Unix.gettimeofday () . t); let t = Unix.gettimeofday () in test (fun () > ignore (fold_right2 ( + ) 0 1 5000)) 10000; Printf.printf "Tailrecursive took: %fs\n\n" (Unix.gettimeofday () . t); let t = Unix.gettimeofday () in test (fun () > ignore (fold_right1 ( + ) 0 1 50000)) 1000; Printf.printf "Nontailrecursive took: %fs\n" (Unix.gettimeofday () . t); let t = Unix.gettimeofday () in test (fun () > ignore (fold_right2 ( + ) 0 1 50000)) 1000; Printf.printf "Tailrecursive took: %fs\n" (Unix.gettimeofday () . t) $ ./test Nontailrecursive took: 0.513307s Tailrecursive took: 0.582472s Nontailrecursive took: 1.950229s Tailrecursive took: 0.590756s  Dr Jon D Harrop, Flying Frog Consultancy Ltd. Objective CAML for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists _______________________________________________ Camllist mailing list. Subscription management: http://yquem.inria.fr/cgibin/mailman/listinfo/camllist Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/camlbugs