internal/runtime/maps: prune tombstones in maps before growing

Before growing, if there are lots of tombstones try to remove them.
If we can remove enough, we can continue at the given size for a
while longer.

Fixes #70886

Change-Id: I71e0d873ae118bb35798314ec25e78eaa5340d73
Reviewed-on: https://go-review.googlesource.com/c/go/+/640955
Reviewed-by: Michael Pratt <mpratt@google.com>
Reviewed-by: Keith Randall <khr@google.com>
Auto-Submit: Keith Randall <khr@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

1 files changed, 55 insertions, 0 deletions

diff --git a/src/internal/runtime/maps/map_test.go b/src/internal/runtime/maps/map_test.go
index 160450ebb2..020adfcd78 100644
--- a/src/internal/runtime/maps/map_test.go
+++ b/src/internal/runtime/maps/map_test.go
@@ -699,3 +699,58 @@ func TestMapDeleteClear(t *testing.T) {
 		t.Errorf("Delete(%d) failed to clear element. got %d want 0", key, gotElem)
 	}
 }
+
+func TestTombstoneGrow(t *testing.T) {
+	tableSizes := []int{16, 32, 64, 128, 256}
+	for _, tableSize := range tableSizes {
+		for _, load := range []string{"low", "mid", "high"} {
+			capacity := tableSize * 7 / 8
+			var initialElems int
+			switch load {
+			case "low":
+				initialElems = capacity / 8
+			case "mid":
+				initialElems = capacity / 2
+			case "high":
+				initialElems = capacity
+			}
+			t.Run(fmt.Sprintf("tableSize=%d/elems=%d/load=%0.3f", tableSize, initialElems, float64(initialElems)/float64(tableSize)), func(t *testing.T) {
+				allocs := testing.AllocsPerRun(1, func() {
+					// Fill the map with elements.
+					m := make(map[int]int, capacity)
+					for i := range initialElems {
+						m[i] = i
+					}
+
+					// This is the heart of our test.
+					// Loop over the map repeatedly, deleting a key then adding a not-yet-seen key
+					// while keeping the map at a ~constant number of elements (+/-1).
+					nextKey := initialElems
+					for range 100000 {
+						for k := range m {
+							delete(m, k)
+							break
+						}
+						m[nextKey] = nextKey
+						nextKey++
+						if len(m) != initialElems {
+							t.Fatal("len(m) should remain constant")
+						}
+					}
+				})
+
+				// The make has 4 allocs (map, directory, table, groups).
+				// Each growth has 2 allocs (table, groups).
+				// We allow two growths if we start full, 1 otherwise.
+				// Fail (somewhat arbitrarily) if there are more than that.
+				allowed := float64(4 + 1*2)
+				if initialElems == capacity {
+					allowed += 2
+				}
+				if allocs > allowed {
+					t.Fatalf("got %v allocations, allowed %v", allocs, allowed)
+				}
+			})
+		}
+	}
+}