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 AD9FDBC32 for ; Thu, 17 Mar 2005 18:26:57 +0100 (CET) Received: from yukon.yapper.org (adsl-67-120-175-89.dsl.lsan03.pacbell.net [67.120.175.89]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j2HHQuvW014026 for ; Thu, 17 Mar 2005 18:26:57 +0100 Received: from kenai.yapper.org (kenai.yapper.org [67.120.175.90]) by yukon.yapper.org (Postfix) with ESMTP id 5940165C; Thu, 17 Mar 2005 09:32:06 -0800 (PST) Received: from [127.0.0.1] (localhost [127.0.0.1]) by kenai.yapper.org (Postfix) with ESMTP id D30B46D3; Thu, 17 Mar 2005 09:32:05 -0800 (PST) Message-ID: <4239BF15.3040504@cs.caltech.edu> Date: Thu, 17 Mar 2005 09:32:05 -0800 From: Jason Hickey Organization: Caltech User-Agent: Mozilla Thunderbird 0.9 (X11/20041127) X-Accept-Language: en-us, en MIME-Version: 1.0 To: brogoff Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] OCaml troll on Slashdot References: <20050316001819.GB347@first.in-berlin.de> <200503160301.11138.jon@ffconsultancy.com> <20050316.224108.35690658.garrigue@math.nagoya-u.ac.jp> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 4239BDE0.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 ocaml:01 recursive:01 recursive:01 runtime:01 generational:01 garbage:01 ocaml:01 pointers:01 generations:01 minor:01 heap:01 wrote:01 tail:01 tail:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO autolearn=disabled version=3.0.2 X-Spam-Level: brogoff wrote: > 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. This optimization is probably reasonable. Note that assignment can have a somewhat unexpected cost when the runtime uses a generational garbage collector (as OCaml does). Speaking generally, the collector would like the invariant "all pointers in a generation refer to younger generations", where the "younger" relation is reflexive. This is true for purely functional languages, but not true when assignment is added. In general, the implementation needs to add a check during assignment: "if the value being modified belongs to a strictly older generation than the value being stored, then mark it." In the implementation of List.map using set_cdr! it should be possible to eliminate the check. The cons-cell was just allocated, so it should belong to the minor heap. Jason -- Jason Hickey http://www.cs.caltech.edu/~jyh Caltech Computer Science Tel: 626-395-6568 FAX: 626-792-4257