Re: GC mark stack

[Stefan Monnier <monnier@iro.umontreal.ca>]

> If the loop can be expressed by a relational expression consisting of
> a concrete relation (like "references"), composition, union, and
> transitive closure, then there is a systematic way to construct an
> algorithm of the type I described.

I think the core of the problem is the following:

In a "key weak" hash table, if a reachable object points (transitively) to
an object that is a key in that table, then the value associated with
that key becomes reachable.  So conceptually we have a reference (an
edge) from the key *object* to the value, but this reference is not
actually represented in the heap.

More specifically, the code that does the marking (i.e. `mark_object`)
only knows about the key object itself: it doesn't know that this object
is a key in a weak hash table nor what is the associated value.

We could try and reify those conceptual references, e.g. in some kind of
auxiliary table, but the added cost of making `mark_object` consult this
table for every object it marks (at least while marking weak-refs)
seems prohibitive.


        Stefan