From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 09FB8D55E for ; Sun, 31 Jul 2005 05:10:55 +0200 (CEST) Received: from ash25e.internode.on.net (ash25e.internode.on.net [203.16.214.182]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j6V3ArIV025567 for ; Sun, 31 Jul 2005 05:10:54 +0200 Received: from rosella (ppp11-151.lns1.syd7.internode.on.net [59.167.11.151] (may be forged)) by ash25e.internode.on.net (8.12.9/8.12.6) with ESMTP id j6V3AeYe037865; Sun, 31 Jul 2005 12:40:47 +0930 (CST) (envelope-from skaller@users.sourceforge.net) Subject: Re: [Caml-list] How to do this properly with OCaml? From: skaller To: Jon Harrop Cc: caml-list@yquem.inria.fr In-Reply-To: <200507310106.46441.jon@ffconsultancy.com> References: <1122478420.6768.36.camel@localhost.localdomain> <200507310106.46441.jon@ffconsultancy.com> Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="=-j5PxYHAX3VMorYLlkpMg" Date: Sun, 31 Jul 2005 13:10:40 +1000 Message-Id: <1122779440.2174.66.camel@localhost.localdomain> Mime-Version: 1.0 X-Mailer: Evolution 2.2.1.1 X-Miltered: at nez-perce with ID 42EC413D.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 ocaml:01 arrays:01 bounded:01 caching:01 indirections:01 caching:01 ...:98 wrote:01 sourceforge:01 sourceforge:01 extensible:01 behaviour:01 computation:01 algorithm:01 X-Attachments: type="application/pgp-signature" name="signature.asc" X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 --=-j5PxYHAX3VMorYLlkpMg Content-Type: text/plain Content-Transfer-Encoding: quoted-printable On Sun, 2005-07-31 at 01:06 +0100, Jon Harrop wrote: > Yes, I think the only advantage of extensible arrays is a slightly improv= ement=20 > in the constant prefactor in the complexity of some algorithms. Not quite, simply because 'complexity' is not the only thing of importance, since it only applies to asymptotic behaviour, which of no interested to clients of algorithms, only algorithm providers: clients are interested in=20 performance and limits on problems which can realistically be solved on their hardware, which is bounded in memory, and limited by processing speed -- please take that as a definition of 'client', ok? Here, the 'constant prefactor' can degrade and lead to quite significant differences: for example (a) doubling the amount of store your major data structure needs is only a 'constant' factor, but may make solution of a problem you are interested in swap from being barely possible to out of the question. (b) because of caching effects, the performance over ranges of problem size may not be 'linear' in the theoretical complexity: doubling the number of indirections could spill a fully 'in cache' intense computation out to the next level of caching and lead to an order of magnitude performance loss on just the size of problem you're interested in: I have been in several 'industrial' situations where this has actually happened, eg in a telco where a transaction rate of 60 calls/second for a switch was achieved but they needed more like=20 600 calls/second .. buying 40 servers instead of 4 isn't something you wish to tell your prospective clients they must do to use your software... :) Another scenario, recently discussed, where this happens is in games: close to the hardware solutions for graphics are often unnecessary but done anyway because programmers don't understand performance characteristics of their code, but sometimes there are places where there is just no other way to=20 build a viable product. In these types of situations, it is better if the vendor doesn't try to tell the application developer what they really need: better to let the application developer make their own mistakes :) --=20 John Skaller --=-j5PxYHAX3VMorYLlkpMg Content-Type: application/pgp-signature; name=signature.asc Content-Description: This is a digitally signed message part -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.5 (GNU/Linux) iD8DBQBC7EEwsRp8/9aGVGsRArBNAJwL1bCwbajonl8216k4V4UbZVgCoQCfebyC /qnjWv917FedCLGKaBxCmyc= =Nr9Q -----END PGP SIGNATURE----- --=-j5PxYHAX3VMorYLlkpMg--