From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id JAA02950 for caml-redistribution; Thu, 7 Oct 1999 09:55:13 +0200 (MET DST)
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA27935 for <caml-list@pauillac.inria.fr>; Wed, 6 Oct 1999 17:39:02 +0200 (MET DST)
Received: from mail5.svr.pol.co.uk (mail5.svr.pol.co.uk [195.92.193.20])
	by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id RAA12811
	for <caml-list@inria.fr>; Wed, 6 Oct 1999 17:39:00 +0200 (MET DST)
Received: from modem-90.prozac.dialup.pol.co.uk ([62.136.85.90] helo=toy.william.bogus)
	by mail5.svr.pol.co.uk with esmtp (Exim 2.12 #2)
	id 11Yt9f-0001yv-00; Wed, 6 Oct 1999 16:38:59 +0100
Received: (from williamc@localhost)
	by toy.william.bogus (8.8.7/8.8.7) id QAA02123;
	Wed, 6 Oct 1999 16:21:05 +0100
Date: Wed, 6 Oct 1999 16:21:05 +0100
Message-Id: <199910061521.QAA02123@toy.william.bogus>
From: William Chesters <williamc@dai.ed.ac.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
To: Gerd.Stolpmann@darmstadt.netsurf.de
Cc: caml-list@inria.fr
Subject: Re: speed versus C
In-Reply-To: <99100522193302.17263@ice>
References: <000f01bf0de7$2f626fd0$240cbed4@jannt>
	<99100522193302.17263@ice>
X-Mailer: VM 6.34 under Emacs 20.2.1
Sender: weis

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.