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 // Each slot in the hash table has a control byte which can have one of three 110 // states: empty, deleted, and full. They have the following bit patterns: 111 // 112 // empty: 1 0 0 0 0 0 0 0 113 // deleted: 1 1 1 1 1 1 1 0 114 // full: 0 h h h h h h h // h represents the H1 hash bits 115 // 116 // TODO(prattmic): Consider inverting the top bit so that the zero value is empty. 117 type ctrl uint8 118 119 // ctrlGroup is a fixed size array of abi.SwissMapGroupSlots control bytes 120 // stored in a uint64. 121 type ctrlGroup uint64 122 123 // get returns the i-th control byte. 124 func (g *ctrlGroup) get(i uintptr) ctrl { 125 if goarch.BigEndian { 126 return *(*ctrl)(unsafe.Add(unsafe.Pointer(g), 7-i)) 127 } 128 return *(*ctrl)(unsafe.Add(unsafe.Pointer(g), i)) 129 } 130 131 // set sets the i-th control byte. 132 func (g *ctrlGroup) set(i uintptr, c ctrl) { 133 if goarch.BigEndian { 134 *(*ctrl)(unsafe.Add(unsafe.Pointer(g), 7-i)) = c 135 return 136 } 137 *(*ctrl)(unsafe.Add(unsafe.Pointer(g), i)) = c 138 } 139 140 // setEmpty sets all the control bytes to empty. 141 func (g *ctrlGroup) setEmpty() { 142 *g = ctrlGroup(bitsetEmpty) 143 } 144 145 // matchH2 returns the set of slots which are full and for which the 7-bit hash 146 // matches the given value. May return false positives. 147 func (g ctrlGroup) matchH2(h uintptr) bitset { 148 return ctrlGroupMatchH2(g, h) 149 } 150 151 // Portable implementation of matchH2. 152 // 153 // Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See 154 // note on bitset about the packed instrinsified return value. 155 func ctrlGroupMatchH2(g ctrlGroup, h uintptr) bitset { 156 // NB: This generic matching routine produces false positive matches when 157 // h is 2^N and the control bytes have a seq of 2^N followed by 2^N+1. For 158 // example: if ctrls==0x0302 and h=02, we'll compute v as 0x0100. When we 159 // subtract off 0x0101 the first 2 bytes we'll become 0xffff and both be 160 // considered matches of h. The false positive matches are not a problem, 161 // just a rare inefficiency. Note that they only occur if there is a real 162 // match and never occur on ctrlEmpty, or ctrlDeleted. The subsequent key 163 // comparisons ensure that there is no correctness issue. 164 v := uint64(g) ^ (bitsetLSB * uint64(h)) 165 return bitset(((v - bitsetLSB) &^ v) & bitsetMSB) 166 } 167 168 // matchEmpty returns the set of slots in the group that are empty. 169 func (g ctrlGroup) matchEmpty() bitset { 170 return ctrlGroupMatchEmpty(g) 171 } 172 173 // Portable implementation of matchEmpty. 174 // 175 // Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See 176 // note on bitset about the packed instrinsified return value. 177 func ctrlGroupMatchEmpty(g ctrlGroup) bitset { 178 // An empty slot is 1000 0000 179 // A deleted slot is 1111 1110 180 // A full slot is 0??? ???? 181 // 182 // A slot is empty iff bit 7 is set and bit 1 is not. We could select any 183 // of the other bits here (e.g. v << 1 would also work). 184 v := uint64(g) 185 return bitset((v &^ (v << 6)) & bitsetMSB) 186 } 187 188 // matchEmptyOrDeleted returns the set of slots in the group that are empty or 189 // deleted. 190 func (g ctrlGroup) matchEmptyOrDeleted() bitset { 191 return ctrlGroupMatchEmptyOrDeleted(g) 192 } 193 194 // Portable implementation of matchEmptyOrDeleted. 195 // 196 // Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See 197 // note on bitset about the packed instrinsified return value. 198 func ctrlGroupMatchEmptyOrDeleted(g ctrlGroup) bitset { 199 // An empty slot is 1000 0000 200 // A deleted slot is 1111 1110 201 // A full slot is 0??? ???? 202 // 203 // A slot is empty or deleted iff bit 7 is set. 204 v := uint64(g) 205 return bitset(v & bitsetMSB) 206 } 207 208 // matchFull returns the set of slots in the group that are full. 209 func (g ctrlGroup) matchFull() bitset { 210 return ctrlGroupMatchFull(g) 211 } 212 213 // Portable implementation of matchFull. 214 // 215 // Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See 216 // note on bitset about the packed instrinsified return value. 217 func ctrlGroupMatchFull(g ctrlGroup) bitset { 218 // An empty slot is 1000 0000 219 // A deleted slot is 1111 1110 220 // A full slot is 0??? ???? 221 // 222 // A slot is full iff bit 7 is unset. 223 v := uint64(g) 224 return bitset(^v & bitsetMSB) 225 } 226 227 // groupReference is a wrapper type representing a single slot group stored at 228 // data. 229 // 230 // A group holds abi.SwissMapGroupSlots slots (key/elem pairs) plus their 231 // control word. 232 type groupReference struct { 233 // data points to the group, which is described by typ.Group and has 234 // layout: 235 // 236 // type group struct { 237 // ctrls ctrlGroup 238 // slots [abi.SwissMapGroupSlots]slot 239 // } 240 // 241 // type slot struct { 242 // key typ.Key 243 // elem typ.Elem 244 // } 245 data unsafe.Pointer // data *typ.Group 246 } 247 248 const ( 249 ctrlGroupsSize = unsafe.Sizeof(ctrlGroup(0)) 250 groupSlotsOffset = ctrlGroupsSize 251 ) 252 253 // alignUp rounds n up to a multiple of a. a must be a power of 2. 254 func alignUp(n, a uintptr) uintptr { 255 return (n + a - 1) &^ (a - 1) 256 } 257 258 // alignUpPow2 rounds n up to the next power of 2. 259 // 260 // Returns true if round up causes overflow. 261 func alignUpPow2(n uint64) (uint64, bool) { 262 if n == 0 { 263 return 0, false 264 } 265 v := (uint64(1) << sys.Len64(n-1)) 266 if v == 0 { 267 return 0, true 268 } 269 return v, false 270 } 271 272 // ctrls returns the group control word. 273 func (g *groupReference) ctrls() *ctrlGroup { 274 return (*ctrlGroup)(g.data) 275 } 276 277 // key returns a pointer to the key at index i. 278 func (g *groupReference) key(typ *abi.SwissMapType, i uintptr) unsafe.Pointer { 279 offset := groupSlotsOffset + i*typ.SlotSize 280 281 return unsafe.Pointer(uintptr(g.data) + offset) 282 } 283 284 // elem returns a pointer to the element at index i. 285 func (g *groupReference) elem(typ *abi.SwissMapType, i uintptr) unsafe.Pointer { 286 offset := groupSlotsOffset + i*typ.SlotSize + typ.ElemOff 287 288 return unsafe.Pointer(uintptr(g.data) + offset) 289 } 290 291 // groupsReference is a wrapper type describing an array of groups stored at 292 // data. 293 type groupsReference struct { 294 // data points to an array of groups. See groupReference above for the 295 // definition of group. 296 data unsafe.Pointer // data *[length]typ.Group 297 298 // lengthMask is the number of groups in data minus one (note that 299 // length must be a power of two). This allows computing i%length 300 // quickly using bitwise AND. 301 lengthMask uint64 302 } 303 304 // newGroups allocates a new array of length groups. 305 // 306 // Length must be a power of two. 307 func newGroups(typ *abi.SwissMapType, length uint64) groupsReference { 308 return groupsReference{ 309 // TODO: make the length type the same throughout. 310 data: newarray(typ.Group, int(length)), 311 lengthMask: length - 1, 312 } 313 } 314 315 // group returns the group at index i. 316 func (g *groupsReference) group(typ *abi.SwissMapType, i uint64) groupReference { 317 // TODO(prattmic): Do something here about truncation on cast to 318 // uintptr on 32-bit systems? 319 offset := uintptr(i) * typ.GroupSize 320 321 return groupReference{ 322 data: unsafe.Pointer(uintptr(g.data) + offset), 323 } 324 } 325