Re: [Caml-list] Efficiency of 'a list

[Neel Krishnaswami <neelk@alum.mit.edu>]

Ville-Pertti Keinonen writes:
> > I've done a little timing of things, and according to my results:
> > If you care about efficiency and use OCaml, you should use lists
> > fairly often, ie if you are always looping and accessing the elements
> > in order. OCaml can iterate through a list (recursively) about twice as
> > fast as it can iterate through an array.  It can iterate through a
> > list about as fast as or maybe even a little faster than C or C++ can
> > iterate through an array.
> 
> Don't trust microbenchmarks too far over what your knowledge of how
> things should work tell you. Iterating over arrays is certainly
> going to be much more cache-and TLB-friendly.

This is not be as true you think. Ocaml's garbage collector is a
compacting, copying GC, so it's very likely that lists will end up in
in continuous blocks of memory. This will end up being nearly as
cache-friendly as an array is.

The big exception is with arrays of floats -- Ocaml unboxes arrays of
floats, but doesn't unbox lists of them.

-- 
Neel Krishnaswami
neelk@alum.mit.edu

-------------------
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