34 ms·

This is a classic paper that's a must-read for anyone interested in GC. The basic idea is that not only is reference counting a form of garbage collection, ther

This is a classic paper that's a must-read for anyone interested in GC. The basic idea is that not only is reference counting a form of garbage collection, there's actually a continuum of GC approaches between pure tracing and pure reference counting. Each algorithm has its tradeoffs, and, crucially, most optimizations—for example, generational garbage collection—actually just move the scheme toward the opposite pole, acquiring some of the upsides and downsides of the other algorithm. Viewed through this lens, most of what we would consider well-optimized GCs deployed in the wild (Java HotSpot, .NET, modern JS engines, etc.) are really best viewed as hybrids of tracing and reference counting, balancing the upsides and downsides of each approach.

Mathnerd314 9y ago
> "classic" Is there anything more recent, in the same "unified" direction? I know Rust was experimenting with garbage-collected pointers but it seems like that's not really a focus anymore: https://www.rust-lang.org/en-US/faq.html#is-rust-garbage-collected https://www.rust-lang.org/en-US/faq.html#is-rust-garbage-col...
- cwzwarich 9y ago
  As far as I can tell, the only real way to take a next step beyond the imprecise informal idea in this paper would be to develop a formal calculus for describing garbage collectors that is 'polarized' in a way that tracing live objects and discovering dead objects are truly dual.
eternalban 9y ago
Respectfully disagree that GC is limited to the 1-D continuum noted. This is only the story of store model of memory management. The cache model with its various flavors of eviction policy -- LRU, LFU, etc. -- represents another dimension in the space of memory management.
zZorgz 9y ago
> 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..
- pcwalton 9y ago
  > 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.
  - zZorgz 9y ago
    > 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. I'm not sure what you're reading. I will quote: "Tracing and reference counting are uniformly viewed as being fundamentally different approaches to garbage collection that possess very distinct performance properties" 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. Further evidence that the author believes that reference counting alone is insufficient for garbage collection: "Finally, tracing collects cyclic garbage while reference counting does not. As a result, when reference counting is applied to heaps that may contain cyclic garbage, cycles must either be collected using a backup tracing collector [43] or with a trial deletion algorithm" "One of the primary disadvantages of reference counting collec- tors is that they do not find cyclic garbage. Therefore, an additional mechanism is required." Regarding "who was first", although I don't have any supporting proof, I'd be shocked if usage of manually managing reference counting hasn't predated both automatic memory management and garbage collectors, which isn't a technique constrained to, say Objective-C. Also worthy of mention, some referenced counted garbage collection implementations (e.g. CPython) vend an API for disabling the GC, which certainly has no implications on reference counting.

Mathnerd314 9y ago

> "classic" Is there anything more recent, in the same "unified" direction? I know Rust was experimenting with garbage-collected pointers but it seems like that's not really a focus anymore: https://www.rust-lang.org/en-US/faq.html#is-rust-garbage-collected https://www.rust-lang.org/en-US/faq.html#is-rust-garbage-col...

cwzwarich 9y ago
As far as I can tell, the only real way to take a next step beyond the imprecise informal idea in this paper would be to develop a formal calculus for describing garbage collectors that is 'polarized' in a way that tracing live objects and discovering dead objects are truly dual.

eternalban 9y ago

Respectfully disagree that GC is limited to the 1-D continuum noted. This is only the story of store model of memory management. The cache model with its various flavors of eviction policy -- LRU, LFU, etc. -- represents another dimension in the space of memory management.

zZorgz 9y ago

> 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..

pcwalton 9y ago
> 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.
- zZorgz 9y ago
  > 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. I'm not sure what you're reading. I will quote: "Tracing and reference counting are uniformly viewed as being fundamentally different approaches to garbage collection that possess very distinct performance properties" 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. Further evidence that the author believes that reference counting alone is insufficient for garbage collection: "Finally, tracing collects cyclic garbage while reference counting does not. As a result, when reference counting is applied to heaps that may contain cyclic garbage, cycles must either be collected using a backup tracing collector [43] or with a trial deletion algorithm" "One of the primary disadvantages of reference counting collec- tors is that they do not find cyclic garbage. Therefore, an additional mechanism is required." Regarding "who was first", although I don't have any supporting proof, I'd be shocked if usage of manually managing reference counting hasn't predated both automatic memory management and garbage collectors, which isn't a technique constrained to, say Objective-C. Also worthy of mention, some referenced counted garbage collection implementations (e.g. CPython) vend an API for disabling the GC, which certainly has no implications on reference counting.