bug#54698: Fwd: GC mark stack

bug#54698: Fwd: GC mark stack

[Lynn Winebarger]

This bug was archived, so I first sent the below to the emacs-devel
list.  I'm not sure what the best/most appropriate target is for the
suggestion.

Lynn

---------- Forwarded message ---------
From: Lynn Winebarger <owinebar@gmail.com>
Date: Sun, Jun 26, 2022 at 11:50 AM
Subject: Re: GC mark stack
To: emacs-devel <emacs-devel@gnu.org>


On Sun, Jun 26, 2022 at 11:31 AM Lynn Winebarger <owinebar@gmail.com> wrote:
>
> 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.

I should point out here, that with only strong references, there's
only one SCC of interest (liveness) and the mark-bit is exactly the
stack-traversal-ordering count I suggested as an alternative to
keeping items on the stack as in the implementation described in the
paper.  For the more general problem of weak references, the algorithm
requires explicitly tracking the SCC candidate sets and
representatives.  Those structures can also be "pre-allocated" in the
weak reference objects if allocation during garbage collection is an
issue.

Lynn