Re: [Caml-list] looping recursion

[brogoff <brogoff@speakeasy.net>]

On Thu, 29 Jul 2004, Daniel Andor wrote:
> On Wednesday 28 July 2004 10:22 pm, brogoff wrote:
> > On Wed, 28 Jul 2004, Jon Harrop wrote:
> > > On Wednesday 28 July 2004 17:38, brogoff wrote:
> > > > > brogoff wrote:
> > > > > > Sometimes lists are best. If lists are OK for 100, 1_000, or 10_000
> > > > > > items, why not 100_000 or 1_000_000? Map and friends shouldn't blow
> > > > > > stack.
> [...]
> > > What's wrong with List.rev_map, List.rev (List.rev_map ...), increasing
> > > the size of the VM's stack, using native code or even writing your own,
> > > tail-recursive map?
> >
> > I'm pretty damned well aware that I can reverse a rev mapped list.
>
> If you've got the mutable list version of map to hand, and you are happy with
> that, then that's clearly the way to go.

And I said as much. I also said it offends my sense of aesthetics ;-).

> Lemme try it out (10^6 elements):
>
> ocamlc:
> rev rev_map version:
>  2 WALL ( 1.19 usr +  0.02 sys =  1.21 CPU)
> vanilla map:
>  7 WALL ( 6.50 usr +  0.09 sys =  6.59 CPU)
>
> ocamlopt:
> rev rev_map version:
>  1 WALL ( 0.81 usr +  0.03 sys =  0.84 CPU)
> vanilla map:
>  2 WALL ( 2.45 usr +  0.02 sys =  2.47 CPU)
>
> Wow, that was unexpected!
>
> > Does it occur to you that that is not efficient?
>
> Not any more!

You neglected the "mutable" list version in your quickie benchmark. My
own quickie benchmark showed that version had better performance
than the doubly reversing implementation on large lists and very slightly
better performance than the default on small ones. I would expect that
if something like holes or promises (a la Alice SML) or whatever were in
OCaml, that under the hood it would be the same as the mutable list version and
so would have equivalent performance.

-- Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners