unique: new package with unique.Handle #62483

mknyszek · 2023-09-06T16:52:19Z

Proposal: `unique` package

Updated: 10 April 2024

Oct 4th EDIT: Changed package name from "intern" to "unique" and renamed "Symbol" to "Handle" based on feedback.
Apr 10th EDIT: Updated the proposal to describe the actual implementation. Notably, map entries can be dropped after just a single GC cycle instead of two, and there's no more object resurrection, which has several well-known problems.

CC @golang/runtime

Motivation

The lack of runtime support for interning in Go represents a gap with other languages. Demand in the Go community for a weak map and/or string interning has shown up in a few GitHub issues over the years. Although the section of the community requesting these features is quite small, we see the consequences of not having built-in support for this functionality in the form of the go4.org/intern package.

go4.org/intern is a package that implements a global intern pool. Its goals are two-fold: intern data to deduplicate copies, and provide fast comparisons for such interned data. Functionally, it returns a unique global identity for every value placed into it. That value is weakly held by the pool's internals, to avoid letting the pool accumulate in an unbounded manner. This implementation follows in the footsteps of Lisp: interning a value produces a "symbol" that may be used for a fast direct comparison and provides a method through which the interned value may be recovered.

Although it has only 4 direct importers, it is transitively used quite widely (estimated 0.1% of modules) thanks to use by inet.af/netaddr (reverse module deps), which uses it to deduplicate strings and reduce the cost of their comparisons. This has caused friction within the ecosystem because go4.org/intern makes assumptions about the implementation of Go. In particular, it imports the package go4.org/unsafe/assume-no-moving-gc to validate those assumptions. That package, by design, needs to be updated with every release of Go.

inet.af/netaddr's functionality has also recently been merged into the standard library as the net/netip package, bringing along with it a copy of go4.org/intern as the internal/intern package. Furthermore, go4.org/unsafe/assume-no-moving-gc now references an internal Go runtime variable to avoid having to update every release.

Although the immediate issue has been mitigated, the gap in functionality remains, and we now have a copy of go4.org/intern in the standard library anyway.

Goals

The goal of this proposal is to tidy up internal/intern's interface with generics, integrate it more tightly into the runtime (for efficiency and future-proofing), and expose it as a standard library package.

This proposal will also motivate why we should move forward with an API that's similar go4.org/intern and not some other direct or indirect ways of enabling efficient value interning.

Design

We more-or-less propose to move the go4.org/intern package API into the standard library, but with a few tweaks. The biggest difference is that go4.org/intern uses an interface to represent the "key" part of the mapping, with a special case for strings (GetByString) to avoid an additional allocation for the string header. Using generics, we can avoid these additional allocations while also improving type-safety and ergonomics.

Here's a sketch of the revised API, which will live in a new package called "unique":

package unique

// Make returns a globally unique handle for a value of type T. Handles
// are equal if and only if the values used to produce them are equal.
func Make[T comparable](value T) Handle[T] {
    ...
}

// Handle is a globally unique identity for some value of type T.
//
// It is trivially and efficiently comparable with other Handle[T] for the same T.
//
// If the value used to create the symbol is the same, the symbols are guaranteed
// to be equal.
type Handle[T comparable] struct {
    value *T
}

// Value returns a shallow copy of the T value that produced the Handle.
func (h Handle[T]) Value() T {
    return *h.value
}

The unique package must maintain an internal mapping of values to globally unique symbols, which risks growing without bound. However, once no copies of symbols produced by Make are reachable, the program loses access to that globally unique identity. The intern package is then free to produce a new one without the program noticing. If it can produce a new one, it can just as well delete the old one during that time period in which no copy of a symbol exists for a given value.

In practice, integration with the garbage collector is necessary to achieve this, introducing the risk of leaking details about the garbage collector's implementation.

A key property to consider with functionality that relies on specific behavior from the garbage collector is whether it preserves the illusion that the executing program has infinite memory (with a GC there's a malloc but no free). The utility of such an illusion is that it makes programs significantly simpler to reason about. When programs are able to observe the fact that the garbage collector reclaimed memory, it is possible for programs to rely on non-deterministic properties of that reclamation. Finalizers are a good example of a feature that breaks the illusion and are difficult to use correctly.

Luckily, it's not possible for programs to notice when New returns a different Handle[T] precisely because it can produce new symbols without the program noticing. Therefore, it's not possible for a program to observe when memory is reclaimed. (Someone could use the unsafe package to write down the Handle[T]'s internal value as a uintptr, but that specifically requires the use of unsafe. One also can't do much with that uintptr; casting that back to a pointer violates the unsafe.Pointer rules.)

Implementation

The core data structure is approximately a map[any]*T, where the *T is a weak reference. The runtime fully controls the *T created here, so it would attach a special that represents a handle to the value that can go nil once the object is reclaimed. Once the *T is no longer referenced, the GC will clear the handle. Later, a background goroutine will clean up map entries with nil handles.

Note that user code here is racing with the garbage collector. It's possible that in between the garbage collector noticing that there are no more references to the *T and the value being collected, the program may read the value out and produce a new strong pointer to the *T. To alleviate this, the reader must synchronize with the garbage collector. To avoid issues with object resurrection and to allow for immediate reclamation of memory, the reader can simply ensure the span containing the T is always swept before accessing the weak pointer handle. The only costs here are thus the highly-optimized span lookup and, once per GC, a single goroutine may need to sweep the span, which is generally quite fast. Note that if a value is being lookup frequently, then only the first lookup in each GC cycle will need to sweep; otherwise it'll return quickly.

This is quite different to the implementation of go4.org/intern, and is only possible by accessing runtime internals. It allows us to reclaim memory in just a single GC cycle instead of the 3 that are currently required by the intern package.

Next is the map implementation itself. Because the map will be global, the underlying data structure will need to be thread-safe. Unfortunately there are far too many choices for a concurrent map data structure, so we need to cut them down by setting some goals and requirements. Here's a list:

Reads are expected to be much more popular than writes.
- Serializing writers (though allowing them to be concurrent with readers) is likely acceptable.
Reads from the map should be allowed to execute concurrently with one another.
Deletions from the map can happen relatively rarely (once per GC), in the background, and in bulk.
Iteration is not strictly necessary since a candidate list of removals may be maintained by the GC.
- If it turns out to be desirable, there could only ever be a single iterator at a time for deletion.
To eliminate an indirection, being able to directly mutate map values would be nice.
The map needs to be able to grow and shrink efficiently.

A traditional bucketed hash map is not terribly difficult to make concurrently under these circumstances, but has the downside that incremental growth and shrinking of such a map is quite complicated. Trying to extend the existing map implementation with concurrency features is also likely to be complicated.

Another option is to use something like an adaptive radix tree over 8-byte hash values. The growth and shrinking of such a tree comes naturally, and making them concurrent within the bounds of our requirements isn't too complicated. The downside is poor locality because of the tree structure. I suspect that at least to begin with, something like this will provide good enough performance.

For the actual implementation, we pick a simplified form of the adaptive radix tree specialized for uintptr values (hashes), essentially forming a hash-trie. It's straightforward to make reads out of this data structure perfectly scalable. Insertions and deletions will be performed using fine-grained locking techniques, reducing contention.

As an additional note on performance, calls to Make should always avoid allocating in the case where the provided value is already in the map. Meanwhile they should explicitly clone the value when adding it to the map. (This means if T is a struct with pointers in it, the values those pointers point to are almost always going to be forced to escape to the heap, like with regular Go maps.)

Risks

API design impact

The fact that interned values are represented by a type Handle[T] means that details around interning may encourage two versions of APIs, one supporting interned values and the other not. Contrast this with an "opaque" alternative (see "Opaque string interning" in the alternatives section) that makes no distinction between interned and non-interned values in the type system.

I believe this is a legitimate concern, but suspect that it will mostly be mitigated in practice. Interning is a somewhat niche technique that helps performance dramatically in certain cases, but only in those certain cases that clearly benefit from data deduplication and/or fast comparisons of data. Elsewhere it's more clearly just cumbersome and simple microbenchmarks should reveal the slowdown.

Thus, I think "polluting" APIs in the cases where it's useful is likely worth the tradeoff, and it's sufficiently cumbersome to use that where it's not necessary it will simply be ignored. I believe the fact that go4.org/intern has relatively few direct importers supports this hypothesis.

Poor performance

One situation we absolutely want to avoid is performance issues like with Java's String.intern. My best understanding of the situation (as of when the linked blog post was written) is that:

The global intern map is not resizable, so once the map fills up, lookups become expensive.
The global intern map leaks memory (map entries are not bound to the lifetime of their values).
The global intern map is part of the GC root set, and it's not well accounted for by the GC (it's just scanned during a STW), leading to high worst-case pause times when the map has many entries.

I believe we avoid all three of these issues in the implementation described above. The third one is less obvious if you're not familiar with the existing Go GC implementation. Briefly, the global intern map would only be a GC root insofar as any global variable is a GC root (i.e. the entire map would not be part of the root set, just the reference to it). And even if it was fully part of the root set, the Go GC already shards and scans the root set concurrently with the mutator executing. Hence, no pause-time impact.

Disclaimer: I don't know if this is still an issue in the Java world; I didn't look into this too deeply. If it's not, then that's great to hear. Nevertheless, it's still worthwhile to learn from past attempts at interning.

Alternatives considered

Opaque string interning

One alternative is interning just for strings, which is a common case. For instance:

package strings

// Intern takes a string and returns a string with equivalent contents,
// though possibly one that shares memory with other strings. This can
// be used to save memory in applications with many duplicate string
// values. If a string is successfully interned, a copy is always made.
func Intern(s string) string

Although such an API is temptingly simple, it's not really useful for any other kind of data structure. Only strings are properly immutable in the language.

Furthermore, because the interning is opaque, we don't get the full benefit of cheap comparisons out-of-the-box. The string comparison fast path would be taken more frequently, but when there's no pointer equality the string data would still need to be compared. To get the full benefit, there would need to be some additional runtime and/or compiler support to identify when two interned strings are being compared, which may end up slowing down non-interned string operations as well.

This is still worth considering for the future, but doesn't properly address the use-cases this proposal intends to address.

Background string deduplication

Another alternative is to just have the runtime deduplicate strings in the background. For instance, the JVM G1 garbage collector has a flag for such a feature (off by default). The advantage of this approach is the programmer has to set one flag and they get to save on memory costs.

However, like the previous alternative, this only really applies to strings again, because only strings are properly immutable at the language level. The other problem is that this feature would need to be opt-in, requiring a new top-level runtime knob. (Presumably this feature isn't on by default because it's not always worth the CPU cost in the garbage collector.) It's also substantially more complex to implement this in the Go garbage collector, because it doesn't currently know the type of anything in the heap.

Weak references

An even more general alternative to the proposed API is to just add support for weak references to the standard library and/or language. After all, the proposed implementation conceptually just uses a weak reference in its implementation anyway.

The main issue with weak references is that they're very hard to use in a system with tracing garbage collection, since they can turn out to be nil at very surprising times (or possibly never). Fundamentally, they break the aforementioned infinite memory illusion, because they reveal when memory is reclaimed.

The bar is extremely high for adding anything this difficult to use, and I believe we should prefer easier-to-use abstractions as much as possible.

The text was updated successfully, but these errors were encountered:

seebs · 2023-09-06T17:56:43Z

Oooh, I like it.

I note that I've wanted both weak-keys and weak-value maps, to solve different problems. A weakly-keyed map[*T]metadata would be used in cases where, if a given T still exists, I want to retain information related to it, but if the item ceases to exist, I don't need to keep the metadata anymore, and I don't want my map to keep the T existing.

You could sort of envision the symbol mapping working this way, except that it solves a slightly different problem. In particular, a key point of the interning is that if no one still has a given symbol, it Could Have Been Anything, so it's fine if the next time someone asks, they get a new one. With a hypothetical weakly-keyed-map approach, the existence of the value-the-symbol-denotes would potentially prevent this.

Not sure whether it makes more sense to try to view these as fundamentally different questions, or as inherently-related questions, because I think weak-reference maps very close to entirely solve the interning problem.

mknyszek · 2023-09-06T18:00:11Z

@seebs We went deep down the weak-keyed maps (specifically, ephemerons, which preserve the GC abstraction) rabbit hole as a solution for interning. I think we concluded that it's insufficient for interning, though they are useful for other purposes (as you note, map[*T]metadata). I actually have a rough draft of a proposal for that somewhere, but we focused on this because it seems more immediately important. (EDIT: I have to look back in my notes and chat history to recall why weak-keyed maps were insufficient for interning.)

RE: Weak-value maps, I believe I came to the conclusion that those are basically weak references, and thus suffer from the same issues.

dsnet · 2023-09-06T18:13:17Z

String interning with the proposed API would be equivalent to this right?

var b []byte = ...
s := intern.New(string(b)).Value()

where the string(b) conversion does not allocate, but intern.New may allocate if the string is not found.

dsnet · 2023-09-06T18:16:22Z

IIUC, this doesn't solve the global type cache problem because you can't attach a value to the key.

Quite a few packages have a global map that caches a complex data structure for a Go type:

go/src/encoding/json/encode.go

Line 336 in e844d72

var encoderCache sync.Map // map[reflect.Type]encoderFunc

Today, there's a memory leak in "json" where dynamically constructed types with reflect.New can never be reclaimed because json.encoderCache is never cleared.

mknyszek · 2023-09-06T18:21:15Z

String interning with the proposed API would be equivalent to this right?

That's basically right, but in this design you're encouraged to keep the Symbol[string] instead of immediately getting the string header back out. As soon as symbols disappear, the internal map entry for them becomes eligible for cleanup. Of course, it won't get cleaned up until at least the next GC cycle, so subsequent lookups will still probably be a hit in the map. But you'll likely get better behavior out of keeping the symbol. Plus, you get a cheap comparison.

dsnet · 2023-09-06T18:29:59Z

you're encouraged to keep the Symbol[string] instead of immediately getting the string header back out

That seems a bit unfortunate. The "json" package when unmarshaling would be storing a string into the user type. There's no place to hold onto a Symbol[string] for long, storing it somewhere leads us back to the same problem this is trying to solve. That said, there is still benefit since we will share string values within a GC cycle.

mknyszek · 2023-09-06T20:25:30Z

EDIT: I have to look back in my notes and chat history to recall why weak-keyed maps were insufficient for interning.

I think the reason weak-keyed maps weren't a great solution because if you allow anything comparable except a pointer, you end up being able to break the GC abstraction. Heap pointers are special because they are an unforgeable identity. So type WeakMap[K any, PK interface{ *K }, V any] struct { ... } is fine, but allowing all comparable types as keys is not because you can construct a value such that you observe when a map entry is reclaimed.

Notably, for the pointers-only case, it's also surprisingly easy to implement, because the Go runtime already has a way to associate arbitrary data with a pointer. But, you probably also want that weak map to be cyclic. That is WeakMap[*T, *T] should still be allowed to collect the map entry where the same *T exists as a value. That's more complicated but is certainly possible to do. It's just going to impact the mark path, so it needs to be designed carefully to be fast.

IIUC, this doesn't solve the global type cache problem because you can't attach a value to the key.

It doesn't. A WeakMap would, but you'd have to unwrap the reflect.Type into the underlying *internal/abi.Type, which is at least fine for std. This particular case might be common enough to warrant a TypeMap or something.

That seems a bit unfortunate. The "json" package when unmarshaling would be storing a string into the user type. There's no place to hold onto a Symbol[string] for long, storing it somewhere leads us back to the same problem this is trying to solve. That said, there is still benefit since we will share string values within a GC cycle.

I believe the only thing that would fully satisfy this particular use-case is the "opaque string interning" alternative. It may be worth considering in the future as it's somewhat orthogonal to this.

I'm pessimistic that there's a single API that will solve all these problems, but I think this package is a decent starting point.

zikaeroh · 2023-09-07T02:49:52Z

you're encouraged to keep the Symbol[string] instead of immediately getting the string header back out

That seems a bit unfortunate. The "json" package when unmarshaling would be storing a string into the user type. There's no place to hold onto a Symbol[string] for long, storing it somewhere leads us back to the same problem this is trying to solve. That said, there is still benefit since we will share string values within a GC cycle.

FWIW there is also @josharian's string interning library, which works somewhat as you've described by keeping a sync.Pool of map[string]string around such that strings are mostly interned until the pool gets rid of its entries: https://pkg.go.dev/github.com/josharian/intern

It seems like it'd be possible to create a sync.Pool of map[Symbol[string]]string instead such that the Symbol[string]s get kept around a little longer... but I guess maybe this isn't an improvement because someone's still going to have to hash the string and this just shifts the work elsewhere?

(I do agree that it's unfortunate that the Symbol has to be kept around to ensure that it gets reused.)

mknyszek · 2023-09-07T03:06:18Z

(I do agree that it's unfortunate that the Symbol has to be kept around to ensure that it gets reused.)

I suppose we could make an exception for strings and have the Symbol refer directly to the backing store for the string, though now we need to carry around a length in each Symbol as well. (It would just be zero for all other types.) So, the cheap comparison becomes slightly less cheap. Maybe that's fine?

FWIW, I think strings are a reasonable exception given that they're the only type that is defined as a reference yet behaves like a value type.

rsc · 2023-09-07T13:53:31Z

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

mknyszek · 2023-09-07T16:50:06Z

I suppose we could make an exception for strings and have the Symbol refer directly to the backing store for the string, though now we need to carry around a length in each Symbol as well. (It would just be zero for all other types.) So, the cheap comparison becomes slightly less cheap. Maybe that's fine?

It occurs to me that if we're going to force a copy and a new allocation for an insertion, then strings are entirely uniquely identifiable via their data pointer (regardless of length). The Value method is slightly more complicated since we'd have to store the length next to the data, but it should actually be doable to properly intern strings and also enable using Symbol[string] for cheap (single pointer) comparisons. The downside of this approach is it prevents optimizations like deduplicating strings in the map by prefix. But maybe that's fine.

TheCoreMan · 2023-09-09T09:29:22Z

It took me three-four reads to understand, but it sounds like a useful addition to the standard library.

What I'm wondering is if there's an automatic way in the profiling tooling to recommend "hey, you should intern this value" as part of the output. Otherwise I can't really see the usage of intern becoming more ubiquitous, and then adding the value of adding it to the stdlib is diminished (integrating it more tightly to the runtime is not without it's costs!)

karianna · 2023-09-14T05:06:49Z

Hi all, I'm still learning about Golang (I'm the group manager for Java and now Golang @ MSFT), so take all of this with that in mind :-).

String Dedup - I wanted to add a quick note that in Java, String Deduplication is accessible to all of the GCs but it is still a runtime flag to enable. https://malloc.se/blog/zgc-jdk18 for the extra detail there. As you can imagine, since it's not on by default it's usage is pretty low, not sure 'we' got the user experience right there.

String intern perf - Although I know you have a different design in mind, I (or more likely one of our real engineers ;-)) will take a look at Java's intern performance and see if the concerns raised above still hold true or if that was patched or a new design put in place. All good things to learn either way I guess. I'll post back here if there's anything interesting.

public + internal? - Is there a use case where keeping an internal version of this for the runtime that can evolve more rapidly for internal only needs as well as an external public facing package make sense? I know if Java they started doing this a bunch with certain com.sun packages within the new module system.

weak references - Your note about using weak references resonates! Speaking from Java-land, its memory management challenges are usually confined to the realms of issues with strongly referenced memory leaks or whatever, but on the odd occasion when WeakReferences go wrong then its an order of magnitude harder to debug with tooling etc. That might just be more a reflection on their design or gaps in o11y tooling but for me its always a case of this is where some Dragons live.

rsc · 2023-09-20T17:47:26Z

'intern' may not be the best name for this package. It requires knowledge of other systems (particularly Lisp) that not everyone has. Also intern here is not the same meaning as intern string in Java. The package is about creating unique identities for values, so what about package unique? Then the bikeshed becomes what the name of the type is.

'Symbol' has the right meaning for people with a Lisp or compiler background, but not to others. Symbol has many other meanings in many other parts of CS.

unique.Handle seems like it strikes the right notes: the thing is a Handle, and it aligns with cgo.Handle too (although this one uses generics but cgo predated them).

package unique

// New returns a globally unique symbol for a value of type T. Symbols
// are equal if and only if the values used to produce them are equal.
func New[T comparable](value T) Handle[T] {
    ...
}

// Symbol is a globally unique identity for some value of type T.
//
// It is trivially and efficiently comparable with other Symbol[T] for the same T.
//
// If the value used to create the symbol is the same, the symbols are guaranteed
// to be equal.
type Handle[T comparable] struct {
    value *T
}

// Value returns a shallow copy of the T value that produced the Symbol.
func (h Handle[T]) Value() T {
    return *h.value
}

mknyszek · 2023-09-20T17:54:18Z

I don't feel strongly about the name. I also think both unique and Handle are reasonable. Happy to update the proposal if that's the consensus.

Merovius · 2023-10-03T05:11:32Z

While we are talking names: I dislike New. 1. New generally is connoted with returning pointers, 2. unique.New reads strangely and 3. it doesn't actually return a new Handle/Symbol, (hopefully) most of the time. I think Make is slightly (though maybe imperceptibly) better. I can't really come up with a significantly better one.

[edit] Maybe I like unique.Intern(v) 🤔 [/edit]

DeedleFake · 2023-10-03T05:34:44Z

Some JavaScript-inspired bikeshedding:

package symbol

func For[T comparable](v T) Of[T]

The type Of[T comparable] is the part I'm the least enthused by. It's a little weird inside the package, but should hopefully read nicely when actually used, and it's pretty short, which is nice. There's obviously no JavaScript equivalent for that one, though.

josharian · 2023-10-03T13:16:46Z

If we want more raw name fodder, I believe that in Elixir (something like) this is called an atom.

mknyszek · 2023-10-03T15:01:02Z

It might be worth using the term "identity" somewhere here, since that's really what's being created. Putting that together with the verb "make" and the package name "unique", you get:

package unique

func Make[T comparable](value T) Identity[T]

This roughly corresponds to "make a unique identity for this value." In usage:

id := unique.Make(v)

🤷

rabbbit · 2023-11-07T15:51:17Z

Not trying to argue or to change anyone's mind, but just to close the discussion (thank you for your comments @rsc and @dsnet):

and yes one package could make the map big, but big maps are still fast.

Rather than size (large size implies it's a valid use-case for handles), I was more worried about handle generation. A package could ("incorrectly"), create A LOT of short-lived handles that get created and removed all the time.

Also, it seems that the implementation of unique could shard the global map based on the Go type passed to Make

I was talking about different disjoint "categories" of the same (Go) type. A string could be an email, IP address, or HTTP tag - but not simultaneously. The application knows this and can shard, thus reducing the need for runtime sharding. Like above, the primary worry here was part of an application that (unnecessarily) creates a lot of short-lived handles.

Like I said above, perhaps I'm being too pessimistic about the potential misuse of the package.

randall77 · 2023-11-08T02:33:44Z

Random tangentially-related thought ahead:

Can we put all the runtime._types in one of these weak maps? So when no more pointers to that runtime._type exist, the entry itself can be garbage collected.

This is an issue with any of the reflect type-building functions, e.g. reflect.StructOf. Once built, those types live forever. It would be great if we could GC those types from the "uniquification map" as soon as no one references them.

This is very close to the problem that prevents us from GCing plugin invocations. If we could determine that no types from a plugin are still accessible from anywhere, we could unload the plugin (and all of its code). A long outstanding issue #20461. (There are more difficulties than just this one, but it is a big one.)

Perhaps we could start with using this implementation for runtime._types (aka internal/abi.Types). It would require no new ABI so we could use it as a "first customer" experiment that involves no new API.

cherrymui · 2023-11-08T15:46:55Z

Can we put all the runtime._types in one of these weak maps? So when no more pointers to that runtime._type exist, the entry itself can be garbage collected.

Sounds like an interesting idea, probably worth trying.

One issue is that currently we don't always track runtime._type references (and assuming they always live), e.g. they may be referenced from non-heap memory, and in some places in the compiler we treat the first word of an interface header as non-pointer. Tracking them is probably possible but may incur some overhead.

hauntedness · 2024-01-28T05:48:35Z

looks this is a similar implementation to unique value + pool.
so why not directly put it into package sync？
Not a native english speaker，but to me Make is worse name to Intern.
I believe sync.Unique is a nice name.

snglagolev · 2024-01-29T19:29:45Z

@rsc is the unique.Handle[T] a kind of weak reference or not?

Looks like Handle holds pointer to value and Handle.value cannot be collected by GC.

mknyszek · 2024-01-29T20:07:59Z

@hauntedness The proposal is accepted, so barring any serious concerns about the name, I doubt we'll be changing the name at this point.

@snglagolev unique.Handle[T] is not a weak reference. For the proposal to work, it must explicitly not be weak reference, since the whole point is to keep the canonical value being referenced live. The internal map for deduplicating values of type T will retain a pointer to the canonical value via something like a weak reference, but this is not exposed in the interface. (The deduplicating behavior and the fact that stale references get cleaned up in the map is guaranteed though, since that's necessary for the API to be useful.)

snglagolev · 2024-01-29T21:02:54Z

The internal map for deduplicating values of type T will retain a pointer to the canonical value via something like a weak reference, but this is not exposed in the interface.

something like a weak reference will not be accessible outside standard library?

mknyszek · 2024-01-29T21:33:01Z

Please read the proposal in the original post; weak references in the standard library and/or language are discussed briefly as an alternative.

snglagolev · 2024-02-05T19:53:53Z

I just want to understand...

h1 := unique.Make([1024]byte{})
h2 := unique.Make([1024]byte{})
v1 := h1.Value()
v2 := h2.Value()

In this case we have:

h1 is equal to h2
v1 is equal to v2
&v1[0] is not equal &v2[0]

Is this expected behavior for unique?

Merovius · 2024-02-05T20:59:21Z

@snglagolev Yes, I definitely would expect that. Handle.Value returns a copy of the contained value. In this case, the contained value is a [1024]byte. So that gets copied into two new variables v1 and v2 and they obviously have different addresses. Note that for arrays, &x[0] is the same as &x. That is different from strings or slices, in which the value contains a reference.

It should still be noted that you end up with three copies - one in v1, one in v2 and one on the heap (that is in the uniqe storage). And in particular, if v1 and v2 don't escape, while you do incur a copy, you don't incur additional allocations - there will only be one copy on the heap, even though you obtain with h1 and h2 two handles from two arrays. And that h1 == h2, but they won't be as large as a [1024]byte, so comparing them is significantly cheaper.

gopherbot · 2024-04-06T04:00:07Z

Change https://go.dev/cl/573956 mentions this issue: internal/concurrent: add HashTrieMap

gopherbot · 2024-04-06T04:00:07Z

Change https://go.dev/cl/574355 mentions this issue: unique: add unique package and implement Make/Handle

gopherbot · 2024-04-06T04:00:08Z

Change https://go.dev/cl/576297 mentions this issue: internal/weak: add package implementing weak pointers

gopherbot · 2024-04-06T04:00:08Z

Change https://go.dev/cl/573955 mentions this issue: internal/abi: define EmptyInterface, TypeOf, and NoEscape

This change defines two commonly-defined functions and a commonly-defined type in internal/abi to try and deduplicate some definitions. This is motivated by a follow-up CL which will want access to TypeOf in yet another package. There still exist duplicate definitions of all three of these things in the runtime, and this CL doesn't try to handle that yet. There are far too many uses in the runtime to handle manually in a way that feels comfortable; automated refactoring will help. For #62483. Change-Id: I02fc64a28f11af618f6071f94d27f45c135fa8ac Reviewed-on: https://go-review.googlesource.com/c/go/+/573955 Auto-Submit: Michael Knyszek <mknyszek@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: David Chase <drchase@google.com>

This change adds a concurrent hash-trie map implementation to the standard library in the new internal/concurrent package, intended to hold concurrent data structures. (The name comes from how Java names their concurrent data structure library in the standard library.) This data structure is created specially for the upcoming unique package. It is built specifically around frequent successful lookups and comparatively rare insertions and deletions. A valid question is whether this is worth it over a simple locked map. Some microbenchmarks in this new package show that yes, this extra complexity appears to be worth it. Single-threaded performance for LoadOrStore is comparable to a locked map for a map with 128k small string elements. The map scales perfectly up to 24 cores for Loads, which is the maximum available parallelism on my machine. LoadOrStore operations scale less well. Small maps will have a high degree of contention, but for the unique library, small maps are very unlikely to stay small if there are a lot of inserts, since they have a full GC cycle to grow. For #62483. Change-Id: I38e5ac958d19ebdd0c8c02e36720bb3338fe2e35 Reviewed-on: https://go-review.googlesource.com/c/go/+/573956 Reviewed-by: David Chase <drchase@google.com> Auto-Submit: Michael Knyszek <mknyszek@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

This change adds the internal/weak package, which exposes GC-supported weak pointers to the standard library. This is for the upcoming weak package, but may be useful for other future constructs. For #62483. Change-Id: I4aa8fa9400110ad5ea022a43c094051699ccab9d Reviewed-on: https://go-review.googlesource.com/c/go/+/576297 Auto-Submit: Michael Knyszek <mknyszek@google.com> Reviewed-by: David Chase <drchase@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

gopherbot added this to the Proposal milestone Sep 6, 2023

gopherbot added the Proposal label Sep 6, 2023

mknyszek added compiler/runtime Issues related to the Go compiler and/or runtime. and removed Proposal labels Sep 6, 2023

mknyszek modified the milestones: Proposal, Backlog Sep 6, 2023

This comment was marked as resolved.

Sign in to view

seankhliao added the Proposal label Sep 6, 2023

seankhliao modified the milestones: Backlog, Proposal Sep 6, 2023

seankhliao mentioned this issue Sep 14, 2023

proposal: spec: memoization #62637

Closed

rsc changed the title ~~proposal: unique: new package with unique.Handle~~ unique: new package with unique.Handle Nov 2, 2023

rsc modified the milestones: Proposal, Backlog Nov 2, 2023

rsc added Proposal-Accepted and removed Proposal-FinalCommentPeriod labels Nov 2, 2023

kakkoyun mentioned this issue Nov 6, 2023

String interning parca-dev/parca#3927

Open

sylr mentioned this issue Dec 16, 2023

[ENHANCEMENT] Enhance performance scalalang2/golang-fifo#12

Closed

qiulaidongfeng mentioned this issue Jan 21, 2024

proposal: arena: new package providing memory arenas #51317

Open

mknyszek self-assigned this Mar 27, 2024

mknyszek modified the milestones: Backlog, Go1.23 Apr 8, 2024

gopherbot closed this as completed in a088e23 Apr 22, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

unique: new package with unique.Handle #62483

unique: new package with unique.Handle #62483

mknyszek commented Sep 6, 2023 •

edited

seebs commented Sep 6, 2023

mknyszek commented Sep 6, 2023 •

edited

dsnet commented Sep 6, 2023

dsnet commented Sep 6, 2023

mknyszek commented Sep 6, 2023

dsnet commented Sep 6, 2023

mknyszek commented Sep 6, 2023

This comment was marked as resolved.

zikaeroh commented Sep 7, 2023

mknyszek commented Sep 7, 2023

rsc commented Sep 7, 2023

mknyszek commented Sep 7, 2023 •

edited

TheCoreMan commented Sep 9, 2023

karianna commented Sep 14, 2023

rsc commented Sep 20, 2023

mknyszek commented Sep 20, 2023

Merovius commented Oct 3, 2023 •

edited

DeedleFake commented Oct 3, 2023 •

edited

josharian commented Oct 3, 2023

mknyszek commented Oct 3, 2023

rabbbit commented Nov 7, 2023 •

edited

randall77 commented Nov 8, 2023

cherrymui commented Nov 8, 2023

hauntedness commented Jan 28, 2024

snglagolev commented Jan 29, 2024

mknyszek commented Jan 29, 2024

snglagolev commented Jan 29, 2024

mknyszek commented Jan 29, 2024

snglagolev commented Feb 5, 2024

Merovius commented Feb 5, 2024 •

edited

gopherbot commented Apr 6, 2024

gopherbot commented Apr 6, 2024

gopherbot commented Apr 6, 2024

gopherbot commented Apr 6, 2024

unique: new package with unique.Handle #62483

unique: new package with unique.Handle #62483

Comments

mknyszek commented Sep 6, 2023 • edited

Proposal: unique package

Motivation

Goals

Design

Implementation

Risks

API design impact

Poor performance

Alternatives considered

Opaque string interning

Background string deduplication

Weak references

seebs commented Sep 6, 2023

mknyszek commented Sep 6, 2023 • edited

dsnet commented Sep 6, 2023

dsnet commented Sep 6, 2023

mknyszek commented Sep 6, 2023

dsnet commented Sep 6, 2023

mknyszek commented Sep 6, 2023

This comment was marked as resolved.

zikaeroh commented Sep 7, 2023

mknyszek commented Sep 7, 2023

rsc commented Sep 7, 2023

mknyszek commented Sep 7, 2023 • edited

TheCoreMan commented Sep 9, 2023

karianna commented Sep 14, 2023

rsc commented Sep 20, 2023

mknyszek commented Sep 20, 2023

Merovius commented Oct 3, 2023 • edited

DeedleFake commented Oct 3, 2023 • edited

josharian commented Oct 3, 2023

mknyszek commented Oct 3, 2023

rabbbit commented Nov 7, 2023 • edited

randall77 commented Nov 8, 2023

cherrymui commented Nov 8, 2023

hauntedness commented Jan 28, 2024

snglagolev commented Jan 29, 2024

mknyszek commented Jan 29, 2024

snglagolev commented Jan 29, 2024

mknyszek commented Jan 29, 2024

snglagolev commented Feb 5, 2024

Merovius commented Feb 5, 2024 • edited

gopherbot commented Apr 6, 2024

gopherbot commented Apr 6, 2024

gopherbot commented Apr 6, 2024

gopherbot commented Apr 6, 2024

mknyszek commented Sep 6, 2023 •

edited

Proposal: `unique` package

mknyszek commented Sep 6, 2023 •

edited

mknyszek commented Sep 7, 2023 •

edited

Merovius commented Oct 3, 2023 •

edited

DeedleFake commented Oct 3, 2023 •

edited

rabbbit commented Nov 7, 2023 •

edited

Merovius commented Feb 5, 2024 •

edited