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

[Ville-Pertti Keinonen <will@exomi.com>]

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