From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.3 required=5.0 tests=AWL,DNS_FROM_RFC_ABUSE autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 9CBB6BC6B for ; Tue, 30 Oct 2007 12:31:26 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAFqyJkfLENaHn2dsb2JhbACOXwIBAQcEBgkIGIET X-IronPort-AV: E=Sophos;i="4.21,347,1188770400"; d="scan'208";a="18761112" Received: from ipmail03.adl2.internode.on.net ([203.16.214.135]) by mail4-smtp-sop.national.inria.fr with ESMTP; 30 Oct 2007 12:31:25 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAIqvJkd5LGK+/2dsb2JhbAAMkCQ X-IronPort-AV: E=Sophos;i="4.21,347,1188743400"; d="scan'208";a="177715795" Received: from ppp121-44-98-190.lns10.syd6.internode.on.net (HELO [192.168.1.201]) ([121.44.98.190]) by ipmail03.adl2.internode.on.net with ESMTP; 30 Oct 2007 22:01:21 +1030 Subject: Re: [Caml-list] Preferred Way to Split a List From: skaller To: Christophe Raffalli Cc: Alain Frisch , caml-list@yquem.inria.fr In-Reply-To: <4725A915.3020005@univ-savoie.fr> References: <47266DB7.1020009@SmokejumperIT.com> <20071030012012.GA29836@localhost> <1193723182.6129.66.camel@rosella.wigram> <4726E433.7060408@frisch.fr> <4725A915.3020005@univ-savoie.fr> Content-Type: text/plain Date: Tue, 30 Oct 2007 22:31:20 +1100 Message-Id: <1193743880.6697.18.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.12.0 Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; 0100,:01 christophe:01 raffalli:01 recursive:01 val:01 allocations:01 pointer:01 pointers:01 mutation:01 pointers:01 grey:98 sourceforge:01 garbage:01 garbage:01 wrote:01 On Mon, 2007-10-29 at 10:34 +0100, Christophe Raffalli wrote: > Or > > let split l n = > let rec aux acc l n = > if n = 0 then List.rev acc, l > else match l with > [] -> List.rev acc, [] > | hd::l -> aux (hd::acc) l (n-1) > in aux [] l n > > This is tail recursive, it does not use magic nor references > and keed the original ordering of the list. Yes, but it double handles the head needlessly. Ignoring the interesting observation you make below, this would be expected to transfer head memory twice into the cache, when once would suffice. > Finally, I did in the past some testing comparing a tail-rec append or map > using magic and the composition of rev and rev-append or rev-map ... > There was no noticable difference, because the extra cost of > mutability (regarding the managment of the grey val list) compensate > the extra call to reverse. However, you raise here an important issue not covered well anywhere: when you have a garbage collection, the effect of some operation should include not just the local algorithmic considerations but also the cost of the garbage collection. In the equivalent Felix code, there is no issue with write barriers because Felix collector doesn't use them, so mutations don't incur any cost. OTOH allocations are expensive. Now, back to collectors .. the append is a special. The mutations in the append are not mutations, but deferred initialisations, that is, the write operation is guaranteed to be replacing a NULL pointer. Overwriting of NULL pointers is already possible in functional coding without it implying mutation. So one might imagine a collector with a minor and major heap, in which the major heap requires special handling for mutations. However the rule for moving an object out of the minor heap is that the object must be fully initialised. (all pointers in the block are non-null). In that design (I have no idea if it is viable!) the performance might be different for the 'append' and other mutations. The bottom line is that a good point is made that the usual fine detail performance analysis doesn't apply to a garbage collected language.. thanks for pointing this out! -- John Skaller Felix, successor to C++: http://felix.sf.net