1// +build darwin linux
2// run
3
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.
7
8// Test that maps don't go quadratic for NaNs and other values.
9
10package main
11
12import (
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.
20func 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
65type I interface {
66	f()
67}
68
69type C int
70
71func (C) f() {}
72
73func 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