Re: List.filter in Ocaml 2.02

[Alexey Nogin <nogin@cs.cornell.edu>]

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)