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