This looks similar to the way of doing weak references that I’m familiar with: for each object that has a weak reference to it taken, make a new reference-counted object that holds the real reference. This requires a table that maps object so their weak placeholder so that you can find it when you deallocated the object and null it out in the object’s finaliser. Most objects have zero weak references so you can use one bit in the object’s finaliser header to skip this check (or reuse the ‘has finaliser’ check). That’s more effort if your language doesn’t have finalisers.
It’s safe to refcount the weak references structure because it doesn’t participate in garbage cycles (it holds one pointer and that is non-owning). When you do a weak-to-strong operation on a nulled weak ref, you decref the structure and null the pointer that referred to it.
If you’re using ref counting everywhere this is more complex. The weak-to-strong transition may happen concurrently with deallocation so you need some synchronisation. The C++ standard library weak pointer simplifies this by putting weak and strong references counts in the same object. When the strong refcount reaches zero, the object is destructed (and deallocated if not allocated with make_shared but the control block is not until both the weak and strong refcounts reach zero. This is simpler, but incurs the space overhead of weak references in all cases, even when they aren’t used.
At least in a moving collector, you don’t need the extra slot for the linked list pointer in the weak pointer object. You don’t even need a table like you describe. Instead, in the GC you move each weak reference-holding object as usual, but you link up the forwarding pointers of each weak pointer object in a linked list as you go (but you let it point to the object in the old space). Then after you’re done, traverse that linked list (which now contains all the weak pointers that are still live). If the weak object still points to a valid object in the old space, you clear the weak reference. Otherwise it points to a forwarding pointer and you update the reference by following the forwarding pointer.
The spot where the weak reference was stored should have enough space for a forwarding pointer and the link to the next reference. This means you don’t need to allocate that extra pointer (for the linked list chain) as part of the weak pointer itself.
I’ve described this approach in more detail in a blog post.
Yes, it’s very similar but the approach in the post requires adding an extra slot to the weak pointer object itself, which means it’s more memory-hungry. But this works also for non moving GCs, while the approach I describe requires a forwarding pointer with enough free space after it.
Ah yes, indeed, I hadn’t read the paper. The paper seems to re-use the cdrs in oldspace to maintain the frontier of the GC’s work set to avoid visiting the same objects more than once, rather than for re-visiting weak pointers. The ideas are definitely related, though!
This looks similar to the way of doing weak references that I’m familiar with: for each object that has a weak reference to it taken, make a new reference-counted object that holds the real reference. This requires a table that maps object so their weak placeholder so that you can find it when you deallocated the object and null it out in the object’s finaliser. Most objects have zero weak references so you can use one bit in the object’s finaliser header to skip this check (or reuse the ‘has finaliser’ check). That’s more effort if your language doesn’t have finalisers.
It’s safe to refcount the weak references structure because it doesn’t participate in garbage cycles (it holds one pointer and that is non-owning). When you do a weak-to-strong operation on a nulled weak ref, you decref the structure and null the pointer that referred to it.
If you’re using ref counting everywhere this is more complex. The weak-to-strong transition may happen concurrently with deallocation so you need some synchronisation. The C++ standard library weak pointer simplifies this by putting weak and strong references counts in the same object. When the strong refcount reaches zero, the object is destructed (and deallocated if not allocated with
make_sharedbut the control block is not until both the weak and strong refcounts reach zero. This is simpler, but incurs the space overhead of weak references in all cases, even when they aren’t used.At least in a moving collector, you don’t need the extra slot for the linked list pointer in the weak pointer object. You don’t even need a table like you describe. Instead, in the GC you move each weak reference-holding object as usual, but you link up the forwarding pointers of each weak pointer object in a linked list as you go (but you let it point to the object in the old space). Then after you’re done, traverse that linked list (which now contains all the weak pointers that are still live). If the weak object still points to a valid object in the old space, you clear the weak reference. Otherwise it points to a forwarding pointer and you update the reference by following the forwarding pointer.
The spot where the weak reference was stored should have enough space for a forwarding pointer and the link to the next reference. This means you don’t need to allocate that extra pointer (for the linked list chain) as part of the weak pointer itself.
I’ve described this approach in more detail in a blog post.
This sounds like the approach mentioned at the bottom of my post
Yes, it’s very similar but the approach in the post requires adding an extra slot to the weak pointer object itself, which means it’s more memory-hungry. But this works also for non moving GCs, while the approach I describe requires a forwarding pointer with enough free space after it.
No, the approach at the bottom–Clark’s approach that uses oldspace. It was barely more than a passing mention, but it was mentioned.
Ah yes, indeed, I hadn’t read the paper. The paper seems to re-use the cdrs in oldspace to maintain the frontier of the GC’s work set to avoid visiting the same objects more than once, rather than for re-visiting weak pointers. The ideas are definitely related, though!