3 //go:build darwin || linux
5 // Copyright 2013 The Go Authors. All rights reserved.
6 // Use of this source code is governed by a BSD-style
7 // license that can be found in the LICENSE file.
9 // Test that maps don't go quadratic for NaNs and other values.
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.
27 timeF := func(n int) time.Duration {
41 // should be 2x (linear); allow up to 3x
44 fmt.Println(typ, "\t", time.Since(t0))
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 {
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",
75 // NaNs. ~31ms on a 1.6GHz Zeon.
76 checkLinear("NaN", 30000, func(n int) {
77 m := map[float64]int{}
79 for i := 0; i < n; i++ {
83 panic("wrong size map after nan insertion")
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++ {
95 // ~7ms on a 1.6GHz Zeon.
96 // Regression test for CL 119360043.
97 checkLinear("iface", 10000, func(n int) {
99 for i := 0; i < n; i++ {
104 // ~6ms on a 1.6GHz Zeon.
105 checkLinear("int", 10000, func(n int) {
107 for i := 0; i < n; i++ {
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++ {
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++ {
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++ {
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
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
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++ {
162 for i := 0; i < n; i++ {
165 for i := 0; i < n; i++ {