4 ms·

> As a trivial example of a data structure with circular references, how about a doubly linked list? Not really, no. There's no reason why the backlink should

> As a trivial example of a data structure with circular references, how about a doubly linked list? 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.

lispm 11y ago
> Realistically, circular references are only a deal-breaker for Lisps, and only due to some very specific design decisions of Lisp. How so?
mikeash 11y ago
If you allow backlinks which don't increment the reference count, then you have circular references. You're just helping a reference counting implementation deal with them. The end result is the same as a GC, except you need more programmer intervention, and the only sign that you've got your intervention wrong is a memory leak, a crash, or mysterious misbehavior.
- paulhodge 11y ago
  More specifically.. a link that doesn't touch the reference count is a weak reference. It's a known strategy and it does avoid the problem where a cycle can't be collected. 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.
  - mikeash 11y ago
    Weak references don't have to be very slow. You need to track all weak references to any given object, but that's no big deal. When it comes to actually zeroing out the weak references on deallocation, it depends on how you do it. 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.
rayiner 11y ago
Uh, any general graph can have cycles and thus result in circular references.

lispm 11y ago

> Realistically, circular references are only a deal-breaker for Lisps, and only due to some very specific design decisions of Lisp. How so?

mikeash 11y ago

If you allow backlinks which don't increment the reference count, then you have circular references. You're just helping a reference counting implementation deal with them. The end result is the same as a GC, except you need more programmer intervention, and the only sign that you've got your intervention wrong is a memory leak, a crash, or mysterious misbehavior.

paulhodge 11y ago
More specifically.. a link that doesn't touch the reference count is a weak reference. It's a known strategy and it does avoid the problem where a cycle can't be collected. 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.
- mikeash 11y ago
  Weak references don't have to be very slow. You need to track all weak references to any given object, but that's no big deal. When it comes to actually zeroing out the weak references on deallocation, it depends on how you do it. 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.

rayiner 11y ago

Uh, any general graph can have cycles and thus result in circular references.