4 // Copyright 2013 The Go Authors. All rights reserved.
5 // Use of this source code is governed by a BSD-style
6 // license that can be found in the LICENSE file.
8 // Test that maps don't go quadratic for NaNs and other values.
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.
26 timeF := func(n int) time.Duration {
40 // should be 2x (linear); allow up to 3x
43 fmt.Println(typ, "\t", time.Since(t0))
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 {
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",
74 // NaNs. ~31ms on a 1.6GHz Zeon.
75 checkLinear("NaN", 30000, func(n int) {
76 m := map[float64]int{}
78 for i := 0; i < n; i++ {
82 panic("wrong size map after nan insertion")
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++ {
94 // ~7ms on a 1.6GHz Zeon.
95 // Regression test for CL 119360043.
96 checkLinear("iface", 10000, func(n int) {
98 for i := 0; i < n; i++ {
103 // ~6ms on a 1.6GHz Zeon.
104 checkLinear("int", 10000, func(n int) {
106 for i := 0; i < n; i++ {
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++ {
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++ {
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++ {
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
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
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++ {
161 for i := 0; i < n; i++ {
164 for i := 0; i < n; i++ {