internal/runtime/maps: reuse deleted slots on insert

While walking the probe sequence, Put keeps track of the first deleted
slot it encountered. If it reaches the end of the probe sequence without
finding a match, then it will prefer to use the deleted slot rather than
a new empty slot.

For #54766.

Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap
Change-Id: I19356ef6780176506f57b42990ac15dc426f1b14
Reviewed-on: https://go-review.googlesource.com/c/go/+/618016
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Keith Randall <khr@google.com>
Auto-Submit: Michael Pratt <mpratt@google.com>
Reviewed-by: Keith Randall <khr@golang.org>

1 files changed, 36 insertions, 0 deletions

diff --git a/src/internal/runtime/maps/export_test.go b/src/internal/runtime/maps/export_test.go
index 369ef1f2fe..8f62739665 100644
--- a/src/internal/runtime/maps/export_test.go
+++ b/src/internal/runtime/maps/export_test.go
@@ -36,12 +36,48 @@ func (m *Map) GroupCount() uint64 {
 	return n
 }
 
+// Return a key from a group containing no empty slots, or nil if there are no
+// full groups.
+//
+// Also returns nil if a group is full but contains entirely deleted slots.
+func (m *Map) KeyFromFullGroup() unsafe.Pointer {
+	var lastTab *table
+	for _, t := range m.directory {
+		if t == lastTab {
+			continue
+		}
+		lastTab = t
+
+		for i := uint64(0); i <= t.groups.lengthMask; i++ {
+			g := t.groups.group(i)
+			match := g.ctrls().matchEmpty()
+			if match != 0 {
+				continue
+			}
+
+			// All full or deleted slots.
+			for j := uint32(0); j < abi.SwissMapGroupSlots; j++ {
+				if g.ctrls().get(j) == ctrlDeleted {
+					continue
+				}
+				return g.key(j)
+			}
+		}
+	}
+
+	return nil
+}
+
 func (m *Map) TableFor(key unsafe.Pointer) *table {
 	hash := m.typ.Hasher(key, m.seed)
 	idx := m.directoryIndex(hash)
 	return m.directory[idx]
 }
 
+func (t *table) GrowthLeft() uint64 {
+	return uint64(t.growthLeft)
+}
+
 // Returns the start address of the groups array.
 func (t *table) GroupsStart() unsafe.Pointer {
 	return t.groups.data