Re: Recognising pointers during garbage collection?

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


There are some great books/FAQs about Garbage collection. Also there
is a list hosted at iecc.com called gclist which might be an OK place.


As far as the relationship between compilers and garbage collection,
sometimes the compiler can provide pointer maps for all the types it
compiles (for language with GC built-in). For conservative collectors
like the "Boehm" system, everything that actually points into or at
the end of some allocated object counts as a reference to that object.
Since most memory isn't allocated in low numbers the likelyhood of
some integer value retaining some large garbage structure by accident
is "small enough" that the Boehm GC is still useful.


If you haven't been reading much about GC, you might wonder how you
can tell whether a pointer is pointing "into or at the end of some
allocated object". Well, you just have to choose a data structure
that maps the location(s) of allocated objects, and which can be
searched. I'm not sure what Boehm uses, but you could for example use
an in-memory b+tree or AVL with all allocated records in it and search
that when you encounter another word in memory. Typically you toss in
some optimisations, like checking if the pointer is less than the
smallest pointer, or more than the greatest pointer (since these are
the worst cases for b+tree and AVL search).


CU
Dobes

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