Involved Source Fileshashtriemap.go Package sync provides basic synchronization primitives such as mutual
exclusion locks to internal packages (including ones that depend on sync).
Tests are defined in package [sync].runtime.go
Package-Level Type Names (total 7, in which 2 are exported)
/* sort exporteds by: | */
Type Parameters:
K: comparable
V: any HashTrieMap is an implementation of a concurrent hash-trie. The implementation
is designed around frequent loads, but offers decent performance for stores
and deletes as well, especially if the map is larger. Its primary use-case is
the unique package, but can be used elsewhere as well.
The zero HashTrieMap is empty and ready to use.
It must not be copied after first use.initMuMutexinitedatomic.Uint32keyHashhashFuncrootatomic.Pointer[indirect[K, V]]seeduintptrvalEqualequalFunc All returns an iterator over each key and value present in the map.
The iterator does not necessarily correspond to any consistent snapshot of the
HashTrieMap's contents: no key will be visited more than once, but if the value
for any key is stored or deleted concurrently (including by yield), the iterator
may reflect any mapping for that key from any point during iteration. The iterator
does not block other methods on the receiver; even yield itself may call any
method on the HashTrieMap. Clear deletes all the entries, resulting in an empty HashTrieMap. CompareAndDelete deletes the entry for key if its value is equal to old.
The value type must be comparable, otherwise this CompareAndDelete will panic.
If there is no current value for key in the map, CompareAndDelete returns false
(even if the old value is the nil interface value). CompareAndSwap swaps the old and new values for key
if the value stored in the map is equal to old.
The value type must be of a comparable type, otherwise CompareAndSwap will panic. Delete deletes the value for a key. Load returns the value stored in the map for a key, or nil if no
value is present.
The ok result indicates whether value was found in the map. LoadAndDelete deletes the value for a key, returning the previous value if any.
The loaded result reports whether the key was present. LoadOrStore returns the existing value for the key if present.
Otherwise, it stores and returns the given value.
The loaded result is true if the value was loaded, false if stored. Range calls f sequentially for each key and value present in the map.
If f returns false, range stops the iteration.
This exists for compatibility with sync.Map; All should be preferred.
It provides the same guarantees as sync.Map, and All. Store sets the value for a key. Swap swaps the value for a key and returns the previous value if any.
The loaded result reports whether the key was present. 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. find searches the tree for a node that contains key (hash must be the hash of key).
If valEqual != nil, then it will also enforce that the values are equal as well.
Returns a non-nil node, which will always be an entry, if found.
If i != nil then i.mu is locked, and it is the caller's responsibility to unlock it.(*HashTrieMap[K, V]) init()(*HashTrieMap[K, V]) initSlow()(*HashTrieMap[K, V]) iter(i *indirect[K, V], yield func(key K, value V) bool) bool
var unique.uniqueMapsisync.HashTrieMap[*abi.Type, any]
A Mutex is a mutual exclusion lock.
See package [sync.Mutex] documentation.semauint32stateint32 Lock locks m.
See package [sync.Mutex] documentation. TryLock tries to lock m and reports whether it succeeded.
See package [sync.Mutex] documentation. Unlock unlocks m.
See package [sync.Mutex] documentation.(*Mutex) lockSlow()(*Mutex) unlockSlow(new int32)
*Mutex : sync.Locker
Type Parameters:
K: comparable
V: any entry is a leaf node in the hash-trie.keyKnodenode[K, V]node.isEntrybool // Overflow for hash collisions.valueV compareAndDelete deletes an entry in the overflow chain if both the key and value compare
equal. Returns the new entry chain and whether or not anything was deleted.
compareAndDelete must be called under the mutex of the indirect node which e is a child of. compareAndSwap replaces an entry in the overflow chain if both the key and value compare
equal. Returns the new entry chain and whether or not anything was swapped.
compareAndSwap must be called under the mutex of the indirect node which e is a child of.(*entry[K, V]) entry() *entry[K, V](*entry[K, V]) indirect() *indirect[K, V] loadAndDelete deletes an entry in the overflow chain by key. Returns the value for the key, the new
entry chain and whether or not anything was loaded (and deleted).
loadAndDelete must be called under the mutex of the indirect node which e is a child of.(*entry[K, V]) lookup(key K) (V, bool)(*entry[K, V]) lookupWithValue(key K, value V, valEqual equalFunc) (V, bool) swap replaces an entry in the overflow chain if keys compare equal. Returns the new entry chain,
the old value, and whether or not anything was swapped.
swap must be called under the mutex of the indirect node which e is a child of.
func newEntryNode[K, V](key K, value V) *entry[K, V]
func (*HashTrieMap)[K, V].expand(oldEntry, newEntry *entry[K, V], newHash uintptr, hashShift uint, parent *indirect[K, V]) *node[K, V]
Pull in runtime.rand so that we don't need to take a dependency
on math/rand/v2.
SemacquireMutex is like Semacquire, but for profiling contended
Mutexes and RWMutexes.
If lifo is true, queue waiter at the head of wait queue.
skipframes is the number of frames to omit during tracing, counting from
runtime_SemacquireMutex's caller.
The different forms of this function just tell the runtime how to present
the reason for waiting in a backtrace, and is used to compute some metrics.
Otherwise they're functionally identical.
Semrelease atomically increments *s and notifies a waiting goroutine
if one is blocked in Semacquire.
It is intended as a simple wakeup primitive for use by the synchronization
library and should not be used directly.
If handoff is true, pass count directly to the first waiter.
skipframes is the number of frames to omit during tracing, counting from
runtime_Semrelease's caller.
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).
Mutex fairness.
Mutex can be in 2 modes of operations: normal and starvation.
In normal mode waiters are queued in FIFO order, but a woken up waiter
does not own the mutex and competes with new arriving goroutines over
the ownership. New arriving goroutines have an advantage -- they are
already running on CPU and there can be lots of them, so a woken up
waiter has good chances of losing. In such case it is queued at front
of the wait queue. If a waiter fails to acquire the mutex for more than 1ms,
it switches mutex to the starvation mode.
In starvation mode ownership of the mutex is directly handed off from
the unlocking goroutine to the waiter at the front of the queue.
New arriving goroutines don't try to acquire the mutex even if it appears
to be unlocked, and don't try to spin. Instead they queue themselves at
the tail of the wait queue.
If a waiter receives ownership of the mutex and sees that either
(1) it is the last waiter in the queue, or (2) it waited for less than 1 ms,
it switches mutex back to normal operation mode.
Normal mode has considerably better performance as a goroutine can acquire
a mutex several times in a row even if there are blocked waiters.
Starvation mode is important to prevent pathological cases of tail latency.
The pages are generated with Goldsv0.7.6. (GOOS=linux GOARCH=amd64)