Could mutable non-GC point to GC?

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Could mutable non-GC point to GC?

Rafael Ávila de Espíndola
The manual says that non-GC cannot point to GC and that Immutable cannot
point to mutable.

Not allowing immutable not point to mutable is easy to understand as it
makes sure that immutable is really immutable and you can for example
copy it to another task.

But why do we restrict that mutable non-GC data cannot point to GC? An
optimization so that the garbage collector only has to look at the GC layer?

Cheers,
Rafael

Reply | Threaded
Open this post in threaded view
|

Could mutable non-GC point to GC?

Graydon Hoare
On 10-12-16 09:30 AM, Rafael ?vila de Esp?ndola wrote:

> But why do we restrict that mutable non-GC data cannot point to GC? An
> optimization so that the garbage collector only has to look at the GC
> layer?

To ensure that the division between GC and non-GC has meaning. The cycle
must be broken somewhere!

GC memory can point to non-GC. If non-GC could, in turn, point to GC,
then it would be possible to form a reference cycle with GC memory:
non-GC memory could wind up owning itself. Meaning: destruction order
would become non-deterministic.

I think. Possibly we the determination of non-GC-ness of mutable memory
(involving inspection of the transitive closure of its structure) could
be refined in such a way as to differentiate the two. But with the
current non-GC-ness definition ("no mutable boxes holding recursive
tags") it won't work. We'd need to ... I guess be able to prove that the
GC-memory subgraphs within a non-GC type do not permit formation of
cycles between themselves. A vector of cyclic lists is itself acyclic,
say; so long as they're not cyclic lists of vectors of cyclic lists :)

Seems potentially harder to formalize. If you're really interested in
studying the problem though, don't let me stop you! A clearer or more
precise / useful rule than the existing one is plausible.

-Graydon

Reply | Threaded
Open this post in threaded view
|

Could mutable non-GC point to GC?

Rafael Ávila de Espíndola-2
> To ensure that the division between GC and non-GC has meaning. The cycle
> must be broken somewhere!
>
> GC memory can point to non-GC. If non-GC could, in turn, point to GC,
> then it would be possible to form a reference cycle with GC memory:
> non-GC memory could wind up owning itself. Meaning: destruction order
> would become non-deterministic.

I am not sure you need something that strong. For example, lets say you
have a type B and a type C that can form a cycle with each other. If you
also have A type A that just points to B, A can point to a cycle, but
cannot be part of one.

> I think. Possibly we the determination of non-GC-ness of mutable memory
> (involving inspection of the transitive closure of its structure) could
> be refined in such a way as to differentiate the two. But with the
> current non-GC-ness definition ("no mutable boxes holding recursive
> tags") it won't work. We'd need to ... I guess be able to prove that the
> GC-memory subgraphs within a non-GC type do not permit formation of
> cycles between themselves. A vector of cyclic lists is itself acyclic,
> say; so long as they're not cyclic lists of vectors of cyclic lists :)

Yes, cases like that is what I had in mind.

> Seems potentially harder to formalize. If you're really interested in
> studying the problem though, don't let me stop you! A clearer or more
> precise / useful rule than the existing one is plausible.

Having the stronger distinction makes it easier and more efficient to
implement the GC, so I would propose not adding it unless needed.

Now, I misunderstood what the current definition is since I thought it
was the one that allowed non-GC to point to GC and you added the
restriction for some other reason :-)

What the current definition is effectively then is that a type is GC if
it can reach a cycle, correct?

> -Graydon

Thanks,
Rafael