From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: weis Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id OAA29947 for caml-redistribution; Mon, 15 Mar 1999 14:29:43 +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 TAA03949 for ; Fri, 12 Mar 1999 19:18:20 +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 TAA04011 for ; Fri, 12 Mar 1999 19:18:18 +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 NAA29607; Fri, 12 Mar 1999 13:18:17 -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 NAA18714; Fri, 12 Mar 1999 13:18:16 -0500 (EST) Sender: weis Message-ID: <36E95A68.5DA46AA2@CS.Cornell.EDU> Date: Fri, 12 Mar 1999 13:18:16 -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: Wolfram Kahl CC: caml-list@inria.fr Subject: Re: List.filter in Ocaml 2.02 References: <19990305114112.34610@pauillac.inria.fr> <36E854D1.E52CD73B@CS.Cornell.EDU> <19990312101049.6512.qmail@diogenes.informatik.unibw-muenchen.de> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Wolfram Kahl wrote: > Alexey Nogin writes: > > > The filter function implementation does not seem to be too efficient. > > I did some testing once and it turned out that the most efficient > > (for my applications) way to write the filter function was: > > > > 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 > > > > The main gain here is that we do not allocate any new memory for sublist > > (or the whole list) that does not change as a result of the filtering. > > The intended sharing here is not fully explicit, but partially implicit. > If this works as described, then it should not make a difference from: > > let rec filter f = function > [] as l -> l > | ... > > , where the sharing is now fully explicit. > The fact that this is reported to work anyway, implies > that the compiler shares these common subexpressions ``[]'', > and this gets me asking: > > How far does this kind of common subexpression sharing extend? > Does it work for user-defined datatypes, too? > Does it work only for zero-ary constructors, or are some > more complicated constructions recognised, too? As far as I understand it, for unboxed values such as integers and zero-ary constants (such as []) in user-defined datatypes == and = are equivalent. It has nothing to do with the fact that they are common subexpressions - if you write let x = [] in some module and let y = [] in another, it will still be the case that x == y. > P.S.: Does it work for ``filter f'', or is it useful to write > (as I often do): > > > let filter f = > > let rec f1 = function > > [] -> [] > > | (h::t) as l -> > > if f h then > > let rem = f1 t in > > if rem == t then l else h::rem > > else > > f1 t > > in f1 This will allocate memory for the closure which is contrary to the main goal - not allocating anything unless really necessary and not allocate anything at all when list does not change. > Will filter be expanded for short constant lists at compile time in > any way? I do not think so. > Or will e.g. List.fold_right or List.fold_left > (known to be primitively recursive at compile-time of user modules :-) > be expanded for short constant lists at compile time > by the inlining mechanism? As far as I know, recursive functions are never inlined. 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)