# Source file test/maplinear.go

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

View as plain text