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 implements Go's builtin map type.
6 package maps
7 8 import (
9 "internal/abi"
10 "internal/goarch"
11 "unsafe"
12 )
13 14 // Maximum size of a table before it is split at the directory level.
15 //
16 // TODO: Completely made up value. This should be tuned for performance vs grow
17 // latency.
18 // TODO: This should likely be based on byte size, as copying costs will
19 // dominate grow latency for large objects.
20 const maxTableCapacity = 1024
21 22 // Ensure the max capacity fits in uint16, used for capacity and growthLeft
23 // below.
24 var _ = uint16(maxTableCapacity)
25 26 // table is a Swiss table hash table structure.
27 //
28 // Each table is a complete hash table implementation.
29 //
30 // Map uses one or more tables to store entries. Extendible hashing (hash
31 // prefix) is used to select the table to use for a specific key. Using
32 // multiple tables enables incremental growth by growing only one table at a
33 // time.
34 type table struct {
35 // The number of filled slots (i.e. the number of elements in the table).
36 used uint16
37 38 // The total number of slots (always 2^N). Equal to
39 // `(groups.lengthMask+1)*abi.SwissMapGroupSlots`.
40 capacity uint16
41 42 // The number of slots we can still fill without needing to rehash.
43 //
44 // We rehash when used + tombstones > loadFactor*capacity, including
45 // tombstones so the table doesn't overfill with tombstones. This field
46 // counts down remaining empty slots before the next rehash.
47 growthLeft uint16
48 49 // The number of bits used by directory lookups above this table. Note
50 // that this may be less then globalDepth, if the directory has grown
51 // but this table has not yet been split.
52 localDepth uint8
53 54 // Index of this table in the Map directory. This is the index of the
55 // _first_ location in the directory. The table may occur in multiple
56 // sequential indicies.
57 //
58 // index is -1 if the table is stale (no longer installed in the
59 // directory).
60 index int
61 62 // groups is an array of slot groups. Each group holds abi.SwissMapGroupSlots
63 // key/elem slots and their control bytes. A table has a fixed size
64 // groups array. The table is replaced (in rehash) when more space is
65 // required.
66 //
67 // TODO(prattmic): keys and elements are interleaved to maximize
68 // locality, but it comes at the expense of wasted space for some types
69 // (consider uint8 key, uint64 element). Consider placing all keys
70 // together in these cases to save space.
71 groups groupsReference
72 }
73 74 func newTable(typ *abi.SwissMapType, capacity uint64, index int, localDepth uint8) *table {
75 if capacity < abi.SwissMapGroupSlots {
76 capacity = abi.SwissMapGroupSlots
77 }
78 79 t := &table{
80 index: index,
81 localDepth: localDepth,
82 }
83 84 if capacity > maxTableCapacity {
85 panic("initial table capacity too large")
86 }
87 88 // N.B. group count must be a power of two for probeSeq to visit every
89 // group.
90 capacity, overflow := alignUpPow2(capacity)
91 if overflow {
92 panic("rounded-up capacity overflows uint64")
93 }
94 95 t.reset(typ, uint16(capacity))
96 97 return t
98 }
99 100 // reset resets the table with new, empty groups with the specified new total
101 // capacity.
102 func (t *table) reset(typ *abi.SwissMapType, capacity uint16) {
103 groupCount := uint64(capacity) / abi.SwissMapGroupSlots
104 t.groups = newGroups(typ, groupCount)
105 t.capacity = capacity
106 t.growthLeft = t.maxGrowthLeft()
107 108 for i := uint64(0); i <= t.groups.lengthMask; i++ {
109 g := t.groups.group(typ, i)
110 g.ctrls().setEmpty()
111 }
112 }
113 114 // maxGrowthLeft is the number of inserts we can do before
115 // resizing, starting from an empty table.
116 func (t *table) maxGrowthLeft() uint16 {
117 if t.capacity == 0 {
118 // No real reason to support zero capacity table, since an
119 // empty Map simply won't have a table.
120 panic("table must have positive capacity")
121 } else if t.capacity <= abi.SwissMapGroupSlots {
122 // If the map fits in a single group then we're able to fill all of
123 // the slots except 1 (an empty slot is needed to terminate find
124 // operations).
125 //
126 // TODO(go.dev/issue/54766): With a special case in probing for
127 // single-group tables, we could fill all slots.
128 return t.capacity - 1
129 } else {
130 if t.capacity*maxAvgGroupLoad < t.capacity {
131 // TODO(prattmic): Do something cleaner.
132 panic("overflow")
133 }
134 return (t.capacity * maxAvgGroupLoad) / abi.SwissMapGroupSlots
135 }
136 137 }
138 139 func (t *table) Used() uint64 {
140 return uint64(t.used)
141 }
142 143 // Get performs a lookup of the key that key points to. It returns a pointer to
144 // the element, or false if the key doesn't exist.
145 func (t *table) Get(typ *abi.SwissMapType, m *Map, key unsafe.Pointer) (unsafe.Pointer, bool) {
146 // TODO(prattmic): We could avoid hashing in a variety of special
147 // cases.
148 //
149 // - One entry maps could just directly compare the single entry
150 // without hashing.
151 // - String keys could do quick checks of a few bytes before hashing.
152 hash := typ.Hasher(key, m.seed)
153 _, elem, ok := t.getWithKey(typ, hash, key)
154 return elem, ok
155 }
156 157 // getWithKey performs a lookup of key, returning a pointer to the version of
158 // the key in the map in addition to the element.
159 //
160 // This is relevant when multiple different key values compare equal (e.g.,
161 // +0.0 and -0.0). When a grow occurs during iteration, iteration perform a
162 // lookup of keys from the old group in the new group in order to correctly
163 // expose updated elements. For NeedsKeyUpdate keys, iteration also must return
164 // the new key value, not the old key value.
165 // hash must be the hash of the key.
166 func (t *table) getWithKey(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer, bool) {
167 // To find the location of a key in the table, we compute hash(key). From
168 // h1(hash(key)) and the capacity, we construct a probeSeq that visits
169 // every group of slots in some interesting order. See [probeSeq].
170 //
171 // We walk through these indices. At each index, we select the entire
172 // group starting with that index and extract potential candidates:
173 // occupied slots with a control byte equal to h2(hash(key)). The key
174 // at candidate slot i is compared with key; if key == g.slot(i).key
175 // we are done and return the slot; if there is an empty slot in the
176 // group, we stop and return an error; otherwise we continue to the
177 // next probe index. Tombstones (ctrlDeleted) effectively behave like
178 // full slots that never match the value we're looking for.
179 //
180 // The h2 bits ensure when we compare a key we are likely to have
181 // actually found the object. That is, the chance is low that keys
182 // compare false. Thus, when we search for an object, we are unlikely
183 // to call Equal many times. This likelihood can be analyzed as follows
184 // (assuming that h2 is a random enough hash function).
185 //
186 // Let's assume that there are k "wrong" objects that must be examined
187 // in a probe sequence. For example, when doing a find on an object
188 // that is in the table, k is the number of objects between the start
189 // of the probe sequence and the final found object (not including the
190 // final found object). The expected number of objects with an h2 match
191 // is then k/128. Measurements and analysis indicate that even at high
192 // load factors, k is less than 32, meaning that the number of false
193 // positive comparisons we must perform is less than 1/8 per find.
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 typ.IndirectKey() {
205 slotKey = *((*unsafe.Pointer)(slotKey))
206 }
207 if typ.Key.Equal(key, slotKey) {
208 slotElem := g.elem(typ, i)
209 if typ.IndirectElem() {
210 slotElem = *((*unsafe.Pointer)(slotElem))
211 }
212 return slotKey, slotElem, true
213 }
214 match = match.removeFirst()
215 }
216 217 match = g.ctrls().matchEmpty()
218 if match != 0 {
219 // Finding an empty slot means we've reached the end of
220 // the probe sequence.
221 return nil, nil, false
222 }
223 }
224 }
225 226 func (t *table) getWithoutKey(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, bool) {
227 seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
228 for ; ; seq = seq.next() {
229 g := t.groups.group(typ, seq.offset)
230 231 match := g.ctrls().matchH2(h2(hash))
232 233 for match != 0 {
234 i := match.first()
235 236 slotKey := g.key(typ, i)
237 if typ.IndirectKey() {
238 slotKey = *((*unsafe.Pointer)(slotKey))
239 }
240 if typ.Key.Equal(key, slotKey) {
241 slotElem := g.elem(typ, i)
242 if typ.IndirectElem() {
243 slotElem = *((*unsafe.Pointer)(slotElem))
244 }
245 return slotElem, true
246 }
247 match = match.removeFirst()
248 }
249 250 match = g.ctrls().matchEmpty()
251 if match != 0 {
252 // Finding an empty slot means we've reached the end of
253 // the probe sequence.
254 return nil, false
255 }
256 }
257 }
258 259 // PutSlot returns a pointer to the element slot where an inserted element
260 // should be written, and ok if it returned a valid slot.
261 //
262 // PutSlot returns ok false if the table was split and the Map needs to find
263 // the new table.
264 //
265 // hash must be the hash of key.
266 func (t *table) PutSlot(typ *abi.SwissMapType, m *Map, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, bool) {
267 seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
268 269 // As we look for a match, keep track of the first deleted slot we
270 // find, which we'll use to insert the new entry if necessary.
271 var firstDeletedGroup groupReference
272 var firstDeletedSlot uintptr
273 274 for ; ; seq = seq.next() {
275 g := t.groups.group(typ, seq.offset)
276 match := g.ctrls().matchH2(h2(hash))
277 278 // Look for an existing slot containing this key.
279 for match != 0 {
280 i := match.first()
281 282 slotKey := g.key(typ, i)
283 if typ.IndirectKey() {
284 slotKey = *((*unsafe.Pointer)(slotKey))
285 }
286 if typ.Key.Equal(key, slotKey) {
287 if typ.NeedKeyUpdate() {
288 typedmemmove(typ.Key, slotKey, key)
289 }
290 291 slotElem := g.elem(typ, i)
292 if typ.IndirectElem() {
293 slotElem = *((*unsafe.Pointer)(slotElem))
294 }
295 296 t.checkInvariants(typ, m)
297 return slotElem, true
298 }
299 match = match.removeFirst()
300 }
301 302 // No existing slot for this key in this group. Is this the end
303 // of the probe sequence?
304 match = g.ctrls().matchEmptyOrDeleted()
305 if match == 0 {
306 continue // nothing but filled slots. Keep probing.
307 }
308 i := match.first()
309 if g.ctrls().get(i) == ctrlDeleted {
310 // There are some deleted slots. Remember
311 // the first one, and keep probing.
312 if firstDeletedGroup.data == nil {
313 firstDeletedGroup = g
314 firstDeletedSlot = i
315 }
316 continue
317 }
318 // We've found an empty slot, which means we've reached the end of
319 // the probe sequence.
320 321 // If we found a deleted slot along the way, we can
322 // replace it without consuming growthLeft.
323 if firstDeletedGroup.data != nil {
324 g = firstDeletedGroup
325 i = firstDeletedSlot
326 t.growthLeft++ // will be decremented below to become a no-op.
327 }
328 329 // If we have no space left, first try to remove some tombstones.
330 if t.growthLeft == 0 {
331 t.pruneTombstones(typ, m)
332 }
333 334 // If there is room left to grow, just insert the new entry.
335 if t.growthLeft > 0 {
336 slotKey := g.key(typ, i)
337 if typ.IndirectKey() {
338 kmem := newobject(typ.Key)
339 *(*unsafe.Pointer)(slotKey) = kmem
340 slotKey = kmem
341 }
342 typedmemmove(typ.Key, slotKey, key)
343 344 slotElem := g.elem(typ, i)
345 if typ.IndirectElem() {
346 emem := newobject(typ.Elem)
347 *(*unsafe.Pointer)(slotElem) = emem
348 slotElem = emem
349 }
350 351 g.ctrls().set(i, ctrl(h2(hash)))
352 t.growthLeft--
353 t.used++
354 m.used++
355 356 t.checkInvariants(typ, m)
357 return slotElem, true
358 }
359 360 t.rehash(typ, m)
361 return nil, false
362 }
363 }
364 365 // uncheckedPutSlot inserts an entry known not to be in the table.
366 // This is used for grow/split where we are making a new table from
367 // entries in an existing table.
368 //
369 // Decrements growthLeft and increments used.
370 //
371 // Requires that the entry does not exist in the table, and that the table has
372 // room for another element without rehashing.
373 //
374 // Requires that there are no deleted entries in the table.
375 //
376 // For indirect keys and/or elements, the key and elem pointers can be
377 // put directly into the map, they do not need to be copied. This
378 // requires the caller to ensure that the referenced memory never
379 // changes (by sourcing those pointers from another indirect key/elem
380 // map).
381 func (t *table) uncheckedPutSlot(typ *abi.SwissMapType, hash uintptr, key, elem unsafe.Pointer) {
382 if t.growthLeft == 0 {
383 panic("invariant failed: growthLeft is unexpectedly 0")
384 }
385 386 // Given key and its hash hash(key), to insert it, we construct a
387 // probeSeq, and use it to find the first group with an unoccupied (empty
388 // or deleted) slot. We place the key/value into the first such slot in
389 // the group and mark it as full with key's H2.
390 seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
391 for ; ; seq = seq.next() {
392 g := t.groups.group(typ, seq.offset)
393 394 match := g.ctrls().matchEmptyOrDeleted()
395 if match != 0 {
396 i := match.first()
397 398 slotKey := g.key(typ, i)
399 if typ.IndirectKey() {
400 *(*unsafe.Pointer)(slotKey) = key
401 } else {
402 typedmemmove(typ.Key, slotKey, key)
403 }
404 405 slotElem := g.elem(typ, i)
406 if typ.IndirectElem() {
407 *(*unsafe.Pointer)(slotElem) = elem
408 } else {
409 typedmemmove(typ.Elem, slotElem, elem)
410 }
411 412 t.growthLeft--
413 t.used++
414 g.ctrls().set(i, ctrl(h2(hash)))
415 return
416 }
417 }
418 }
419 420 // Delete returns true if it put a tombstone in t.
421 func (t *table) Delete(typ *abi.SwissMapType, m *Map, hash uintptr, key unsafe.Pointer) bool {
422 seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
423 for ; ; seq = seq.next() {
424 g := t.groups.group(typ, seq.offset)
425 match := g.ctrls().matchH2(h2(hash))
426 427 for match != 0 {
428 i := match.first()
429 430 slotKey := g.key(typ, i)
431 origSlotKey := slotKey
432 if typ.IndirectKey() {
433 slotKey = *((*unsafe.Pointer)(slotKey))
434 }
435 436 if typ.Key.Equal(key, slotKey) {
437 t.used--
438 m.used--
439 440 if typ.IndirectKey() {
441 // Clearing the pointer is sufficient.
442 *(*unsafe.Pointer)(origSlotKey) = nil
443 } else if typ.Key.Pointers() {
444 // Only bothing clear the key if there
445 // are pointers in it.
446 typedmemclr(typ.Key, slotKey)
447 }
448 449 slotElem := g.elem(typ, i)
450 if typ.IndirectElem() {
451 // Clearing the pointer is sufficient.
452 *(*unsafe.Pointer)(slotElem) = nil
453 } else {
454 // Unlike keys, always clear the elem (even if
455 // it contains no pointers), as compound
456 // assignment operations depend on cleared
457 // deleted values. See
458 // https://go.dev/issue/25936.
459 typedmemclr(typ.Elem, slotElem)
460 }
461 462 // Only a full group can appear in the middle
463 // of a probe sequence (a group with at least
464 // one empty slot terminates probing). Once a
465 // group becomes full, it stays full until
466 // rehashing/resizing. So if the group isn't
467 // full now, we can simply remove the element.
468 // Otherwise, we create a tombstone to mark the
469 // slot as deleted.
470 var tombstone bool
471 if g.ctrls().matchEmpty() != 0 {
472 g.ctrls().set(i, ctrlEmpty)
473 t.growthLeft++
474 } else {
475 g.ctrls().set(i, ctrlDeleted)
476 tombstone = true
477 }
478 479 t.checkInvariants(typ, m)
480 return tombstone
481 }
482 match = match.removeFirst()
483 }
484 485 match = g.ctrls().matchEmpty()
486 if match != 0 {
487 // Finding an empty slot means we've reached the end of
488 // the probe sequence.
489 return false
490 }
491 }
492 }
493 494 // pruneTombstones goes through the table and tries to remove
495 // tombstones that are no longer needed. Best effort.
496 // Note that it only removes tombstones, it does not move elements.
497 // Moving elements would do a better job but is infeasbile due to
498 // iterator semantics.
499 //
500 // Pruning should only succeed if it can remove O(n) tombstones.
501 // It would be bad if we did O(n) work to find 1 tombstone to remove.
502 // Then the next insert would spend another O(n) work to find 1 more
503 // tombstone to remove, etc.
504 //
505 // We really need to remove O(n) tombstones so we can pay for the cost
506 // of finding them. If we can't, then we need to grow (which is also O(n),
507 // but guarantees O(n) subsequent inserts can happen in constant time).
508 func (t *table) pruneTombstones(typ *abi.SwissMapType, m *Map) {
509 if t.tombstones()*10 < t.capacity { // 10% of capacity
510 // Not enough tombstones to be worth the effort.
511 return
512 }
513 514 // Bit set marking all the groups whose tombstones are needed.
515 var needed [(maxTableCapacity/abi.SwissMapGroupSlots + 31) / 32]uint32
516 517 // Trace the probe sequence of every full entry.
518 for i := uint64(0); i <= t.groups.lengthMask; i++ {
519 g := t.groups.group(typ, i)
520 match := g.ctrls().matchFull()
521 for match != 0 {
522 j := match.first()
523 match = match.removeFirst()
524 key := g.key(typ, j)
525 if typ.IndirectKey() {
526 key = *((*unsafe.Pointer)(key))
527 }
528 if !typ.Key.Equal(key, key) {
529 // Key not equal to itself. We never have to find these
530 // keys on lookup (only on iteration), so we can break
531 // their probe sequences at will.
532 continue
533 }
534 // Walk probe sequence for this key.
535 // Each tombstone group we need to walk past is marked required.
536 hash := typ.Hasher(key, m.seed)
537 for seq := makeProbeSeq(h1(hash), t.groups.lengthMask); ; seq = seq.next() {
538 if seq.offset == i {
539 break // reached group of element in probe sequence
540 }
541 g := t.groups.group(typ, seq.offset)
542 m := g.ctrls().matchEmptyOrDeleted()
543 if m != 0 { // must be deleted, not empty, as we haven't found our key yet
544 // Mark this group's tombstone as required.
545 needed[seq.offset/32] |= 1 << (seq.offset % 32)
546 }
547 }
548 }
549 if g.ctrls().matchEmpty() != 0 {
550 // Also mark non-tombstone-containing groups, so we don't try
551 // to remove tombstones from them below.
552 needed[i/32] |= 1 << (i % 32)
553 }
554 }
555 556 // First, see if we can remove enough tombstones to restore capacity.
557 // This function is O(n), so only remove tombstones if we can remove
558 // enough of them to justify the O(n) cost.
559 cnt := 0
560 for i := uint64(0); i <= t.groups.lengthMask; i++ {
561 if needed[i/32]>>(i%32)&1 != 0 {
562 continue
563 }
564 g := t.groups.group(typ, i)
565 m := g.ctrls().matchEmptyOrDeleted() // must be deleted
566 cnt += m.count()
567 }
568 if cnt*10 < int(t.capacity) { // Can we restore 10% of capacity?
569 return // don't bother removing tombstones. Caller will grow instead.
570 }
571 572 // Prune unneeded tombstones.
573 for i := uint64(0); i <= t.groups.lengthMask; i++ {
574 if needed[i/32]>>(i%32)&1 != 0 {
575 continue
576 }
577 g := t.groups.group(typ, i)
578 m := g.ctrls().matchEmptyOrDeleted() // must be deleted
579 for m != 0 {
580 k := m.first()
581 m = m.removeFirst()
582 g.ctrls().set(k, ctrlEmpty)
583 t.growthLeft++
584 }
585 // TODO: maybe we could convert all slots at once
586 // using some bitvector trickery.
587 }
588 }
589 590 // tombstones returns the number of deleted (tombstone) entries in the table. A
591 // tombstone is a slot that has been deleted but is still considered occupied
592 // so as not to violate the probing invariant.
593 func (t *table) tombstones() uint16 {
594 return (t.capacity*maxAvgGroupLoad)/abi.SwissMapGroupSlots - t.used - t.growthLeft
595 }
596 597 // Clear deletes all entries from the map resulting in an empty map.
598 func (t *table) Clear(typ *abi.SwissMapType) {
599 mgl := t.maxGrowthLeft()
600 if t.used == 0 && t.growthLeft == mgl { // no current entries and no tombstones
601 return
602 }
603 for i := uint64(0); i <= t.groups.lengthMask; i++ {
604 g := t.groups.group(typ, i)
605 if g.ctrls().matchFull() != 0 {
606 typedmemclr(typ.Group, g.data)
607 }
608 g.ctrls().setEmpty()
609 }
610 t.used = 0
611 t.growthLeft = mgl
612 }
613 614 type Iter struct {
615 key unsafe.Pointer // Must be in first position. Write nil to indicate iteration end (see cmd/compile/internal/walk/range.go).
616 elem unsafe.Pointer // Must be in second position (see cmd/compile/internal/walk/range.go).
617 typ *abi.SwissMapType
618 m *Map
619 620 // Randomize iteration order by starting iteration at a random slot
621 // offset. The offset into the directory uses a separate offset, as it
622 // must adjust when the directory grows.
623 entryOffset uint64
624 dirOffset uint64
625 626 // Snapshot of Map.clearSeq at iteration initialization time. Used to
627 // detect clear during iteration.
628 clearSeq uint64
629 630 // Value of Map.globalDepth during the last call to Next. Used to
631 // detect directory grow during iteration.
632 globalDepth uint8
633 634 // dirIdx is the current directory index, prior to adjustment by
635 // dirOffset.
636 dirIdx int
637 638 // tab is the table at dirIdx during the previous call to Next.
639 tab *table
640 641 // group is the group at entryIdx during the previous call to Next.
642 group groupReference
643 644 // entryIdx is the current entry index, prior to adjustment by entryOffset.
645 // The lower 3 bits of the index are the slot index, and the upper bits
646 // are the group index.
647 entryIdx uint64
648 }
649 650 // Init initializes Iter for iteration.
651 func (it *Iter) Init(typ *abi.SwissMapType, m *Map) {
652 it.typ = typ
653 654 if m == nil || m.used == 0 {
655 return
656 }
657 658 dirIdx := 0
659 var groupSmall groupReference
660 if m.dirLen <= 0 {
661 // Use dirIdx == -1 as sentinel for small maps.
662 dirIdx = -1
663 groupSmall.data = m.dirPtr
664 }
665 666 it.m = m
667 it.entryOffset = rand()
668 it.dirOffset = rand()
669 it.globalDepth = m.globalDepth
670 it.dirIdx = dirIdx
671 it.group = groupSmall
672 it.clearSeq = m.clearSeq
673 }
674 675 func (it *Iter) Initialized() bool {
676 return it.typ != nil
677 }
678 679 // Map returns the map this iterator is iterating over.
680 func (it *Iter) Map() *Map {
681 return it.m
682 }
683 684 // Key returns a pointer to the current key. nil indicates end of iteration.
685 //
686 // Must not be called prior to Next.
687 func (it *Iter) Key() unsafe.Pointer {
688 return it.key
689 }
690 691 // Key returns a pointer to the current element. nil indicates end of
692 // iteration.
693 //
694 // Must not be called prior to Next.
695 func (it *Iter) Elem() unsafe.Pointer {
696 return it.elem
697 }
698 699 func (it *Iter) nextDirIdx() {
700 // Skip other entries in the directory that refer to the same
701 // logical table. There are two cases of this:
702 //
703 // Consider this directory:
704 //
705 // - 0: *t1
706 // - 1: *t1
707 // - 2: *t2a
708 // - 3: *t2b
709 //
710 // At some point, the directory grew to accommodate a split of
711 // t2. t1 did not split, so entries 0 and 1 both point to t1.
712 // t2 did split, so the two halves were installed in entries 2
713 // and 3.
714 //
715 // If dirIdx is 0 and it.tab is t1, then we should skip past
716 // entry 1 to avoid repeating t1.
717 //
718 // If dirIdx is 2 and it.tab is t2 (pre-split), then we should
719 // skip past entry 3 because our pre-split t2 already covers
720 // all keys from t2a and t2b (except for new insertions, which
721 // iteration need not return).
722 //
723 // We can achieve both of these by using to difference between
724 // the directory and table depth to compute how many entries
725 // the table covers.
726 entries := 1 << (it.m.globalDepth - it.tab.localDepth)
727 it.dirIdx += entries
728 it.tab = nil
729 it.group = groupReference{}
730 it.entryIdx = 0
731 }
732 733 // Return the appropriate key/elem for key at slotIdx index within it.group, if
734 // any.
735 func (it *Iter) grownKeyElem(key unsafe.Pointer, slotIdx uintptr) (unsafe.Pointer, unsafe.Pointer, bool) {
736 newKey, newElem, ok := it.m.getWithKey(it.typ, key)
737 if !ok {
738 // Key has likely been deleted, and
739 // should be skipped.
740 //
741 // One exception is keys that don't
742 // compare equal to themselves (e.g.,
743 // NaN). These keys cannot be looked
744 // up, so getWithKey will fail even if
745 // the key exists.
746 //
747 // However, we are in luck because such
748 // keys cannot be updated and they
749 // cannot be deleted except with clear.
750 // Thus if no clear has occurred, the
751 // key/elem must still exist exactly as
752 // in the old groups, so we can return
753 // them from there.
754 //
755 // TODO(prattmic): Consider checking
756 // clearSeq early. If a clear occurred,
757 // Next could always return
758 // immediately, as iteration doesn't
759 // need to return anything added after
760 // clear.
761 if it.clearSeq == it.m.clearSeq && !it.typ.Key.Equal(key, key) {
762 elem := it.group.elem(it.typ, slotIdx)
763 if it.typ.IndirectElem() {
764 elem = *((*unsafe.Pointer)(elem))
765 }
766 return key, elem, true
767 }
768 769 // This entry doesn't exist anymore.
770 return nil, nil, false
771 }
772 773 return newKey, newElem, true
774 }
775 776 // Next proceeds to the next element in iteration, which can be accessed via
777 // the Key and Elem methods.
778 //
779 // The table can be mutated during iteration, though there is no guarantee that
780 // the mutations will be visible to the iteration.
781 //
782 // Init must be called prior to Next.
783 func (it *Iter) Next() {
784 if it.m == nil {
785 // Map was empty at Iter.Init.
786 it.key = nil
787 it.elem = nil
788 return
789 }
790 791 if it.m.writing != 0 {
792 fatal("concurrent map iteration and map write")
793 return
794 }
795 796 if it.dirIdx < 0 {
797 // Map was small at Init.
798 for ; it.entryIdx < abi.SwissMapGroupSlots; it.entryIdx++ {
799 k := uintptr(it.entryIdx+it.entryOffset) % abi.SwissMapGroupSlots
800 801 if (it.group.ctrls().get(k) & ctrlEmpty) == ctrlEmpty {
802 // Empty or deleted.
803 continue
804 }
805 806 key := it.group.key(it.typ, k)
807 if it.typ.IndirectKey() {
808 key = *((*unsafe.Pointer)(key))
809 }
810 811 // As below, if we have grown to a full map since Init,
812 // we continue to use the old group to decide the keys
813 // to return, but must look them up again in the new
814 // tables.
815 grown := it.m.dirLen > 0
816 var elem unsafe.Pointer
817 if grown {
818 var ok bool
819 newKey, newElem, ok := it.m.getWithKey(it.typ, key)
820 if !ok {
821 // See comment below.
822 if it.clearSeq == it.m.clearSeq && !it.typ.Key.Equal(key, key) {
823 elem = it.group.elem(it.typ, k)
824 if it.typ.IndirectElem() {
825 elem = *((*unsafe.Pointer)(elem))
826 }
827 } else {
828 continue
829 }
830 } else {
831 key = newKey
832 elem = newElem
833 }
834 } else {
835 elem = it.group.elem(it.typ, k)
836 if it.typ.IndirectElem() {
837 elem = *((*unsafe.Pointer)(elem))
838 }
839 }
840 841 it.entryIdx++
842 it.key = key
843 it.elem = elem
844 return
845 }
846 it.key = nil
847 it.elem = nil
848 return
849 }
850 851 if it.globalDepth != it.m.globalDepth {
852 // Directory has grown since the last call to Next. Adjust our
853 // directory index.
854 //
855 // Consider:
856 //
857 // Before:
858 // - 0: *t1
859 // - 1: *t2 <- dirIdx
860 //
861 // After:
862 // - 0: *t1a (split)
863 // - 1: *t1b (split)
864 // - 2: *t2 <- dirIdx
865 // - 3: *t2
866 //
867 // That is, we want to double the current index when the
868 // directory size doubles (or quadruple when the directory size
869 // quadruples, etc).
870 //
871 // The actual (randomized) dirIdx is computed below as:
872 //
873 // dirIdx := (it.dirIdx + it.dirOffset) % it.m.dirLen
874 //
875 // Multiplication is associative across modulo operations,
876 // A * (B % C) = (A * B) % (A * C),
877 // provided that A is positive.
878 //
879 // Thus we can achieve this by adjusting it.dirIdx,
880 // it.dirOffset, and it.m.dirLen individually.
881 orders := it.m.globalDepth - it.globalDepth
882 it.dirIdx <<= orders
883 it.dirOffset <<= orders
884 // it.m.dirLen was already adjusted when the directory grew.
885 886 it.globalDepth = it.m.globalDepth
887 }
888 889 // Continue iteration until we find a full slot.
890 for ; it.dirIdx < it.m.dirLen; it.nextDirIdx() {
891 // Resolve the table.
892 if it.tab == nil {
893 dirIdx := int((uint64(it.dirIdx) + it.dirOffset) & uint64(it.m.dirLen-1))
894 newTab := it.m.directoryAt(uintptr(dirIdx))
895 if newTab.index != dirIdx {
896 // Normally we skip past all duplicates of the
897 // same entry in the table (see updates to
898 // it.dirIdx at the end of the loop below), so
899 // this case wouldn't occur.
900 //
901 // But on the very first call, we have a
902 // completely randomized dirIdx that may refer
903 // to a middle of a run of tables in the
904 // directory. Do a one-time adjustment of the
905 // offset to ensure we start at first index for
906 // newTable.
907 diff := dirIdx - newTab.index
908 it.dirOffset -= uint64(diff)
909 dirIdx = newTab.index
910 }
911 it.tab = newTab
912 }
913 914 // N.B. Use it.tab, not newTab. It is important to use the old
915 // table for key selection if the table has grown. See comment
916 // on grown below.
917 918 entryMask := uint64(it.tab.capacity) - 1
919 if it.entryIdx > entryMask {
920 // Continue to next table.
921 continue
922 }
923 924 // Fast path: skip matching and directly check if entryIdx is a
925 // full slot.
926 //
927 // In the slow path below, we perform an 8-slot match check to
928 // look for full slots within the group.
929 //
930 // However, with a max load factor of 7/8, each slot in a
931 // mostly full map has a high probability of being full. Thus
932 // it is cheaper to check a single slot than do a full control
933 // match.
934 935 entryIdx := (it.entryIdx + it.entryOffset) & entryMask
936 slotIdx := uintptr(entryIdx & (abi.SwissMapGroupSlots - 1))
937 if slotIdx == 0 || it.group.data == nil {
938 // Only compute the group (a) when we switch
939 // groups (slotIdx rolls over) and (b) on the
940 // first iteration in this table (slotIdx may
941 // not be zero due to entryOffset).
942 groupIdx := entryIdx >> abi.SwissMapGroupSlotsBits
943 it.group = it.tab.groups.group(it.typ, groupIdx)
944 }
945 946 if (it.group.ctrls().get(slotIdx) & ctrlEmpty) == 0 {
947 // Slot full.
948 949 key := it.group.key(it.typ, slotIdx)
950 if it.typ.IndirectKey() {
951 key = *((*unsafe.Pointer)(key))
952 }
953 954 grown := it.tab.index == -1
955 var elem unsafe.Pointer
956 if grown {
957 newKey, newElem, ok := it.grownKeyElem(key, slotIdx)
958 if !ok {
959 // This entry doesn't exist
960 // anymore. Continue to the
961 // next one.
962 goto next
963 } else {
964 key = newKey
965 elem = newElem
966 }
967 } else {
968 elem = it.group.elem(it.typ, slotIdx)
969 if it.typ.IndirectElem() {
970 elem = *((*unsafe.Pointer)(elem))
971 }
972 }
973 974 it.entryIdx++
975 it.key = key
976 it.elem = elem
977 return
978 }
979 980 next:
981 it.entryIdx++
982 983 // Slow path: use a match on the control word to jump ahead to
984 // the next full slot.
985 //
986 // This is highly effective for maps with particularly low load
987 // (e.g., map allocated with large hint but few insertions).
988 //
989 // For maps with medium load (e.g., 3-4 empty slots per group)
990 // it also tends to work pretty well. Since slots within a
991 // group are filled in order, then if there have been no
992 // deletions, a match will allow skipping past all empty slots
993 // at once.
994 //
995 // Note: it is tempting to cache the group match result in the
996 // iterator to use across Next calls. However because entries
997 // may be deleted between calls later calls would still need to
998 // double-check the control value.
999 1000 var groupMatch bitset
1001 for it.entryIdx <= entryMask {
1002 entryIdx := (it.entryIdx + it.entryOffset) & entryMask
1003 slotIdx := uintptr(entryIdx & (abi.SwissMapGroupSlots - 1))
1004 1005 if slotIdx == 0 || it.group.data == nil {
1006 // Only compute the group (a) when we switch
1007 // groups (slotIdx rolls over) and (b) on the
1008 // first iteration in this table (slotIdx may
1009 // not be zero due to entryOffset).
1010 groupIdx := entryIdx >> abi.SwissMapGroupSlotsBits
1011 it.group = it.tab.groups.group(it.typ, groupIdx)
1012 }
1013 1014 if groupMatch == 0 {
1015 groupMatch = it.group.ctrls().matchFull()
1016 1017 if slotIdx != 0 {
1018 // Starting in the middle of the group.
1019 // Ignore earlier groups.
1020 groupMatch = groupMatch.removeBelow(slotIdx)
1021 }
1022 1023 // Skip over groups that are composed of only empty or
1024 // deleted slots.
1025 if groupMatch == 0 {
1026 // Jump past remaining slots in this
1027 // group.
1028 it.entryIdx += abi.SwissMapGroupSlots - uint64(slotIdx)
1029 continue
1030 }
1031 1032 i := groupMatch.first()
1033 it.entryIdx += uint64(i - slotIdx)
1034 if it.entryIdx > entryMask {
1035 // Past the end of this table's iteration.
1036 continue
1037 }
1038 entryIdx += uint64(i - slotIdx)
1039 slotIdx = i
1040 }
1041 1042 key := it.group.key(it.typ, slotIdx)
1043 if it.typ.IndirectKey() {
1044 key = *((*unsafe.Pointer)(key))
1045 }
1046 1047 // If the table has changed since the last
1048 // call, then it has grown or split. In this
1049 // case, further mutations (changes to
1050 // key->elem or deletions) will not be visible
1051 // in our snapshot table. Instead we must
1052 // consult the new table by doing a full
1053 // lookup.
1054 //
1055 // We still use our old table to decide which
1056 // keys to lookup in order to avoid returning
1057 // the same key twice.
1058 grown := it.tab.index == -1
1059 var elem unsafe.Pointer
1060 if grown {
1061 newKey, newElem, ok := it.grownKeyElem(key, slotIdx)
1062 if !ok {
1063 // This entry doesn't exist anymore.
1064 // Continue to the next one.
1065 groupMatch = groupMatch.removeFirst()
1066 if groupMatch == 0 {
1067 // No more entries in this
1068 // group. Continue to next
1069 // group.
1070 it.entryIdx += abi.SwissMapGroupSlots - uint64(slotIdx)
1071 continue
1072 }
1073 1074 // Next full slot.
1075 i := groupMatch.first()
1076 it.entryIdx += uint64(i - slotIdx)
1077 continue
1078 } else {
1079 key = newKey
1080 elem = newElem
1081 }
1082 } else {
1083 elem = it.group.elem(it.typ, slotIdx)
1084 if it.typ.IndirectElem() {
1085 elem = *((*unsafe.Pointer)(elem))
1086 }
1087 }
1088 1089 // Jump ahead to the next full slot or next group.
1090 groupMatch = groupMatch.removeFirst()
1091 if groupMatch == 0 {
1092 // No more entries in
1093 // this group. Continue
1094 // to next group.
1095 it.entryIdx += abi.SwissMapGroupSlots - uint64(slotIdx)
1096 } else {
1097 // Next full slot.
1098 i := groupMatch.first()
1099 it.entryIdx += uint64(i - slotIdx)
1100 }
1101 1102 it.key = key
1103 it.elem = elem
1104 return
1105 }
1106 1107 // Continue to next table.
1108 }
1109 1110 it.key = nil
1111 it.elem = nil
1112 return
1113 }
1114 1115 // Replaces the table with one larger table or two split tables to fit more
1116 // entries. Since the table is replaced, t is now stale and should not be
1117 // modified.
1118 func (t *table) rehash(typ *abi.SwissMapType, m *Map) {
1119 // TODO(prattmic): SwissTables typically perform a "rehash in place"
1120 // operation which recovers capacity consumed by tombstones without growing
1121 // the table by reordering slots as necessary to maintain the probe
1122 // invariant while eliminating all tombstones.
1123 //
1124 // However, it is unclear how to make rehash in place work with
1125 // iteration. Since iteration simply walks through all slots in order
1126 // (with random start offset), reordering the slots would break
1127 // iteration.
1128 //
1129 // As an alternative, we could do a "resize" to new groups allocation
1130 // of the same size. This would eliminate the tombstones, but using a
1131 // new allocation, so the existing grow support in iteration would
1132 // continue to work.
1133 1134 newCapacity := 2 * t.capacity
1135 if newCapacity <= maxTableCapacity {
1136 t.grow(typ, m, newCapacity)
1137 return
1138 }
1139 1140 t.split(typ, m)
1141 }
1142 1143 // Bitmask for the last selection bit at this depth.
1144 func localDepthMask(localDepth uint8) uintptr {
1145 if goarch.PtrSize == 4 {
1146 return uintptr(1) << (32 - localDepth)
1147 }
1148 return uintptr(1) << (64 - localDepth)
1149 }
1150 1151 // split the table into two, installing the new tables in the map directory.
1152 func (t *table) split(typ *abi.SwissMapType, m *Map) {
1153 localDepth := t.localDepth
1154 localDepth++
1155 1156 // TODO: is this the best capacity?
1157 left := newTable(typ, maxTableCapacity, -1, localDepth)
1158 right := newTable(typ, maxTableCapacity, -1, localDepth)
1159 1160 // Split in half at the localDepth bit from the top.
1161 mask := localDepthMask(localDepth)
1162 1163 for i := uint64(0); i <= t.groups.lengthMask; i++ {
1164 g := t.groups.group(typ, i)
1165 for j := uintptr(0); j < abi.SwissMapGroupSlots; j++ {
1166 if (g.ctrls().get(j) & ctrlEmpty) == ctrlEmpty {
1167 // Empty or deleted
1168 continue
1169 }
1170 1171 key := g.key(typ, j)
1172 if typ.IndirectKey() {
1173 key = *((*unsafe.Pointer)(key))
1174 }
1175 1176 elem := g.elem(typ, j)
1177 if typ.IndirectElem() {
1178 elem = *((*unsafe.Pointer)(elem))
1179 }
1180 1181 hash := typ.Hasher(key, m.seed)
1182 var newTable *table
1183 if hash&mask == 0 {
1184 newTable = left
1185 } else {
1186 newTable = right
1187 }
1188 newTable.uncheckedPutSlot(typ, hash, key, elem)
1189 }
1190 }
1191 1192 m.installTableSplit(t, left, right)
1193 t.index = -1
1194 }
1195 1196 // grow the capacity of the table by allocating a new table with a bigger array
1197 // and uncheckedPutting each element of the table into the new table (we know
1198 // that no insertion here will Put an already-present value), and discard the
1199 // old table.
1200 func (t *table) grow(typ *abi.SwissMapType, m *Map, newCapacity uint16) {
1201 newTable := newTable(typ, uint64(newCapacity), t.index, t.localDepth)
1202 1203 if t.capacity > 0 {
1204 for i := uint64(0); i <= t.groups.lengthMask; i++ {
1205 g := t.groups.group(typ, i)
1206 for j := uintptr(0); j < abi.SwissMapGroupSlots; j++ {
1207 if (g.ctrls().get(j) & ctrlEmpty) == ctrlEmpty {
1208 // Empty or deleted
1209 continue
1210 }
1211 1212 key := g.key(typ, j)
1213 if typ.IndirectKey() {
1214 key = *((*unsafe.Pointer)(key))
1215 }
1216 1217 elem := g.elem(typ, j)
1218 if typ.IndirectElem() {
1219 elem = *((*unsafe.Pointer)(elem))
1220 }
1221 1222 hash := typ.Hasher(key, m.seed)
1223 1224 newTable.uncheckedPutSlot(typ, hash, key, elem)
1225 }
1226 }
1227 }
1228 1229 newTable.checkInvariants(typ, m)
1230 m.replaceTable(newTable)
1231 t.index = -1
1232 }
1233 1234 // probeSeq maintains the state for a probe sequence that iterates through the
1235 // groups in a table. The sequence is a triangular progression of the form
1236 //
1237 // p(i) := (i^2 + i)/2 + hash (mod mask+1)
1238 //
1239 // The sequence effectively outputs the indexes of *groups*. The group
1240 // machinery allows us to check an entire group with minimal branching.
1241 //
1242 // It turns out that this probe sequence visits every group exactly once if
1243 // the number of groups is a power of two, since (i^2+i)/2 is a bijection in
1244 // Z/(2^m). See https://en.wikipedia.org/wiki/Quadratic_probing
1245 type probeSeq struct {
1246 mask uint64
1247 offset uint64
1248 index uint64
1249 }
1250 1251 func makeProbeSeq(hash uintptr, mask uint64) probeSeq {
1252 return probeSeq{
1253 mask: mask,
1254 offset: uint64(hash) & mask,
1255 index: 0,
1256 }
1257 }
1258 1259 func (s probeSeq) next() probeSeq {
1260 s.index++
1261 s.offset = (s.offset + s.index) & s.mask
1262 return s
1263 }
1264 1265 func (t *table) clone(typ *abi.SwissMapType) *table {
1266 // Shallow copy the table structure.
1267 t2 := new(table)
1268 *t2 = *t
1269 t = t2
1270 1271 // We need to just deep copy the groups.data field.
1272 oldGroups := t.groups
1273 newGroups := newGroups(typ, oldGroups.lengthMask+1)
1274 for i := uint64(0); i <= oldGroups.lengthMask; i++ {
1275 oldGroup := oldGroups.group(typ, i)
1276 newGroup := newGroups.group(typ, i)
1277 cloneGroup(typ, newGroup, oldGroup)
1278 }
1279 t.groups = newGroups
1280 1281 return t
1282 }
1283