From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 69DD0BC32 for ; Thu, 17 Mar 2005 02:06:08 +0100 (CET) Received: from kurims.kurims.kyoto-u.ac.jp (kurims.kurims.kyoto-u.ac.jp [130.54.16.1]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j2H16656029822 for ; Thu, 17 Mar 2005 02:06:07 +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 j2H162q0025526; Thu, 17 Mar 2005 10:06:03 +0900 (JST) Date: Thu, 17 Mar 2005 10:05:55 +0900 (JST) Message-Id: <20050317.100555.35043913.garrigue@math.nagoya-u.ac.jp> To: brogoff@speakeasy.net Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] OCaml troll on Slashdot From: Jacques Garrigue In-Reply-To: References: <20050316.224108.35690658.garrigue@math.nagoya-u.ac.jp> 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 nez-perce with ID 4238D7FE.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 ocaml:01 irisa:01 ocaml:01 recursive:01 inputs:01 recursive:01 stack:01 rec:01 utime:01 utime:01 iter:01 printf:01 printf:01 stdout: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: brogoff > On Wed, 16 Mar 2005, Jacques Garrigue wrote: > > From: Yoann Padioleau > > > Jon Harrop writes: > > > > In OCaml, non-tail-recursive functions are often faster than their tail > > > > recursive equivalents for small inputs (e.g. short lists). > > > > > > really ? why ? > > > > 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. > > 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 beg to differ on performance. Here are the results of a micro-benchmark comparing List.map and ExtLib.List.map. With List.map l10*10000: 0.117188s l100*1000: 0.132812s l1000*100: 0.195312s l10000*10: 0.859375s l100000*1: 3.328125s With ExtLib.List.map l10'*10000: 0.187500s l100'*1000: 0.203125s l1000'*100: 0.304688s l10000'*10: 1.382812s l100000'*1: 1.937500s So you can see that the tail-recursive version only gets faster somewhere between 10000 and 100000 elements. Hardly typical use of lists. On the other hand, there are cases where the non tail-recursive version will blow-up your stack, so you have no choice but to go with the possibly slower tail-recursive one. Jacques Garrigue Code used: let rec genlist n = if n > 0 then n :: genlist (n-1) else [] let l10 = genlist 10 let l100 = genlist 100 let l1000 = genlist 1000 let l10000 = genlist 10000 let l100000 = genlist 100000 let time f n = let t0 = (Unix.times ()).Unix.tms_utime in f n; (Unix.times()).Unix.tms_utime -. t0 let call_map l n = for i = 1 to n do ignore (List.map succ l) done let call_extmap l n = for i = 1 to n do ignore (ExtList.List.map succ l) done let process l = List.iter (fun (name, f, n) -> Gc.full_major (); let t = time f (n*100) in Printf.printf "%s*%d: %fs\n" name n t; flush stdout) l let () = process [ "l10", call_map l10, 10000; "l100", call_map l100, 1000; "l1000", call_map l1000, 100; "l10000", call_map l10000, 10; "l100000", call_map l100000, 1; "l10'", call_extmap l10, 10000; "l100'", call_extmap l100, 1000; "l1000'", call_extmap l1000, 100; "l10000'", call_extmap l10000, 10; "l100000'", call_extmap l100000, 1; ]