7 ms·

As someone who primarily works on iOS, I would have liked to see Apple's ARC mentioned. With the addition of weak pointers, I think it gives a good blend of per

• mikeash 11y ago
  ARC is one of the oldest (if not the oldest) kinds of GC out there. It's even the subject of one of the famous AI Koans: http://www.catb.org/jargon/html/koans.html http://www.catb.org/jargon/html/koans.html (see "Moon instructs a student") It stopped being considered proper garbage collection long ago because of the inability to collect circular references without help, which of course is the subject of that story. Apple is doing decently well with their version of it, but they're essentially reinventing ancient history. Other GCs often have weak pointers too. You just use them less, because with a GC that can deal with circular references you don't need them nearly as often.
  • vbezhenar 11y ago
    Apple tried to implement a garbage collector but they abandoned it later. May be they don't have good developers (but they got a lot of money so they probably can buy anyone) or reference counting isn't that bad in practice.
    • lispm 11y ago
      > Apple tried to implement a garbage collector but they abandoned it later. May be they don't have good developers (but they got a lot of money so they probably can buy anyone) or reference counting isn't that bad in practice. Garbage Collection is not very good with a C-language. C is simply the wrong language to be used with GC - same for Objective C. Personally I would also not use a 'conservative GC' in this context. Additionally GC has some overhead and it is not going away: memory usage, responsiveness, etc.. Apple would need to switch to a real higher-level language with managed memory and a precise GC. GC, Swift and more RAM might have more chances.
    • pjmlp 11y ago
      They never managed to make it work without segfaults, due to the underlying C features.
      • mikeash 11y ago
        It worked fine if you followed the rules. The trouble is that the rules were kind of annoying to follow and weren't automatically enforced at compile time very well. More troublesome was the fact that a C collector necessarily needs to be conservative, and that means you lose out on nice advanced GC features like compaction.
        • pjmlp 11y ago
          Exactly, which was specially problematic with third party libraries. What proponents of ARC miss, is that Apple gave up on GC because they didn't managed to make it work with Objective-C semantics, not due to merits of RC over GC. Also Swift is also ARC based, because the goal is for a smooth integration with the Objective-C runtime, not due to merits of RC over GC.
    • millstone 11y ago
      Reference counting has a lower memory high-water mark than any GC, due to eager reclamation. This is important on a mobile device that does not page to disk, since it means that you have more memory available to actually use.
  • otabdeveloper1 11y ago
    Having circular references is a logic bug. I don't believe there's any algorithm in existence that requires circular references.
    • chris_overseas 11y ago
      As a trivial example of a data structure with circular references, how about a doubly linked list? Admittedly there are alternative data structures to solve the same problem (eg an array), but that changes the performance characteristics too and may not be optimal for your particular use case. This isn't the point though. A general purpose programming language shouldn't impose arbitrary restrictions on data structures like this. Even if such a restriction was in place it would have to be enforced at runtime which doesn't sound like a trivial problem from a performance point of view.
      • bsdetector 11y ago
        An even more trivial example is a singly-linked list with a sentinel node (the last node points back to it). But that's not really the question here. Any linked list is not an algorithm, it's a data structure. The question is what operations can you do using circular references cannot be done without. I think otabdeveloper1 is right, because you can use a garbage collection type process to 'run' any other algorithm on a graph with cycles in it, using temporary lists and stacks to do whatever the algorithm would use circular references for.
        • mikeash 11y ago
          It seems obvious that you can do anything without circular references. Proof: implement a Turing machine without using them. The question is whether it's a reasonable constraint for real-world programs. In theory, Malbolge can be used to perform any algorithm, but few people would actually want to. Circular references are really convenient in many cases. For example, view hierarchies typically have a pointer from a view back to its parent view. This means you can walk up the view hierarchy as well as down, so you can find sibling views, remove a view from its parent, invalidate a parent's layout when the view's sizing needs change, and stuff like that. Without circular references you could still accomplish all this, it just becomes slower and more painful. In practice, reference cycles are a big problem for ARC. One of the most common questions I see with Objective-C and Swift programmers is when it's necessary to use a weak reference to self in a block, and when it's necessary to use a strong reference. It's difficult enough that I've seen a lot of people just punt on the entire question and go for "always capture self as a weak reference no matter what." Which works most of the time, and occasionally creates entertaining bugs. Even for experienced developers it's easy to miss a spot occasionally, and end up with a silent leak or a subtle bug.
  • hamstergene 11y ago
    You're mixing up Apple's ARC with reference counting in general. A typical RC implementation suffers from either requiring to do AddRef/Release calls manually (what Apple had in pre-ARC era), or blindly doing too many automatic calls. That's ancient history and can not complete with a moderately decent modern GC. ARC has neither of those disadvantages and so provides convincing alternative to GC, and AFAIK is the first and unique to do so. BTW, the correct term to use here is "automatic memory management" (AMM), not garbage collection, and there is no such thing as "proper" AMM. Handling circular references is not a must-have property of AMM, it is just the price RC pays, in GC, that will be pauses and higher footprint, and other approaches exist too: for example, to disallow in compile time to create a structure that can be potentially circular.
    • repsilat 11y ago
      Something I've wondered about reference counting and optimising compilers: I assume at a lowish level an inlined function call might look something like, pointer->ref_count += 1 obj = pointer->ptr //...do something with obj... pointer->ref_count -= 1 if pointer->ref_count == 0: free(pointer->ptr) Assuming ref_count isn't messed up by another thread (which I guess we're free to do if we haven't put locks around it, or declared it volatile?) then you could optimise away the increment and decrement on `ref_count`, right? I guess I wouldn't be surprised either way. What I'd like to know, though, is whether the `ref_count == 0` check could get optimised away as well. To you and me it's obvious that the count is positive at the start (as a precondition for the pointer access being correct), but I can't really see how an optimising compiler could know that.
    • mikeash 11y ago
      Nobody else ever put an optimizer in front of the refcounting calls to remove redundant pairs? I find that hard to believe.
    • zZorgz 11y ago
      ARC can add automatic calls when not needed (just to be safe). When converting from manual management to ARC for one of my projects I had to resolve performance issues found in tight loops where it inserted unneeded retain/releases.
• cwzwarich 11y ago
  The biggest performance problem with automatic reference counting is that it requires atomic reference counting and/or type system separation of thread-local and shared data. In a sufficiently multicore scenario the overhead of atomic reference counting becomes unacceptable. If you want to reduce the number of atomic operations you have to do deferred reference counting, which destroys many of the benefits of reference counting, e.g. you can no longer run destructors in a predictable way and have to use GC finalizer semantics. There is a possibility that better whole-program optimization (potentially combined with annotations for function parameters) can reduce this overhead, but it's a bit of an unknown.
  • millstone 11y ago
    Atomic reference counting is expensive mainly under contention, when the same object is used from multiple threads. Uncontended atomic operations are ~2-3x slower than their nonatomic analogs, which is still very fast. Also I'd expect that GCs should experience a slowdown in the contention scenario, due to write barriers; is it so?
    • cwzwarich 11y ago
      While uncontended atomic operations are a lot faster than contended ones, it's hard to avoid the contended case. If you pass a single piece of read-only data throughout your program you will be adjusting its reference count frequently, and those contended atomics will dominate your performance profile. In a concurrent card-marking write barrier you would generally set bytes rather than individual bits so that you can avoid the use of atomic instructions. You still have the problem of false sharing. If this were really a problem, you could emit a conditional write barrier that checks the existing value (with a racy unsynchronized load) before setting the byte. The usual use of a write barrier for generational GC will produce fewer stores than automatic reference counting anyways, because a write barrier is only emitted for potential stores of a reference to a younger generation in an older generation. Automatic reference counting requires reference count adjustments for function parameters and local variables.
    • rbehrends 11y ago