Fundamentals of garbage collection (2023) • Hacker News Board

Re: Fundamentals of garbage collection (2023)

#31

Post by rurban » Sun, Jul 13, 2025, 7:30 AM UTC

BlimpSpike wrote: post #3

Kindof unrelated to the article, but I was recently wondering if it would be possible to detect and deny pointer cycles in a language in an efficient way, so that you could then use simple reference counting instead of full-blown garbage collection. It probably wouldn't be usable for a general-purpose programming language, but for a special-purpose scripting language I could see it making the language implementation…

reference counting is never simple. It blows up the data size, and it costs twice for each setter.

Re: Fundamentals of garbage collection (2023)

#32

Post by kazinator » Sun, Jul 13, 2025, 7:37 AM UTC

BlimpSpike wrote: post #3

Kindof unrelated to the article, but I was recently wondering if it would be possible to detect and deny pointer cycles in a language in an efficient way, so that you could then use simple reference counting instead of full-blown garbage collection. It probably wouldn't be usable for a general-purpose programming language, but for a special-purpose scripting language I could see it making the language implementation…

Lexical closures easily give rise to cycles, without the program doing any imperative pointer swizzling to make a cycle explicitly.

For instance, a named lexical function can have itself in scope so that it can call itself recursively. This means that, as an object, it has a pointer to an environment, and that environment has an entry which contains that function itself: cycle.

If you deny cycles, that blows up at the starting line.

Re: Fundamentals of garbage collection (2023)

#33

Post by sfink » Mon, Jul 14, 2025, 4:45 PM UTC

andreamonaco wrote: post #20

zozbot234 wrote: post #16

Earlier quoted context omitted.

A somewhat different approach was recently proposed here: https://news.ycombinator.com/item?id=44319427 but it seems to have non-trivial overhead. (Still very much worthwhile, given the potential advantages of deterministic cycle collection.) The paper you reference is quite a bit older so it would of course be interesting to do a proper comparison.

I'll look at that. About performance: people in practice have always favored GC, so I think there's a lot to be discovered in optimization of reference counting algorithms, including concurrent traversal (which is easier because each node has local info in the form of refcounts and flags) and maybe detection of problematic worse-case graphs

Naive ref counting (RC) and tracing GC are very different, but they start looking more and more similar the more you optimize them. Adding cycle collection to RC means adding some tracing. Adding deferred/batched destruction to RC is similar to making a tracing GC incremental. Saturated ref counts (or otherwise avoiding updates) are similar to creating an older generation in a tracing GC. Barriers in a tracing GC (for incremental/generational/concurrent collection) are similar to the ref count updates when mutating RC objects. RC cycle collection time is heavily determined by how much of the graph is traced through from "suspected" roots, so it can be optimized by tracing known-live stuff and removing it from consideration.

But some significant performance-relevant differences remain. RC's cycle collection tends to take time proportional to the amount of dead stuff. Tracing GC tends to take time proportional to the amount of live stuff. (Both use optimizations that weaken the connection, but they still show their origins.)

Re: Fundamentals of garbage collection (2023)

#34

Post by louthy » Tue, Jul 15, 2025, 6:41 AM UTC

Findecanor wrote: post #23

louthy wrote: post #4

Earlier quoted context omitted.

On any one object you can just follow the references to see if you get back to the same object. Not super efficient as you’d have to do it for each reference as it is set. But if it was a simple scripting language and you needed that constraint, it’s relativity easy to implement.

That would still be tracing. The problem is that if there is a cycle, the reference count would be too high, and you'd not detect that the object should be reclaimed.

I was replying to the OP:

> "but I was recently wondering if it would be possible to detect and deny pointer cycles in a language in an efficient way"

...not whatever issue you are worried about.