[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: GC mark stack

From: Stefan Monnier
Subject: Re: GC mark stack
Date: Mon, 15 Aug 2022 14:17:11 -0400
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux)

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


reply via email to

[Prev in Thread] Current Thread [Next in Thread]