Package: unique

package unique Import Path unique (on go.dev) Dependency Relation imports 9 packages, and imported by one package

Involved Source Files canonmap.go clone.go d doc.go The unique package provides facilities for canonicalizing ("interning") comparable values. handle.go

Package-Level Type Names (total 7, in which 1 is exported)

/* sort exporteds by: alphabet | popularity */

type Handle[T] (struct) Type Parameters: T: comparable Handle is a globally unique identity for some value of type T. Two handles compare equal exactly if the two values used to create the handles would have also compared equal. The comparison of two handles is trivial and typically much more efficient than comparing the values used to create them. Fields (only one, which is unexported) /* one unexported ... *//* one unexported: */ value *T Methods (only one, which is exported) ( Handle[T]) Value() T Value returns a shallow copy of the T value that produced the Handle. Value is safe for concurrent use by multiple goroutines. As Outputs Of (at least one exported) func Make[T](value T) Handle[T] As Types Of (total 3, none are exported) /* 3 unexporteds ... *//* 3 unexporteds: */ var net/netip.z0 unique.Handle[addrDetail] var net/netip.z4 unique.Handle[...] var net/netip.z6noz unique.Handle[...]

/* 6 unexporteds ... *//* 6 unexporteds: */

type canonMap[T] (struct) Type Parameters: T: comparable canonMap is a map of T -> *T. The map controls the creation of a canonical *T, and elements of the map are automatically deleted when the canonical *T is no longer referenced. Fields (total 3, none are exported) /* 3 unexporteds ... *//* 3 unexporteds: */ hash func(unsafe.Pointer, uintptr) uintptr root atomic.Pointer[indirect[T]] seed uintptr Methods (total 4, in which 2 are exported) (*canonMap[T]) Load(key T) *T (*canonMap[T]) LoadOrStore(key T) *T /* 2 unexporteds ... *//* 2 unexporteds: */ (*canonMap[T]) cleanup(hash uintptr, wp weak.Pointer[T]) cleanup deletes the entry corresponding to wp in the canon map, if it's still in the map. wp must have a Value method that returns nil by the time this function is called. hash must be the hash of the value that wp once pointed to (that is, the hash of *wp.Value()). (*canonMap[T]) expand(oldEntry, newEntry *entry[T], newHash uintptr, hashShift uint, parent *indirect[T]) *node[T] expand takes oldEntry and newEntry whose hashes conflict from bit 64 down to hashShift and produces a subtree of indirect nodes to hold the two new entries. newHash is the hash of the value in the new entry. As Outputs Of (at least one unexported) /* at least one unexported ... *//* at least one unexported: */ func newCanonMap[T]() *canonMap[T]

type cloneSeq (struct) cloneSeq describes how to clone a value of a particular type. Fields (only one, which is unexported) /* one unexported ... *//* one unexported: */ stringOffsets []uintptr As Outputs Of (at least one unexported) /* at least one unexported ... *//* at least one unexported: */ func makeCloneSeq(typ *abi.Type) cloneSeq As Inputs Of (at least 3, none are exported) /* 3+ unexporteds ... *//* 3+ unexporteds: */ func buildArrayCloneSeq(typ *abi.Type, seq *cloneSeq, baseOffset uintptr) func buildStructCloneSeq(typ *abi.Type, seq *cloneSeq, baseOffset uintptr) func clone[T](value T, seq *cloneSeq) T As Types Of (only one, which is unexported) /* one unexported ... *//* one unexported: */ var singleStringClone

type entry[T] (struct) Type Parameters: T: comparable entry is a leaf node in the hash-trie. Fields (total 5, none are exported) /* 5 unexporteds ... *//* 5 unexporteds: */ hash uintptr key weak.Pointer[T] node node[T] node.isEntry bool overflow atomic.Pointer[entry[T]] // Overflow for hash collisions. Methods (total 5, none are exported) /* 5 unexporteds ... *//* 5 unexporteds: */ (*entry[T]) entry() *entry[T] (*entry[T]) hasWeakPointer(wp weak.Pointer[T]) bool hasWeakPointer returns true if the provided weak pointer can be found in the overflow chain. (*entry[T]) indirect() *indirect[T] (*entry[T]) lookup(key T) (*T, weak.Pointer[T]) lookup finds the entry in the overflow chain that has the provided key. Returns the key's canonical pointer and the weak pointer for that canonical pointer. (*entry[T]) prune() *entry[T] prune removes all entries in the overflow chain whose keys are nil. The caller must hold the lock on e's parent node. As Outputs Of (at least one unexported) /* at least one unexported ... *//* at least one unexported: */ func newEntryNode[T](key T, hash uintptr) (*entry[T], *T, weak.Pointer[T])

type indirect[T] (struct) Type Parameters: T: comparable indirect is an internal node in the hash-trie. Fields (total 6, none are exported) /* 6 unexporteds ... *//* 6 unexporteds: */ children [16]atomic.Pointer[node[T]] dead atomic.Bool mu sync.Mutex // Protects mutation to children and any children that are entry nodes. node node[T] node.isEntry bool parent *indirect[T] Methods (total 3, none are exported) /* 3 unexporteds ... *//* 3 unexporteds: */ (*indirect[T]) empty() bool (*indirect[T]) entry() *entry[T] (*indirect[T]) indirect() *indirect[T] As Outputs Of (at least one unexported) /* at least one unexported ... *//* at least one unexported: */ func newIndirectNode[T](parent *indirect[T]) *indirect[T] As Inputs Of (at least one unexported) /* at least one unexported ... *//* at least one unexported: */ func newIndirectNode[T](parent *indirect[T]) *indirect[T]

type node[T] (struct) Type Parameters: T: comparable node is the header for a node. It's polymorphic and is actually either an entry or an indirect. Fields (only one, which is unexported) /* one unexported ... *//* one unexported: */ isEntry bool Methods (total 2, neither is exported) /* 2 unexporteds ... *//* 2 unexporteds: */ (*node[T]) entry() *entry[T] (*node[T]) indirect() *indirect[T]

type uniqueMap[T] (struct) Type Parameters: T: comparable Fields (total 6, none are exported) /* 6 unexporteds ... *//* 6 unexporteds: */ canonMap *canonMap[T] canonMap.hash func(unsafe.Pointer, uintptr) uintptr canonMap.root atomic.Pointer[indirect[T]] canonMap.seed uintptr cloneSeq cloneSeq cloneSeq.stringOffsets []uintptr Methods (total 4, in which 2 are exported) ( uniqueMap[T]) Load(key T) *T ( uniqueMap[T]) LoadOrStore(key T) *T /* 2 unexporteds ... *//* 2 unexporteds: */ ( uniqueMap[T]) cleanup(hash uintptr, wp weak.Pointer[T]) cleanup deletes the entry corresponding to wp in the canon map, if it's still in the map. wp must have a Value method that returns nil by the time this function is called. hash must be the hash of the value that wp once pointed to (that is, the hash of *wp.Value()). ( uniqueMap[T]) expand(oldEntry, newEntry *entry[T], newHash uintptr, hashShift uint, parent *indirect[T]) *node[T] expand takes oldEntry and newEntry whose hashes conflict from bit 64 down to hashShift and produces a subtree of indirect nodes to hold the two new entries. newHash is the hash of the value in the new entry.

Package-Level Functions (total 9, in which 1 is exported)

func Make[T](value T) Handle[T] Type Parameters: T: comparable 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. Make is safe for concurrent use by multiple goroutines.

/* 8 unexporteds ... *//* 8 unexporteds: */

func buildArrayCloneSeq(typ *abi.Type, seq *cloneSeq, baseOffset uintptr) buildArrayCloneSeq populates a cloneSeq for an abi.Type that has Kind abi.Array.

func buildStructCloneSeq(typ *abi.Type, seq *cloneSeq, baseOffset uintptr) buildStructCloneSeq populates a cloneSeq for an abi.Type that has Kind abi.Struct.

func clone[T](value T, seq *cloneSeq) T Type Parameters: T: comparable clone makes a copy of value, and may update string values found in value with a cloned version of those strings. The purpose of explicitly cloning strings is to avoid accidentally giving a large string a long lifetime. Note that this will clone strings in structs and arrays found in value, and will clone value if it itself is a string. It will not, however, clone strings if value is of interface or slice type (that is, found via an indirection).

func makeCloneSeq(typ *abi.Type) cloneSeq makeCloneSeq creates a cloneSeq for a type.

func newCanonMap[T]() *canonMap[T] Type Parameters: T: comparable

func newEntryNode[T](key T, hash uintptr) (*entry[T], *T, weak.Pointer[T]) Type Parameters: T: comparable

func newIndirectNode[T](parent *indirect[T]) *indirect[T] Type Parameters: T: comparable

func runtime_rand() uint64 Pull in runtime.rand so that we don't need to take a dependency on math/rand/v2.

Package-Level Variables (total 3, none are exported) /* 3 unexporteds ... *//* 3 unexporteds: */

var singleStringClone cloneSeq singleStringClone describes how to clone a single string.

var uniqueMaps isync.HashTrieMap[*abi.Type, any] // any is always a *uniqueMap[T]. uniqueMaps is an index of type-specific concurrent maps used for unique.Make. The two-level map might seem odd at first since the HashTrieMap could have "any" as its key type, but the issue is escape analysis. We do not want to force lookups to escape the argument, and using a type-specific map allows us to avoid that where possible (for example, for strings and plain-ol'-data structs). We also get the benefit of not cramming every different type into a single map, but that's certainly not enough to outweigh the cost of two map lookups. What is worth it though, is saving on those allocations.

var zero uintptr

Package-Level Constants (total 3, none are exported) /* 3 unexporteds ... *//* 3 unexporteds: */

const nChildren = 16

const nChildrenLog2 = 4 16 children. This seems to be the sweet spot for load performance: any smaller and we lose out on 50% or more in CPU performance. Any larger and the returns are minuscule (~1% improvement for 32 children).

const nChildrenMask = 15