From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id JAA04458; Mon, 13 Sep 2004 09:02:18 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f 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 JAA05270 for ; Mon, 13 Sep 2004 09:02:17 +0200 (MET DST) Received: from post.bourget.univ-savoie.fr (post.bourget.univ-savoie.fr [193.48.120.73]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id i8D72GSv023918 (version=TLSv1/SSLv3 cipher=EDH-RSA-DES-CBC3-SHA bits=168 verify=NO); Mon, 13 Sep 2004 09:02:17 +0200 Received: from univ-savoie.fr (d85.lama.univ-savoie.fr [193.48.123.85]) by post.bourget.univ-savoie.fr (8.12.3/jtpda-5.4) with ESMTP id i8D72Cg5005509 ; Mon, 13 Sep 2004 09:02:13 +0200 Message-ID: <414545FC.3090009@univ-savoie.fr> Date: Mon, 13 Sep 2004 09:02:20 +0200 From: Christophe Raffalli User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.6) Gecko/20040115 X-Accept-Language: en-us, en MIME-Version: 1.0 To: Christophe Raffalli CC: Jon Harrop , caml users , Damien Doligez Subject: Re: Array.init (was [Caml-list] Gripes with array) References: <200409090310.29295.jon@jdh30.plus.com> <200409091758.05679.jon@jdh30.plus.com> <41414200.40509@univ-savoie.fr> In-Reply-To: <41414200.40509@univ-savoie.fr> X-Enigmail-Version: 0.83.3.0 X-Enigmail-Supports: pgp-inline, pgp-mime Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="------------enig7DA77864623C33585BA8D4C5" Content-Transfer-Encoding: 8bit X-Scanned-By: MIMEDefang 2.33 (www . roaringpenguin . com / mimedefang) X-Miltered: at nez-perce with ID 414545F8.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; raffalli:01 raffalli:01 univ-savoie:01 caml-list:01 openpgp:01 2440:01 3156:01 invariants:01 runtime:01 addresse:99 initialized:01 runtime:01 pointers:01 savoie:01 chablais:01 X-Attachments: type="application/pgp-signature" name="signature.asc" name="signature.asc" Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enig7DA77864623C33585BA8D4C5 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit Christophe Raffalli wrote: > >> >>>> Also, can Array.init be made to fill the elements only once? >>> >>> >>> No, that's impossible without breaking the GC invariants. >> >> > > This is not true if the runtime maintains a list of array in > construction with the current position of the index. This list will stay > rather small, but each addresse read by the GC will have to be checked > for membership in the list. If the list is rather small it will be in > the cache, but still I am afraid it will slow down noticably the GC. > > Did someone tried to implement such a list of partially initialized > objects in the GC ? (I do not think it is worth it ?) > You could also lie in the tag about the size of array (if the way the > runtime finds free block of memory does not use it). It will cost an > increment of integer at each step in the initialisation process which > should not be much since the beginning of array may stay in the cache if > the initialisation function is simple and this will be neggligeable if not. > > This second solution is only for non copying GC, so not for OCaml And yet another solution would have to have a tag with the total size + the number of non pointers at the end of the block. This would be usefull not only for Arrays. It just makes again a (too) strong limit on the size of arrays. I am now wondering why the structure of a block does not allow a second tag word (and even a third tag word) for the tag in case of big objects ? A cons cell keeps a tag of only one word (that's still too much :-), but an array (or even only an array of size > 2^n) uses a bigger tag. Moreover this extra tag word could be at address (p-1) if p is the address of the object so that some code like unsafe.get do not need to access it. The Gc and few other function like Array.length, Array.get in the bound check,.. would have an extra test to do, but the GC would have less memory to scan (because it would have to scan not all word in a block). -- Christophe Raffalli Université de Savoie Batiment Le Chablais, bureau 21 73376 Le Bourget-du-Lac Cedex tél: (33) 4 79 75 81 03 fax: (33) 4 79 75 87 42 mail: Christophe.Raffalli@univ-savoie.fr www: http://www.lama.univ-savoie.fr/~RAFFALLI --------------------------------------------- IMPORTANT: this mail is signed using PGP/MIME At least Enigmail/Mozilla, mutt or evolution can check this signature --------------------------------------------- --------------enig7DA77864623C33585BA8D4C5 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.4 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFBRUX9SQDyWB/+xBwRApM5AKDA9s+jvZsnjvnxFZ/KA3IWyxcH1wCgjFbe 6K64t4DSGr5GXKjCl8GZL1I= =UCD5 -----END PGP SIGNATURE----- --------------enig7DA77864623C33585BA8D4C5-- ------------------- 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