GC mark stack

[Lynn Winebarger]

I was reviewing alloc.c in the 28.1 source, and noted that it uses a
semi-naive computation of the transitive closure of the graph of live
data structures (weak hash tables is where I see it).
Since the fix to https://debbugs.gnu.org/cgi/bugreport.cgi?bug=54698
(commit 7a8798de95a57c8ff85f070075e0a0176b458578) moved to using an
explicit stack, I was curious if you'd considered using a variant of
Tarjan's SCC algorithm, such as the one described in
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.9019&rep=rep1&type=pdf
,
to guarantee that each edge is traversed at most once.  The algorithm
described never removes traversed objects from its stack (so it can
tell when an object has already been traversed, even if the current
link into it is not part of its SCC).
The algorithm would only need to account for objects like weak hash
tables, so a direct implementation would only leave those on the
stack.  An alternative would be to create an additional field in the
objects (like weak hash table) recording the order in which they were
traversed, which also makes the algorithm more efficient since there's
no stack search involved when determining the SCC representative of
particular node - it's just a matter of comparing their stack
ordering.
Of course, I don't have any idea how much time is spent on this type
of recursion for weak references.  The SCC-based algorithms can make a
significant performance improvement compared to semi-naive calculation
of transitive closure for general relational queries.  It might not be
so useful when you don't require an explicit enumeration of the set of
answers.

Lynn