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 bitsetDeleted = bitsetLSB * uint64(ctrlDeleted) 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 // arithemetic 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.SwissMapGroupSlots 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 instrinsified return value. 161 func ctrlGroupMatchH2(g ctrlGroup, h uintptr) bitset { 162 // NB: This generic matching routine produces false positive matches when 163 // h is 2^N and the control bytes have a seq of 2^N followed by 2^N+1. For 164 // example: if ctrls==0x0302 and h=02, we'll compute v as 0x0100. When we 165 // subtract off 0x0101 the first 2 bytes we'll become 0xffff and both be 166 // considered matches of h. The false positive matches are not a problem, 167 // just a rare inefficiency. Note that they only occur if there is a real 168 // match and never occur on ctrlEmpty, or ctrlDeleted. The subsequent key 169 // comparisons ensure that there is no correctness issue. 170 v := uint64(g) ^ (bitsetLSB * uint64(h)) 171 return bitset(((v - bitsetLSB) &^ v) & bitsetMSB) 172 } 173 174 // matchEmpty returns the set of slots in the group that are empty. 175 func (g ctrlGroup) matchEmpty() bitset { 176 return ctrlGroupMatchEmpty(g) 177 } 178 179 // Portable implementation of matchEmpty. 180 // 181 // Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See 182 // note on bitset about the packed instrinsified return value. 183 func ctrlGroupMatchEmpty(g ctrlGroup) bitset { 184 // An empty slot is 1000 0000 185 // A deleted slot is 1111 1110 186 // A full slot is 0??? ???? 187 // 188 // A slot is empty iff bit 7 is set and bit 1 is not. We could select any 189 // of the other bits here (e.g. v << 1 would also work). 190 v := uint64(g) 191 return bitset((v &^ (v << 6)) & bitsetMSB) 192 } 193 194 // matchEmptyOrDeleted returns the set of slots in the group that are empty or 195 // deleted. 196 func (g ctrlGroup) matchEmptyOrDeleted() bitset { 197 return ctrlGroupMatchEmptyOrDeleted(g) 198 } 199 200 // Portable implementation of matchEmptyOrDeleted. 201 // 202 // Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See 203 // note on bitset about the packed instrinsified return value. 204 func ctrlGroupMatchEmptyOrDeleted(g ctrlGroup) bitset { 205 // An empty slot is 1000 0000 206 // A deleted slot is 1111 1110 207 // A full slot is 0??? ???? 208 // 209 // A slot is empty or deleted iff bit 7 is set. 210 v := uint64(g) 211 return bitset(v & bitsetMSB) 212 } 213 214 // matchFull returns the set of slots in the group that are full. 215 func (g ctrlGroup) matchFull() bitset { 216 return ctrlGroupMatchFull(g) 217 } 218 219 // Portable implementation of matchFull. 220 // 221 // Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See 222 // note on bitset about the packed instrinsified return value. 223 func ctrlGroupMatchFull(g ctrlGroup) bitset { 224 // An empty slot is 1000 0000 225 // A deleted slot is 1111 1110 226 // A full slot is 0??? ???? 227 // 228 // A slot is full iff bit 7 is unset. 229 v := uint64(g) 230 return bitset(^v & bitsetMSB) 231 } 232 233 // groupReference is a wrapper type representing a single slot group stored at 234 // data. 235 // 236 // A group holds abi.SwissMapGroupSlots slots (key/elem pairs) plus their 237 // control word. 238 type groupReference struct { 239 // data points to the group, which is described by typ.Group and has 240 // layout: 241 // 242 // type group struct { 243 // ctrls ctrlGroup 244 // slots [abi.SwissMapGroupSlots]slot 245 // } 246 // 247 // type slot struct { 248 // key typ.Key 249 // elem typ.Elem 250 // } 251 data unsafe.Pointer // data *typ.Group 252 } 253 254 const ( 255 ctrlGroupsSize = unsafe.Sizeof(ctrlGroup(0)) 256 groupSlotsOffset = ctrlGroupsSize 257 ) 258 259 // alignUp rounds n up to a multiple of a. a must be a power of 2. 260 func alignUp(n, a uintptr) uintptr { 261 return (n + a - 1) &^ (a - 1) 262 } 263 264 // alignUpPow2 rounds n up to the next power of 2. 265 // 266 // Returns true if round up causes overflow. 267 func alignUpPow2(n uint64) (uint64, bool) { 268 if n == 0 { 269 return 0, false 270 } 271 v := (uint64(1) << sys.Len64(n-1)) 272 if v == 0 { 273 return 0, true 274 } 275 return v, false 276 } 277 278 // ctrls returns the group control word. 279 func (g *groupReference) ctrls() *ctrlGroup { 280 return (*ctrlGroup)(g.data) 281 } 282 283 // key returns a pointer to the key at index i. 284 func (g *groupReference) key(typ *abi.SwissMapType, i uintptr) unsafe.Pointer { 285 offset := groupSlotsOffset + i*typ.SlotSize 286 287 return unsafe.Pointer(uintptr(g.data) + offset) 288 } 289 290 // elem returns a pointer to the element at index i. 291 func (g *groupReference) elem(typ *abi.SwissMapType, i uintptr) unsafe.Pointer { 292 offset := groupSlotsOffset + i*typ.SlotSize + typ.ElemOff 293 294 return unsafe.Pointer(uintptr(g.data) + offset) 295 } 296 297 // groupsReference is a wrapper type describing an array of groups stored at 298 // data. 299 type groupsReference struct { 300 // data points to an array of groups. See groupReference above for the 301 // definition of group. 302 data unsafe.Pointer // data *[length]typ.Group 303 304 // lengthMask is the number of groups in data minus one (note that 305 // length must be a power of two). This allows computing i%length 306 // quickly using bitwise AND. 307 lengthMask uint64 308 } 309 310 // newGroups allocates a new array of length groups. 311 // 312 // Length must be a power of two. 313 func newGroups(typ *abi.SwissMapType, length uint64) groupsReference { 314 return groupsReference{ 315 // TODO: make the length type the same throughout. 316 data: newarray(typ.Group, int(length)), 317 lengthMask: length - 1, 318 } 319 } 320 321 // group returns the group at index i. 322 func (g *groupsReference) group(typ *abi.SwissMapType, i uint64) groupReference { 323 // TODO(prattmic): Do something here about truncation on cast to 324 // uintptr on 32-bit systems? 325 offset := uintptr(i) * typ.GroupSize 326 327 return groupReference{ 328 data: unsafe.Pointer(uintptr(g.data) + offset), 329 } 330 } 331 332 func cloneGroup(typ *abi.SwissMapType, newGroup, oldGroup groupReference) { 333 typedmemmove(typ.Group, newGroup.data, oldGroup.data) 334 if typ.IndirectKey() { 335 // Deep copy keys if indirect. 336 for i := uintptr(0); i < abi.SwissMapGroupSlots; i++ { 337 oldKey := *(*unsafe.Pointer)(oldGroup.key(typ, i)) 338 if oldKey == nil { 339 continue 340 } 341 newKey := newobject(typ.Key) 342 typedmemmove(typ.Key, newKey, oldKey) 343 *(*unsafe.Pointer)(newGroup.key(typ, i)) = newKey 344 } 345 } 346 if typ.IndirectElem() { 347 // Deep copy elems if indirect. 348 for i := uintptr(0); i < abi.SwissMapGroupSlots; i++ { 349 oldElem := *(*unsafe.Pointer)(oldGroup.elem(typ, i)) 350 if oldElem == nil { 351 continue 352 } 353 newElem := newobject(typ.Elem) 354 typedmemmove(typ.Elem, newElem, oldElem) 355 *(*unsafe.Pointer)(newGroup.elem(typ, i)) = newElem 356 } 357 } 358 359 } 360