From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id AE8E1BC32 for ; Fri, 18 Mar 2005 02:13:53 +0100 (CET) Received: from kurims.kurims.kyoto-u.ac.jp (kurims.kurims.kyoto-u.ac.jp [130.54.16.1]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j2I1DpC9012353 for ; Fri, 18 Mar 2005 02:13:53 +0100 Received: from localhost (suiren [130.54.16.25]) by kurims.kurims.kyoto-u.ac.jp (8.13.1/8.13.1) with ESMTP id j2I1DZCa024424; Fri, 18 Mar 2005 10:13:36 +0900 (JST) Date: Fri, 18 Mar 2005 10:13:29 +0900 (JST) Message-Id: <20050318.101329.00954286.garrigue@math.nagoya-u.ac.jp> To: sebastian.egner@philips.com Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] tail-recursion vs. no tail-recursion in list functions From: Jacques Garrigue In-Reply-To: References: <200503161951.48923.jon@ffconsultancy.com> X-Mailer: Mew version 4.2 on Emacs 21.3 / Mule 5.0 (SAKAKI) Mime-Version: 1.0 Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 423A2B4F.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 rec:01 recursion:01 heap:01 stack:01 recursion:01 ocamlopt:01 bytecode:01 recursive:01 stack:01 runtime:01 trade-off:01 ocaml:01 compiler:01 tail:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: From: sebastian.egner@philips.com > 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. I just tried to do it, and it seems to work well. The overhead of the counter is really small. Note that in the long list case I call the extlib map function rather than rev o rev_map, as it performs better on such long lists. Results: (ocamlopt, limit=1000) using List.map l10*10000: 0.117188s l100*1000: 0.132812s l1000*100: 0.195312s l10000*10: 0.843750s l100000*1: 3.328125 using your approach (reverting to ExtLib.List.map) l10'*10000: 0.140625s l100'*1000: 0.140625s l1000'*100: 0.203125s l10000'*10: 1.265625s l100000'*1: 1.945312s using ExtLib.List.map l10'*10000: 0.187500s l100'*1000: 0.203125s l1000'*100: 0.304688s l10000'*10: 1.382812s l100000'*1: 1.937500s The performance is even better with append, and with bytecode also. So this seems that at least extlib could use that. One criticism is that it is not really tail recursive, as it consumes some large amount of stack, albeit limited. Brian seemed to imply that he has programs for which even this would be bad, but I'm really curious to such case. Basically it would mean using map recursively rather deep, meaning exponential runtime anyway, so I'm not sure this is a problem. > 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. Honestly, this part is going to be difficult. And I'm not sure it is that relevant anyway. A fixed value already gives safety, good performance on small lists, and reasonable overall performance. Jacques Garrigue