runtime: on bigger maps, start iterator at a random bucket.

This change brings the iter/delete pattern down to O(n lgn) from O(n^2).

Fixes #8412.

before:
BenchmarkMapPop100	   50000	     32498 ns/op
BenchmarkMapPop1000	     500	   3244851 ns/op
BenchmarkMapPop10000	       5	 270276855 ns/op

after:
BenchmarkMapPop100	  100000	     16169 ns/op
BenchmarkMapPop1000	    5000	    300416 ns/op
BenchmarkMapPop10000	     300	   5990814 ns/op

LGTM=iant
R=golang-codereviews, iant, khr
CC=golang-codereviews
https://golang.org/cl/141270043

1 files changed, 21 insertions, 0 deletions

diff --git a/src/runtime/map_test.go b/src/runtime/map_test.go
index 8bedc05689..2e87a94a03 100644
--- a/src/runtime/map_test.go
+++ b/src/runtime/map_test.go
@@ -475,3 +475,24 @@ func TestMapStringBytesLookup(t *testing.T) {
 		t.Errorf("AllocsPerRun for x,ok = m[string(buf)] = %v, want 0", n)
 	}
 }
+
+func benchmarkMapPop(b *testing.B, n int) {
+	m := map[int]int{}
+	for i := 0; i < b.N; i++ {
+		for j := 0; j < n; j++ {
+			m[j] = j
+		}
+		for j := 0; j < n; j++ {
+			// Use iterator to pop an element.
+			// We want this to be fast, see issue 8412.
+			for k := range m {
+				delete(m, k)
+				break
+			}
+		}
+	}
+}
+
+func BenchmarkMapPop100(b *testing.B)   { benchmarkMapPop(b, 100) }
+func BenchmarkMapPop1000(b *testing.B)  { benchmarkMapPop(b, 1000) }
+func BenchmarkMapPop10000(b *testing.B) { benchmarkMapPop(b, 10000) }