From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id OAA12177 for caml-redistribution; Mon, 15 Mar 1999 14:30:25 +0100 (MET) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA14768 for ; Fri, 12 Mar 1999 19:37:57 +0100 (MET) Received: from simon.cs.cornell.edu (SIMON.CS.CORNELL.EDU [128.84.154.10]) by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id TAA04397 for ; Fri, 12 Mar 1999 19:37:55 +0100 (MET) Received: from cloyd.cs.cornell.edu (CLOYD.CS.CORNELL.EDU [128.84.227.15]) by simon.cs.cornell.edu (8.9.3/8.9.3/R-2.1) with ESMTP id NAA00811; Fri, 12 Mar 1999 13:37:54 -0500 (EST) Received: from CS.Cornell.EDU (nogin@GULAG.CS.CORNELL.EDU [128.84.248.53]) by cloyd.cs.cornell.edu (8.8.8/8.8.8/M-1.12) with ESMTP id NAA19552; Fri, 12 Mar 1999 13:37:53 -0500 (EST) Sender: weis Message-ID: <36E95F00.129D35DB@CS.Cornell.EDU> Date: Fri, 12 Mar 1999 13:37:53 -0500 From: Alexey Nogin Organization: Cornell University, department of Computer Science X-Mailer: Mozilla 4.08 [en] (X11; U; Linux 2.0.37 i686) MIME-Version: 1.0 To: Jean-Francois Monin CC: caml-list@inria.fr Subject: Re: List.filter in Ocaml 2.02 References: <19990305114112.34610@pauillac.inria.fr> <36E854D1.E52CD73B@CS.Cornell.EDU> <199903121011.LAA27611@lsun565.lannion.cnet.fr> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Jean-Francois Monin wrote: > > let rec filter f = function > > [] -> [] > > | (h::t) as l -> > > if f h then > > let rem = filter f t in > > if rem == t then l else h::rem > > else > > filter f t > > Here is a version without "==" and "as", with the same property on > memory allocation. > > exception No_change > let rec filter f l = > try fil f l with No_change -> l > and fil f = function > [] -> raise No_change > | h::t -> if f h then h :: fil f t else filter f t If would be much slower. Here are the reasons: 1) Even when exception is not raised, the try ... with ... construction executes lots of extra instructions and is quite expensive. 2) Even if the list is not changed, you first allocate the space and put its copy there, then raise an exception and return the old value. That means that you first waste time in memory allocation and then you waste it in garbage collection. 3) "raise No_change" allocates 8 bytes (on x86), so you'll waste some time in garbage collection. Alexey -------------------------------------------------------------- Home Page: http://www.cs.cornell.edu/nogin/ E-Mail: nogin@cs.cornell.edu (office), ayn2@cornell.edu (home) Office: Upson 4139, tel: 1-607-255-4934 ICQ #: 24708107 (office), 24678341 (home)