Re: List.filter in Ocaml 2.02

From: Alexey Nogin (nogin@cs.cornell.edu)
Date: Fri Mar 12 1999 - 19:18:16 MET


Date: Fri, 12 Mar 1999 13:18:16 -0500
From: Alexey Nogin <nogin@cs.cornell.edu>
To: Wolfram Kahl <kahl@diogenes.informatik.unibw-muenchen.de>
Subject: Re: List.filter in Ocaml 2.02

Wolfram Kahl wrote:

> Alexey Nogin <nogin@cs.cornell.edu> 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)



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:21 MET