Re: Run-time representation of classes

George Neuner wrote:


> On Mon, 02 Feb 2009 14:05:48 +0100, Michael Schuerig
> <michael@schuerig.de> wrote:
>
>>George Neuner wrote:
>>
>>> Most texts cover basic GC and creating pointer/reference maps for
>>> your
>>> structured types. That works well provided the maps are simple and
>>> fast to decode (e.g., byte or word maps rather than bits). A
>>> slightly faster, but more complex, method is to generate a
>>> customized scanning function for each type that knows where to find
>>> embedded references ... not all texts mention this method.
>>
>>Could you be a bit more specific about the texts, please? AFAIR,
>>neither the Dragon Book nor Jones/Lins, "Garbage Collection", or
>>Scott, "Programming Language Pragmatics", cover this. Surprisingly, I
>>might add.
>
> You need to re-read chapters 9,10 in Jones/Lins. *Carefully*.


Definitely, however, they are concerned with GC for C and C++, but
that's not what my question was (meant to be) about. What I didn't see
in the books I mentioned is a description of pointer/reference maps for
precise GC. The terms aren't even in the indexes. Of course, the
concept shines through in places, but there is no treatment of specific
datastructures generated by, say, a Haskell or Scheme compiler, neither
of how these structures are used by the GC.


Now, with some imagination I can fill-in the blanks, still, I'm
surprised that I have to.


[...]
> Checking my shelf ... I find:
>
> Appel's "Modern Compiler Implementation" [...]


I don't know that one, but have his "Compiling with Continuations" on my
list to read some day.


> I don't have the latest [purple] dragon book, but given how recent it
> is and its stated emphasis on compiling for more advanced languages, I
> would be very surprised if there wasn't a treatment of pointer finding
> and maps. Perhaps not an implementation, but certainly a discussion.


There's about one page (sec. 7.8.3, p. 498) on conservative GC and
scanning for pointers, but, no, there is nothing on how a precise GC
knows which words in a chunk of memory are pointers.


Again, I presume, they have left this out because they think it is
obvious. And I agree, conceptually it is obvious. Looking at the source
code of a safe language, there is no question what is a reference and
what isn't. Well, let's just assume the GC knows the same and be done
with it, there's no theoretical problem there. But then, there's no
real theoretical problem with GC: just discard those objects that
aren't referenced anymore.


Still, not knowing any better, I suspect that there's a whole lot of
interesting practical issues related to reference maps. Just three that
I can think of: What are the trade-offs among various datastructures
that might be used for the task? How do reference maps affect caching
if the GC has to access a reference map for each object it touches? How
are they organized when there are multiple translation units that are
linked together?


Michael


--
Michael Schuerig
mailto:michael@schuerig.de
http://www.schuerig.de/michael/

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