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>

4 files changed, 33 insertions, 9 deletions

diff --git a/src/runtime/map_benchmark_test.go b/src/runtime/map_benchmark_test.go
index 663abf6202..6f527c3af6 100644
--- a/src/runtime/map_benchmark_test.go
+++ b/src/runtime/map_benchmark_test.go
@@ -1008,11 +1008,12 @@ func benchmarkMapDelete[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testin
 
 	for i := 0; i < b.N; i++ {
 		if len(m) == 0 {
-			b.StopTimer()
+			// We'd like to StopTimer while refilling the map, but
+			// it is way too expensive and thus makes the benchmark
+			// take a long time. See https://go.dev/issue/20875.
 			for j := range k {
 				m[k[j]] = e[j]
 			}
-			b.StartTimer()
 		}
 		delete(m, k[i%n])
 	}
diff --git a/src/runtime/map_swiss.go b/src/runtime/map_swiss.go
index bd0d05d092..e62def9677 100644
--- a/src/runtime/map_swiss.go
+++ b/src/runtime/map_swiss.go
@@ -76,7 +76,7 @@ func makemap(t *abi.SwissMapType, hint int, m *maps.Map) *maps.Map {
 	capacity := checkHint(t, hint)
 
 	// TODO: use existing m
-	return maps.NewTable(t, capacity)
+	return maps.NewMap(t, capacity)
 }
 
 // alignUpPow2 rounds n up to the next power of 2.
diff --git a/src/runtime/map_swiss_test.go b/src/runtime/map_swiss_test.go
index aa019e1c31..93b1fd430f 100644
--- a/src/runtime/map_swiss_test.go
+++ b/src/runtime/map_swiss_test.go
@@ -18,8 +18,8 @@ import (
 func TestHmapSize(t *testing.T) {
 	// The structure of Map is defined in internal/runtime/maps/map.go
 	// and in cmd/compile/internal/reflectdata/map_swiss.go and must be in sync.
-	// The size of Map should be 72 bytes on 64 bit and 56 bytes on 32 bit platforms.
-	wantSize := uintptr(4*goarch.PtrSize + 5*8)
+	// The size of Map should be 64 bytes on 64 bit and 40 bytes on 32 bit platforms.
+	wantSize := uintptr(6*goarch.PtrSize + 2*8)
 	gotSize := unsafe.Sizeof(maps.Map{})
 	if gotSize != wantSize {
 		t.Errorf("sizeof(maps.Map{})==%d, want %d", gotSize, wantSize)
@@ -73,7 +73,3 @@ func TestMapIterOrder(t *testing.T) {
 		}
 	}
 }
-
-func TestMapBuckets(t *testing.T) {
-	t.Skipf("todo")
-}
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)
+				}
+			}
+		})
+	}
+}