Hi there,

In my maniacal pursuit of efficiency I figured that I don't truly understand 
the performance of ocaml lists.

Could somebody please point to an explanation of ocaml linked list 
implementation or summarize its performance characteristics? This might seem 
like a trivial question but having used many functional languages I know that 
it's easy to commit performance genocide using linked lists.

For instance, a naive implementation of an optimal comparison sorting 
algorithm in LISP almost invariably results in an O(n^2logn) routine :)

Therefore, it would be a good start to explain whether ocaml lists are in fact 
LISP lists and if not in what aspects they differ.

The motivation for this question comes from trying to understand the use of 
linked lists in an efficient algorithm, such as graph algorithms (say we are 
implementing topological sort)

Assume I'm using the following structure that is far from handsome:
type x = (int list) array

Let a's type be x. Consider codes as the following
a.(i) <- a.(i) @ [x;y;z]
a.(i) <- [x] :: a.(i)

What travesty results in execution of such codes with i coming from an 
arbitrary sequence? Do using such constructs result in unholy incarnations of 
space leaks or gross inefficiencies?

Another question, does ocaml make any effort to place members of a list close 
to each other? Or, more naturally, the list element is allocated using a 
global model and then simply linked inside the structure?

These questions may sound weird but I'm hoping it will make sense to somebody!

Regards,

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