cmd/compile,internal/runtime/maps: add extendible hashing

Extendible hashing splits a swisstable map into many swisstables. This
keeps grow operations small.

For #54766.

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

1 files changed, 27 insertions, 0 deletions

diff --git a/src/runtime/map_test.go b/src/runtime/map_test.go
index 0e1342f904..1b4ebe276f 100644
--- a/src/runtime/map_test.go
+++ b/src/runtime/map_test.go
@@ -1147,3 +1147,30 @@ func TestMemHashGlobalSeed(t *testing.T) {
 		}
 	})
 }
+
+func TestMapIterDeleteReplace(t *testing.T) {
+	inc := 1
+	if testing.Short() {
+		inc = 100
+	}
+	for i := 0; i < 10000; i += inc {
+		t.Run(fmt.Sprint(i), func(t *testing.T) {
+			m := make(map[int]bool)
+			for j := range i {
+				m[j] = false
+			}
+
+			// Delete and replace all entries.
+			for k := range m {
+				delete(m, k)
+				m[k] = true
+			}
+
+			for k, v := range m {
+				if !v {
+					t.Errorf("m[%d] got false want true", k)
+				}
+			}
+		})
+	}
+}