summaryrefslogtreecommitdiff
path: root/test
diff options
context:
space:
mode:
authorAlan Donovan <adonovan@google.com>2014-08-06 17:02:55 -0400
committerAlan Donovan <adonovan@google.com>2014-08-06 17:02:55 -0400
commit30f0d5c388b623a4d6052f28c221b57ba988aa29 (patch)
treea0a9b60553b49817108c64460b4d33004ef3b01c /test
parentb5e1b23735b905d5ab739883e8e11c1ea8ea270e (diff)
downloadgo-30f0d5c388b623a4d6052f28c221b57ba988aa29.tar.gz
test/mapnan.go: add regression test for non-empty interfaces.
LGTM=rsc, khr R=rsc, khr, bradfitz CC=golang-codereviews https://codereview.appspot.com/126720043
Diffstat (limited to 'test')
-rw-r--r--test/map.go2
-rw-r--r--test/maplinear.go143
-rw-r--r--test/mapnan.go56
3 files changed, 144 insertions, 57 deletions
diff --git a/test/map.go b/test/map.go
index 485e743fe..2c1cf8a14 100644
--- a/test/map.go
+++ b/test/map.go
@@ -5,7 +5,7 @@
// license that can be found in the LICENSE file.
// Test maps, almost exhaustively.
-// NaN complexity test is in mapnan.go.
+// Complexity (linearity) test is in maplinear.go.
package main
diff --git a/test/maplinear.go b/test/maplinear.go
new file mode 100644
index 000000000..56e50951a
--- /dev/null
+++ b/test/maplinear.go
@@ -0,0 +1,143 @@
+// +build darwin linux
+// run
+
+// Copyright 2013 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Test that maps don't go quadratic for NaNs and other values.
+
+package main
+
+import (
+ "fmt"
+ "math"
+ "time"
+)
+
+// checkLinear asserts that the running time of f(n) is in O(n).
+// tries is the initial number of iterations.
+func checkLinear(typ string, tries int, f func(n int)) {
+ // Depending on the machine and OS, this test might be too fast
+ // to measure with accurate enough granularity. On failure,
+ // make it run longer, hoping that the timing granularity
+ // is eventually sufficient.
+
+ timeF := func(n int) time.Duration {
+ t1 := time.Now()
+ f(n)
+ return time.Since(t1)
+ }
+
+ t0 := time.Now()
+
+ n := tries
+ fails := 0
+ for {
+ t1 := timeF(n)
+ t2 := timeF(2 * n)
+
+ // should be 2x (linear); allow up to 3x
+ if t2 < 3*t1 {
+ if false {
+ fmt.Println(typ, "\t", time.Since(t0))
+ }
+ return
+ }
+ fails++
+ if fails == 6 {
+ panic(fmt.Sprintf("%s: too slow: %d inserts: %v; %d inserts: %v\n",
+ typ, n, t1, 2*n, t2))
+ }
+ if fails < 4 {
+ n *= 2
+ }
+ }
+}
+
+type I interface {
+ f()
+}
+
+type C int
+
+func (C) f() {}
+
+func main() {
+ // NaNs. ~31ms on a 1.6GHz Zeon.
+ checkLinear("NaN", 30000, func(n int) {
+ m := map[float64]int{}
+ nan := math.NaN()
+ for i := 0; i < n; i++ {
+ m[nan] = 1
+ }
+ if len(m) != n {
+ panic("wrong size map after nan insertion")
+ }
+ })
+
+ // ~6ms on a 1.6GHz Zeon.
+ checkLinear("eface", 10000, func(n int) {
+ m := map[interface{}]int{}
+ for i := 0; i < n; i++ {
+ m[i] = 1
+ }
+ })
+
+ // ~7ms on a 1.6GHz Zeon.
+ // Regression test for CL 119360043.
+ checkLinear("iface", 10000, func(n int) {
+ m := map[I]int{}
+ for i := 0; i < n; i++ {
+ m[C(i)] = 1
+ }
+ })
+
+ // ~6ms on a 1.6GHz Zeon.
+ checkLinear("int", 10000, func(n int) {
+ m := map[int]int{}
+ for i := 0; i < n; i++ {
+ m[i] = 1
+ }
+ })
+
+ // ~18ms on a 1.6GHz Zeon.
+ checkLinear("string", 10000, func(n int) {
+ m := map[string]int{}
+ for i := 0; i < n; i++ {
+ m[fmt.Sprint(i)] = 1
+ }
+ })
+
+ // ~6ms on a 1.6GHz Zeon.
+ checkLinear("float32", 10000, func(n int) {
+ m := map[float32]int{}
+ for i := 0; i < n; i++ {
+ m[float32(i)] = 1
+ }
+ })
+
+ // ~6ms on a 1.6GHz Zeon.
+ checkLinear("float64", 10000, func(n int) {
+ m := map[float64]int{}
+ for i := 0; i < n; i++ {
+ m[float64(i)] = 1
+ }
+ })
+
+ // ~22ms on a 1.6GHz Zeon.
+ checkLinear("complex64", 10000, func(n int) {
+ m := map[complex64]int{}
+ for i := 0; i < n; i++ {
+ m[complex(float32(i), float32(i))] = 1
+ }
+ })
+
+ // ~32ms on a 1.6GHz Zeon.
+ checkLinear("complex128", 10000, func(n int) {
+ m := map[complex128]int{}
+ for i := 0; i < n; i++ {
+ m[complex(float64(i), float64(i))] = 1
+ }
+ })
+}
diff --git a/test/mapnan.go b/test/mapnan.go
deleted file mode 100644
index f081cab01..000000000
--- a/test/mapnan.go
+++ /dev/null
@@ -1,56 +0,0 @@
-// +build darwin linux
-// run
-
-// Copyright 2013 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// Test that NaNs in maps don't go quadratic.
-
-package main
-
-import (
- "fmt"
- "math"
- "time"
-)
-
-func main() {
-
- // Test that NaNs in maps don't go quadratic.
- t := func(n int) time.Duration {
- t1 := time.Now()
- m := map[float64]int{}
- nan := math.NaN()
- for i := 0; i < n; i++ {
- m[nan] = 1
- }
- if len(m) != n {
- panic("wrong size map after nan insertion")
- }
- return time.Since(t1)
- }
-
- // Depending on the machine and OS, this test might be too fast
- // to measure with accurate enough granularity. On failure,
- // make it run longer, hoping that the timing granularity
- // is eventually sufficient.
-
- n := 30000 // ~8ms user time on a Mid 2011 MacBook Air (1.8 GHz Core i7)
- fails := 0
- for {
- t1 := t(n)
- t2 := t(2 * n)
- // should be 2x (linear); allow up to 3x
- if t2 < 3*t1 {
- return
- }
- fails++
- if fails == 6 {
- panic(fmt.Sprintf("too slow: %d inserts: %v; %d inserts: %v\n", n, t1, 2*n, t2))
- }
- if fails < 4 {
- n *= 2
- }
- }
-}