Re: Recognising pointers during garbage collection?

"Maarten D. de Jong" <cymric73@hotmail.com> writes:


>I realise there is probably no fool-proof way of detecting whether a bit-
>pattern is a pointer or not, and that consequently there is a lot of black
>magic and heuristics involved. Can someone explain some of the more common
>techniques in uncooperative languages (like C) or cooperative ones (which
>you design yourself)?


Conservative collectors are generally only concerned with pointers that
point into the heap. The collector knows where the heap is, and which
parts of the heap have been allocated, so it can easily check whether
a pointer-sized bit pattern points into the heap. Also, if interior
pointers (pointers that point not to the start of an object, but to
some field within an object) are not allowed, the collector can check
whether the bit pattern points at the start of an object.


See also the following papers.
For conservative collection in uncooperative environments, see [1].
For (type-)accurate collection in uncooperative environments, see [2].
For (type-)accurate collection in cooperative environments, see [3] and
the references cite by [4]. For more general information about keeping
information around at runtime in order to identify the types of objects
(including whether objects are pointers or not), see [4] and the
references that it cites.


References


[1] Hans Boehm and Mark Weiser,
        "Garbage collection in an uncooperative environment".
        In Software -- Practice and Experience, volume 18, 1988, pages 807-820.


[2] Fergus Henderson,
        "Accurate garbage collection in an uncooperative environment".
        Proceedings of the 2002 International Symposium on Memory Management,
        Berlin, Germany, June 2002, pages 150-156.
        <http://www.cs.mu.oz.au/research/mercury/information/papers.html#high_level_gc>.


[3] Benjamin Goldberg,
        "Tag-Free Garbage Collection for Strongly Typed Programming Languages".
        Proceedings of the ACM SIGPLAN '91 Conference on Programming Language
        Design and Implementation, Toronto, Ontario, Canada, June 1991, pages 165-176.


[4] Tyson Dowd, Zoltan Somogyi, Fergus Henderson, Thomas Conway and David Jeffery.
        "Run time type information in Mercury".
        Proceedings of the International Conference on the Principles and
        Practice of Declarative Programming, Paris, France, September/October 1999.
        Lecture Notes in Computer Science 1702, Springer Verlag, pages 224-243.
        <http://www.cs.mu.oz.au/research/mercury/information/papers.html#rtti_ppdp>.


--
Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit
The University of Melbourne | of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.

Return to the comp.compilers page.
Search the comp.compilers archives again.