> not every AMM technique works by producing garbage then collecting it
And the confusing thing is that garbage collection (GC) doesn’t collect garbage, while reference counting (RC) does.
GC doesn’t look at every object to decide whether it’s garbage (how would it determine nothing points at it?); it collects the live objects, then discards all the non-live objects as garbage.
RC determines an object has become garbage when its reference count goes to zero, and then collects it.
That difference also is one way GC can be better than RC: if there are L live objects and G garbage objects, GC has to visit L objects, and RC G. Even if GC spends more time per object visited than RC, it still can come out faster if L « G.
That also means that GC gets faster if you give it more memory so that it runs with a smaller L/G ratio (the large difference in speed in modern memory cache hierarchies makes that not quite true, but I think it still holds, ballpark)
> Technically, reference counting is a form of garbage collection, and it is often discussed in the garbage collection literature.
This is something I always thought was true, but then I see people talk about reference counting VERSUS garbage collection, when I was taught that reference counting is a subset of garbage collection.
In other words, "garbage collection" merely refers to any method of automatic memory management that the programmer doesn't have to think about, and reference counting is merely one method of implementing garbage collecting.
Heck, Python uses reference counting, yet the library for directly interacting with the reference counter is called "gc", for "garbage collection".
> People recommend tracing garbage collection because it performs better than atomic reference counting, even though reference counting is much simpler.
Reference counting is a lot more complicated! It turns every read into a write.
> [...] if my goal is performance and predictable latency?
Reference counters don't have predictable latency: a single reference decrement can lead to an arbitrary amount of follow up work, like more decrements and deallocations.
Performance of reference counting isn't generally better than that of garbage collectors. (Especially since you still need a backup solution to deal with cycles.)
Figuring out a lot of your memory management at compile time is definitely a win. But doesn't really have much to do with reference counting.
> this meme needs to die. Garbage collection is not "super sophisticated reference counting", and in fact, can't even be used in most places where reference counting is used. It's not a substitution, or a superset, of reference counting.
I never said that garbage collection is sophisticated reference counting so if you've seen that "meme," it wasn't here. But reference counting and tracing are two classical approaches to garbage collection, the garbage collection literature does refer counting as a garbage collection algorithm, and refcounting is used for garbage collection in languages such as Rust. Refcounting has other uses, too, but this discussion is about garbage collection and not about 101 uses for refcounting.
Anyway, reference counting GC is not intrinsically more primitive or worse-performing than tracing, but in practice, tracing GCs tend to be sophisticated, while languages that rely on refcounting usually employ a rather simple algorithm. In fact, this is one of the attractions of refcounting for GC: it is easier to get OK performance with primitive refcounting than with primitive tracing.
> Perhaps the biggest misconception about reference counting is that people believe it avoids GC pauses. That's not true.
When I can easily replace the deallocator (thus excluding most non-RC production GCs), I can (re)write the code to avoid GC pauses (e.g. by amortizing deallocation, destructors, etc. over several frames - perhaps in a way that returning ownership of some type and its allocations to the type's originating thread, and thus reducing contention while I'm at it!) I have done this a few times. By "coincidence", garbage generation storms causing noticable delays are suprisingly uncommon IME.
As programs scale up and consume more memory, "live data" outscales "garbage" - clever generational optimizations aside, I'd argue the former gets expensive more quickly, and is harder to mitigate.
It's also been my experience that tracing or profiling any 'ole bog standard refcounted system to find performance problems is way more easy and straightforward than dealing with the utter vulgarity of deferred, ambiguously scheduled, likely on a different thread, frequently opaque garbage collection - as found in non-refcounted garbage collection systems.
So, at best, you're technically correct here - which, to be fair, is the best kind of correct. But in practice, I think it's no coincidence that refcounting systems tend to automatically and implicitly amortize their costs and avoid GC storms in just about every workload I've ever touched, and at bare minimum, reference counting avoids GC pauses... in the code I've written... by allowing me easier opportunities to fix them when they do occur. Indirectly causal rather than directly causal.
> if you read a heap-object out of a data structure, you have to increment the object's reference count.
This isn't universal. Merely accessing and dereferencing a shared_ptr in C++ won't touch the refcount, for example - you need to copy the shared_ptr to cause that. Rust's Arc/Rc need to be clone()d to touch the refcount, and the borrow checker reduces much of the need to do such a thing defensively, "in case the heap object is removed out from under me".
Of course, it can be a problem if you bake refcounting directly into language semantics and constantly churn refcounts for basic stack variables while failing to optimize said churn away. There's a reason why many GCed languages don't use reference counting to optimize the common "no cycles" case, after all - often, someone tried it out as an obvious and low hanging "optimization", and found it was a pessimization that made overall performance worse!
And even without being baked into the language, there are of course niches where heavy manipulation of long-term storage of references will be a thing, or cases where the garbage collected version can become lock-free in a context where such things actually matter - so I'll 100% agree with you on this:
> There are no hard lines; this is about performance tradeoffs, and always will be.
> People differ on whether or not universal reference counting is a form of garbage collection with weak guarantees or a form of manual memory manage with flexible semantics.
Which is pretty unfortunate, because the memory management field has always treated reference counting as a form of garbage collection—because it is [1] [2]. The idea that reference counting is somehow not GC is as far as I can tell a recent one (popularized, I think, by Cocoa and iOS?)
This is not just a semantic quibble, because there are successful garbage collection techniques that combine tracing with reference counting (e.g. ulterior reference counting [3]) to achieve GC, so treating tracing as the only way to do GC makes no sense. In fact, David Bacon observed in 2004 that reference counting and tracing garbage collection are best viewed as just two extremes of a continuum [4], and many "optimizations" that you apply to one scheme or the other are really just moving the scheme you choose toward the opposite pole.
> The basic idea is that not only is reference counting a form of garbage collection..
Oh, how this leads to debate. The confusion is whether having automatic reference counting without a cycle detector is considered GC by the masses (what language publicizes a GC and does this?), and if people question GC to be a form of automatic memory management, where other forms may exist.
Briefly looking at the article I think the authors opinion on this matter is pretty clear that an additional algorithm such as a cycle collector is required to be considered GC.
edit: "Reference counting" itself also isn't even necessarily 'automatic'. Just find it odd the way this gets phrased. GC can use reference counting, not the other way around..
> We don't want Garbage Collection to the contrary we want reference counting. Reference counting is the best compromise between handling memory manually and using GC ala Java. I would argue that the mental strain for the programmer is equal for reference counting(at least with ARC) to that of GC. However Reference Counting is extremely lightweight.
I used to think that, until I started to spend more time on modern GC platforms like Java and .NET. It's impressive how performant a good generational garbage collector can be. For many business applications (i.e., not the kinds of workloads you'll see being simulated by popular benchmarks) a good generational GC can even improve performance thanks to improved locality of reference. I think a lot of us don't fully appreciate the cost of a cache miss.
Speaking of, I'm not sure a lot of us fully appreciate the cost of synchronization, either. It's one big reason why I'm not convinced that reference counting is particularly well-suited to concurrent programming, since it turns a really commonplace operation (retaining a reference to an object) into a synchronization point in the program. There's a non-trivial cost associated with that. You could avoid repeatedly stalling the CPU by being very careful about not sharing objects among threads, but I don't think most developers can reasonably be expected to make a habit of that in practice.
> The problem is that "garbage collection" as a term seems to have become synonymous with "tracing GC"
The term has been used that way since I first heard it back in the '80s, so it's probably not a battle worth fighting at this point.
Yes, of course, there's a formal sense under which reference counting is just an outlying position within the broader world of garbage collection, but from an engineering point of view, it's a significantly different set of tradeoffs, and reference counting doesn't really qualify as the same thing when you're deciding how to structure your program.
> Historically, there has been two major forms of GC: reference counting, and tracing. The argument happens because, with the rise of tracing garbage collectors in many popular programming languages, for many programmers, “garbage collection” is synonymous with “tracing garbage collection.” For this reason, I’ve been coming around to the term “automatic memory management”, as it doesn’t carry this baggage.
It's fairly confusing to refer to this as automatic memory management. That term already exists to refer to stack variables getting allocated and initialized in C/C++.
> reference counting will always use more ram because a reference count must be stored
True, reference counting stores references… but garbage collection stores garbage, which is typically bigger than references :)
(Unless you’re thinking of a language where the GC gets run after every instruction - but I’m not aware of any that do that, all the ones I know of run periodically which gives garbage time to build up)
> Saying reference counting is an approach that garbage collection can use is certainly valid, but is not the same as saying that reference counting is a form of garbage collection, which is nonsensical usage IMO.
You're drawing distinctions in the paper that the author almost certainly did not intend. "An approach to garbage collection" means "a form of garbage collection". If Bacon had meant to write "an approach that garbage collection can use", he would have written that.
David Bacon's opinion is that RC systems should have some mechanism to collect cycles. This is understandable, given that he did more work than anyone else to develop good cycle collectors (and his work in this area is a good read). But nobody in the GC field, including him, would claim that reference counting without cycle detection isn't garbage collection at all.
All garbage collection (automatic memory management) systems use a form of approximation to determine which objects are reachable. Some approximations involve reachability; that is what tracing GCs use. Some approximations involve tracking the number of outstanding references; that is what reference counting GCs use. A pure GC has a more fine-grained approximation than a pure reference counting one does. But both are approximations to the real problem: whether some data will dynamically be accessed by the program again. Reference counting has a less precise approximation, but that doesn't make it not a form of garbage collection.
> A pretty naive question: what is the advantage of garbage collection over just reference counting?
It's not that naive, and the unpopular answer is "not much". A good modern GC, faced with a usage paradigm that it expects (this part is important!), is almost certainly going to be faster. It's indeed safe from circular reference leaks. Generational collectors can often compact memory better and have a smaller footprint for the same data.
Those are all real advantages. But they come at the cost of outrageous complexity and code footprint. A reference counter is probably more than an 80% solution for almost any reasonable application, and it's something college kids write in 15-20 lines in their intro course.
> A GC system with explicitly visible reference counts (and immediate freeing) with language support to make it easier to get the refcounts right [...]
To be a little pedantic on the subject, such a system (reference counting and immediate freeing) is a form of automatic memory management, but it is not GC in any way. Garbage collection implies that the system leaves garbage around, which needs to be collected in some way or another. The usual approach to refcounting releases resources as soon as they are no longer required (either by free()ing immediately or by sending it to a pool of unused resources), thus doesn't leave garbage around, and doesn't need a collector thread or mechanism to.
There are partial-GC implementations of refcounting, either because items are not free()d when they reach zero references, or to automatically detect reference loops which are not handled directly.
I agree with Torvalds on this matter. GC as it is promoted today is a giant step that gives programmers one benefit, solving one problem, while introducing a immeasurable pile of complexity to the system creating another pile of problems that are still not fixed today. And to fix some of these problems (like speed) you have to introduce more complexity.
This is my problem with GC. I like simplicity. Simplicity tends to perform well, and being simple also means it has little space for problems. Refcounting is simple and elegant, you just have to take care of reference loops, which also has another simple solution, that is weak references. I can teach a class of CS students everything they need to know to design a refcounting resource management system in one lesson.
GC is the opposite: it is big, complex, and a problem that the more you try to fix it, the more complex it becomes. The original idea is simple, but nobody uses the original idea because it performs so badly. To teach the same class how to design a GC system that performs as well as we expect today, an entire semester may not be enough.
“with five times as much memory, an Appel-style generational collector with a non- copying mature space matches the performance of reachability- based explicit memory management. With only three times as much memory, the collector runs on average 17% slower than explicit memory management. However, with only twice as much memory, garbage collection degrades performance by nearly 70%. When physical memory is scarce, paging causes garbage collection to run an order of magnitude slower than explicit memory management.”
That paper is old and garbage collectors have improved, but I think there typically still is a factor of 2 to 3.
Would love to see a comparison between modern recounting and modern GC, though. Static code analysis can avoid a lot of recount updates and creation of garbage.
> Its actually usually slower than both manual memory management and GC
[citation needed]
You and the blog post are arguing opposite things, and neither of you have shown any evidence. I get that you're arguing that reference counted objects are bigger (to store the reference count) and/or might use double indirection (depending on implementation), which are both bad for caches. It's not a bad argument. But the counter-argument that the blog posts makes is persuasive as well: it's expensive running a GC that scans the heap looking for loose objects, and reference counting does not need to do that. GC is also "stop-the-world" as well unpredictable and jittery in a way reference counting is not.
My instinct is that reference counting is actually faster (which matches my personal experience), but really, this is not an argument you can solve by arguing in the abstract, you need actual data and benchmarks.
> Briefly looking at the article I think the authors opinion on this matter is pretty clear that an additional algorithm such as a cycle collector is required to be considered GC.
That is almost certainly not what David Bacon thinks. I don't know how you could get that idea from reading the introduction. Reference counting is a form of garbage collection, period.
C++, Objective-C, etc. started muddying the waters in the '90s and 2000s and got people thinking that somehow reference counting isn't GC and therefore doesn't have the downsides of automatic memory management. But the literature is clear on this point.
"It’s a common but false belief that reference counting (using shared pointers in particular) is better than garbage collection. There is actual research showing that the two approaches are just two sides of the same coin."
Yeah. But RC is at least deterministic and controllable side. Also, RC is just one of options of C++, while you can implement GC yourself in C++ without any overhead unlike any memory management method on GC.
> On the other hand reference counting is extremely slow. So slow that it puts a lot of restrictions on API design and that is definitely a mental burden.
This is very wrong on both points. Reference counting has a lot less mental burden compared to GC, because it's predictable. You can rely on destructors to actually work and be useful. For example, you don't have to keep track of whether you closed your file descriptor or not, but in GCd languages you have to do that manually, sometimes even with the same reference counting, but hand-written and explicit. Reference counting is also very fast, with the exception of concurrent decades old implementations, that are irrelevant today.
And the confusing thing is that garbage collection (GC) doesn’t collect garbage, while reference counting (RC) does.
GC doesn’t look at every object to decide whether it’s garbage (how would it determine nothing points at it?); it collects the live objects, then discards all the non-live objects as garbage.
RC determines an object has become garbage when its reference count goes to zero, and then collects it.
That difference also is one way GC can be better than RC: if there are L live objects and G garbage objects, GC has to visit L objects, and RC G. Even if GC spends more time per object visited than RC, it still can come out faster if L « G.
That also means that GC gets faster if you give it more memory so that it runs with a smaller L/G ratio (the large difference in speed in modern memory cache hierarchies makes that not quite true, but I think it still holds, ballpark)
reply