RE: AW: [Caml-list] The tag bit

["Ennals, Robert" <robert.ennals@intel.com>]

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
> 
> 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

-------------------
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