Re: GC mark stack

[Lynn Winebarger]

On Mon, Aug 15, 2022 at 12:28 PM Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
>
> >> Are you talking about the code in `mark_and_sweep_weak_table_contents`?
> >> Maybe the `do .. while` loop?
> > That is exactly it.  Some of my characterization of the mark-sweep
> > algorithm (for non-weak references) in terms of SCC calculation was
> > incorrect - I don't really think about this day-to-day anymore.  But,
>
> This `do...while` loop can be a source of performance problems, indeed,
> if we have many/large weak hash tables (i.e. many weak references) since
> it's O(n²) for `n` weak references.
>
> AFAIK, so far this has not been a problem (I suspect in practice it's
> usually O(n) because we usually don't have many cycles between weak hash
> tables), so any improvement would need to be "cheap" (both in terms of
> code complexity and in terms of best-case CPU&heap cost).
>
> > But, you can certainly calculate the SCCs of the "weakly-references *"
> > (Kleene * operation intended) relation while recursing the entries of
> > a weak hash table in one pass
>
> I'm not sure that's the case because we don't know the full set of weak
> references right from the start (or at least, in order to know the full
> set, we'd have to traverse all the weak references before we know for
> sure that they survive).

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.  And that loop sure looks like it
is calculating the transitive closure of such a relation.
Perhaps the confusion is because any marking of
non-weak-hash-table-entries done during the calculation of the
weak-reference SCCs would only be to avoid infinite cycling, not for
marking liveness?  The only meaningful marking would be of weak hash
table entries, with the traversal order/SCC representative.
As I mentioned, I purposefully have not sat down and worked through
the details required to construct the relational expression.

Lynn