runtime_faststr_swiss.mx raw
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 //go:build goexperiment.swissmap
6
7 package maps
8
9 import (
10 "internal/abi"
11 "internal/goarch"
12 "internal/race"
13 "internal/runtime/sys"
14 "unsafe"
15 )
16
17 func (m *Map) getWithoutKeySmallFastStr(typ *abi.SwissMapType, key string) unsafe.Pointer {
18 g := groupReference{
19 data: m.dirPtr,
20 }
21
22 ctrls := *g.ctrls()
23 slotKey := g.key(typ, 0)
24 slotSize := typ.SlotSize
25
26 // The 64 threshold was chosen based on performance of BenchmarkMapStringKeysEight,
27 // where there are 8 keys to check, all of which don't quick-match the lookup key.
28 // In that case, we can save hashing the lookup key. That savings is worth this extra code
29 // for strings that are long enough that hashing is expensive.
30 if len(key) > 64 {
31 // String hashing and equality might be expensive. Do a quick check first.
32 j := abi.SwissMapGroupSlots
33 for i := range abi.SwissMapGroupSlots {
34 if ctrls&(1<<7) == 0 && longStringQuickEqualityTest(key, *(*string)(slotKey)) {
35 if j < abi.SwissMapGroupSlots {
36 // 2 strings both passed the quick equality test.
37 // Break out of this loop and do it the slow way.
38 goto dohash
39 }
40 j = i
41 }
42 slotKey = unsafe.Pointer(uintptr(slotKey) + slotSize)
43 ctrls >>= 8
44 }
45 if j == abi.SwissMapGroupSlots {
46 // No slot passed the quick test.
47 return nil
48 }
49 // There's exactly one slot that passed the quick test. Do the single expensive comparison.
50 slotKey = g.key(typ, uintptr(j))
51 if key == *(*string)(slotKey) {
52 return unsafe.Pointer(uintptr(slotKey) + 2*goarch.PtrSize)
53 }
54 return nil
55 }
56
57 dohash:
58 // This path will cost 1 hash and 1+ε comparisons.
59 hash := typ.Hasher(abi.NoEscape(unsafe.Pointer(&key)), m.seed)
60 h2 := uint8(h2(hash))
61 ctrls = *g.ctrls()
62 slotKey = g.key(typ, 0)
63
64 for range abi.SwissMapGroupSlots {
65 if uint8(ctrls) == h2 && key == *(*string)(slotKey) {
66 return unsafe.Pointer(uintptr(slotKey) + 2*goarch.PtrSize)
67 }
68 slotKey = unsafe.Pointer(uintptr(slotKey) + slotSize)
69 ctrls >>= 8
70 }
71 return nil
72 }
73
74 // Returns true if a and b might be equal.
75 // Returns false if a and b are definitely not equal.
76 // Requires len(a)>=8.
77 func longStringQuickEqualityTest(a, b string) bool {
78 if len(a) != len(b) {
79 return false
80 }
81 x, y := stringPtr(a), stringPtr(b)
82 // Check first 8 bytes.
83 if *(*[8]byte)(x) != *(*[8]byte)(y) {
84 return false
85 }
86 // Check last 8 bytes.
87 x = unsafe.Pointer(uintptr(x) + uintptr(len(a)) - 8)
88 y = unsafe.Pointer(uintptr(y) + uintptr(len(a)) - 8)
89 if *(*[8]byte)(x) != *(*[8]byte)(y) {
90 return false
91 }
92 return true
93 }
94 func stringPtr(s string) unsafe.Pointer {
95 type stringStruct struct {
96 ptr unsafe.Pointer
97 len int
98 }
99 return (*stringStruct)(unsafe.Pointer(&s)).ptr
100 }
101
102 //go:linkname runtime_mapaccess1_faststr runtime.mapaccess1_faststr
103 func runtime_mapaccess1_faststr(typ *abi.SwissMapType, m *Map, key string) unsafe.Pointer {
104 if race.Enabled && m != nil {
105 callerpc := sys.GetCallerPC()
106 pc := abi.FuncPCABIInternal(runtime_mapaccess1_faststr)
107 race.ReadPC(unsafe.Pointer(m), callerpc, pc)
108 }
109
110 if m == nil || m.Used() == 0 {
111 return unsafe.Pointer(&zeroVal[0])
112 }
113
114 if m.writing != 0 {
115 fatal("concurrent map read and map write")
116 return nil
117 }
118
119 if m.dirLen <= 0 {
120 elem := m.getWithoutKeySmallFastStr(typ, key)
121 if elem == nil {
122 return unsafe.Pointer(&zeroVal[0])
123 }
124 return elem
125 }
126
127 k := key
128 hash := typ.Hasher(abi.NoEscape(unsafe.Pointer(&k)), m.seed)
129
130 // Select table.
131 idx := m.directoryIndex(hash)
132 t := m.directoryAt(idx)
133
134 // Probe table.
135 seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
136 for ; ; seq = seq.next() {
137 g := t.groups.group(typ, seq.offset)
138
139 match := g.ctrls().matchH2(h2(hash))
140
141 for match != 0 {
142 i := match.first()
143
144 slotKey := g.key(typ, i)
145 if key == *(*string)(slotKey) {
146 slotElem := unsafe.Pointer(uintptr(slotKey) + 2*goarch.PtrSize)
147 return slotElem
148 }
149 match = match.removeFirst()
150 }
151
152 match = g.ctrls().matchEmpty()
153 if match != 0 {
154 // Finding an empty slot means we've reached the end of
155 // the probe sequence.
156 return unsafe.Pointer(&zeroVal[0])
157 }
158 }
159 }
160
161 //go:linkname runtime_mapaccess2_faststr runtime.mapaccess2_faststr
162 func runtime_mapaccess2_faststr(typ *abi.SwissMapType, m *Map, key string) (unsafe.Pointer, bool) {
163 if race.Enabled && m != nil {
164 callerpc := sys.GetCallerPC()
165 pc := abi.FuncPCABIInternal(runtime_mapaccess2_faststr)
166 race.ReadPC(unsafe.Pointer(m), callerpc, pc)
167 }
168
169 if m == nil || m.Used() == 0 {
170 return unsafe.Pointer(&zeroVal[0]), false
171 }
172
173 if m.writing != 0 {
174 fatal("concurrent map read and map write")
175 return nil, false
176 }
177
178 if m.dirLen <= 0 {
179 elem := m.getWithoutKeySmallFastStr(typ, key)
180 if elem == nil {
181 return unsafe.Pointer(&zeroVal[0]), false
182 }
183 return elem, true
184 }
185
186 k := key
187 hash := typ.Hasher(abi.NoEscape(unsafe.Pointer(&k)), m.seed)
188
189 // Select table.
190 idx := m.directoryIndex(hash)
191 t := m.directoryAt(idx)
192
193 // Probe table.
194 seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
195 for ; ; seq = seq.next() {
196 g := t.groups.group(typ, seq.offset)
197
198 match := g.ctrls().matchH2(h2(hash))
199
200 for match != 0 {
201 i := match.first()
202
203 slotKey := g.key(typ, i)
204 if key == *(*string)(slotKey) {
205 slotElem := unsafe.Pointer(uintptr(slotKey) + 2*goarch.PtrSize)
206 return slotElem, true
207 }
208 match = match.removeFirst()
209 }
210
211 match = g.ctrls().matchEmpty()
212 if match != 0 {
213 // Finding an empty slot means we've reached the end of
214 // the probe sequence.
215 return unsafe.Pointer(&zeroVal[0]), false
216 }
217 }
218 }
219
220 func (m *Map) putSlotSmallFastStr(typ *abi.SwissMapType, hash uintptr, key string) unsafe.Pointer {
221 g := groupReference{
222 data: m.dirPtr,
223 }
224
225 match := g.ctrls().matchH2(h2(hash))
226
227 // Look for an existing slot containing this key.
228 for match != 0 {
229 i := match.first()
230
231 slotKey := g.key(typ, i)
232 if key == *(*string)(slotKey) {
233 // Key needs update, as the backing storage may differ.
234 *(*string)(slotKey) = key
235 slotElem := g.elem(typ, i)
236 return slotElem
237 }
238 match = match.removeFirst()
239 }
240
241 // There can't be deleted slots, small maps can't have them
242 // (see deleteSmall). Use matchEmptyOrDeleted as it is a bit
243 // more efficient than matchEmpty.
244 match = g.ctrls().matchEmptyOrDeleted()
245 if match == 0 {
246 fatal("small map with no empty slot (concurrent map writes?)")
247 }
248
249 i := match.first()
250
251 slotKey := g.key(typ, i)
252 *(*string)(slotKey) = key
253
254 slotElem := g.elem(typ, i)
255
256 g.ctrls().set(i, ctrl(h2(hash)))
257 m.used++
258
259 return slotElem
260 }
261
262 //go:linkname runtime_mapassign_faststr runtime.mapassign_faststr
263 func runtime_mapassign_faststr(typ *abi.SwissMapType, m *Map, key string) unsafe.Pointer {
264 if m == nil {
265 panic(errNilAssign)
266 }
267 if race.Enabled {
268 callerpc := sys.GetCallerPC()
269 pc := abi.FuncPCABIInternal(runtime_mapassign_faststr)
270 race.WritePC(unsafe.Pointer(m), callerpc, pc)
271 }
272 if m.writing != 0 {
273 fatal("concurrent map writes")
274 }
275
276 k := key
277 hash := typ.Hasher(abi.NoEscape(unsafe.Pointer(&k)), m.seed)
278
279 // Set writing after calling Hasher, since Hasher may panic, in which
280 // case we have not actually done a write.
281 m.writing ^= 1 // toggle, see comment on writing
282
283 if m.dirPtr == nil {
284 m.growToSmall(typ)
285 }
286
287 if m.dirLen == 0 {
288 if m.used < abi.SwissMapGroupSlots {
289 elem := m.putSlotSmallFastStr(typ, hash, key)
290
291 if m.writing == 0 {
292 fatal("concurrent map writes")
293 }
294 m.writing ^= 1
295
296 return elem
297 }
298
299 // Can't fit another entry, grow to full size map.
300 m.growToTable(typ)
301 }
302
303 var slotElem unsafe.Pointer
304 outer:
305 for {
306 // Select table.
307 idx := m.directoryIndex(hash)
308 t := m.directoryAt(idx)
309
310 seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
311
312 // As we look for a match, keep track of the first deleted slot
313 // we find, which we'll use to insert the new entry if
314 // necessary.
315 var firstDeletedGroup groupReference
316 var firstDeletedSlot uintptr
317
318 for ; ; seq = seq.next() {
319 g := t.groups.group(typ, seq.offset)
320 match := g.ctrls().matchH2(h2(hash))
321
322 // Look for an existing slot containing this key.
323 for match != 0 {
324 i := match.first()
325
326 slotKey := g.key(typ, i)
327 if key == *(*string)(slotKey) {
328 // Key needs update, as the backing
329 // storage may differ.
330 *(*string)(slotKey) = key
331 slotElem = g.elem(typ, i)
332
333 t.checkInvariants(typ, m)
334 break outer
335 }
336 match = match.removeFirst()
337 }
338
339 // No existing slot for this key in this group. Is this the end
340 // of the probe sequence?
341 match = g.ctrls().matchEmptyOrDeleted()
342 if match == 0 {
343 continue // nothing but filled slots. Keep probing.
344 }
345 i := match.first()
346 if g.ctrls().get(i) == ctrlDeleted {
347 // There are some deleted slots. Remember
348 // the first one, and keep probing.
349 if firstDeletedGroup.data == nil {
350 firstDeletedGroup = g
351 firstDeletedSlot = i
352 }
353 continue
354 }
355 // We've found an empty slot, which means we've reached the end of
356 // the probe sequence.
357
358 // If we found a deleted slot along the way, we can
359 // replace it without consuming growthLeft.
360 if firstDeletedGroup.data != nil {
361 g = firstDeletedGroup
362 i = firstDeletedSlot
363 t.growthLeft++ // will be decremented below to become a no-op.
364 }
365
366 // If we have no space left, first try to remove some tombstones.
367 if t.growthLeft == 0 {
368 t.pruneTombstones(typ, m)
369 }
370
371 // If there is room left to grow, just insert the new entry.
372 if t.growthLeft > 0 {
373 slotKey := g.key(typ, i)
374 *(*string)(slotKey) = key
375
376 slotElem = g.elem(typ, i)
377
378 g.ctrls().set(i, ctrl(h2(hash)))
379 t.growthLeft--
380 t.used++
381 m.used++
382
383 t.checkInvariants(typ, m)
384 break outer
385 }
386
387 t.rehash(typ, m)
388 continue outer
389 }
390 }
391
392 if m.writing == 0 {
393 fatal("concurrent map writes")
394 }
395 m.writing ^= 1
396
397 return slotElem
398 }
399
400 //go:linkname runtime_mapdelete_faststr runtime.mapdelete_faststr
401 func runtime_mapdelete_faststr(typ *abi.SwissMapType, m *Map, key string) {
402 if race.Enabled {
403 callerpc := sys.GetCallerPC()
404 pc := abi.FuncPCABIInternal(runtime_mapdelete_faststr)
405 race.WritePC(unsafe.Pointer(m), callerpc, pc)
406 }
407
408 if m == nil || m.Used() == 0 {
409 return
410 }
411
412 m.Delete(typ, abi.NoEscape(unsafe.Pointer(&key)))
413 }
414