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

[Eray Ozkural <exa@kablonet.com.tr>]

On Sunday 04 May 2003 13:56, Neel Krishnaswami wrote:
> > 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.

Now, we're getting some performance talk :)

To be precise, comparing an int list and int array we'll see that list 
occupies twice the same memory and therefore will generate more cache misses. 
But as the size of 'a in 'a list grows the difference will be negligible. 
However, if one modifies the elements of an array, in FORTRAN style, won't 
really be storing huge records inside elements of the array. He will likely 
split things up in parallel arrays where necessary, and if there are records 
they will be stored in a private heap and pointers will be stored in the 
array, etc.

Cheers,

-- 
Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara  KDE Project: http://www.kde.org
www: http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C

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