5 ms·
I find this whole conversation frustrating or somewhat confusing because it's a weird distinction: Reference counting is garbage collecting. It's not a mark & s
by cmrdporcupine 5y ago
I find this whole conversation frustrating or somewhat confusing because it's a weird distinction: Reference counting is garbage collecting. It's not a mark & sweep or generational tracing collector, but it's a collector. And in fact it even traces, though the tracing is explicit (in the form of the declaration or management of references.)
My copy of the Jones/Lins Garbage Collection book I'm looking at on my shelf makes this quite explicit, the chapter on reference counting makes it clear it's one form of garbage collection.
When I was messing with this stuff 20 years ago, that was my understanding of it, anyways.
There are advantages and disadvantages to reference counting. I think some of the confusion in terminology and some of the frustrations (or opposite) here comes from the rather awkward way that Objective-C implements reference counting as something you have to be explicitly aware of and careful about, even with ARC. My brief stint doing iOS dev made this clear to me.
But I've used (and written) programming languages that had transparent automatic garbage collection via reference counting, and the programmer need not be aware of it at all, esp if you have cycle detection & collection (or alternatively, no cycles at all). And, there are compelling RC implementation that are capable of collecting cycles just fine (albeit through a limited local trace.)
Anyways, he's right that RC can be better for things like database handles etc. Back in the day I/we used reference counting for persistent MUDs/MOOs, where the reference counts were tracked to disk and back, 'twas nice and slick.
- melissalobos 5y ago> Reference counting is garbage collecting I am drawing a blank on google scholar at the moment, but I recall a very popular paper on exactly this topic of RC as the other side of Tracing GC.
- hayley-patton 5y ago"A unified theory of garbage collection"? https://dl.acm.org/doi/10.1145/1028976.1028982 https://dl.acm.org/doi/10.1145/1028976.1028982
- melissalobos 5y agoYes! Thank you, I couldn't think of the terms to search for to find this.
- cmrdporcupine 5y agoNice, will put this paper in my bookmarks for later read. I feel like once you stop and think about it, the distinction between a 'tracing' GC and a 'non-tracing' GC is specious: To do its work at acquire and release, RC collector must in fact trace a tree of objects. It's just that the semantics of how this is declared might differ, or, more specifically the time(s) in which it does this work.
- hayley-patton 5y agoI think a fair part of the unified theory is that a tracing GC traces live objects, whereas a refcounting GC traces dead objects.
- cmrdporcupine 5y agoUpcounts trace live objects though. Just more incrementally.
- hayley-patton 5y agoBy "trace" I mean the act of consulting the state of an object, then recursively tracing pointers in the object. A tracing GC propagates a "known to be live" state through an object graph while doing a collection cycle, and a refcounting GC propagates a "known to be dead" state through an object graph, when RC drops to zero.
- hmlongco 5y agoUmm... but isn't the refcounting GC more deterministic? If I create a chain of 10 object and then release the head, I run through 10 allocations and then 10 release cycles on those 10 objects. Period.
- hayley-patton 5y agoSome people refer to only tracing algorithms (mark-sweep, copying, etc) as "garbage collection". The best reason I can think of is marketing. There are generational reference counting systems e.g. ulterior reference counting [1] and age-oriented collection [2]. "Tracing" usually refers to scanning a heap to work out liveness all at once, which reference counting doesn't do; though deferred reference counting scans the roots to collect, and ulterior reference counting traces a nursery. Deferring these (more common) updates to reference counts improves throughput considerably. [1] https://people.cs.umass.edu/~emery/classes/cmpsci691s-fall2004/papers/ulterior-reference-counting.pdf https://people.cs.umass.edu/~emery/classes/cmpsci691s-fall20... [2] https://users.cecs.anu.edu.au/~steveb/pubs/papers/aogc-cc-2005.pdf https://users.cecs.anu.edu.au/~steveb/pubs/papers/aogc-cc-20...
- pizlonator 5y agoARC makes ref counting a part of semantics in the sense that the deref that reaches zero immediately runs the destructor, and destructors can have any effects they like. Therefore, it’s not really valid to say that ARC “is” garbage collection. Reference counting is only a form of garbage collection if it is totally transparent to the programmer, and it’s not like that in ARC.
- pjmlp 5y agoWhich is why when Apple introduced new ARC optimizations last year, they had a talk about possible gotchas that might crash the application due to them.
- SamReidHughes 5y agoYou might as well classify allocating without freeing as a form of garbage collection. If the implementation can fail to collect cycles and the language can create them, thus leaking memory, lumping in reference counting with real garbage collection is a bad definition because it smears together a crucial distinction. I get that some people, or many people, or some book, have defined it that way, but others have used it in the meaning as distinguished from plain refcounting. Many developers have always understood GC and refcounting (in languages with mutation) to be mutually exclusive concepts. That definition is used in practice, and when people say, "I'm going to implement garbage collection for my programming language," what they mean is one which doesn't leak memory. A reason people use this other definition may be that plain reference counting and "having a garbage collector" are mutually disjoint, even if you define "garbage collection" as including reference-counted implementations. Making garbage collection a distinct concept from the set of acts a garbage collector might do will always be fighting against how language usually works.
- kibwen 5y agoThey get lumped together because when some people say "garbage collection" they mean "whatever Java specifically does", and when other people say "garbage collection" they mean "automatic dynamic lifetime determination" (as a contrast to C-style "manual static lifetime determination", or Rust-style "automatic static lifetime determination").
- Kranar 5y ago>You might as well classify allocating without freeing as a form of garbage collection. Of course, Java even explicitly supports this garbage collection strategy: https://openjdk.java.net/jeps/318 https://openjdk.java.net/jeps/318 The best definition I've read comes from Raymond Chen, which is that garbage collection is a system to simulate an infinite amount of memory: https://devblogs.microsoft.com/oldnewthing/20100809-00/?p=13203 https://devblogs.microsoft.com/oldnewthing/20100809-00/?p=13... This definition is very elegant in that it allows one to reason about program correctness across all garbage collectors without having to know any of the implementation details, be it reference counting or the many flavors of mark and sweep. Basically garbage collection is not an implementation detail, nor is it a specific algorithm or even class of algorithms, garbage collection is a goal, namely the goal of achieving an infinite amount of memory. Different algorithms will reach that goal to different degrees and with different trade-offs.
- zarzavat 5y agoIn the modern sense of the word, a GC is an algorithm that manages memory automatically and without cycles. A GC must maintain the property that a leak is only possible if an object is reachable from a root. RC on its own does not obey this property. Reference counting is not GC in the modern sense unless it also includes a cycle collector. So Swift is not GC’d (RC only) yet Python is GC’d (RC+CC).
- knome 5y ago>RC on its own does not obey this property. It is sufficient in a functional language that lacks haskell's lazy capacity to "tie the knot". Erlang's data structures, for example, are fully immutable, and it is not possible to create a cyclic data structure. Since there cannot be a cyclic data structure, reference counting would be sufficient to manage its memory automatically. It would still suck since it has to constantly write to all objects being referenced, but it would work.
- cmrdporcupine 5y agoThere are RC systems where the counts are held external to the objects, which can be a bit more cache friendly.
- Kranar 5y agoYou want the opposite behavior in order to be cache friendly, an RC system where the counts are stored next to the object.
- cmrdporcupine 5y agoNot necessarily. The issue is that releasing a reference at the top of a tree of objects has the potential to walk a large graph of objects (doing downcounts at each) that are not in cache, causing some thrash. In an ideal world and in a program running with a not-huge # of objects you could keep the entire basket of reference counts in L1 cache, separate from the objects. Then decrements would be potentially cheap. A bit utopian though.
- josephg 5y ago> Reference counting is garbage collecting. I hear you, but this is just a terminology thing. I was taught that the "garbage collector" term only refers to tracing garbage collectors. It sounds weird and wrong for me to hear the term GC referring to to things like C/Zig's manual memory management (malloc and free) or Rust's borrowck. And it sounds like its the same for you, in reverse. In my school, the whole class of systems are "memory management systems" and "Garbage Collector" is one such class of approach. (What you would call tracing GCs). But I don't think either of us is canonically right. Its just a "pop" vs "soda" thing. You and Jones/Lins say "pop". Me and Chris Lattner say "soda". Its no big deal.
- mirekrusin 5y agoIt would help us all if "gc" term would be used for solutions that require dedicated thread to operate.