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 72B9ABB81 for ; Mon, 28 Nov 2005 10:27:27 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id jAS9RQCN006119 for ; Mon, 28 Nov 2005 10:27:26 +0100 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 KAA11091 for ; Mon, 28 Nov 2005 10:27:26 +0100 (MET) Received: from smtp.cegetel.net (217-19-192-72.dti.cegetel.net [217.19.192.72]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id jAS9RPOV006114 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL) for ; Mon, 28 Nov 2005 10:27:26 +0100 Received: from [192.168.144.2] (80-125-86-59.adslgp.cegetel.net [80.125.86.59]) by smtp.cegetel.net (Postfix) with ESMTP id 68F391A402D; Mon, 28 Nov 2005 10:27:24 +0100 (CET) Message-ID: <438ACD76.5060200@univ-savoie.fr> Date: Mon, 28 Nov 2005 10:27:18 +0100 From: Christophe Raffalli User-Agent: Mozilla Thunderbird 1.0.7 (X11/20051017) X-Accept-Language: fr, en MIME-Version: 1.0 To: Nicolas Cannasse Cc: Christophe Raffalli , Brian Hurt , caml-list@inria.fr Subject: Re: [Caml-list] Obj or not Obj References: <4387ACC9.2040107@motion-twin.com> <438A4CAA.6070006@univ-savoie.fr> <438AC2AE.3040200@motion-twin.com> In-Reply-To: <438AC2AE.3040200@motion-twin.com> X-Enigmail-Version: 0.93.0.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="------------enigBC1378E904845FAA81524FA1" X-Miltered: at nez-perce with ID 438ACD7E.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 438ACD7D.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; christophe:01 raffalli:01 christophe:01 raffalli:01 univ-savoie:01 caml-list:01 cannasse:01 rec:01 rec:01 ocaml's:01 mutable:01 val:01 minor:01 mutable:01 val:01 X-Attachments: type="application/pgp-signature" name="signature.asc" 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 This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enigBC1378E904845FAA81524FA1 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Nicolas Cannasse a =E9crit : >> Just a small word about one of my bad experiment with Obj about tail r= ec >> map ... it is easy to get a tail >> rec map using Obj to make ocaml's list mutable ... it is just slower >> that the original map and using roughly the same >> amount of memory, because every cons cell you gain ... is now in the >> list of grey val as soon as your list does not >> fit in the minor heap anymore !! So even writing you own mutable_list >> type would be as bad ! >> >> Explanation: the list of grey val is a list of pointers from the major= >> heap to the minor heap which >> are created when using mutable data structure and which would break >> incremental GC if each minor GC did not scan >> the list of grey val) ... >=20 > This is not correct. > When you're building a mutable list you're allocating first in the mino= r > heap, then all cons go into the major heap at once, so only the "last" > cons before a GC cycle is greyed. It is indeed true that for short > lists, using the stack is better than using mutable structures. >=20 > But using the stack is getting speed against correctness, since it will= > overflow for big lists. >=20 I did timing for big lists with mutation using object and rev + rev_map and the later was faster ... If the list is big, and there is allocating computation for the car of each list in map, then I think a lot of cons cells can be greyed once =2E.. even all if each computation in the car triggers at least one minor= collection ... but then the complexity of map does not matter ... so my explanation for the observed timing was wrong ... may be this is just the test to know if one have to grey the cons-cell that's costly ? any way I now think rev + rev_map is better than dirty Obj for that pb. remark: I only tested on my athlon 32 ... > Nicolas --------------enigBC1378E904845FAA81524FA1 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.4.2 (GNU/Linux) Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org iQIVAwUBQ4rNepEBCSatcik9AQLBug//Q5obYLzWZ9mS1m/06m24Mtqhb9nzhbE+ dgfK9em7nmBR1xy8mCteuuu2NdsJ2s0nNHaIFFHbjxwS//Egjiy2M6/O1PQPKwo/ DoRVGyhxP+LMkquvWMcYEPLS6Kmzi5Ijvs+32+lFiK7fLFZoUV177O0OlbZ3ZFnG XrWn01ZtS7cU6PVE3hIlKriKnnTvjQAFkxsltowhz4+kCfO6iNTJ/m1hmDP2jQj5 ZX8jcHCioriLYgbmy3SzCR54DYkOKEs4w12awKMEfULlPQfleYdb7VQD0M+QnnqA L/exUWQuEcDmK7+otB4U3ktiVTkvu4YiEqZNsDE0zAvWBFRQMOtGs8W+NiXvKQC3 sXSoEv4EpkjJDeEpmcr0VCRI7z93pOZBmH+sEBkRCUWoiU0/DyOjHPXW+iu1p24r 2DQEcqUdUc6Rp4YnNSaCYn1QuVKUSSdBbwXUvJf1W9BFey1bUqmJ2DsZwG8B3XhE 2eleSbsyqLu47vH5zoo1l4SzVc2AFna91ve9fL4JB7YzWc4R9cFRxx6o1c2kKtiS ERJuajKyHAZ/sMhqMsk6ua2Ahz+PNptNQ6azc5bGqOIl0MeuI+5TVbV1Vf6dWNB7 7rCAoFxiogtXmDCfm3kz0BHr9MHjRugMYh6xBgVHp7xR1PbtqpRjh30MO3ZAsGQ3 NL+dxBSV9Lk= =KkZA -----END PGP SIGNATURE----- --------------enigBC1378E904845FAA81524FA1--