AW: [Caml-list] The tag bit

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 RAA01675; Thu, 12 Aug 2004 17:23:01 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA02072 for ; Thu, 12 Aug 2004 17:23:00 +0200 (MET DST) Received: from kaiserslautern1.lms-gmbh.de (kaiserslautern1.lms-gmbh.de [212.43.68.201]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i7CFMxRM011744 for ; Thu, 12 Aug 2004 17:22:59 +0200 Received: by mail.lms-gmbh.de with Internet Mail Service (5.5.2653.19) id ; Thu, 12 Aug 2004 17:22:59 +0200 Message-ID: From: "Bauer, Christoph" To: caml-list@inria.fr Subject: AW: [Caml-list] The tag bit Date: Thu, 12 Aug 2004 17:22:53 +0200 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2653.19) Content-Type: multipart/alternative; boundary="----_=_NextPart_001_01C48080.3CCEEDE0" X-Miltered: at concorde with ID 411B8B53.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; bauer:01 bauer:01 caml-list:01 65.:99 caml-list:01 W4:99 65.:99 garbage:01 garbage:01 collector:02 collector:02 address:96 address:96 pointer:03 anyway:05 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk This message is in MIME format. Since your mail reader does not understand this format, some or all of this message may not be legible. ------_=_NextPart_001_01C48080.3CCEEDE0 Content-Type: text/plain > Well, I can see several reasons : > * processors like powers of two, especially when it comes > to the size > of a memory address, because of cache issues, so you'd better > make it 32 > or 64 words than 33 or 65. > * If the tag bit can be anywhere in a word you have to spend extra > time to extract it, whereas when it is at a fixed place, > especially LSB > or MSB, it is very cheap and easy. > * You would need two registers to access a value and its > tag instead > of one, and registers are very precious, at least on IA-32 > architectures. But who needs the tag bit? Only the garbage collector. Maybe it's an advantage to see 32 tag bits as a whole, e.g. the question "does the block contains any pointer" can be calculated bit-parallel. Anyway the garbage collector could works on blocks and needs just one additional memory access per block. Regards, Christoph Bauer ------_=_NextPart_001_01C48080.3CCEEDE0 Content-Type: text/html AW: [Caml-list] The tag bit

>     Well, I can see several reasons :
>   * processors like powers of two, especially when it comes
> to the size
> of a memory address, because of cache issues, so you'd better
> make it 32
> or 64 words than 33 or 65.
>   * If the tag bit can be anywhere in a word you have to spend extra
> time to extract it, whereas when it is at a fixed place,
> especially LSB
> or MSB, it is very cheap and easy.
>   * You would need two registers to access a value and its
> tag instead
> of one, and registers are very precious, at least on IA-32
> architectures.

But who needs the tag bit? Only the garbage collector. Maybe it's
an advantage to see 32 tag bits as a whole, e.g. the question
"does the block contains any pointer" can be calculated bit-parallel.
Anyway the garbage collector could works on blocks and needs
just one additional memory access per block.

Regards,
Christoph Bauer

------_=_NextPart_001_01C48080.3CCEEDE0-- ------------------- 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 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 FAA26684; Fri, 13 Aug 2004 05:54:47 +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 FAA27211 for ; Fri, 13 Aug 2004 05:54:46 +0200 (MET DST) Received: from kurims.kurims.kyoto-u.ac.jp (kurims.kurims.kyoto-u.ac.jp [130.54.16.1]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i7D3shmL025736 for ; Fri, 13 Aug 2004 05:54:45 +0200 Received: from localhost (tet.kurims.kyoto-u.ac.jp [130.54.16.184]) by kurims.kurims.kyoto-u.ac.jp (8.9.3p2-20030924/3.7W) with ESMTP id MAA28419; Fri, 13 Aug 2004 12:54:35 +0900 (JST) Date: Fri, 13 Aug 2004 12:53:29 +0900 (JST) Message-Id: <20040813.125329.74721093.garrigue@kurims.kyoto-u.ac.jp> To: Christoph.Bauer@lms-gmbh.de Cc: caml-list@inria.fr Subject: Re: AW: [Caml-list] The tag bit From: Jacques Garrigue In-Reply-To: References: X-Mailer: Mew version 4.0.64 on Emacs 21.3 / Mule 5.0 (SAKAKI) Mime-Version: 1.0 Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 411C3B83.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 jacques:01 bauer:01 bauer:01 jacques:01 garbage:01 garbage:01 approaches:01 lisp:01 garrigue:01 garrigue:01 collector:02 collector:02 pointer:03 suppose:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk From: "Bauer, Christoph" > But who needs the tag bit? Only the garbage collector. Maybe it's > an advantage to see 32 tag bits as a whole, e.g. the question > "does the block contains any pointer" can be calculated bit-parallel. > Anyway the garbage collector could works on blocks and needs > just one additional memory access per block. But who works in your program? The garbage collector! Do some profiling, and you will be surprised at how much time is used collecting garbage in a perfectly sane program. No surprise here: in symbolic programming, you are generating garbage all the time. In the old lisp days, people talked of the mutator (your program) and the collector, emphasizing that they are almost equal. And you wouldn't give 1 bit for your brother, doing all the dirty work? :-) More seriously, it may be that your idea of blocks could be made to work, but it's not going to be easy. For instance, what do you do when manipulating data between registers? Looks like it would mean updating some special register every time you do a move operation. This could generate heaps of code. GC is such an old field that I suppose all weird approaches have already been studied in the litterature. Jacques Garrigue ------------------- 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 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 OAA12644; Fri, 13 Aug 2004 14:58:42 +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 OAA10552 for ; Fri, 13 Aug 2004 14:58:40 +0200 (MET DST) Received: from smtp.cegetel.net (mf00.sitadelle.com [212.94.174.77]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i7DCwdmL012303 for ; Fri, 13 Aug 2004 14:58:40 +0200 Received: from univ-savoie.fr (unknown [80.125.77.158]) by smtp.cegetel.net (Postfix) with ESMTP id 79853672A6; Fri, 13 Aug 2004 14:58:34 +0200 (CEST) Message-ID: <411CBAF6.3010101@univ-savoie.fr> Date: Fri, 13 Aug 2004 14:58:30 +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: Jacques Garrigue Cc: Christoph.Bauer@lms-gmbh.de, caml-list@inria.fr Subject: Re: AW: [Caml-list] The tag bit References: <20040813.125329.74721093.garrigue@kurims.kyoto-u.ac.jp> In-Reply-To: <20040813.125329.74721093.garrigue@kurims.kyoto-u.ac.jp> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit X-Miltered: at nez-perce with ID 411CBAFF.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 pointers:01 hashtbl:01 caml's:01 savoie:01 chablais:01 73376:01 univ-savoie:01 lama:01 enigmail:01 mutt:01 christophe:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk There is a less costly way to avoid the tag bit in integer: "conservative GC": any int which happens to point in an alloccated block (or only at the beginning if you do not consider C but ML) is considered as a pointer. You will have very few wrong pointers (especially in the second case). Moreover, array of int or float, or block of memory can be tagged with a flag saying they do not old pointer. The Boehm GC for C and C++ is very succefull to do that and very often allow you to share data-structure in C as you would in ML (not caring about who will release first the data) and gain both speed and memory. Does anyone have a comparison between two identical GC except one should have a tag bit and the other be conservative ? The cost of conservative GC is the test to know if an int is pointing in (or at the beginning) of an allocated block which require for instance a hashtbl of allocated blocks by adress ranges. I don't know if the gain for arithmetic + easier C interface would compensate the lost in the GC for a real GC like Caml's. -- 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 --------------------------------------------- ------------------- 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 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 PAA12390; Fri, 13 Aug 2004 15:17:11 +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 PAA12551 for ; Fri, 13 Aug 2004 15:17:10 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i7DDH9mL014258 for ; Fri, 13 Aug 2004 15:17:10 +0200 Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.11/jtpda-5.4) with ESMTP id i7DDG4c4034194 ; Fri, 13 Aug 2004 15:16:04 +0200 (CEST) X-Ids: 168 Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id PAA123200 ; Fri, 13 Aug 2004 15:15:05 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id PAA495850 ; Fri, 13 Aug 2004 15:14:44 +0200 X-Authentication-Warning: ibm1.cicrp.jussieu.fr: fernande owned process doing -bs Date: Fri, 13 Aug 2004 15:14:44 +0200 (DST) From: Diego Olivier Fernandez Pons X-X-Sender: fernande@ibm1 To: Christophe Raffalli cc: caml-list@inria.fr Subject: [Caml-list] Other GC in ML family ? In-Reply-To: <411CBAF6.3010101@univ-savoie.fr> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at nez-perce with ID 411CBF55.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 411CBF14.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Loop: caml-list@inria.fr X-Spam: no; 0.00; pons:01 pons:01 etu:99 raffalli:01 hashtbl:01 caml's:01 mlton:01 mlton:01 source-code:01 fernandez:01 fernandez:01 christophe:01 -bit:01 garbage:01 garbage:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Bonjour, On Fri, 13 Aug 2004, Christophe Raffalli wrote: > The cost of conservative GC is the test to know if an int is > pointing in (or at the beginning) of an allocated block which > require for instance a hashtbl of allocated blocks by adress ranges. > I don't know if the gain for arithmetic + easier C interface would > compensate the lost in the GC for a real GC like Caml's. How does the GC of mlton work ? If I understood correctly mlton does have 32-bit integers so if it has a mark-and-copy family garbage collector, its tags are kept apart. ML-Kit has a region garbage collector. It collects static information by analyzing the source-code at compile time but it is not enough so it is combined with an other kind of 'dynamically computed' collection (also by regions if I understood correctly the simple explanations of the user manual) Maybe could you find more information (or at least their filling) on the subject ? (C interface, performances, etc.) Diego Olivier ------------------- 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 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 PAA12016; Fri, 13 Aug 2004 15:24:31 +0200 (MET DST) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA13165 for ; Fri, 13 Aug 2004 15:24:30 +0200 (MET DST) Received: from eris.rz.uni-saarland.de (eris.rz.uni-saarland.de [134.96.7.8]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i7DDOTRM026794 for ; Fri, 13 Aug 2004 15:24:29 +0200 Received: from cs.uni-sb.de (cs.uni-sb.de [134.96.254.254]) by eris.rz.uni-saarland.de (SGI-8.12.5/8.12.10) with ESMTP id i7DDORCS12182134 for ; Fri, 13 Aug 2004 15:24:28 +0200 (CST) Received: from mail.cs.uni-sb.de (mail.cs.uni-sb.de [134.96.254.200]) by cs.uni-sb.de (8.13.1/2004080400) with ESMTP id i7DDORYP027657 for ; Fri, 13 Aug 2004 15:24:27 +0200 (CEST) Received: from ps.uni-sb.de (grizzly.ps.uni-sb.de [134.96.186.68]) by mail.cs.uni-sb.de (8.13.1/2004080200) with ESMTP id i7DDOQBJ011667 for ; Fri, 13 Aug 2004 15:24:26 +0200 (CEST) X-Authentication-Warning: email: Host grizzly.ps.uni-sb.de [134.96.186.68] claimed to be ps.uni-sb.de Received: from ps.uni-sb.de (groove.ps.uni-sb.de [134.96.186.172]) by ps.uni-sb.de (8.12.10/8.12.10) with ESMTP id i7DDOP9x006327; Fri, 13 Aug 2004 15:24:25 +0200 Message-ID: <411CC109.6050105@ps.uni-sb.de> Date: Fri, 13 Aug 2004 15:24:25 +0200 From: Andreas Rossberg User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.4.1) Gecko/20031114 X-Accept-Language: en-us, en MIME-Version: 1.0 To: caml-list@inria.fr Subject: Re: AW: [Caml-list] The tag bit References: <20040813.125329.74721093.garrigue@kurims.kyoto-u.ac.jp> <411CBAF6.3010101@univ-savoie.fr> In-Reply-To: <411CBAF6.3010101@univ-savoie.fr> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-1.5.1 (eris.rz.uni-saarland.de [134.96.7.8]); Fri, 13 Aug 2004 15:24:28 +0200 (CEST) X-AntiVirus: checked by AntiVir Milter 1.0.6; AVE 6.27.0.4; VDF 6.27.0.9 X-Miltered: at concorde with ID 411CC10D.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; rossberg:01 rossberg:01 uni-sb:01 caml-list:01 raffalli:01 pointers:01 inherently:01 incompatible:01 compacting:01 generational:01 uni-sb:01 christophe:01 tagged:01 ocaml:01 afaik:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Christophe Raffalli wrote: > There is a less costly way to avoid the tag bit in integer: > "conservative GC": any int which happens to point in an alloccated block > (or only at the beginning if you do not consider C but ML) is considered > as a pointer. You will have very few wrong pointers (especially in the > second case). Moreover, array of int or float, or block of memory can be > tagged with a flag saying they do not old pointer. > > The Boehm GC for C and C++ is very succefull to do that and very often > allow you to share data-structure in C as you would in ML (not caring > about who will release first the data) and gain both speed and memory. AFAIK, a conservative collector is not allowed to move anything. Hence it is inherently incompatible with compacting and generational GC, like used in OCaml (and highly desirable). Cheers, - Andreas -- Andreas Rossberg, rossberg@ps.uni-sb.de Let's get rid of those possible thingies! -- TB ------------------- 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 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 PAA14162; Fri, 13 Aug 2004 15:43:25 +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 PAA13700 for ; Fri, 13 Aug 2004 15:43:23 +0200 (MET DST) Received: from petasus.isw.intel.com (petasus.isw.intel.com [192.55.37.196]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i7DDhLmL017129 for ; Fri, 13 Aug 2004 15:43:22 +0200 Received: from swsmsxvs01.isw.intel.com (swsmsxvs01.isw.intel.com [172.28.130.22]) by petasus.isw.intel.com (8.12.9-20030918-01/8.12.9/d: small-solo.mc,v 1.9 2004/01/09 01:01:53 root Exp $) with SMTP id i7DDhDNf028327; Fri, 13 Aug 2004 13:43:22 GMT Received: from swsmsx331.ger.corp.intel.com ([172.28.130.50]) by swsmsxvs01.isw.intel.com (SAVSMTP 3.1.2.35) with SMTP id M2004081314431712150 ; Fri, 13 Aug 2004 14:43:17 +0100 Received: from swsmsx402.ger.corp.intel.com ([172.28.130.26]) by swsmsx331.ger.corp.intel.com with Microsoft SMTPSVC(5.0.2195.6713); Fri, 13 Aug 2004 14:43:16 +0100 X-MimeOLE: Produced By Microsoft Exchange V6.0.6487.1 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Subject: RE: AW: [Caml-list] The tag bit Date: Fri, 13 Aug 2004 14:43:15 +0100 Message-ID: <78B55F0E8771CC4B8F6995AB83AF6552051138E5@swsmsx402.ger.corp.intel.com> Thread-Topic: AW: [Caml-list] The tag bit Thread-Index: AcSBNg8c/9EYiywhTVm0APAlP94S3AABDzSQ From: "Ennals, Robert" To: "Christophe Raffalli" , X-OriginalArrivalTime: 13 Aug 2004 13:43:16.0297 (UTC) FILETIME=[7C608390:01C4813B] X-Miltered: at nez-perce with ID 411CC57A.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 incompatible:01 buffer:01 pointers:01 pointers:01 tagging:01 owner-caml-:01 raffalli:01 2004:99 jacques:01 bauer:01 caml-list:01 hashtbl:01 caml's:01 raffalli:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Unfortunately, conservative GC is incompatible with copying collection = (which I believe is what O'Caml uses - though I may be wrong). With a copying collector, data is allocated sequentially in a nursery = buffer, and the collector periodically moves the reachable data to a new = area area of memory, fixing up all pointers to point to new locations. The advantage of this approach is that allocation on the heap is very = cheap - just return the current position of the heap pointer, and = increment it by the object size. The downside is that one must know for certain whether or not an object = is a pointer - as pointers will be changed when the data they point to = is moved. Regarding the block-based approach: as others have mentioned - this = approach is entirely practical, and is indeed the approach taken by = several other compiler implementations (including GHC), however = anecdotal evidence suggests that the bit tagging approach makes GC = faster. > -----Original Message----- > From: owner-caml-list@pauillac.inria.fr [mailto:owner-caml- > list@pauillac.inria.fr] On Behalf Of Christophe Raffalli > Sent: 13 August 2004 13:59 > To: Jacques Garrigue > Cc: Christoph.Bauer@lms-gmbh.de; caml-list@inria.fr > Subject: Re: AW: [Caml-list] The tag bit >=20 > There is a less costly way to avoid the tag bit in integer: > "conservative GC": any int which happens to point in an alloccated = block > (or only at the beginning if you do not consider C but ML) is = considered > as a pointer. You will have very few wrong pointers (especially in the > second case). Moreover, array of int or float, or block of memory can = be > tagged with a flag saying they do not old pointer. >=20 > The Boehm GC for C and C++ is very succefull to do that and very often > allow you to share data-structure in C as you would in ML (not caring > about who will release first the data) and gain both speed and memory. >=20 > Does anyone have a comparison between two identical GC except one > should have a tag bit and the other be conservative ? >=20 > The cost of conservative GC is the test to know if an int is pointing = in > (or at the beginning) of an allocated block which require for instance = a > hashtbl of allocated blocks by adress ranges. I don't know if the gain > for arithmetic + easier C interface would compensate the lost in the = GC > for a real GC like Caml's. >=20 >=20 > -- > Christophe Raffalli > Universit=E9 de Savoie > Batiment Le Chablais, bureau 21 > 73376 Le Bourget-du-Lac Cedex >=20 > t=E9l: (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 > --------------------------------------------- >=20 > ------------------- > 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 ------------------- 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 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 QAA14973; Fri, 13 Aug 2004 16:28:31 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA15694 for ; Fri, 13 Aug 2004 16:28:30 +0200 (MET DST) Received: from smtp3.adl2.internode.on.net (smtp3.adl2.internode.on.net [203.16.214.203]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i7DESORM001966 for ; Fri, 13 Aug 2004 16:28:28 +0200 Received: from [192.168.1.200] (ppp197-3.lns1.syd2.internode.on.net [203.122.197.3]) by smtp3.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id i7DESDHY087783; Fri, 13 Aug 2004 23:58:15 +0930 (CST) Subject: Re: AW: [Caml-list] The tag bit From: skaller Reply-To: skaller@users.sourceforge.net To: Christophe Raffalli Cc: Jacques Garrigue , Christoph.Bauer@lms-gmbh.de, caml-list In-Reply-To: <411CBAF6.3010101@univ-savoie.fr> References: <20040813.125329.74721093.garrigue@kurims.kyoto-u.ac.jp> <411CBAF6.3010101@univ-savoie.fr> Content-Type: text/plain Message-Id: <1092407293.29139.219.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 14 Aug 2004 00:28:13 +1000 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 411CD008.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 sourceforge:01 2004:99 raffalli:01 encodings:01 generational:01 9660:01 glebe:01 christophe:01 ocaml:01 ocaml:01 nsw:01 snail:02 collector:02 collector:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Fri, 2004-08-13 at 22:58, Christophe Raffalli wrote: > Does anyone have a comparison between two identical GC except one > should have a tag bit and the other be conservative ? The Boehm collector is quite efficient: if you compare it to hand written encodings such as reference counting for example. The main problem with it is that it has to 'stop the world' whilst it is doing its thing, and so isn't useful for real time applications such as a game where you can easily pay 20% of all CPU for the GC -- but you simply can't freeze up the game for 10 seconds every few minutes. The Ocaml generational collector is likely to be much better at this -- some of the workload is spread over time, and the remaining major collection when needed will also be faster, and can be called manually at appropriate points. A second point is -- Boehm cannot defragment memory. Ocaml can (although the compaction is 'world stop'). So .. i don't think the 'overall CPU use' of the two collector kinds is actually what you need to compare: the real time performance and/or ability to operate with C/C++ code are the likely issues. -- John Skaller, mailto:skaller@users.sf.net voice: 061-2-9660-0850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net ------------------- 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 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 QAA13234; Fri, 13 Aug 2004 16:32:54 +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 QAA15504 for ; Fri, 13 Aug 2004 16:32:53 +0200 (MET DST) Received: from tkb.mpl.com ([66.109.164.210]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i7DEWpmL022632 for ; Fri, 13 Aug 2004 16:32:52 +0200 Received: from tkb.mpl.com (tkb.mpl.com [66.109.164.210]) by tkb.mpl.com (8.12.11/8.12.11) with ESMTP id i7DEWnth079645; Fri, 13 Aug 2004 10:32:50 -0400 (EDT) (envelope-from tkb@tkb.mpl.com) From: "T. Kurt Bond" MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <16668.53521.633388.479965@tkb.mpl.com> Date: Fri, 13 Aug 2004 10:32:49 -0400 To: Andreas Rossberg Cc: caml-list@inria.fr Subject: Re: AW: [Caml-list] The tag bit In-Reply-To: <411CC109.6050105@ps.uni-sb.de> References: <20040813.125329.74721093.garrigue@kurims.kyoto-u.ac.jp> <411CBAF6.3010101@univ-savoie.fr> <411CC109.6050105@ps.uni-sb.de> X-Mailer: VM 7.18 under Emacs 21.3.1 X-Miltered: at nez-perce with ID 411CD113.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 rossberg:01 inherently:01 incompatible:01 compacting:01 generational:01 compacting:01 1989:99 bdw:99 pietro:01 customisable:99 compiler:01 ocaml:01 garbage:01 garbage:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Andreas Rossberg writes: > AFAIK, a conservative collector is not allowed to move anything. Hence > it is inherently incompatible with compacting and generational GC, like > used in OCaml (and highly desirable). Joel F. Bartlett's 1988 paper "Compacting garbage collection with ambiguous roots" describes a conservative "mostly copying" compacting GC scheme; his 1989 paper "Mostly-Copying Garbage Collection Picks Up Generations and C++" descibes a generation variation. Frederick Smith and Greg Morrisett's 1997 paper "Mostly-Copying Collection: A Viable Alternative to Conservative Mark-Sweep" describes an improved variant that they compared with the BDW by using both with the TIL/C ML compiler. Giuseppe Attardi, Tito Flagella, and Pietro Iglio describe a GC in their 1998 paper "A Customisable Memory Management Framework for C++" that uses mostly copying GC for the default heap. -- T. Kurt Bond, tkb@tkb.mpl.com ------------------- 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 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 QAA15049; Fri, 13 Aug 2004 16:41:30 +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 QAA16390 for ; Fri, 13 Aug 2004 16:41:29 +0200 (MET DST) Received: from tkb.mpl.com ([66.109.164.210]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i7DEfSmL023603 for ; Fri, 13 Aug 2004 16:41:28 +0200 Received: from tkb.mpl.com (tkb.mpl.com [66.109.164.210]) by tkb.mpl.com (8.12.11/8.12.11) with ESMTP id i7DEfQks079670; Fri, 13 Aug 2004 10:41:27 -0400 (EDT) (envelope-from tkb@tkb.mpl.com) From: "T. Kurt Bond" MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <16668.54038.680668.895858@tkb.mpl.com> Date: Fri, 13 Aug 2004 10:41:26 -0400 To: caml-list@inria.fr Cc: "T. Kurt Bond" Subject: Re: AW: [Caml-list] Conservative GC In-Reply-To: <16668.53521.633388.479965@tkb.mpl.com> References: <20040813.125329.74721093.garrigue@kurims.kyoto-u.ac.jp> <411CBAF6.3010101@univ-savoie.fr> <411CC109.6050105@ps.uni-sb.de> <16668.53521.633388.479965@tkb.mpl.com> X-Mailer: VM 7.18 under Emacs 21.3.1 X-Miltered: at nez-perce with ID 411CD318.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 bdw:99 drscheme:01 bdw:99 folks:01 discarded:02 drawback:03 scheme:03 tkb:04 tkb:04 source:07 problem:07 problem:07 difficult:07 occasionally:07 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Conservative GC has the drawback that there *are* pathological cases where the GC, because of its conservatism, retains memory that could actually be discarded. If I remember correctly, the PLT Scheme folks, who use the BDW conservative gc, apparently ran into this with the web server that is distributed with DrScheme, and I've seen mention of other programs that use the BDW gc occasionally running into this problem. In these cases it is often possible to tune the program to eliminate the pathological case, but it's often difficult to figure out the source of the problem. Accurate (that is, non-conservative) gc, of course, does not have this problem. -- T. Kurt Bond, tkb@tkb.mpl.com ------------------- 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 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 QAA16123; Fri, 13 Aug 2004 16:58:37 +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 QAA16465 for ; Fri, 13 Aug 2004 16:58:36 +0200 (MET DST) Received: from petasus.isw.intel.com (petasus.isw.intel.com [192.55.37.196]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i7DEwYmL025660 for ; Fri, 13 Aug 2004 16:58:35 +0200 Received: from swsmsxvs01.isw.intel.com (swsmsxvs01.isw.intel.com [172.28.130.22]) by petasus.isw.intel.com (8.12.9-20030918-01/8.12.9/d: small-solo.mc,v 1.9 2004/01/09 01:01:53 root Exp $) with SMTP id i7DEw8Nd001460; Fri, 13 Aug 2004 14:58:34 GMT Received: from swsmsx331.ger.corp.intel.com ([172.28.130.50]) by swsmsxvs01.isw.intel.com (SAVSMTP 3.1.2.35) with SMTP id M2004081315583014208 ; Fri, 13 Aug 2004 15:58:32 +0100 Received: from swsmsx402.ger.corp.intel.com ([172.28.130.26]) by swsmsx331.ger.corp.intel.com with Microsoft SMTPSVC(5.0.2195.6713); Fri, 13 Aug 2004 15:58:31 +0100 X-MimeOLE: Produced By Microsoft Exchange V6.0.6487.1 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Subject: RE: AW: [Caml-list] The tag bit Date: Fri, 13 Aug 2004 15:58:30 +0100 Message-ID: <78B55F0E8771CC4B8F6995AB83AF655205113A32@swsmsx402.ger.corp.intel.com> Thread-Topic: AW: [Caml-list] The tag bit Thread-Index: AcSBQue39S6w5soVQEGP3YIO466TWQAAjv9Q From: "Ennals, Robert" To: "T. Kurt Bond" , X-OriginalArrivalTime: 13 Aug 2004 14:58:31.0317 (UTC) FILETIME=[FF89E450:01C48145] X-Miltered: at nez-perce with ID 411CD71A.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 pointers:01 pointers:01 rubbish:01 owner-caml-:01 2004:99 rossberg:01 caml-list:01 rossberg:01 inherently:01 incompatible:01 compacting:01 generational:01 compacting:01 1989:99 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Do mostly copying collectors actually solve the problem Andreas was discussing? My impression was that mostly copying collectors are only really useful when the vast majority of pointers are tagged. If all pointers into a block are tagged, then the block is copied (just as it would be in a copying collector); however if there are some ambiguous pointers into a block (e.g. from within some C code you have linked to) then that block is "pinned" into position, and must remain pinned until there are no ambiguous pointers into it. Thus, my impression was the mostly copying collection is great if one has a language that uses tagged pointers, but wishes it to share GC-ed objects with a language that doesn't understand tags, but that it wouldn't really buy you anything in a situation where nothing was tagged (which is what I think people were proposing). Of course, I may be talking complete rubbish here - this isn't really my field. Please feel free to tell me that I've completely misunderstood everything. -Rob > -----Original Message----- > From: owner-caml-list@pauillac.inria.fr [mailto:owner-caml- > list@pauillac.inria.fr] On Behalf Of T. Kurt Bond > Sent: 13 August 2004 15:33 > To: Andreas Rossberg > Cc: caml-list@inria.fr > Subject: Re: AW: [Caml-list] The tag bit >=20 > Andreas Rossberg writes: > > AFAIK, a conservative collector is not allowed to move anything. Hence > > it is inherently incompatible with compacting and generational GC, like > > used in OCaml (and highly desirable). >=20 > Joel F. Bartlett's 1988 paper "Compacting garbage collection with > ambiguous roots" describes a conservative "mostly copying" compacting > GC scheme; his 1989 paper "Mostly-Copying Garbage Collection Picks Up > Generations and C++" descibes a generation variation. Frederick Smith > and Greg Morrisett's 1997 paper "Mostly-Copying Collection: A Viable > Alternative to Conservative Mark-Sweep" describes an improved variant > that they compared with the BDW by using both with the TIL/C ML > compiler. Giuseppe Attardi, Tito Flagella, and Pietro Iglio describe > a GC in their 1998 paper "A Customisable Memory Management Framework > for C++" that uses mostly copying GC for the default heap. >=20 > -- > T. Kurt Bond, tkb@tkb.mpl.com >=20 > ------------------- > 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 ------------------- 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 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 RAA18437; Fri, 13 Aug 2004 17:32:50 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA17039 for ; Fri, 13 Aug 2004 17:32:49 +0200 (MET DST) Received: from herd.plethora.net (herd.plethora.net [205.166.146.1]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i7DFWmRM010119 for ; Fri, 13 Aug 2004 17:32:48 +0200 Received: from bhurt.plethora.net (bhurt.plethora.net [205.166.146.49]) by herd.plethora.net (8.11.6/8.10.1) with ESMTP id i7DFWKJ12358; Fri, 13 Aug 2004 10:32:21 -0500 (CDT) Date: Fri, 13 Aug 2004 10:40:09 -0500 (CDT) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: Christophe Raffalli cc: Jacques Garrigue , , Subject: Re: AW: [Caml-list] The tag bit In-Reply-To: <411CBAF6.3010101@univ-savoie.fr> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at concorde with ID 411CDF20.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 raffalli:01 pointers:01 ocaml's:01 allocating:01 slower:01 allocating:01 christophe:01 tagged:01 ocaml:01 ocaml:01 garbage:01 garbage:01 int:01 int:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Fri, 13 Aug 2004, Christophe Raffalli wrote: > There is a less costly way to avoid the tag bit in integer: > "conservative GC": any int which happens to point in an alloccated block > (or only at the beginning if you do not consider C but ML) is considered > as a pointer. You will have very few wrong pointers (especially in the > second case). Moreover, array of int or float, or block of memory can be > tagged with a flag saying they do not old pointer. > > The Boehm GC for C and C++ is very succefull to do that and very often > allow you to share data-structure in C as you would in ML (not caring > about who will release first the data) and gain both speed and memory. This works well for languages like C/C++, where allocation is (compartively) rare. Ocaml programs allocate like crazy (most of the stuff they allocate becomes garbage almost immediately, which is why they don't take 300 terabytes of ram to run). Cost of allocation is a very important number to Ocaml's performance. The problem with Boehm-style conservative GC is that you can't do copying collection with it. You're not *sure* if that word is an integer or a pointer, so you can't change it to move the object it's pointing to- you might be changing an integer, with catastrophic consequences for the program. With copying garbage collection, allocation is very, very fast. Ocaml, on the x86, takes five simple instructions to allocate a block of memory (if you don't kick off a garbage collection). So a high allocation rate isn't a big problem. But this only works because Ocaml keeps the heap compact by moving objects around. So allocating on the heap is not much slower than allocating on the stack- you just bump a pointer. If you can't move objects around, the heap becomes fragmented- free and used blocks mixed together. And you end up searching the heap for a free space when you want to allocate. This isn't a problem if allocation is rare, but it's deadly for Ocaml. -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian ------------------- 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 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 RAA14384; Fri, 13 Aug 2004 17:44:29 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA19439 for ; Fri, 13 Aug 2004 17:44:27 +0200 (MET DST) Received: from smtp.cegetel.net (mf01.sitadelle.com [212.94.174.78]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i7DFiQRM011641 for ; Fri, 13 Aug 2004 17:44:27 +0200 Received: from univ-savoie.fr (unknown [80.125.77.158]) by smtp.cegetel.net (Postfix) with ESMTP id 193D63796E; Fri, 13 Aug 2004 17:44:23 +0200 (CEST) Message-ID: <411CE1D1.8070304@univ-savoie.fr> Date: Fri, 13 Aug 2004 17:44:17 +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: skaller@users.sourceforge.net Cc: Jacques Garrigue , Christoph.Bauer@lms-gmbh.de, caml-list Subject: Re: AW: [Caml-list] The tag bit References: <20040813.125329.74721093.garrigue@kurims.kyoto-u.ac.jp> <411CBAF6.3010101@univ-savoie.fr> <1092407293.29139.219.camel@pelican.wigram> In-Reply-To: <1092407293.29139.219.camel@pelican.wigram> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit X-Miltered: at concorde with ID 411CE1DA.002 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 2004:99 encodings:01 generational:01 savoie:01 chablais:01 73376:01 univ-savoie:01 lama:01 enigmail:01 mutt:01 christophe:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk skaller wrote: > On Fri, 2004-08-13 at 22:58, Christophe Raffalli wrote: > > >>Does anyone have a comparison between two identical GC except one >>should have a tag bit and the other be conservative ? > > > The Boehm collector is quite efficient: if you compare it > to hand written encodings such as reference counting > for example. > > The main problem with it is that it has to 'stop the world' > whilst it is doing its thing, and so isn't useful for > real time applications such as a game where you can easily > pay 20% of all CPU for the GC -- but you simply can't freeze > up the game for 10 seconds every few minutes. > > The Ocaml generational collector is likely to be much better > at this -- some of the workload is spread over time, and > the remaining major collection when needed will also be > faster, and can be called manually at appropriate points. > > A second point is -- Boehm cannot defragment memory. > Ocaml can (although the compaction is 'world stop'). > > So .. i don't think the 'overall CPU use' of the two collector > kinds is actually what you need to compare: the real time > performance and/or ability to operate with C/C++ code > are the likely issues. > > It is not true, on some configuration (including intel I think) Boehm's GC can be incremental. At least the documentation say so. -- 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 --------------------------------------------- ------------------- 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 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 SAA20919; Fri, 13 Aug 2004 18:15:25 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA20776 for ; Fri, 13 Aug 2004 18:15:24 +0200 (MET DST) Received: from will.iki.fi (will.iki.fi [217.169.64.20]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i7DGFNRM015407 for ; Fri, 13 Aug 2004 18:15:23 +0200 Received: from [10.129.39.131] (b212-54-23-216.elisa-laajakaista.fi [212.54.23.216]) by will.iki.fi (Postfix) with ESMTP id 7A82E3E; Fri, 13 Aug 2004 19:17:34 +0300 (EEST) Message-ID: <411CE8FD.6020101@exomi.com> Date: Fri, 13 Aug 2004 19:14:53 +0300 From: Ville-Pertti Keinonen User-Agent: Mozilla Thunderbird 0.7.1 (X11/20040708) X-Accept-Language: en-us, en MIME-Version: 1.0 To: "T. Kurt Bond" Cc: Andreas Rossberg , caml-list@inria.fr Subject: Re: AW: [Caml-list] The tag bit References: <20040813.125329.74721093.garrigue@kurims.kyoto-u.ac.jp> <411CBAF6.3010101@univ-savoie.fr> <411CC109.6050105@ps.uni-sb.de> <16668.53521.633388.479965@tkb.mpl.com> In-Reply-To: <16668.53521.633388.479965@tkb.mpl.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 411CE91B.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 compacting:01 compacting:01 1989:99 bdw:99 pietro:01 customisable:99 generational:01 pointers:01 implemented:01 thesis:01 ocaml's:01 pointers:01 ocaml's:01 compiler:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk T. Kurt Bond wrote: >Joel F. Bartlett's 1988 paper "Compacting garbage collection with >ambiguous roots" describes a conservative "mostly copying" compacting >GC scheme; his 1989 paper "Mostly-Copying Garbage Collection Picks Up >Generations and C++" descibes a generation variation. Frederick Smith >and Greg Morrisett's 1997 paper "Mostly-Copying Collection: A Viable >Alternative to Conservative Mark-Sweep" describes an improved variant >that they compared with the BDW by using both with the TIL/C ML >compiler. Giuseppe Attardi, Tito Flagella, and Pietro Iglio describe >a GC in their 1998 paper "A Customisable Memory Management Framework >for C++" that uses mostly copying GC for the default heap. > > Don't forget G. May Yip's "Incremental, generational mostly-copying garbage collection in uncooperative environments". :) Obviously, all of these variations are subject to the problem mentioned by others - movable pointers must be tagged or otherwise identifiable. I've implemented a variation of the algorithm described in G. May Yip's thesis - it works nicely, but my impression of the technique is that it inevitably has far more processing overhead than OCaml's collector (even without the incremental aspect). However, it may be worthwile for some applications (incremental, supports a mixed environment of arbitrary C/C++ code that may refer to the heap of another language that does tag (non-)pointers). The thing with garbage collection is that while it's often obviously a good solution, for some specific requirements no garbage collector seems "quite right", and you have to either give up on the idea of garbage collection or use a massively customized algorithm. OCaml's collector is impressive - it's not (properly) incremental or real-time, but fast, precise, compacting and very good for a lot of practical purposes. From Xavier's papers, we can see that quite a bit of testing and tuning has gone into it. ------------------- 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