Comment by jlouis
1 day ago
You can make a programming language where cycles are impossible. Erlang is a prime example.
Region inference is another strategy in this space. It can limit the need for full-blown garbage collection in many cases, but also comes with its own set of added trade-offs.
Reference counting is just a different kind of garbage collection, really. It acts like a dual construction to a tracing GC in many cases. If you start optimizing both, you tend to converge to the same ideas over time. Refcounting isn't void of e.g. latency problems either: if I have a long linked list and snip the last pointer, then we have to collect all of that list. That's going to take O(n) time in the size of the list. For that reason, you'd have to delay collecting the large list right away, which means you are converging toward a tracing GC that can work simultaneously with the mutator. See e.g., Go's garbage collector.
> latency problems either: if I have a long linked list and snip the last pointer, then we have to collect all of that list. That's going to take O(n) time in the size of the list. For that reason, you'd have to delay collecting the large list right away
These latency issues are inherent to deterministic destruction, which is an often desirable feature otherwise; they have little to do with reference counting itself. In principle, they can be addressed by "parking" objects for which delayed disposal is non-problematic onto a separate, lower-priority task.
> It acts like a dual construction to a tracing GC in many cases
yeah one of the most helpful realizations I’ve read is that tracing and ref counting are essentially two formulations of the same problem - one is finding objects that are alive (by tracing), and the other is finding things that are dead (i.e. their ref counts reach zero). and of course, every object is either dead or alive!
It's a useful realization but the follow on (unfortunately rather popular) claim that this inverse relation makes them the same thing is clearly wrong. They exhibit entirely different performance characteristics in places where it matters.