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 E371ABC32 for ; Wed, 16 Mar 2005 18:43:45 +0100 (CET) Received: from mail21.sea5.speakeasy.net (mail21.sea5.speakeasy.net [69.17.117.23]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j2GHhhc2018461 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Wed, 16 Mar 2005 18:43:45 +0100 Received: (qmail 24320 invoked from network); 16 Mar 2005 17:43:42 -0000 Received: from shell2.sea5.speakeasy.net ([69.17.116.3]) (envelope-sender ) by mail21.sea5.speakeasy.net (qmail-ldap-1.03) with AES256-SHA encrypted SMTP for ; 16 Mar 2005 17:43:42 -0000 Date: Wed, 16 Mar 2005 09:43:42 -0800 (PST) From: brogoff To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] OCaml troll on Slashdot In-Reply-To: <20050316.224108.35690658.garrigue@math.nagoya-u.ac.jp> Message-ID: References: <20050316001819.GB347@first.in-berlin.de> <200503160301.11138.jon@ffconsultancy.com> <20050316.224108.35690658.garrigue@math.nagoya-u.ac.jp> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at concorde with ID 4238704F.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 wrote:01 writes:01 short:01 tail:01 tail:01 functions:01 functions:01 speakeasy: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: 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. -- Brian