4
$\begingroup$

How can weak references (weakrefs) be implemented, and how do the different approaches compare?

The most important considerations for implementing weakrefs are:

  • Safety ─ a weakref shouldn't allow access after its allocation is freed.
  • Overhead ─ the metadata used for implementing weakrefs should be as small as possible.
  • Preventing leaks ─ objects should not be kept around too long by stale weakrefs.
  • Performance ─ the runtime cost of checking and updating the status of a weakref should be minimal.

Feel free to also address any other considerations I may have missed.

$\endgroup$
1
  • $\begingroup$ Weak references are tightly coupled to garbage collection, so how they are implemented depends on the garbage collection algorithm(s) used. Reference counting, mark-sweep, and copying collectors need different weak pointer implementations. $\endgroup$
    – Chris Dodd
    Commented Jun 8 at 5:22

4 Answers 4

8
$\begingroup$

Most of the information in this answer comes from a blog post titled Surprising Weak-Ref Implementations: Swift, Obj-C, C++, Rust, and Vale by Evan Ovadia, the designer of Vale.

Objective-C

The program has a global hashtable, mapping each memory address to a list of all weakrefs to that address. When an allocation becomes inaccessible via strong references, all weakrefs to that allocation are eagerly replaced with nulls.

This has significant overhead and performance costs; a hashtable of lists is a relatively high-cost data structure, it costs space per weakref (not just per allocation), and a lock must be acquired each time it's used. However, it guarantees memory safety, and always frees an allocation as soon as possible.

Swift, C++ and Rust

Allocations have counters for both strong and weak references, and an allocation is not freed until both counters reach zero. Weakrefs are lazily replaced with nulls, only when a weakref is accessed after the strong counter reaches zero.

The memory overhead and performance costs of this approach are relatively low; there is just one extra counter held by the allocation (assuming that the strong counter would be needed anyway). The cost of maintaining reference counters is often not insigificant, but there are ways to mitigate this ─ for example, Lobster claims to statically eliminate 95% of refcount operations via lifetime analysis.

The main disadvantage of this approach is what Ovadia calls "zombie objects" ─ allocations can't be freed until all stale weakrefs have been actively checked and nulled out, so there will be a memory leak if some stale weakrefs never get checked. (In particular, if a data structure uses weakrefs to avoid reference cycles, an inaccessible object can keep itself alive through its own inaccessible weakrefs.) Another issue is that memory safety is only guaranteed if refcount operations are done in a thread-safe way, which adds performance costs.

There are some further differences between Swift, C++ and Rust discussed in Ovadia's post.

Vale

Each allocation is prefixed with an auto-incremented generation number, so the pair of (address, generation) is unique for the whole lifetime of the program. Weakrefs are fat pointers which include the generation number, and a weakref is stale if the allocation's generation number doesn't equal the weakref's.

Memory safety is guaranteed in this approach as long as (1) addresses used for generation numbers will not hold other data after reallocation, and (2) generation numbers never overflow. The former can be addressed by allocating objects in arrays according to their sizes, so that generation numbers occur at predictable locations. The latter can be addressed by

  • Not re-allocating a block of memory once its generation number reaches the maximum;
  • Using a wide enough integer that overflow can never practically happen; or
  • Just accepting that even if overflow does happen it's still profoundly unlikely that a very old weakref with a colliding generation number still exists.

This approach also allows immediate deallocation of stale objects, and according to Ovadia, maintaining and checking the generation number at runtime is about 57% faster than reference counting ─ not as much of an improvement as Lobster manages, but lifetime analysis may likewise be able to statically eliminate many checks of the generation number.

Due to the use of fat pointers, there is some memory overhead per weakref, not just per allocation.

$\endgroup$
7
$\begingroup$

Python

Python's weakref implementation is more complicated than any of the above implementations.

The basic behavior is that each object has one associated object representing a weakref, which is strong refcounted. If you create a weakref to the same object twice, then the weakref creation will return the same weakref both times.

The object itself stores a reference to that weakref, and therefore can clear it when it itself is deallocated. This accomplishes safety and makes leaks impossible, and in terms of overhead is only more than Swift/C++/Rust's approach by a constant factor, although it does add an extra layer of indirection so may harm performance.

Python also allows you to create weakrefs with callbacks that run when the object is deallocated, which are separate objects and have significantly greater overhead because the base object has to keep a reference to each ref and its callback individually.

$\endgroup$
2
  • $\begingroup$ Nice! I wouldn't say it's more complicated; implementation-wise, this seems the simplest of all of them. I'd describe it as elegant, even. Maybe worth adding that this means an extra layer of pointer indirection when accessing an object via its weakref, since you have to follow a pointer to the weakref object and then another to the actual object ─ that's probably not great for performance. $\endgroup$
    – kaya3
    Commented Jun 2, 2023 at 20:28
  • $\begingroup$ I added a little about that. $\endgroup$
    – pppery
    Commented Jun 2, 2023 at 20:56
6
$\begingroup$

I wrote Lock-free GC Handles in Mono, implementing the .NET GCHandle API, which is used to implement WeakReference internally. This supports both plain weak references and those that allow “resurrection” of an object by a finaliser.

Overhead and Performance

That article describes the representation, but here’s a summary:

  • A handle is a 32-bit integer index into a handle table
  • The spine of the table is an array of pointers to buckets
  • Buckets are allocated as needed, and never freed
  • Each bucket is twice the size of the previous
  • Buckets are arrays of 64-bit hidden object pointers with tag bits

All operations are lock-free, and rarely contentious, even in highly artificial benchmarks that allocate enormous numbers of weak references from several threads.

Because there’s no way to safely reduce the capacity of the GC handle table in a lock-free way, it never shrinks. However, this would only be a problem for an application that allocated many weakrefs and also retained them for a long time, which is extraordinarily unusual and not worth optimising.

I can’t speak to the absolute performance, but relative to the previous implementation, it was about 80% faster in stress tests with high contention. Serial microbenchmarks were 33–50% faster and one parallel microbenchmark of WeakReference.IsAlive was 98% faster, whereas previously it had been slow enough for customers to complain about. I don’t have stats on memory usage, but it was rather lower.

Safety and Correctness

The implementation ensures safety in a few ways.

When getting a weakref, we include a retry loop to ensure that, even if the access is interrupted by the collector, we will only return a valid object reference or null, never a use-after-free.

Weakrefs are only cleared during a collection, while the world is stopped, and a global GC lock is held.

If it’s necessary to update a weakref, this happens as soon as an object is moved.

Any unmanaged code that may run concurrently with the mutator always uses handles opaquely (if their target may be freed) or explicitly retains them (if it must not be freed).

A pointer must be held in a register or on the stack in order to be considered a GC root. If the unmanaged code is interrupted by a collection, and it temporarily holds the only reference to an object, that object must not be freed preemptively. So we must insert a full fence to ensure sequential consistency here, and a “dummy use” to prevent the C compiler from shrinking the live range of a variable.

Other standard knife-juggling disclaimers about lock-free code apply—we must use volatile to prevent the C compiler from reordering accesses, and at least a write barrier (store–load fence) when allocating a new handle or a new bucket, to ensure that a handle can’t be given to another thread without having been fully initialised, and that the table remain consistent across threads.

So it’s not easy to get right by any means, but I’d guess it’s the most efficient thing you can retrofit into a standard tracing generational collector.

$\endgroup$
2
  • $\begingroup$ It's not quite clear to me how this works. I'm assuming that, when an object is collected (no more strong references) and there's a hidden pointer to it in the table, that pointer is eagerly overwritten with NULL. But how does the implementation signal that this needs to be done, and efficiently find the pointer to null out? Does the stop-the-world collection simply know that the table exists, and do a sweep over it? In this case, how does it determine that a given pointer in the table is one that it just invalidated during the collection? $\endgroup$ Commented Jun 6 at 23:24
  • 1
    $\begingroup$ @KarlKnechtel: We just iterate over the weakref table after marking. When marking is done concurrently, this is after the workers have joined. Each weakref is then updated: if the referent is marked and has been moved, the weakref is updated; if the referent is unmarked, it’s about to be swept, so the weakref is nulled. That’s about it. I mean, there’s a bunch of other stuff—support for finalizers that can resurrect objects, .NET-specific things like app domains…—but the core idea is just to make allocation & access lock-free, and sweep during a normal sweep phase when you lock anyway. $\endgroup$
    – Jon Purdy
    Commented Jun 14 at 6:51
4
$\begingroup$

Unowned references

Swift has four types of references:

  • Strong references keep an object alive. As @kaya3 mentioned in his answer, objects with no strong references are deinitialized but not necessarily deallocated.
  • weak references are set to nil when there are no more strong references.
  • unowned references trap when there are no more strong references.
  • unowned(unsafe) references are like plain C references: they become dangling pointers if the object drops out from under it.

unowned(unsafe) only exists for Objective-C interop and is highly discouraged in Swift code.

This article talks about weak and unowned references in great detail. To summarize:

Every object has two refcounts, a strong rc and an unowned rc. When you create a weak or unowned reference, the latter is incremented. When you use one, it has to be temporarily converted to a strong reference to make sure another thread doesn't pull the object out from under you; the logic for that looks like this at a high level:

unownedRetainStrong(obj):
  assert(obj.strongRC++ != 0 && obj.unownedRC != 0)
  return obj

weakLoadStrong(obj):
  if (obj == nil):
    return nil
  if (obj.strongRC == 0):
    if (--obj.unownedRC == 0):
      dealloc(obj)
    return nil
  ++obj.strongRC
  return obj

Because every access to the refcounts requires a lock, and because the same weak reference might be available on multiple threads, weak references can be much slower than unowned references under high contention.

$\endgroup$
5
  • $\begingroup$ How does an unowned reference determine that there are no more strong references? Couldn't the object have been deallocated already at this point, such that it can't be inspected? $\endgroup$ Commented Jun 6 at 23:26
  • $\begingroup$ As I mentioned in the post, weak and safe unowned references prevent the object from being deallocated, but it can still be deinitialized. In other words, the destructor may run, but the memory is not freed until the unowned RC also hits 0. $\endgroup$
    – Bbrk24
    Commented Jun 7 at 3:07
  • $\begingroup$ Ah, so objects also have some kind of marker of this "zombie" state? $\endgroup$ Commented Jun 7 at 17:29
  • $\begingroup$ Not directly; the marker is that the strong refcount is 0 and the unowned refcount isn't. $\endgroup$
    – Bbrk24
    Commented Jun 7 at 19:08
  • $\begingroup$ Of course. Neat system! $\endgroup$ Commented Jun 8 at 5:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .