8 ms·

Great article, but I'm curious why automatic reference counting (ARC) and smart pointers never seemed to really catch on outside of Objective-C and Swift: http

Great article, but I'm curious why automatic reference counting (ARC) and smart pointers never seemed to really catch on outside of Objective-C and Swift: https://en.wikipedia.org/wiki/Automatic_Reference_Counting https://en.wikipedia.org/wiki/Automatic_Reference_Counting https://en.wikipedia.org/wiki/Smart_pointer https://en.wikipedia.org/wiki/Smart_pointer They almost "just work", except for circular references: https://en.wikipedia.org/wiki/Reference_count#Dealing_with_reference_cycles https://en.wikipedia.org/wiki/Reference_count#Dealing_with_r... I'd like to see some real-world studies on what percentage of unclaimed memory is taken up by orphaned circular references, because my gut feeling is that it's below 10%. So that really makes me question why so much work has gone into various garbage collection schemes, nearly all of which suffer from performance problems (or can't be made realtime due to nondetermistic collection costs). Also I can't prove it, but I think a major source of pain in garbage collection is mutability, which is exacerbated by our fascination with object-oriented programming. I'd like to see a solid comparison of garbage collection overhead between functional and imperative languages. I feel like if we put the storage overage of the reference count aside (which becomes less relevant as time goes on), then there should be some mathematical proof for how small the time cost can get with a tracing garbage collector or the cycle collection algorithm of Bacon and Paz.

munificent 7y ago
> They almost "just work", except for circular references Well, and they're often slower since they require mutating the reference count on every single time a field is stored. You can optimize that using lazy reference counting, or not updating refcounts for references on the stack and instead scanning the stack before a collection. But at that point... you're halfway to implementing a tracing collector. Every refcounting implementation eventually gets "optimized" to the point that it has most of a tracing collector hiding inside of it. I think it's simpler, cleaner, and faster to just start with tracing in the first place. There's a reason almost no widely used language implementation relies on ref-counting. CPython is the only real exception and they would switch to tracing if they could. They can't because they exposed deterministic finalization to the user which means now their GC strategy is a language "feature" that they're stuck with. That being said, ref-counting is fine for other kinds of resource management where resources are pretty coarse-grained and don't have cyclic references. For example, I think Delphi uses ref-counting to manage strings, which makes a lot of sense. Many games use ref-counting for tracking resources loaded from disc, and that also works well. In both of those cases, there's nothing to trace through, and the overhead of updating refcounts is fairly low.
- blattimwind 7y ago
  > There's a reason almost no widely used language implementation relies on ref-counting. CPython is the only real exception and they would switch to tracing if they could. They can't because they exposed deterministic finalization to the user which means now their GC strategy is a language "feature" that they're stuck with. Reference counting and address-semantics (which prohibits moving objects, so even if you work around the refcount, you can only do a tracing GC, but you don't get to compact) are deeply ingrained into CPython's C API as well, which is very widely used.
- nostrademons 7y ago
  There's a classic paper that shows that refcounting and GC are in fact duals of each other, where GC is effectively tracing live objects and refcounting is tracing dead objects: https://dl.acm.org/citation.cfm?id=1028982 https://dl.acm.org/citation.cfm?id=1028982 This had a number of important corollaries to this. One is that they have opposite performance characteristics: GCs make creating new references fast but then create a large pause when RAM is exhausted and a collection happens, while refcounts make creating new references slow and create a large pause when large object graphs are freed all at once. Another is that nearly all high-performance memory management systems are hybrids of the two: lazy refcounting is basically like implementing a local garbage collector and then feeding the live set of that into the refcounts, while generational garbage collection is like implementing a local refcount (the write barrier) and feeding the results of that into the root set.
- ridiculous_fish 7y ago
  Objective-C and then Swift are surely the most serious goes at fast widely used RC languages. Neither requires mutating the reference count on every store, and neither seems at risk of growing a tracing GC. ObjC had some elision tricks like objc_retainAutoreleasedReturnValue, but more importantly the optimizer was taught about RC manipulation. Swift then extended this with a new ABI that minimizes unnecessary mutations. The big advantages of this scheme are efficient COW collections and a simpler FFI (very important with Swift). More generally RC integrates better. Imagine teaching the JS GC to walk the Java heap!
akiselev 7y ago
What is the difference between Clang's ARC implementation and Rust's std::rc::Rc implementation? Rust's ownership system provides the scaffolding for the Drop implementation that manages reference counting instead of Clang doing it as part of the Swift/ObjC frontend but otherwise, they seem to be very similar. It's just another tool in Rust's box (no pun intended) but I wouldn't say it hasn't caught on. It's used quite often, along with its multithreaded cousin std::sync::Arc.
- ridiculous_fish 7y ago
  One difference is optimization. Rust's Arc is runtime-only, while Clang's ARC is understood by the compiler and optimizer. This allows eliding balanced mutations, and also weird ABIs - functions which return a +1 object, or functions which accept a +1 object. See Arc#Optimization [1]. More generally there's an ABI. While to Rust "Arc is just another tool", reference counting is deeply pervasive on iOS and macOS. You would not attempt to pass a Rust Arc to C, and expect something useful to happen. But Clang's ARC works well with C, and Swift, and with ObjC and even with ObjC-pre-ARC. This isn't a critique of Rust, just reflecting different priorities. 1: https://clang.llvm.org/docs/AutomaticReferenceCounting.html#optimization https://clang.llvm.org/docs/AutomaticReferenceCounting.html#...
  - pjmlp 7y ago
    Those compiler optimizations need some work I guess. https://github.com/ixy-languages/ixy-languages https://github.com/ixy-languages/ixy-languages
    - tom_mellior 7y ago
      Personally, I appreciate you posting this link once, but seeing it this many times gets tedious.
      - pjmlp 7y ago
        Unfortunately it is hard to give an answer were all advocates of "Swift ARC performance" are able to read, thus urban myths keep being spread. ARC makes sense given Objective-C compatibility, as otherwise a layer similar to RCW on .NET for dealing with COM/UWP would be needed. And Objective-C only dropped its tracing GC, because it was too unstable while mixing GC enabled frameworks with classical ones, while making the compiler automatically call retain/release would provide better productivity without being unstable.
Tuna-Fish 7y ago
The reason they are not used is not the circular reference problem, it's performance. Single-threaded ARC is passable, but thread-safe ARC is really, really slow. It basically hits all the worst performance pitfalls of modern CPUs.
- zozbot234 7y ago
  Performance is really bad if you use Arc for practically everything, as with Swift. If you can deal with the simplest (tree-like) allocation patterns statically as Rust does, and use refcounting only where it's actually needed, you can outperform tracing GC.
  - Razengan 7y ago
    > Performance is really bad if you use Arc for practically everything, as with Swift. Do you have examples where Swift suffers compared to other languages solely because of ARC? Also, is this something that Apple might theoretically make up for by optimizing their custom CPUs for it, without changing Swift?
    - pjmlp 7y ago
      Yes, here it arrives always last. https://github.com/ixy-languages/ixy-languages https://github.com/ixy-languages/ixy-languages Since the Xerox PARC workstations and Genera Lisp Machines, all hardware specific instructions for memory management have proven to be worse than doing it eventually in software.
      - Razengan 7y ago
        How does that compare to SwiftNIO? https://github.com/apple/swift-nio https://github.com/apple/swift-nio
        pjmlp 7y ago
        SwiftNIO is not high-speed network driver to start with. As for memory management impact in overall performance, a similar set of benchmarks would be needed.
YorickPeterse 7y ago
ARC is just reference counting, as there's nothing in reference counting that requires a runtime to do this for you (that is, just because the compiler inserts increments/decrements doesn't make it an entirely different thing). The reason reference counting is not more common is because of its performance. Naive reference counting works in some cases (e.g. when the counts are not modified often), but doesn't work too well for most programming languages, as the reference counts will be modified frequently. Deferred and coalesced reference counting are two techniques of improving performance, but they come at a cost: they are quite complex to implement, and require additional memory to keep track of what/when to increment/decrement. You will also end up facing similar nondeterministic behaviour and pauses, as an optimised RC collector may still need to pause the program to scan for cycles. You can handle cycles by supporting weak and strong references, but this puts the burden on the developer, and it's not always clear if cycles may appear when writing code. Combining this with a good allocator you can achieve performance that is on par with a tracing collector (http://users.cecs.anu.edu.au/~steveb/pubs/papers/rcix-oopsla-2013.pdf http://users.cecs.anu.edu.au/~steveb/pubs/papers/rcix-oopsla...), but it's not easy. If you are going down the path of implementing a complex collector, I think you're better off focusing on a real-time or concurrent collector.
alexisread 7y ago
I'd agree that mutability is an issue with GC, in fact some LISPs like Losak are deterministic simply by being entirely functional: http://losak.sourceforge.net/ http://losak.sourceforge.net/ It is true that you can get cyclical refs higher up in the language even with functional code though, and at some level you need a cycle checker. There is another type of managed memory not talked about much, and that's the model used by Composita- RAII but with defined message interfaces between modules, such that you can deterministically allocate memory for that: http://concurrency.ch/Content/publications/Blaeser_ETH_Diss_2007.pdf http://concurrency.ch/Content/publications/Blaeser_ETH_Diss_... It looks to be the best way of doing deterministic performant memory management, though you'll need a cycle checker in the language runtime.
oldmanhorton 7y ago
Another major user of reference counting is COM and WinRT. A major feature of WinRT projections over just using the raw C APIs is that you get reference counting implemented for you using whatever your higher level language uses for object lifetimes.
kccqzy 7y ago
> Also I can't prove it, but I think a major source of pain in garbage collection is mutability, which is exacerbated by our fascination with object-oriented programming. I'd like to see a solid comparison of garbage collection overhead between functional and imperative languages. I can only speak for Haskell's GC, but it's pretty conventional. You might think that GC is simpler for Haskell without mutability but you'd be wrong, because (1) Haskell actually gives you plenty of safe and unsafe ways to have mutability, safe ways such as the ST monad (not to be confused with the State monad), (2) laziness effectively is mutation: evaluating a value is effectively overwriting the closure to compute the value with the value itself. The lazy list is a pretty common sight in most Haskell code. So basically Haskell has a pretty conventional stop-the-world, generational GC not unlike imperative languages.
lokedhs 7y ago
The issue here is that while GC does take some time to perform, it's easy to make the assumption that removing the GC will reclaim the performance lost by the GC. This is a fallacy. We can compare memory strategies like so: Garbage Collection: - Allocations: Very fast (often a single instruction) - Ownership transfer: Free - Pointer release: Zero - Post-free: Garbage collection phase (this is where the time is spent) Reference Counting: - Allocations (similar to malloc(), requires a binary search at least) - Ownership transfer: At least one instruction for single-threaded. Multi-threading: Requires a lock. - Pointer release: Slow. Locking issues, memory housekeeping. - Post-free: Zero. Good for realtime. The first point might require some clarification. When you have a compacting garbage collector, the free memory is usually in a single block. This means that allocations merely require a single pointer to be updated. If the pointer hits the end of the free block, you trigger a GC. You don't even have to check for the end of the free block if the subsequent memory page is marked no-access. One can spend a lot of time measuring the performance impact of all these different steps, and I am not going to try to prove that GC is always faster than refcounting, but at least it should be clear that it's not a simple matter of assuming that having no GC means that you will have no memory management overhead.
- cesarb 7y ago
  There's another difference: memory usage. For garbage collection, it's at the minimum only after a full GC (and there's a memory/performance tradeoff, in that using more memory allows doing less GC), while for reference counting, it's always at the minimum. Using more memory for the GC means less memory for other things like the disk cache (which caused a performance problem at work once, which we solved by giving the GC less memory to work with). (Also, "ownership transfer" can be free in reference counting, since the number of references is the same before and after so there's no need to modify the reference count. What isn't free is sharing ownership, since it needs reference count manipulation.)
  - lokedhs 7y ago
    Indeed. Memory usage is a point I never addressed in my comment. When managing large Java applications, that is indeed one of the most important issues that one has to be aware of. Some runtimes tries to be more automatic than others, and there are books worth discussions to be had about that. As for the second paragraph, thank you for clarifying that. I used poor terminology. I should probable have said pointer sharing, or copying. For ownership transfer to be zero cost, the compiler have to be clever enough to figure out that the original reference isn't used after copy. This can be handled by the compiler itself, or be enforced by the language (as is the case with Rust, as far as I understand).
rumanator 7y ago
> and smart pointers never seemed to really catch on outside of Objective-C and Swift: Smart pointers are a central feature of C++ even before they were added to the C++ standard in 2011.
- pjmlp 7y ago
  Indeed, OWL, MFC and VCL already supported them for COM programming since its early days.

munificent 7y ago

> They almost "just work", except for circular references Well, and they're often slower since they require mutating the reference count on every single time a field is stored. You can optimize that using lazy reference counting, or not updating refcounts for references on the stack and instead scanning the stack before a collection. But at that point... you're halfway to implementing a tracing collector. Every refcounting implementation eventually gets "optimized" to the point that it has most of a tracing collector hiding inside of it. I think it's simpler, cleaner, and faster to just start with tracing in the first place. There's a reason almost no widely used language implementation relies on ref-counting. CPython is the only real exception and they would switch to tracing if they could. They can't because they exposed deterministic finalization to the user which means now their GC strategy is a language "feature" that they're stuck with. That being said, ref-counting is fine for other kinds of resource management where resources are pretty coarse-grained and don't have cyclic references. For example, I think Delphi uses ref-counting to manage strings, which makes a lot of sense. Many games use ref-counting for tracking resources loaded from disc, and that also works well. In both of those cases, there's nothing to trace through, and the overhead of updating refcounts is fairly low.

blattimwind 7y ago
> There's a reason almost no widely used language implementation relies on ref-counting. CPython is the only real exception and they would switch to tracing if they could. They can't because they exposed deterministic finalization to the user which means now their GC strategy is a language "feature" that they're stuck with. Reference counting and address-semantics (which prohibits moving objects, so even if you work around the refcount, you can only do a tracing GC, but you don't get to compact) are deeply ingrained into CPython's C API as well, which is very widely used.
nostrademons 7y ago
There's a classic paper that shows that refcounting and GC are in fact duals of each other, where GC is effectively tracing live objects and refcounting is tracing dead objects: https://dl.acm.org/citation.cfm?id=1028982 https://dl.acm.org/citation.cfm?id=1028982 This had a number of important corollaries to this. One is that they have opposite performance characteristics: GCs make creating new references fast but then create a large pause when RAM is exhausted and a collection happens, while refcounts make creating new references slow and create a large pause when large object graphs are freed all at once. Another is that nearly all high-performance memory management systems are hybrids of the two: lazy refcounting is basically like implementing a local garbage collector and then feeding the live set of that into the refcounts, while generational garbage collection is like implementing a local refcount (the write barrier) and feeding the results of that into the root set.
ridiculous_fish 7y ago
Objective-C and then Swift are surely the most serious goes at fast widely used RC languages. Neither requires mutating the reference count on every store, and neither seems at risk of growing a tracing GC. ObjC had some elision tricks like objc_retainAutoreleasedReturnValue, but more importantly the optimizer was taught about RC manipulation. Swift then extended this with a new ABI that minimizes unnecessary mutations. The big advantages of this scheme are efficient COW collections and a simpler FFI (very important with Swift). More generally RC integrates better. Imagine teaching the JS GC to walk the Java heap!

akiselev 7y ago

What is the difference between Clang's ARC implementation and Rust's std::rc::Rc implementation? Rust's ownership system provides the scaffolding for the Drop implementation that manages reference counting instead of Clang doing it as part of the Swift/ObjC frontend but otherwise, they seem to be very similar. It's just another tool in Rust's box (no pun intended) but I wouldn't say it hasn't caught on. It's used quite often, along with its multithreaded cousin std::sync::Arc.

ridiculous_fish 7y ago
One difference is optimization. Rust's Arc is runtime-only, while Clang's ARC is understood by the compiler and optimizer. This allows eliding balanced mutations, and also weird ABIs - functions which return a +1 object, or functions which accept a +1 object. See Arc#Optimization [1]. More generally there's an ABI. While to Rust "Arc is just another tool", reference counting is deeply pervasive on iOS and macOS. You would not attempt to pass a Rust Arc to C, and expect something useful to happen. But Clang's ARC works well with C, and Swift, and with ObjC and even with ObjC-pre-ARC. This isn't a critique of Rust, just reflecting different priorities. 1: https://clang.llvm.org/docs/AutomaticReferenceCounting.html#optimization https://clang.llvm.org/docs/AutomaticReferenceCounting.html#...
- pjmlp 7y ago
  Those compiler optimizations need some work I guess. https://github.com/ixy-languages/ixy-languages https://github.com/ixy-languages/ixy-languages
  - tom_mellior 7y ago
    Personally, I appreciate you posting this link once, but seeing it this many times gets tedious.
    - pjmlp 7y ago
      Unfortunately it is hard to give an answer were all advocates of "Swift ARC performance" are able to read, thus urban myths keep being spread. ARC makes sense given Objective-C compatibility, as otherwise a layer similar to RCW on .NET for dealing with COM/UWP would be needed. And Objective-C only dropped its tracing GC, because it was too unstable while mixing GC enabled frameworks with classical ones, while making the compiler automatically call retain/release would provide better productivity without being unstable.

Tuna-Fish 7y ago

The reason they are not used is not the circular reference problem, it's performance. Single-threaded ARC is passable, but thread-safe ARC is really, really slow. It basically hits all the worst performance pitfalls of modern CPUs.

zozbot234 7y ago
Performance is really bad if you use Arc for practically everything, as with Swift. If you can deal with the simplest (tree-like) allocation patterns statically as Rust does, and use refcounting only where it's actually needed, you can outperform tracing GC.
- Razengan 7y ago
  > Performance is really bad if you use Arc for practically everything, as with Swift. Do you have examples where Swift suffers compared to other languages solely because of ARC? Also, is this something that Apple might theoretically make up for by optimizing their custom CPUs for it, without changing Swift?
  - pjmlp 7y ago
    Yes, here it arrives always last. https://github.com/ixy-languages/ixy-languages https://github.com/ixy-languages/ixy-languages Since the Xerox PARC workstations and Genera Lisp Machines, all hardware specific instructions for memory management have proven to be worse than doing it eventually in software.
    - Razengan 7y ago
      How does that compare to SwiftNIO? https://github.com/apple/swift-nio https://github.com/apple/swift-nio
      - pjmlp 7y ago
        SwiftNIO is not high-speed network driver to start with. As for memory management impact in overall performance, a similar set of benchmarks would be needed.

YorickPeterse 7y ago

ARC is just reference counting, as there's nothing in reference counting that requires a runtime to do this for you (that is, just because the compiler inserts increments/decrements doesn't make it an entirely different thing). The reason reference counting is not more common is because of its performance. Naive reference counting works in some cases (e.g. when the counts are not modified often), but doesn't work too well for most programming languages, as the reference counts will be modified frequently. Deferred and coalesced reference counting are two techniques of improving performance, but they come at a cost: they are quite complex to implement, and require additional memory to keep track of what/when to increment/decrement. You will also end up facing similar nondeterministic behaviour and pauses, as an optimised RC collector may still need to pause the program to scan for cycles. You can handle cycles by supporting weak and strong references, but this puts the burden on the developer, and it's not always clear if cycles may appear when writing code. Combining this with a good allocator you can achieve performance that is on par with a tracing collector (http://users.cecs.anu.edu.au/~steveb/pubs/papers/rcix-oopsla-2013.pdf http://users.cecs.anu.edu.au/~steveb/pubs/papers/rcix-oopsla...), but it's not easy. If you are going down the path of implementing a complex collector, I think you're better off focusing on a real-time or concurrent collector.

alexisread 7y ago

I'd agree that mutability is an issue with GC, in fact some LISPs like Losak are deterministic simply by being entirely functional: http://losak.sourceforge.net/ http://losak.sourceforge.net/ It is true that you can get cyclical refs higher up in the language even with functional code though, and at some level you need a cycle checker. There is another type of managed memory not talked about much, and that's the model used by Composita- RAII but with defined message interfaces between modules, such that you can deterministically allocate memory for that: http://concurrency.ch/Content/publications/Blaeser_ETH_Diss_2007.pdf http://concurrency.ch/Content/publications/Blaeser_ETH_Diss_... It looks to be the best way of doing deterministic performant memory management, though you'll need a cycle checker in the language runtime.

oldmanhorton 7y ago

Another major user of reference counting is COM and WinRT. A major feature of WinRT projections over just using the raw C APIs is that you get reference counting implemented for you using whatever your higher level language uses for object lifetimes.

kccqzy 7y ago

> Also I can't prove it, but I think a major source of pain in garbage collection is mutability, which is exacerbated by our fascination with object-oriented programming. I'd like to see a solid comparison of garbage collection overhead between functional and imperative languages. I can only speak for Haskell's GC, but it's pretty conventional. You might think that GC is simpler for Haskell without mutability but you'd be wrong, because (1) Haskell actually gives you plenty of safe and unsafe ways to have mutability, safe ways such as the ST monad (not to be confused with the State monad), (2) laziness effectively is mutation: evaluating a value is effectively overwriting the closure to compute the value with the value itself. The lazy list is a pretty common sight in most Haskell code. So basically Haskell has a pretty conventional stop-the-world, generational GC not unlike imperative languages.

lokedhs 7y ago

The issue here is that while GC does take some time to perform, it's easy to make the assumption that removing the GC will reclaim the performance lost by the GC. This is a fallacy. We can compare memory strategies like so: Garbage Collection: - Allocations: Very fast (often a single instruction) - Ownership transfer: Free - Pointer release: Zero - Post-free: Garbage collection phase (this is where the time is spent) Reference Counting: - Allocations (similar to malloc(), requires a binary search at least) - Ownership transfer: At least one instruction for single-threaded. Multi-threading: Requires a lock. - Pointer release: Slow. Locking issues, memory housekeeping. - Post-free: Zero. Good for realtime. The first point might require some clarification. When you have a compacting garbage collector, the free memory is usually in a single block. This means that allocations merely require a single pointer to be updated. If the pointer hits the end of the free block, you trigger a GC. You don't even have to check for the end of the free block if the subsequent memory page is marked no-access. One can spend a lot of time measuring the performance impact of all these different steps, and I am not going to try to prove that GC is always faster than refcounting, but at least it should be clear that it's not a simple matter of assuming that having no GC means that you will have no memory management overhead.

cesarb 7y ago
There's another difference: memory usage. For garbage collection, it's at the minimum only after a full GC (and there's a memory/performance tradeoff, in that using more memory allows doing less GC), while for reference counting, it's always at the minimum. Using more memory for the GC means less memory for other things like the disk cache (which caused a performance problem at work once, which we solved by giving the GC less memory to work with). (Also, "ownership transfer" can be free in reference counting, since the number of references is the same before and after so there's no need to modify the reference count. What isn't free is sharing ownership, since it needs reference count manipulation.)
- lokedhs 7y ago
  Indeed. Memory usage is a point I never addressed in my comment. When managing large Java applications, that is indeed one of the most important issues that one has to be aware of. Some runtimes tries to be more automatic than others, and there are books worth discussions to be had about that. As for the second paragraph, thank you for clarifying that. I used poor terminology. I should probable have said pointer sharing, or copying. For ownership transfer to be zero cost, the compiler have to be clever enough to figure out that the original reference isn't used after copy. This can be handled by the compiler itself, or be enforced by the language (as is the case with Rust, as far as I understand).

rumanator 7y ago

> and smart pointers never seemed to really catch on outside of Objective-C and Swift: Smart pointers are a central feature of C++ even before they were added to the C++ standard in 2011.

pjmlp 7y ago
Indeed, OWL, MFC and VCL already supported them for COM programming since its early days.