Cyclic references in garbage collection

Posted Jan 3, 2025 16:46 UTC (Fri) by epa (subscriber, #39769)
Parent article: Preventing data races with Pony

I didn’t understand how cycles are avoided in garbage collection. Surely you can have an object A in one actor which points to object B in another, and B points back to A? Granted, the objects would not be mutable, but still self-referential and creating a cycle that could not be garbage collected, even if there are no other references to these two objects.

Cyclic references in garbage collection

Posted Jan 3, 2025 17:09 UTC (Fri) by daroc (editor, #160859) [Link]

The trick is that you can create a cycle within an actor as much as you want, but you cannot send only part of a cycle to another actor unless the data is immutable, and you can't create a cycle between two actors. (With the exception of tag pointers, which are slightly magic; see below.)

So imagine that I have mutually referential objects A and B.

If I have an isolated pointer to the whole cycle, I can send the whole cycle to another actor. But A and B can't directly reference each other with isolated pointers, because then either they would immediately be garbage, or the isolated pointers wouldn't be unique.

For value pointers, the objects are immutable, so sending B to another actor doesn't cause problems — from the first actor's point of view, it just pins the cycle as a garbage collection root until the second actor is done with it.

For reference, box, and transition pointers, the objects can't be sent to another actor.

For tag pointers, the runtime pulls a little bit of magic to detect cycles at the same time it detects dead actors; you're correct that you can actually have between-actor cycles using tag pointers, and this complicates things. For the purposes of garbage collection, though, they really are just treated as collection roots, with cycles getting cleaned up by the separate system that reaps dead actors.

Cyclic references in garbage collection

Posted Jan 3, 2025 17:10 UTC (Fri) by sionescu (subscriber, #59410) [Link] (2 responses)

You can solve cross-actor referencing if each actor has its own private heap/arena and sending messages does a deep copy. That's pretty much what Erlang does.

Cyclic references in garbage collection

Posted Jan 3, 2025 17:33 UTC (Fri) by daroc (editor, #160859) [Link]

Pony's advantage over Erlang is that sending messages doesn't need a deep copy, because of the compile-time checks. So while you can make a deep copy if you want to, you don't have to if that will be detrimental to performance.

Cyclic references in garbage collection

Posted Jan 3, 2025 19:14 UTC (Fri) by kleptog (subscriber, #1183) [Link]

An interesting side effect of the Erlang approach is that in practice, most threads (actors) do not live long enough to trigger the garbage collector. When they die you can simply destroy the stack+heap of that thread since you know it's unreferenced.

Pony can't take advantage of this trick though, but their approach is novel, like a cross between Erlang and Rust.

You don't use Erlang for performance (though the JIT they're working on helps a lot), you use it because throughput scales linearly with the number of CPUs. And you can connect multiple machines into a single large cluster without changing your program.