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