Re: speed versus C

[William Chesters <williamc@dai.ed.ac.uk>]

Gerd Stolpmann writes:
 > - The recursive data types of Ocaml are often more problem-oriented than
 >   "imperative" data structures. Consider you want to fill an (C) array with an
 >   unknown number of elements. The typical solution puts the elements into the
 >   array until it is full, and then enlarges the array by reallocating new
 >   memory. If you use the Ocaml lists instead, you do not have this problem.

   But you do have N little problems (N memory allocations and
structure initialisations); you waste large amounts of memory in
headers and pointers, thereby filling up your caches; and you end up
with a data structure which takes at just as long to traverse and
entirely fails to support any other kind of access.  If you do the
sums, you will find that an array-based data structure (`Vector')
works out cheaper any way you care to look at it---as long as you
increase its capacity exponentially, e.g. doubling it each time it
runs out.  This stipulation is not a problem because the space you
thereby waste is still less than the amount you would lose to the
spine of a list (and is less pernicious since it doesn't have to churn
through the cache).

   Incidentally, implementing a Vector in ocaml is slightly fiddly,
because you have to keep valid pointers of the right type in even the
unused part all the time.  This means o.a. delaying the creation of
the underlying array until you have at least one element to put in it.