...

# Source file test/maplinear.go

## Documentation: test

```     1  // +build darwin linux
2  // run
3
5  // Use of this source code is governed by a BSD-style
7
8  // Test that maps don't go quadratic for NaNs and other values.
9
10  package main
11
12  import (
13  	"fmt"
14  	"math"
15  	"time"
16  )
17
18  // checkLinear asserts that the running time of f(n) is in O(n).
19  // tries is the initial number of iterations.
20  func checkLinear(typ string, tries int, f func(n int)) {
21  	// Depending on the machine and OS, this test might be too fast
22  	// to measure with accurate enough granularity. On failure,
23  	// make it run longer, hoping that the timing granularity
24  	// is eventually sufficient.
25
26  	timeF := func(n int) time.Duration {
27  		t1 := time.Now()
28  		f(n)
29  		return time.Since(t1)
30  	}
31
32  	t0 := time.Now()
33
34  	n := tries
35  	fails := 0
36  	for {
37  		t1 := timeF(n)
38  		t2 := timeF(2 * n)
39
40  		// should be 2x (linear); allow up to 3x
41  		if t2 < 3*t1 {
42  			if false {
43  				fmt.Println(typ, "\t", time.Since(t0))
44  			}
45  			return
46  		}
47  		// If n ops run in under a second and the ratio
48  		// doesn't work out, make n bigger, trying to reduce
49  		// the effect that a constant amount of overhead has
50  		// on the computed ratio.
51  		if t1 < 1*time.Second {
52  			n *= 2
53  			continue
54  		}
55  		// Once the test runs long enough for n ops,
56  		// try to get the right ratio at least once.
57  		// If five in a row all fail, give up.
58  		if fails++; fails >= 5 {
59  			panic(fmt.Sprintf("%s: too slow: %d inserts: %v; %d inserts: %v\n",
60  				typ, n, t1, 2*n, t2))
61  		}
62  	}
63  }
64
65  type I interface {
66  	f()
67  }
68
69  type C int
70
71  func (C) f() {}
72
73  func main() {
74  	// NaNs. ~31ms on a 1.6GHz Zeon.
75  	checkLinear("NaN", 30000, func(n int) {
76  		m := map[float64]int{}
77  		nan := math.NaN()
78  		for i := 0; i < n; i++ {
79  			m[nan] = 1
80  		}
81  		if len(m) != n {
82  			panic("wrong size map after nan insertion")
83  		}
84  	})
85
86  	// ~6ms on a 1.6GHz Zeon.
87  	checkLinear("eface", 10000, func(n int) {
88  		m := map[interface{}]int{}
89  		for i := 0; i < n; i++ {
90  			m[i] = 1
91  		}
92  	})
93
94  	// ~7ms on a 1.6GHz Zeon.
95  	// Regression test for CL 119360043.
96  	checkLinear("iface", 10000, func(n int) {
97  		m := map[I]int{}
98  		for i := 0; i < n; i++ {
99  			m[C(i)] = 1
100  		}
101  	})
102
103  	// ~6ms on a 1.6GHz Zeon.
104  	checkLinear("int", 10000, func(n int) {
105  		m := map[int]int{}
106  		for i := 0; i < n; i++ {
107  			m[i] = 1
108  		}
109  	})
110
111  	// ~18ms on a 1.6GHz Zeon.
112  	checkLinear("string", 10000, func(n int) {
113  		m := map[string]int{}
114  		for i := 0; i < n; i++ {
115  			m[fmt.Sprint(i)] = 1
116  		}
117  	})
118
119  	// ~6ms on a 1.6GHz Zeon.
120  	checkLinear("float32", 10000, func(n int) {
121  		m := map[float32]int{}
122  		for i := 0; i < n; i++ {
123  			m[float32(i)] = 1
124  		}
125  	})
126
127  	// ~6ms on a 1.6GHz Zeon.
128  	checkLinear("float64", 10000, func(n int) {
129  		m := map[float64]int{}
130  		for i := 0; i < n; i++ {
131  			m[float64(i)] = 1
132  		}
133  	})
134
135  	// ~22ms on a 1.6GHz Zeon.
136  	checkLinear("complex64", 10000, func(n int) {
137  		m := map[complex64]int{}
138  		for i := 0; i < n; i++ {
139  			m[complex(float32(i), float32(i))] = 1
140  		}
141  	})
142
143  	// ~32ms on a 1.6GHz Zeon.
144  	checkLinear("complex128", 10000, func(n int) {
145  		m := map[complex128]int{}
146  		for i := 0; i < n; i++ {
147  			m[complex(float64(i), float64(i))] = 1
148  		}
149  	})
150
151  	// ~70ms on a 1.6GHz Zeon.
152  	// The iterate/delete idiom currently takes expected
153  	// O(n lg n) time.  Fortunately, the checkLinear test
154  	// leaves enough wiggle room to include n lg n time
155  	// (it actually tests for O(n^log_2(3)).
156  	// To prevent false positives, average away variation
157  	// by doing multiple rounds within a single run.
158  	checkLinear("iterdelete", 2500, func(n int) {
159  		for round := 0; round < 4; round++ {
160  			m := map[int]int{}
161  			for i := 0; i < n; i++ {
162  				m[i] = i
163  			}
164  			for i := 0; i < n; i++ {
165  				for k := range m {
166  					delete(m, k)
167  					break
168  				}
169  			}
170  		}
171  	})
172  }
173
```

View as plain text