Package-Level Type Names (total 9, in which 2 are exported)
/* sort exporteds by: | */
Snapshot of Map.clearSeq at iteration initialization time. Used to
detect clear during iteration. dirIdx is the current directory index, prior to adjustment by
dirOffset.dirOffsetuint64 // Must be in second position (see cmd/compile/internal/walk/range.go). entryIdx is the current entry index, prior to adjustment by entryOffset.
The lower 3 bits of the index are the slot index, and the upper bits
are the group index. Randomize iteration order by starting iteration at a random slot
offset. The offset into the directory uses a separate offset, as it
must adjust when the directory grows. Value of Map.globalDepth during the last call to Next. Used to
detect directory grow during iteration. group is the group at entryIdx during the previous call to Next. // Must be in first position. Write nil to indicate iteration end (see cmd/compile/internal/walk/range.go).m*Map tab is the table at dirIdx during the previous call to Next.typ*abi.SwissMapType Key returns a pointer to the current element. nil indicates end of
iteration.
Must not be called prior to Next. Init initializes Iter for iteration.(*Iter) Initialized() bool Key returns a pointer to the current key. nil indicates end of iteration.
Must not be called prior to Next. Map returns the map this iterator is iterating over. Next proceeds to the next element in iteration, which can be accessed via
the Key and Elem methods.
The table can be mutated during iteration, though there is no guarantee that
the mutations will be visible to the iteration.
Init must be called prior to Next. Return the appropriate key/elem for key at slotIdx index within it.group, if
any.(*Iter) nextDirIdx()
func reflect.mapIterNext(it *Iter)
func reflect.mapIterStart(t *abi.SwissMapType, m *Map, it *Iter)
func runtime.mapIterNext(it *Iter)
func runtime.mapIterStart(t *abi.SwissMapType, m *Map, it *Iter)
bitset represents a set of slots within a group.
The underlying representation depends on GOARCH.
On AMD64, bitset uses one bit per slot, where the bit is set if the slot is
part of the set. All of the ctrlGroup.match* methods are replaced with
intrinsics that return this packed representation.
On other architectures, bitset uses one byte per slot, where each byte is
either 0x80 if the slot is part of the set or 0x00 otherwise. This makes it
convenient to calculate for an entire group at once using standard
arithemetic instructions. first returns the relative index of the first control byte in the group that
is in the set.
Preconditions: b is not 0 (empty). lowestSet returns true if the bit is set for the lowest index in the bitset.
This is intended for use with shiftOutLowest to loop over all entries in the
bitset regardless of whether they are set. removeBelow clears all set bits below slot i (non-inclusive). removeFirst clears the first set bit (that is, resets the least significant
set bit to 0). shiftOutLowest shifts the lowest entry out of the bitset. Afterwards, the
lowest entry in the bitset corresponds to the next slot.
func bitsetRemoveBelow(b bitset, i uintptr) bitset
func bitsetShiftOutLowest(b bitset) bitset
func ctrlGroupMatchEmpty(g ctrlGroup) bitset
func ctrlGroupMatchEmptyOrDeleted(g ctrlGroup) bitset
func ctrlGroupMatchFull(g ctrlGroup) bitset
func ctrlGroupMatchH2(g ctrlGroup, h uintptr) bitset
func bitsetFirst(b bitset) uintptr
func bitsetLowestSet(b bitset) bool
func bitsetRemoveBelow(b bitset, i uintptr) bitset
func bitsetShiftOutLowest(b bitset) bitset
Each slot in the hash table has a control byte which can have one of three
states: empty, deleted, and full. They have the following bit patterns:
empty: 1 0 0 0 0 0 0 0
deleted: 1 1 1 1 1 1 1 0
full: 0 h h h h h h h // h represents the H1 hash bits
TODO(prattmic): Consider inverting the top bit so that the zero value is empty.
const ctrlDeleted
const ctrlEmpty
ctrlGroup is a fixed size array of abi.SwissMapGroupSlots control bytes
stored in a uint64. get returns the i-th control byte. matchEmpty returns the set of slots in the group that are empty. matchEmptyOrDeleted returns the set of slots in the group that are empty or
deleted. matchFull returns the set of slots in the group that are full. matchH2 returns the set of slots which are full and for which the 7-bit hash
matches the given value. May return false positives. set sets the i-th control byte. setEmpty sets all the control bytes to empty.
func ctrlGroupMatchEmpty(g ctrlGroup) bitset
func ctrlGroupMatchEmptyOrDeleted(g ctrlGroup) bitset
func ctrlGroupMatchFull(g ctrlGroup) bitset
func ctrlGroupMatchH2(g ctrlGroup, h uintptr) bitset
groupReference is a wrapper type representing a single slot group stored at
data.
A group holds abi.SwissMapGroupSlots slots (key/elem pairs) plus their
control word. data points to the group, which is described by typ.Group and has
layout:
type group struct {
ctrls ctrlGroup
slots [abi.SwissMapGroupSlots]slot
}
type slot struct {
key typ.Key
elem typ.Elem
} // data *typ.Group ctrls returns the group control word. elem returns a pointer to the element at index i. key returns a pointer to the key at index i.
groupsReference is a wrapper type describing an array of groups stored at
data. data points to an array of groups. See groupReference above for the
definition of group. // data *[length]typ.Group lengthMask is the number of groups in data minus one (note that
length must be a power of two). This allows computing i%length
quickly using bitwise AND. group returns the group at index i.
func newGroups(typ *abi.SwissMapType, length uint64) groupsReference
probeSeq maintains the state for a probe sequence that iterates through the
groups in a table. The sequence is a triangular progression of the form
p(i) := (i^2 + i)/2 + hash (mod mask+1)
The sequence effectively outputs the indexes of *groups*. The group
machinery allows us to check an entire group with minimal branching.
It turns out that this probe sequence visits every group exactly once if
the number of groups is a power of two, since (i^2+i)/2 is a bijection in
Z/(2^m). See https://en.wikipedia.org/wiki/Quadratic_probingindexuint64maskuint64offsetuint64( probeSeq) next() probeSeq
func makeProbeSeq(hash uintptr, mask uint64) probeSeq
table is a Swiss table hash table structure.
Each table is a complete hash table implementation.
Map uses one or more tables to store entries. Extendible hashing (hash
prefix) is used to select the table to use for a specific key. Using
multiple tables enables incremental growth by growing only one table at a
time. The total number of slots (always 2^N). Equal to
`(groups.lengthMask+1)*abi.SwissMapGroupSlots`. groups is an array of slot groups. Each group holds abi.SwissMapGroupSlots
key/elem slots and their control bytes. A table has a fixed size
groups array. The table is replaced (in rehash) when more space is
required.
TODO(prattmic): keys and elements are interleaved to maximize
locality, but it comes at the expense of wasted space for some types
(consider uint8 key, uint64 element). Consider placing all keys
together in these cases to save space. The number of slots we can still fill without needing to rehash.
We rehash when used + tombstones > loadFactor*capacity, including
tombstones so the table doesn't overfill with tombstones. This field
counts down remaining empty slots before the next rehash. Index of this table in the Map directory. This is the index of the
_first_ location in the directory. The table may occur in multiple
sequential indicies.
index is -1 if the table is stale (no longer installed in the
directory). The number of bits used by directory lookups above this table. Note
that this may be less then globalDepth, if the directory has grown
but this table has not yet been split. The number of filled slots (i.e. the number of elements in the table). Clear deletes all entries from the map resulting in an empty map.(*table) Delete(typ *abi.SwissMapType, m *Map, hash uintptr, key unsafe.Pointer) Get performs a lookup of the key that key points to. It returns a pointer to
the element, or false if the key doesn't exist.(*table) Print(typ *abi.SwissMapType, m *Map) PutSlot returns a pointer to the element slot where an inserted element
should be written, and ok if it returned a valid slot.
PutSlot returns ok false if the table was split and the Map needs to find
the new table.
hash must be the hash of key.(*table) Used() uint64(*table) checkInvariants(typ *abi.SwissMapType, m *Map) getWithKey performs a lookup of key, returning a pointer to the version of
the key in the map in addition to the element.
This is relevant when multiple different key values compare equal (e.g.,
+0.0 and -0.0). When a grow occurs during iteration, iteration perform a
lookup of keys from the old group in the new group in order to correctly
expose updated elements. For NeedsKeyUpdate keys, iteration also must return
the new key value, not the old key value.
hash must be the hash of the key.(*table) getWithoutKey(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, bool) grow the capacity of the table by allocating a new table with a bigger array
and uncheckedPutting each element of the table into the new table (we know
that no insertion here will Put an already-present value), and discard the
old table. Replaces the table with one larger table or two split tables to fit more
entries. Since the table is replaced, t is now stale and should not be
modified. reset resets the table with new, empty groups with the specified new total
capacity. Preconditions: table must be empty. split the table into two, installing the new tables in the map directory. tombstones returns the number of deleted (tombstone) entries in the table. A
tombstone is a slot that has been deleted but is still considered occupied
so as not to violate the probing invariant. uncheckedPutSlot inserts an entry known not to be in the table.
This is used for grow/split where we are making a new table from
entries in an existing table.
Decrements growthLeft and increments used.
Requires that the entry does not exist in the table, and that the table has
room for another element without rehashing.
Requires that there are no deleted entries in the table.
For indirect keys and/or elements, the key and elem pointers can be
put directly into the map, they do not need to be copied. This
requires the caller to ensure that the referenced memory never
changes (by sourcing those pointers from another indirect key/elem
map).
func newTable(typ *abi.SwissMapType, capacity uint64, index int, localDepth uint8) *table
func (*Map).directoryAt(i uintptr) *table
func (*Map).directorySet(i uintptr, nt *table)
func (*Map).installTableSplit(old, left, right *table)
func (*Map).replaceTable(nt *table)
Package-Level Functions (total 46, in which 2 are exported)
If m is non-nil, it should be used rather than allocating.
maxAlloc should be runtime.maxAlloc.
TODO(prattmic): Put maxAlloc somewhere accessible.
alignUp rounds n up to a multiple of a. a must be a power of 2.
alignUpPow2 rounds n up to the next power of 2.
Returns true if round up causes overflow.
Portable implementation of first.
On AMD64, this is replaced with an intrisic that simply does
TrailingZeros64. There is no need to shift as the bitset is packed.
Portable implementation of lowestSet.
On AMD64, this is replaced with an intrisic that checks the lowest bit.
Portable implementation of removeBelow.
On AMD64, this is replaced with an intrisic that clears the lower i bits.
Portable implementation of shiftOutLowest.
On AMD64, this is replaced with an intrisic that shifts a single bit.
Portable implementation of matchEmpty.
Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See
note on bitset about the packed instrinsified return value.
Portable implementation of matchEmptyOrDeleted.
Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See
note on bitset about the packed instrinsified return value.
Portable implementation of matchFull.
Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See
note on bitset about the packed instrinsified return value.
Portable implementation of matchH2.
Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See
note on bitset about the packed instrinsified return value.
mapaccess1 returns a pointer to h[key]. Never returns nil, instead
it will return a reference to the zero object for the elem type if
the key is not in the map.
NOTE: The returned pointer may keep the whole map live, so don't
hold onto it for very long.
Key is a 32-bit pointer (only called on 32-bit GOARCH). This source is identical to fast64ptr.
TODO(prattmic): With some compiler refactoring we could avoid duplication of this function.
Package-Level Variables (total 2, neither is exported)
Pushed from runtime in order to use runtime.plainError
Pull from runtime. It is important that is this the exact same copy as the
runtime because runtime.mapaccess1_fat compares the returned pointer with
&runtime.zeroVal[0].
TODO: move zeroVal to internal/abi?
Package-Level Constants (total 11, none are exported)
Maximum load factor prior to growing.
7/8 is the same load factor used by Abseil, but Abseil defaults to
16 slots per group, so they get two empty slots vs our one empty
slot. We may want to reevaluate if this is best for us.
Maximum size of a table before it is split at the directory level.
TODO: Completely made up value. This should be tuned for performance vs grow
latency.
TODO: This should likely be based on byte size, as copying costs will
dominate grow latency for large objects.
The pages are generated with Goldsv0.7.6. (GOOS=linux GOARCH=amd64)