weak: new package providing weak pointers

[mknyszek]

What is a weak pointer?

Weak pointers (or weak references, as they are referred to in other languages) allow developers to reference memory without preventing the garbage collector from reclaiming it. To prevent visible dangling references, weak pointers become nil when the referenced memory is collected. Weak pointers can be converted to regular ("strong") pointers which do prevent the garbage collector from reclaiming memory, and allow typical use and access to that memory.

Weak pointers are typically a bit harder to work with than regular pointers because they can become nil at any time. Virtually every weak-to-strong conversion must be guarded by a nil check. Often, weak pointers will become nil at unexpected times.

Nonetheless, weak pointers exist in many languages because they are useful. The main use-cases for weak pointers are related to efficient memory management and reclamation. For example, efficiently managing memory for canonicalization maps, or for memory whose lifetime is bound to the lifetime of another object (akin to JavaScript's WeakMap). Another good use case for weak pointers is for hinting to the GC that it's OK to drop some resources because they're cheap to reconstruct later, especially if those resources have a large memory footprint.

Proposal

I propose adding a new weak package to the standard library with the following API.

// Pointer is a weak pointer to a value of type T.
//
// Two Pointer values compare equal if the pointers
// that they were created from compare equal. This property is retained even
// after the object referenced by the pointer used to create a weak reference
// is reclaimed.
//
// If multiple weak pointers are made to different offsets within same object
// (for example, pointers to different fields of the same struct), those pointers
// will not compare equal.
// If a weak pointer is created from an object that becomes unreachable, but is
// then resurrected due to a finalizer, that weak pointer will not compare equal
// with weak pointers created after resurrection.
//
// Calling Make with a nil pointer returns a weak pointer whose Value method
// always returns nil. The zero value of a Pointer behaves as if it was created
// by passing nil to Make and compares equal with such pointers.
type Pointer[T any] struct { ... }

// Make creates a weak pointer from a pointer to a value of type T.
func Make[T any](ptr *T) Pointer[T] { ... }

// Value returns the original pointer used to create the weak pointer.
// It returns nil if the value pointed to by the original pointer was reclaimed by
// the garbage collector.
// If a weak pointer points to an object with a finalizer, then Value will
// return nil as soon as the object's finalizer is queued for execution.
func (p Pointer[T]) Value() *T { ... }

Design discussion

Representation

The weak pointer we propose would be represented via an indirection object under the hood. This means that each pointer that has any weak pointers associated with it also has an associated 8 byte allocation that contains a single pointer. This pointer is the actual weak reference. This representation is very CPU efficient, since the GC can atomically set a single pointer to make all weak references to an object nil.

This 8 byte allocation is rarely a problem in practice since weak pointers are most often useful for memory efficiency anyway. For example, canonicalization maps are deduplicating memory already, so the extra 8 bytes per canonical copy is relatively cheap. However, it may be worth calling out this detail in the documentation as the C# language does.

This representation has other benefits. One benefit is that the API's equality semantics fall out very naturally. Weak pointers created from the same pointer remain equal even after that pointer no longer exists. This makes it possible to build maps keyed by weak pointers. Another benefit is its simplicity: very little of the GC has to change to support weak pointers.

Avoiding object resurrection

A subtle but important property of the weak pointer implementation is that it must not enable object resurrection. This would create many complications, including the fact that weakly-referenced objects would take 2 GC cycles to reclaim; and they could not be involved in cycles, or they would never be reclaimed (much like finalizers).

A simple way to implement weak references that maintains this property is to guard weak-to-strong conversions with ensuring the object is swept. A swept object cannot be resurrected, because it is always definitely reachable or unreachable, nothing in between. This means the weak-to-strong conversion path may need to sweep the object, but this happens at most once per GC cycle, and the Go runtime's sweeper is quite fast, so the cost shouldn't be noticeable in practice.

Why this specific interaction with finalizers?

The interaction between weak pointers and finalizers that resurrect objects is subtle. There are two choices: the weak pointer can go nil before the finalizer runs, or it can track the object's resurrection, and only go nil once the object is well and truly dead. In C# jargon, this is the difference between "short" weak reference and a "long" weak reference.

At first glance, the latter seems clearer since the weak pointer really only goes nil once nothing can reference the object. However, this semantics has a big problem, and it's subtle.

Today, the decision to resurrect an object in a finalizer is internal to an API’s implementation. If we allowed weak-to-strong conversions after finalization, then clients of an API could resurrect an object without the cooperation of its implementation, at which point the object's internals may be in an inconsistent state. This creates the potential for a race that is not immediately apparent to either the API authors or the client. Worse still, these races will be very rare and unlikely to be caught by testing, even with the race detector enabled. If the weak pointer goes nil before the finalizer runs, then such races are impossible.

It is telling that other garbage collected languages either make "short" weak references the default and do not recommend their "long" form (C#), or only offer the "short" form to begin with (Java).

Risks

Breaking the GC abstraction

The unique.Handle proposal explicitly rejected weak pointers as an alternative on the grounds that they are difficult to use. Fundamentally, this is because they break the GC abstraction by revealing the timing with which memory is actually reclaimed, and this is mainly a problem because that timing is unpredictable. The GC abstraction of "infinite memory" (only allocation, no apparent free) is important in general for composability.

While it is true that weak pointers are more difficult to use than regular pointers, we believe that we have picked an API (building on the experiences of other languages) that minimizes surprises, maintains composability, and has a simple implementation. This was discovered during the implementation of unique.Handle and it was compelling enough that it led to this proposal.

Although weak pointers will be misused in some cases, providing documentation, examples, and advice in the GC guide will go a long way to mitigating that.

[thediveo]

glad this is being resurrected *scnr*

[cespare]

How does this interact with the unique package (#62483)? Isn't it possible for a user to implement unique (or at least solve the same problems that unique solves) using weak pointers? If we add weak, will we regret having both weak and unique?

[mknyszek]

@cespare I don't think we'll regret having both. The main reason to have unique in std is that canonicalization maps benefit from being as global as possible, both for performance (bigger potential for sharing data) and composability (handles are always comparable, regardless of their origin). That alone makes it worth it, I think.

A secondary reason is that it's not actually possible to safely implement the concurrent map underlying unique outside of the standard library today. #54670 (maphash.Comparable) would change that. While I think maphash.Comparable is still important for the ecosystem, it's not going to be easy to make that as efficient as the hashing the std maps use. (See the issue for a breakdown of the problem by Austin.)

Weak pointers are still useful for lots of other cases where globalness is less useful and maybe even not what you want at all. For example, implementing weak-keyed maps, which are generally used for attaching data to memory you don't own the lifecycle of. There's also plenty more reasonable ad-hoc use-cases that don't neatly fall into something std would support out of the box.

[Merovius]

What does Make((*T)(nil)) do? Useless and the answer is probably "return a Pointer that always returns nil", but just to make sure.

[mknyszek]

@Merovius Yep, that's right. Thanks! Updated the proposal.

[apparentlymart]

Although a weak.Pointer that is immediately nil is a little strange, I've written programs with similar features in other languages where it's been helpful to represent an "optional weak pointer" without adding another level of indirection. I probably wouldn't complain too much if it weren't possible, but it has enough marginal use that I don't think it's worth overcomplicating things to forbid it.

(For example, a Rust analog would be std::rc::Weak::new(), which returns a Weak where upgrade always returns None, which is directly analogous to a weak.Pointer where Value always returns nil.)

Is the zero value of weak.Pointer[T] equivalent to what you'd get from passing nil to weak.Make?

[mknyszek]

Is the zero value of weak.Pointer[T] equivalent to what you'd get from passing nil to weak.Make?

From my perspective, I believe that's what the semantics would have to imply. In the implementation, yes, I'd probably just have it return the zero value of the weak pointer.

EDIT: Oh, it occurs to me that passing nil for a specific type could have a different value than the zero value. (Some per-type sentinel value.) I don't think we should do that. I think the zero value of a weak.Pointer[T] should compare equal with the result of weak.Make[T](nil). Updated the proposal.

[LukeXeon]

go/src/internal/weak/pointer.go

Line 51 in 3776465

type Pointer[T any] struct {

I see "weak pointer" under the "internal" package. Is there any progress on this proposal currently?

[mknyszek]

@LukeXeon This proposal is awaiting review. If accepted, the internal/weak package already contains an implementation that mostly implements the semantics laid out here. It could just be moved out of internal with a few minor tweaks. Note that, if the proposal is accepted, this would land in Go 1.24, not the upcoming Go 1.23 (it's already too late for Go 1.23).

[eihigh]

Unlike server programs that allocate and release memory for each request and persist it in the DB, a weak pointer is essential for client programs that hold multiple containers or partially release items. I feel that Go lacks support for such programs.

(As an aside, #64777 is another example of a feature needed for client programs)

[rsc]

In our discussion yesterday, @bradfitz asked if weak pointers made it possible to maintain a map of expensive derived information about something without preventing the GC of that something. Here is a worked example of how weak pointer enables that:

var cache struct {
    mu sync.Mutex
    m map[weak.Pointer[Foo]]*derived
}

func init() {
    cache.m = make(map[weak.Pointer[Foo]]*derived)
}

func cached(f *Foo) *derived {
    cache.mu.Lock()
    defer cache.mu.Unlock()

    p := weak.Make(f)
    d := cache.m[p]
    if d != nil {
        return d
    }
    d = expensiveComputation(f)
    cache.m[p] = d
    runtime.AddCleanup(f, deleteP, p)
}

func deleteP(p weak.Pointer[Foo]) {
    cache.mu.Lock()
    defer cache.mu.Unlock()

    delete(cache.m, p)
}

I am assuming runtime.AddCleanup from #67535, which is guaranteed to work with any pointer f.
(SetFinalizer might break things if f already had a finalizer, or if f was inside another object.)

[thediveo]

@rsc can this please find its way into the official documentation or alternatively the Tour of Go? Such things really need to be easily accessible, and not buried only in an issue comment.

[rsc]

I think it would make sense for this to be an example in the weak package, if the proposal is accepted. Putting it in the Go tour seems TMI.

[thediveo]

Yeah, it could otherwise become a "Tor-Tour of Go" (sorry, couldn't resist)

[rsc]

Following up on my comment from last week, here is a potential weak cache abstraction that avoids holding the lock during expensiveComputation and also wraps up the idioms nicely so you don't have to retype them. I am not proposing to add it to the package (others can argue for that if they want) but it's here as an example, and we can include it as an example in the package too.

type Cache[K any, V any] struct {
    f func(*K) V
    m atomic.Map[weak.Pointer[K], func() V]
}

func NewCache[K comparable, V any](f func(*K)V) *Cache[K, V] {
    return &Cache[K, V]{f: f}
}

func (c *Cache[K, V]) Get(k *K) V {
    kw := weak.Make(k)
    vf, ok := c.m.Load(kw)
    if ok {
        return vf()
    }
    vf = sync.OnceValue(func() V { return c.f(k) })
    vf, loaded := c.m.LoadOrStore(kw)
    if !loaded {
        // Stored kw→vf to c.m; add the cleanup.
        runtime.AddCleanup(k, c.cleanup, kw)
    }
    return vf()
}

func (c *Cache[K, V]) cleanup(kw weak.Pointer[K]) {
    c.m.Delete(kw)
}

var cached = NewCache(expensiveComputation)

[DmitriyMV]

@rsc

Since the cache doesn't do weak -> strong pointer, and with current GC this should also work, no?

type Cache[K any, V any] struct {
    f func(*K) V
    m atomic.Map[uintptr, func() V]
}

func NewCache[K comparable, V any](f func(*K)V) *Cache[K, V] {
    return &Cache[K, V]{f: f}
}

func (c *Cache[K, V]) Get(k *K) V {
    kw := uintptr(unsafe.Pointer((k))
    vf, ok := c.m.Load(kw)
    if ok {
        return vf()
    }
    vf = sync.OnceValue(func() V { return c.f(k) })
    vf, loaded := c.m.LoadOrStore(kw)
    if !loaded {
        // Stored kw→vf to c.m; add the cleanup.
        runtime.AddCleanup(k, c.cleanup, kw)
    }
    return vf()
}

func (c *Cache[K, V]) cleanup(kw uintptr) {
    c.m.Delete(kw)
}

var cached = NewCache(expensiveComputation)

[rsc]

@DmitriyMV There is a race in that code. It could theoretically happen that the GC identifies k as garbage, puts it back on a free list for future allocation, queues the cleanup, and then the program allocates a new k, gets the recycled address, and reuses the stale value because the cleanup has not gotten a chance to run yet. (It's also not guaranteed to work in an implementation that moves objects, but objects aren't moving today except on the stack, and k escapes to the heap so it won't be a stack object in the current implementation.)

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

[rsc]

Have all remaining concerns about this proposal been addressed?

The details are in the top comment under the "Proposal" heading.

[ChrisHines]

I am trying to figure out what the atomic.Map[weak.Pointer[K], func() V] refers to in @rsc's example in #67552 (comment).

Is that the sync.MapOf (or maybe it is sync/v2.Map now) proposed in #47657 (which I think is on hold)?

While searching for that I also came across another related proposal I didn't see referenced here yet: #43615.

Russ's example also uses runtime.AddCleanup from #67535 which is not approved yet.

Hopefully these cross-refs are useful to someone, but also it would seem we cannot use that example in the weak package docs if the v2/sync.Map or AddCleanup are not available at the time.

[Merovius]

@ChrisHines You can't use the example as written, but you can use sync.Map with type-assertions instead. Or one of the third-party generic concurrency-safe map packages.

[RLH]

I once came to the conclusion that ephemorons ( https://dl.acm.org/doi/pdf/10.1145/263698.263733) were better than weak pointers and starting with .NET many other post Java languages have come to the same conclusion and implemented them (see https://en.wikipedia.org/wiki/Ephemeron for a list). Ephemerons solve some thorny key/value problems where reachability of key should be independent of the value structure thus allowing value to reference key without keeping key alive. The GC trace implementation is 3 pass instead of the current 2 pass and complexity is O(ND) where N is the number of unreachable ephemerons and D is the depth of the structures needing to the traced from them in pass 3. I suspect if we do weak pointers there will be a request for ephemerons once users run into the problems. I have not thought through the concurrency issues beyond noticing that Go would be the first to deal with such issues. Implementing iterators that can reference keys implicitly are another problem I haven't thought through. In any case if Go doesn't implement ephemorons this issue should track the discussion..

…

On Thu, Aug 15, 2024 at 1:20 AM Axel Wagner ***@***.***> wrote: @ChrisHines <https://github.com/ChrisHines> You can't use the example as written, but you can use sync.Map with type-assertions instead. — Reply to this email directly, view it on GitHub <#67552 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAHNNH4F64GQSXLL2HH3FFDZRQ3AZAVCNFSM6AAAAABICGOSGKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEOJQGY2DSNJWGU> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[mknyszek]

Hi Rick! I'm glad you brought up ephemerons -- they resolve a real issue when working with weak pairs (like in maps) and this proposal certainly should mention them somewhere. This issue will almost certainly come up in the future.

TL;DR: My gut feeling is we won't regret the weak pointers as described in this proposal.

And now, the long version...

In general, my main gripe with ephemerons is the value side. The question on my mind is "which value?" Having only one value for each possible key runs into composability problems like SetFinalizer, so I think that's a no-go.

.NET 4.0 introduced the ConditionalWeakTable which you have to use to specify which value you mean, but I think it ends up being insufficient for some use-cases (like the unique package; that clearly exists now, so I'm thinking any such class of problems). .NET 6.0 later made the underlying abstraction, DependentHandle, public. Maybe that's something we'd want? Some explicit handle representing the dependent association?

EDIT: A previous version of this comment contained an example that wasn't totally coherent. I've replaced it below with something much clearer.

Like, I think in the spirit of Russ' cache example, given both DependentHandle and ConditionalWeakTable, one might express the map behind such a cache as:

ConditionalWeakTable[K, func() DependentHandle[K, V]]

... in order to avoid any leak issues in case the value-generating closure or the cached value itself containing a strong reference to the key. (Which seems unlikely, but is of course still possible.) Since ConditionalWeakTable is implemented using DependentHandle, in theory DependentHandle is all you need to be provided by the runtime for this use-case.

I haven't fully worked out the details, but here's what I think DependentHandle would look like:

package weak

// DependentHandle is an association between a pointer to a value of type K, the key,
// and some value of type V, the value. The key pointer is treated as a weak pointer, and
// the value is only considered reachable if the key is reachable.
type DependentHandle[K, V] struct {
    // unexported fields
}
func NewDependentHandle[K, V](key *K, value V) DependentHandle[K, V]
func (d DependentHandle[K, V]) Key() *K
func (d DependentHandle[K, V]) Value() (V, bool)

DependentHandle is interesting, because I think you can define a weak pointer as:

package weak

type Pointer[T] struct {
    handle DependentHandle[T, *T]
}

func Make[T any](t *T) Pointer[T] {
    return Pointer[T]{NewDependentHandle[T, *T](t, t)}
}

func (p Pointer[T]) Value() *T {
    v, ok := p.handle.Value()
    if ok {
        return v
    }
    return nil
}

This is not quite a perfect mapping. What's lost is the equality semantics that this proposal has for weak pointers. In fact, there's a general problem here with dependent handles and maps: how does one define the key type? A simple map[DependentHandle[K, *K]]DependentHandle[K, V] doesn't quite work, because DependentHandle aren't forgeable in the same way that weak pointers are forgeable. You can build a custom map type utilizing DependentHandle, but that's a bit disappointing. If we defined both a weak.Pointer and weak.DependentHandle, then you could write map[weak.Pointer[K]]DependentHandle[K, V] and I believe the right semantics fall out nicely.

So... my gut feeling is that we won't regret weak pointers, and we may just end up with both. I think this state of things makes sense to me, but I'm happy to be proven wrong. The weak pointers as described in this proposal are fairly simple and straightforward (both in implementation and usage), and have clean semantics that fall out nicely from the API.

On a final note, the implementation complexity of ephemerons/DependentHandle is also a bit unfortunate, what with the traditional "extra GC phase" implementation strategy. I think it might be possible to simplify this by handling ephemerons while greying objects:

1. Hold ephemeron values weakly via specials.
2. When an object is greyed, cheaply check some metadata (we're already in the guts of the mspan at that point, so we could probably have an extra bit next to the mark bits or put a bit in the allocation header to avoid another cache miss).
3. If there's at least one ephemeron, do a slower lookup for the ephemeron specials, iterate over them, and queue the weakly-held values with the GC.

Of course, the downside here is the extra check on the mark hot path. As I alluded to in (2) above, I suspect we can hide this cost, but not without some engineering work.

(As an additional tangential note, I think Java never got ephemerons, but I'm not sure why.)

[mknyszek]

I definitely got some things wrong in my previous comment earlier -- I've corrected them now. I've also worked out an example of how ephemerons might be exposed in Go, but there are some difficulties with composability and defining comparability on an ephemeron, such that it actually can be used in all the same ways. I think on a theoretical level you can write your code in most (maybe all?) use-cases to use an ephemeron instead, but it's more complex and may require you to reimplement a lot more than you bargained for (like, a new special map implementation).

So, I think there's still some utility to keeping weak pointers around, and I also don't think we should ignore the complexity (and possible performance difficulties) introduced by an ephemeron implementation. I'm also happy to hear other opinions.

[Merovius]

@bdbyrne

Is it possible for two pointers to compare equal if they were created from distinct objects? E.g. the first was reclaimed and its memory subsequently reused.

For an object to be reclaimed, there can't be any pointers to it anymore. So, no.

Although the language is unambiguous, can it be strengthened to be "if and only if the original pointer was reclaimed"?

"If and only if" is not true under the proposed API. It also returns nil if the pointer passed to Make is nil (last paragraph is the doc string of Make).

[DeedleFake]

For an object to be reclaimed, there can't be any pointers to it anymore. So, no.

I think the scenario in question is one where you have a weak pointer to a and all other references are gone so a gets collected. Then, later, b is allocated with the same address that a had previously. Will a new weak pointer to b compare equal to any leftover weak pointers to a?

[Merovius]

Ah, that makes sense. The doc comment says

Two Pointer values compare equal if the pointers that they were created from compare equal. This property is retained even after the object referenced by the pointer used to create a weak reference is reclaimed.

I would read that as "yes, in that scenario, the weak pointers are equal", which does seem strange. Especially if it would mean that (by a strict reading) you would now have two weak pointers comparing equal, with one returning nil from Value() and one returning a non-nil pointer. The only way I could reconcile that is by the runtime ruling out that an address is re-used as long as it is still stored in a weak pointer.

So, really "I don't know" and I'll step back from this question, sorry for the noise :)

[mknyszek]

Is it possible for two pointers to compare equal if they were created from distinct objects? E.g. the first was reclaimed and its memory subsequently reused.

No, that is not possible. Note that this can't be true for things like using weak pointers in maps to be useful.

I would read that as "yes, in that scenario, the weak pointers are equal", which does seem strange. Especially if it would mean that (by a strict reading) you would now have two weak pointers comparing equal, with one returning nil from Value() and one returning a non-nil pointer.

Perhaps I didn't explain this well in the original proposal, but weak pointers should be considered to be updated atomically, globally. It's not possible to have any skew, where one simultaneously returns nil and another does not.

The only way I could reconcile that is by the runtime ruling out that an address is re-used as long as it is still stored in a weak pointer.

This is kind of quarantining of memory not necessary, and it would be leaky. The implementation part of the proposal describes how this would work. In short, weak pointers point are themselves objects which are mapped 1:1 with some offset in some other object. The address of each "weak pointer object" at determines its identity.

[bdbyrne]

No, that is not possible. Note that this can't be true for things like using weak pointers in maps to be useful.

Great! Could this also be strengthened in the documentation, such as "Two Pointer values compare equal if and only if the pointers..."? It's not clear to intuit this property in the context of pointers to reclaimed objects.

Edit: removed the second portion, I believe I realized my mistake.

[rsc]

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group

The details are in the top comment under the "Proposal" heading.

[gopherbot]

Change https://go.dev/cl/628455 mentions this issue: weak: move internal/weak to weak, and update according to proposal

[gopherbot]

Change https://go.dev/cl/637555 mentions this issue: _content/doc/gc-guide: add section on object death features

[lmb]

@mknyszek is it intentional that weak pointers are freely convertible between each other?

	p := "hey you!"
	a := weak.Make(&p)
	fmt.Println(*a.Value())
	fmt.Println(*((weak.Pointer[uint])(a)).Value())
	runtime.KeepAlive(p)

See https://go.dev/play/p/UYCA76_Oxcv?v=gotip

[mateusz834]

@lmb Thanks, opened #71583 to mark this as a release-blocker.

[thepudds]

I wonder if you could do something like:

 type Pointer[T any] struct {
-       u unsafe.Pointer
+       u *T
 }

I am about to give that a try.

[gopherbot]

Change https://go.dev/cl/647215 mentions this issue: weak: disallow type conversions of Pointer[T]

[thepudds]

#67552 (comment) was not a good idea. (I could blame my pre-coffee state, but probably better just to blame myself).

I instead sent https://go.dev/cl/647195, which follows the pattern that sync/atomic.Pointer used to avoid a similar problem.

[mknyszek]

@lmb Nope, not intentional. Thanks all for the quick response here.

Just for completeness, the right fix is _ [0]*T, which is what @thepudds' CL does. At the very least we should probably have the standard library's API check look for this. I suspect it's basically never going to be intentional to allow such conversions...