Source file src/internal/runtime/maps/group.go
1 // Copyright 2024 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package maps 6 7 import ( 8 "internal/abi" 9 "internal/goarch" 10 "internal/runtime/sys" 11 "unsafe" 12 ) 13 14 const ( 15 // Maximum load factor prior to growing. 16 // 17 // 7/8 is the same load factor used by Abseil, but Abseil defaults to 18 // 16 slots per group, so they get two empty slots vs our one empty 19 // slot. We may want to reevaluate if this is best for us. 20 maxAvgGroupLoad = 7 21 22 ctrlEmpty ctrl = 0b10000000 23 ctrlDeleted ctrl = 0b11111110 24 25 bitsetLSB = 0x0101010101010101 26 bitsetMSB = 0x8080808080808080 27 bitsetEmpty = bitsetLSB * uint64(ctrlEmpty) 28 ) 29 30 // bitset represents a set of slots within a group. 31 // 32 // The underlying representation depends on GOARCH. 33 // 34 // On AMD64, bitset uses one bit per slot, where the bit is set if the slot is 35 // part of the set. All of the ctrlGroup.match* methods are replaced with 36 // intrinsics that return this packed representation. 37 // 38 // On other architectures, bitset uses one byte per slot, where each byte is 39 // either 0x80 if the slot is part of the set or 0x00 otherwise. This makes it 40 // convenient to calculate for an entire group at once using standard 41 // arithmetic instructions. 42 type bitset uint64 43 44 // first returns the relative index of the first control byte in the group that 45 // is in the set. 46 // 47 // Preconditions: b is not 0 (empty). 48 func (b bitset) first() uintptr { 49 return bitsetFirst(b) 50 } 51 52 // Portable implementation of first. 53 // 54 // On AMD64, this is replaced with an intrisic that simply does 55 // TrailingZeros64. There is no need to shift as the bitset is packed. 56 func bitsetFirst(b bitset) uintptr { 57 return uintptr(sys.TrailingZeros64(uint64(b))) >> 3 58 } 59 60 // removeFirst clears the first set bit (that is, resets the least significant 61 // set bit to 0). 62 func (b bitset) removeFirst() bitset { 63 return b & (b - 1) 64 } 65 66 // removeBelow clears all set bits below slot i (non-inclusive). 67 func (b bitset) removeBelow(i uintptr) bitset { 68 return bitsetRemoveBelow(b, i) 69 } 70 71 // Portable implementation of removeBelow. 72 // 73 // On AMD64, this is replaced with an intrisic that clears the lower i bits. 74 func bitsetRemoveBelow(b bitset, i uintptr) bitset { 75 // Clear all bits below slot i's byte. 76 mask := (uint64(1) << (8 * uint64(i))) - 1 77 return b &^ bitset(mask) 78 } 79 80 // lowestSet returns true if the bit is set for the lowest index in the bitset. 81 // 82 // This is intended for use with shiftOutLowest to loop over all entries in the 83 // bitset regardless of whether they are set. 84 func (b bitset) lowestSet() bool { 85 return bitsetLowestSet(b) 86 } 87 88 // Portable implementation of lowestSet. 89 // 90 // On AMD64, this is replaced with an intrisic that checks the lowest bit. 91 func bitsetLowestSet(b bitset) bool { 92 return b&(1<<7) != 0 93 } 94 95 // shiftOutLowest shifts the lowest entry out of the bitset. Afterwards, the 96 // lowest entry in the bitset corresponds to the next slot. 97 func (b bitset) shiftOutLowest() bitset { 98 return bitsetShiftOutLowest(b) 99 } 100 101 // Portable implementation of shiftOutLowest. 102 // 103 // On AMD64, this is replaced with an intrisic that shifts a single bit. 104 func bitsetShiftOutLowest(b bitset) bitset { 105 return b >> 8 106 } 107 108 // count returns the number of bits set in b. 109 func (b bitset) count() int { 110 // Note: works for both bitset representations (AMD64 and generic) 111 return sys.OnesCount64(uint64(b)) 112 } 113 114 // Each slot in the hash table has a control byte which can have one of three 115 // states: empty, deleted, and full. They have the following bit patterns: 116 // 117 // empty: 1 0 0 0 0 0 0 0 118 // deleted: 1 1 1 1 1 1 1 0 119 // full: 0 h h h h h h h // h represents the H2 hash bits 120 // 121 // TODO(prattmic): Consider inverting the top bit so that the zero value is empty. 122 type ctrl uint8 123 124 // ctrlGroup is a fixed size array of abi.MapGroupSlots control bytes 125 // stored in a uint64. 126 type ctrlGroup uint64 127 128 // get returns the i-th control byte. 129 func (g *ctrlGroup) get(i uintptr) ctrl { 130 if goarch.BigEndian { 131 return *(*ctrl)(unsafe.Add(unsafe.Pointer(g), 7-i)) 132 } 133 return *(*ctrl)(unsafe.Add(unsafe.Pointer(g), i)) 134 } 135 136 // set sets the i-th control byte. 137 func (g *ctrlGroup) set(i uintptr, c ctrl) { 138 if goarch.BigEndian { 139 *(*ctrl)(unsafe.Add(unsafe.Pointer(g), 7-i)) = c 140 return 141 } 142 *(*ctrl)(unsafe.Add(unsafe.Pointer(g), i)) = c 143 } 144 145 // setEmpty sets all the control bytes to empty. 146 func (g *ctrlGroup) setEmpty() { 147 *g = ctrlGroup(bitsetEmpty) 148 } 149 150 // matchH2 returns the set of slots which are full and for which the 7-bit hash 151 // matches the given value. May return false positives. 152 func (g ctrlGroup) matchH2(h uintptr) bitset { 153 return ctrlGroupMatchH2(g, h) 154 } 155 156 // Portable implementation of matchH2. 157 // 158 // Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See 159 // note on bitset about the packed intrinsified return value. 160 func ctrlGroupMatchH2(g ctrlGroup, h uintptr) bitset { 161 // NB: This generic matching routine produces false positive matches when 162 // h is 2^N and the control bytes have a seq of 2^N followed by 2^N+1. For 163 // example: if ctrls==0x0302 and h=02, we'll compute v as 0x0100. When we 164 // subtract off 0x0101 the first 2 bytes we'll become 0xffff and both be 165 // considered matches of h. The false positive matches are not a problem, 166 // just a rare inefficiency. Note that they only occur if there is a real 167 // match and never occur on ctrlEmpty, or ctrlDeleted. The subsequent key 168 // comparisons ensure that there is no correctness issue. 169 v := uint64(g) ^ (bitsetLSB * uint64(h)) 170 return bitset(((v - bitsetLSB) &^ v) & bitsetMSB) 171 } 172 173 // matchEmpty returns the set of slots in the group that are empty. 174 func (g ctrlGroup) matchEmpty() bitset { 175 return ctrlGroupMatchEmpty(g) 176 } 177 178 // Portable implementation of matchEmpty. 179 // 180 // Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See 181 // note on bitset about the packed intrinsified return value. 182 func ctrlGroupMatchEmpty(g ctrlGroup) bitset { 183 // An empty slot is 1000 0000 184 // A deleted slot is 1111 1110 185 // A full slot is 0??? ???? 186 // 187 // A slot is empty iff bit 7 is set and bit 1 is not. We could select any 188 // of the other bits here (e.g. v << 1 would also work). 189 v := uint64(g) 190 return bitset((v &^ (v << 6)) & bitsetMSB) 191 } 192 193 // matchEmptyOrDeleted returns the set of slots in the group that are empty or 194 // deleted. 195 func (g ctrlGroup) matchEmptyOrDeleted() bitset { 196 return ctrlGroupMatchEmptyOrDeleted(g) 197 } 198 199 // Portable implementation of matchEmptyOrDeleted. 200 // 201 // Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See 202 // note on bitset about the packed intrinsified return value. 203 func ctrlGroupMatchEmptyOrDeleted(g ctrlGroup) bitset { 204 // An empty slot is 1000 0000 205 // A deleted slot is 1111 1110 206 // A full slot is 0??? ???? 207 // 208 // A slot is empty or deleted iff bit 7 is set. 209 v := uint64(g) 210 return bitset(v & bitsetMSB) 211 } 212 213 // matchFull returns the set of slots in the group that are full. 214 func (g ctrlGroup) matchFull() bitset { 215 return ctrlGroupMatchFull(g) 216 } 217 218 // anyFull reports whether any slots in the group are full. 219 func (g ctrlGroup) anyFull() bool { 220 // A slot is full iff bit 7 is unset. Test whether any slot has bit 7 unset. 221 return (^g)&bitsetMSB != 0 222 } 223 224 // Portable implementation of matchFull. 225 // 226 // Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See 227 // note on bitset about the packed intrinsified return value. 228 func ctrlGroupMatchFull(g ctrlGroup) bitset { 229 // An empty slot is 1000 0000 230 // A deleted slot is 1111 1110 231 // A full slot is 0??? ???? 232 // 233 // A slot is full iff bit 7 is unset. 234 v := uint64(g) 235 return bitset(^v & bitsetMSB) 236 } 237 238 // groupReference is a wrapper type representing a single slot group stored at 239 // data. 240 // 241 // A group holds abi.MapGroupSlots slots (key/elem pairs) plus their 242 // control word. 243 type groupReference struct { 244 // data points to the group, which is described by typ.Group and has 245 // layout depending on GOEXPERIMENT=mapsplitgroup: 246 // 247 // With mapsplitgroup (split arrays): 248 // type group struct { 249 // ctrls ctrlGroup 250 // keys [abi.MapGroupSlots]typ.Key 251 // elems [abi.MapGroupSlots]typ.Elem 252 // } 253 // 254 // Without (interleaved slots): 255 // type group struct { 256 // ctrls ctrlGroup 257 // slots [abi.MapGroupSlots]struct { 258 // key typ.Key 259 // elem typ.Elem 260 // } 261 // } 262 // 263 // In both cases, key(i) and elem(i) use the same formula via 264 // typ.KeysOff/KeyStride and typ.ElemsOff/ElemStride. 265 data unsafe.Pointer // data *typ.Group 266 } 267 268 // alignUp rounds n up to a multiple of a. a must be a power of 2. 269 func alignUp(n, a uintptr) uintptr { 270 return (n + a - 1) &^ (a - 1) 271 } 272 273 // alignUpPow2 rounds n up to the next power of 2. 274 // 275 // Returns true if round up causes overflow. 276 func alignUpPow2(n uint64) (uint64, bool) { 277 if n == 0 { 278 return 0, false 279 } 280 v := (uint64(1) << sys.Len64(n-1)) 281 if v == 0 { 282 return 0, true 283 } 284 return v, false 285 } 286 287 // ctrls returns the group control word. 288 func (g *groupReference) ctrls() *ctrlGroup { 289 return (*ctrlGroup)(g.data) 290 } 291 292 // key returns a pointer to the key at index i. 293 func (g *groupReference) key(typ *abi.MapType, i uintptr) unsafe.Pointer { 294 offset := typ.KeysOff + i*typ.KeyStride 295 296 return unsafe.Pointer(uintptr(g.data) + offset) 297 } 298 299 // elem returns a pointer to the element at index i. 300 func (g *groupReference) elem(typ *abi.MapType, i uintptr) unsafe.Pointer { 301 offset := typ.ElemsOff + i*typ.ElemStride 302 303 return unsafe.Pointer(uintptr(g.data) + offset) 304 } 305 306 // groupsReference is a wrapper type describing an array of groups stored at 307 // data. 308 type groupsReference struct { 309 // data points to an array of groups. See groupReference above for the 310 // definition of group. 311 data unsafe.Pointer // data *[length]typ.Group 312 313 // lengthMask is the number of groups in data minus one (note that 314 // length must be a power of two). This allows computing i%length 315 // quickly using bitwise AND. 316 lengthMask uint64 317 } 318 319 // newGroups allocates a new array of length groups. 320 // 321 // Length must be a power of two. 322 func newGroups(typ *abi.MapType, length uint64) groupsReference { 323 return groupsReference{ 324 // TODO: make the length type the same throughout. 325 data: newarray(typ.Group, int(length)), 326 lengthMask: length - 1, 327 } 328 } 329 330 // group returns the group at index i. 331 func (g *groupsReference) group(typ *abi.MapType, i uint64) groupReference { 332 // TODO(prattmic): Do something here about truncation on cast to 333 // uintptr on 32-bit systems? 334 offset := uintptr(i) * typ.GroupSize 335 336 return groupReference{ 337 data: unsafe.Pointer(uintptr(g.data) + offset), 338 } 339 } 340 341 func cloneGroup(typ *abi.MapType, newGroup, oldGroup groupReference) { 342 typedmemmove(typ.Group, newGroup.data, oldGroup.data) 343 if typ.IndirectKey() { 344 // Deep copy keys if indirect. 345 for i := uintptr(0); i < abi.MapGroupSlots; i++ { 346 oldKey := *(*unsafe.Pointer)(oldGroup.key(typ, i)) 347 if oldKey == nil { 348 continue 349 } 350 newKey := newobject(typ.Key) 351 typedmemmove(typ.Key, newKey, oldKey) 352 *(*unsafe.Pointer)(newGroup.key(typ, i)) = newKey 353 } 354 } 355 if typ.IndirectElem() { 356 // Deep copy elems if indirect. 357 for i := uintptr(0); i < abi.MapGroupSlots; i++ { 358 oldElem := *(*unsafe.Pointer)(oldGroup.elem(typ, i)) 359 if oldElem == nil { 360 continue 361 } 362 newElem := newobject(typ.Elem) 363 typedmemmove(typ.Elem, newElem, oldElem) 364 *(*unsafe.Pointer)(newGroup.elem(typ, i)) = newElem 365 } 366 } 367 368 } 369