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: 246 // 247 // type group struct { 248 // ctrls ctrlGroup 249 // slots [abi.MapGroupSlots]slot 250 // } 251 // 252 // type slot struct { 253 // key typ.Key 254 // elem typ.Elem 255 // } 256 data unsafe.Pointer // data *typ.Group 257 } 258 259 const ( 260 ctrlGroupsSize = unsafe.Sizeof(ctrlGroup(0)) 261 groupSlotsOffset = ctrlGroupsSize 262 ) 263 264 // alignUp rounds n up to a multiple of a. a must be a power of 2. 265 func alignUp(n, a uintptr) uintptr { 266 return (n + a - 1) &^ (a - 1) 267 } 268 269 // alignUpPow2 rounds n up to the next power of 2. 270 // 271 // Returns true if round up causes overflow. 272 func alignUpPow2(n uint64) (uint64, bool) { 273 if n == 0 { 274 return 0, false 275 } 276 v := (uint64(1) << sys.Len64(n-1)) 277 if v == 0 { 278 return 0, true 279 } 280 return v, false 281 } 282 283 // ctrls returns the group control word. 284 func (g *groupReference) ctrls() *ctrlGroup { 285 return (*ctrlGroup)(g.data) 286 } 287 288 // key returns a pointer to the key at index i. 289 func (g *groupReference) key(typ *abi.MapType, i uintptr) unsafe.Pointer { 290 offset := groupSlotsOffset + i*typ.SlotSize 291 292 return unsafe.Pointer(uintptr(g.data) + offset) 293 } 294 295 // elem returns a pointer to the element at index i. 296 func (g *groupReference) elem(typ *abi.MapType, i uintptr) unsafe.Pointer { 297 offset := groupSlotsOffset + i*typ.SlotSize + typ.ElemOff 298 299 return unsafe.Pointer(uintptr(g.data) + offset) 300 } 301 302 // groupsReference is a wrapper type describing an array of groups stored at 303 // data. 304 type groupsReference struct { 305 // data points to an array of groups. See groupReference above for the 306 // definition of group. 307 data unsafe.Pointer // data *[length]typ.Group 308 309 // lengthMask is the number of groups in data minus one (note that 310 // length must be a power of two). This allows computing i%length 311 // quickly using bitwise AND. 312 lengthMask uint64 313 } 314 315 // newGroups allocates a new array of length groups. 316 // 317 // Length must be a power of two. 318 func newGroups(typ *abi.MapType, length uint64) groupsReference { 319 return groupsReference{ 320 // TODO: make the length type the same throughout. 321 data: newarray(typ.Group, int(length)), 322 lengthMask: length - 1, 323 } 324 } 325 326 // group returns the group at index i. 327 func (g *groupsReference) group(typ *abi.MapType, i uint64) groupReference { 328 // TODO(prattmic): Do something here about truncation on cast to 329 // uintptr on 32-bit systems? 330 offset := uintptr(i) * typ.GroupSize 331 332 return groupReference{ 333 data: unsafe.Pointer(uintptr(g.data) + offset), 334 } 335 } 336 337 func cloneGroup(typ *abi.MapType, newGroup, oldGroup groupReference) { 338 typedmemmove(typ.Group, newGroup.data, oldGroup.data) 339 if typ.IndirectKey() { 340 // Deep copy keys if indirect. 341 for i := uintptr(0); i < abi.MapGroupSlots; i++ { 342 oldKey := *(*unsafe.Pointer)(oldGroup.key(typ, i)) 343 if oldKey == nil { 344 continue 345 } 346 newKey := newobject(typ.Key) 347 typedmemmove(typ.Key, newKey, oldKey) 348 *(*unsafe.Pointer)(newGroup.key(typ, i)) = newKey 349 } 350 } 351 if typ.IndirectElem() { 352 // Deep copy elems if indirect. 353 for i := uintptr(0); i < abi.MapGroupSlots; i++ { 354 oldElem := *(*unsafe.Pointer)(oldGroup.elem(typ, i)) 355 if oldElem == nil { 356 continue 357 } 358 newElem := newobject(typ.Elem) 359 typedmemmove(typ.Elem, newElem, oldElem) 360 *(*unsafe.Pointer)(newGroup.elem(typ, i)) = newElem 361 } 362 } 363 364 } 365