Re: List.filter in Ocaml 2.02

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


Date: Fri, 12 Mar 1999 13:37:53 -0500
From: Alexey Nogin <nogin@cs.cornell.edu>
To: Jean-Francois Monin <JeanFrancois.Monin@cnet.francetelecom.fr>
Subject: Re: List.filter in Ocaml 2.02

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)



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