5 ms·
A Unified Theory of Garbage Collection (2004) [pdf]
- eru 9y agoGreat paper! Especially useful when talking to C++ fanatics who are proud of their language's de-facto reference counting via 'smart pointers'.
- todd8 9y agoPython uses reference counting with a backup garbage collector just to pick up unreachable sets of object having circular references.
- __s 9y agoPython is slow & CPython is ever slower because reference counting is part of what makes removing the GIL such a challenge
- dfox 9y agoThe hard part of removing GIL are the language semantics themselves. Replacing CPython's reference counting with some kind of tracing GC will still leave you with problem of coming up with low-overhead thread-safe dictionary implementation.
- hyperpape 9y agoI agree with the first sentence. For the second part, what are you thinking of? For reads, there's very low overhead for using an implementation like Java's ConcurrentHashMap. The overhead for insertions is more significant, but not enormous.
- johncolanduoni 9y ago> reference counting is part of what makes removing the GIL such a challenge Interesting, I would have expected that switching reference counting to atomic operations would be pretty trivial. What about CPython's design complicates this?
- gpderetta 9y agoPretty trivial. Also pretty expensive.
- jgh 9y agoOther languages use reference counting too. I don't really see how that applies to a discussion on a paper about GC. Edit: my bad, they literally mention reference counting in the first sentence. Leaving this here because I should read the link before the comments.
- hamstergene 9y agoThis is exactly why I insist on using the wording "automatic memory management" instead of "garbage collection". When you say AMM, it's clear and intuitive: it means an object's lifetime is not really under programmer's control, but is up to some automatically working algorithm/mechanism. But if you say GC to mean not tracing GC, half of audience is doomed to misunderstand you.
- pjmlp 9y agoThat is more common among those that only did C -> C++ transition, without any experience in other languages with automatic memory management, though. If you check Herb Sutter's talk about "deferred pointers", he goes to great lengths to only speak the forbidden word towards the end, to avoid loosing the audience. He also presents a few examples where RC can lead to long pauses or even stack overflow, in the presence of deeply nested data structures.
- Rexxar 9y ago<insert language> fanatics != good coders
- pcwalton 9y agoThis 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 agoAs 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 agoRespectfully 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..
- tybit 9y agoI'm curious how RAII approaches relate to this? Would it be considered a form of binary reference counting(where reference counting isn't explicitly used, i.e non shared_ptr code in C++) or it's just completely separate and not part of the dual GC theory?
- eru 9y agoAt it's basic RAII is about re-using the a hierarchy of lifetimes (induced from the hierarchy of stack frames in as strict language) for managing resources other than memory.