runtime: add timing test for iterate/delete map idiom.
LGTM=bradfitz, iant
R=iant, bradfitz
CC=golang-codereviews
https://golang.org/cl/140510043
diff --git a/test/maplinear.go b/test/maplinear.go
index 56e5095..8cc198b 100644
--- a/test/maplinear.go
+++ b/test/maplinear.go
@@ -140,4 +140,22 @@
m[complex(float64(i), float64(i))] = 1
}
})
+
+ // ~70ms on a 1.6GHz Zeon.
+ // The iterate/delete idiom currently takes expected
+ // O(n lg n) time. Fortunately, the checkLinear test
+ // leaves enough wiggle room to include n lg n time
+ // (it actually tests for O(n^log_2(3)).
+ checkLinear("iterdelete", 10000, func(n int) {
+ m := map[int]int{}
+ for i := 0; i < n; i++ {
+ m[i] = i
+ }
+ for i := 0; i < n; i++ {
+ for k := range m {
+ delete(m, k)
+ break
+ }
+ }
+ })
}
