Re: GC mark stack

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

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


        Stefan