But maybe that's just rationalization.
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.
Also I'd expect that GCs should experience a slowdown in the contention scenario, due to write barriers; is it so?
More like up to 20x slower; atomic reference counting has to hit the L3 cache at least. A quick benchmark seems to confirm that. Also, there are still some nasty corner cases with pointers that are shared between threads (because reading/writing a pointer and updating its associated reference count are not a single atomic operation).
> Also I'd expect that GCs should experience a slowdown in the contention scenario, due to write barriers; is it so?
Write barriers only come into play when pointers on the heap or in static memory are being modified. Reference counting means that you need to update the reference count whenever you assign references, even from one local variable to another (much of the work that Apple's done is to use compiler optimizations to get rid of those that are provably unnecessary). For example, having multiple threads traversing a tree in parallel can generate a lot of contention in the RC case, but none for a GC with a write barrier.
Deferred reference counting is closer in performance to GC, but then you have to write most of the machinery of a tracing GC, too.
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.
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.
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.
pointer->ref_count += 1
obj = pointer->ptr
//...do something with obj...
pointer->ref_count -= 1
if pointer->ref_count == 0:
free(pointer->ptr)
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.
I love what Apple has done with ARC: they've taken a very inefficient approach to garbage collection, one which has repeatedly shown to be the "worst case" algorithm with the worst performance characteristics, and then proceeded to convince legions of developers that that same approach is actually the best one.
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.
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.
I don't believe there's any algorithm in existence that requires circular references.
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.
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.
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.
Not really, no. There's no reason why the backlink should increment the reference count.
Realistically, circular references are only a deal-breaker for Lisps, and only due to some very specific design decisions of Lisp. E.g., circular references are never a problem in C++.
> A general purpose programming language shouldn't impose arbitrary restrictions on data structures like this.
Really? Why not? "We don't support refcounted circular references, please rewrite your code if you use them" is a perfectly valid design decision. Personally, I'd rather have that than some rube-goldberg type monstrocity of a memory management system just to support a very obscure corner case.
If the weak references are safe (as in, their pointer is assigned to 0 when the target object is collected) then I think there can be performance issues (compared to the competition of a tracing GC).
If the weak references aren't safe, then you have a data structure that's more in the realm of manual memory management, so it's hard to draw a fair comparison with fully memory-managed objects.
With an eager implementation, you need to ensure that deallocation and zeroing is atomic. The entire operation of decrement refcount -> deallocate -> zero weak references can't be interrupted by looking up a weak reference. In a multithreaded environment that means there's locking needed.
However, you can do a lazy implementation which doesn't suffer so much. Here, you keep a separate weak reference count in the object itself. When the normal reference count reaches zero, you deinitialize the object (decrement the refcount of anything it refers to, run custom deinitialization code if any), but leave the memory for the object itself intact. Then, upon accessing a weak reference, you can just check to see if the target is in this "zombie" state, and zero out the weak reference at that point. Once the weak reference count also reaches zero, the object memory can be deallocated.
Objective-C uses the eager approach for weak references, which is necessary because of compatibility concerns. Swift uses the lazy approach with native Swift objects, although it still has to use the eager approach for subclasses of Objective-C classes.
How so?
Assume you have an algorithm that does make use of circular references. Then, you could replace all pointers by integers. And you could put all referenced data into a large array.
That way you would have "broken up" all circular references. However, from another point of view, you could argue that your algorithm still makes use of circular references, they are just expressed differently.
(Also, now no garbage collector will help you cleaning up that thing, other than releasing that large array at once. So that's not really an improvement.)
Otherwise, you can avoid parent pointers by reversing pointers while you traverse, but this requires using a bit per node (which you can generally steal from a pointer in practice) to indicate whether a visited node was the left or right child of its parent. Getting rid of the extra bit is trickier, but it can be done, e.g. Robson traversal that uses the links of leaf nodes to store the stack.