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