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