diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-16 19:19:13 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-16 19:19:13 +0000 |
commit | ccd992355df7192993c666236047820244914598 (patch) | |
tree | f00fea65147227b7743083c6148396f74cd66935 /test/maplinear.go | |
parent | Initial commit. (diff) | |
download | golang-1.21-ccd992355df7192993c666236047820244914598.tar.xz golang-1.21-ccd992355df7192993c666236047820244914598.zip |
Adding upstream version 1.21.8.upstream/1.21.8
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'test/maplinear.go')
-rw-r--r-- | test/maplinear.go | 172 |
1 files changed, 172 insertions, 0 deletions
diff --git a/test/maplinear.go b/test/maplinear.go new file mode 100644 index 0000000..34d0914 --- /dev/null +++ b/test/maplinear.go @@ -0,0 +1,172 @@ +// +build darwin linux +// run + +// Copyright 2013 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Test that maps don't go quadratic for NaNs and other values. + +package main + +import ( + "fmt" + "math" + "time" +) + +// checkLinear asserts that the running time of f(n) is in O(n). +// tries is the initial number of iterations. +func checkLinear(typ string, tries int, f func(n int)) { + // Depending on the machine and OS, this test might be too fast + // to measure with accurate enough granularity. On failure, + // make it run longer, hoping that the timing granularity + // is eventually sufficient. + + timeF := func(n int) time.Duration { + t1 := time.Now() + f(n) + return time.Since(t1) + } + + t0 := time.Now() + + n := tries + fails := 0 + for { + t1 := timeF(n) + t2 := timeF(2 * n) + + // should be 2x (linear); allow up to 3x + if t2 < 3*t1 { + if false { + fmt.Println(typ, "\t", time.Since(t0)) + } + return + } + // If n ops run in under a second and the ratio + // doesn't work out, make n bigger, trying to reduce + // the effect that a constant amount of overhead has + // on the computed ratio. + if t1 < 1*time.Second { + n *= 2 + continue + } + // Once the test runs long enough for n ops, + // try to get the right ratio at least once. + // If five in a row all fail, give up. + if fails++; fails >= 5 { + panic(fmt.Sprintf("%s: too slow: %d inserts: %v; %d inserts: %v\n", + typ, n, t1, 2*n, t2)) + } + } +} + +type I interface { + f() +} + +type C int + +func (C) f() {} + +func main() { + // NaNs. ~31ms on a 1.6GHz Zeon. + checkLinear("NaN", 30000, func(n int) { + m := map[float64]int{} + nan := math.NaN() + for i := 0; i < n; i++ { + m[nan] = 1 + } + if len(m) != n { + panic("wrong size map after nan insertion") + } + }) + + // ~6ms on a 1.6GHz Zeon. + checkLinear("eface", 10000, func(n int) { + m := map[interface{}]int{} + for i := 0; i < n; i++ { + m[i] = 1 + } + }) + + // ~7ms on a 1.6GHz Zeon. + // Regression test for CL 119360043. + checkLinear("iface", 10000, func(n int) { + m := map[I]int{} + for i := 0; i < n; i++ { + m[C(i)] = 1 + } + }) + + // ~6ms on a 1.6GHz Zeon. + checkLinear("int", 10000, func(n int) { + m := map[int]int{} + for i := 0; i < n; i++ { + m[i] = 1 + } + }) + + // ~18ms on a 1.6GHz Zeon. + checkLinear("string", 10000, func(n int) { + m := map[string]int{} + for i := 0; i < n; i++ { + m[fmt.Sprint(i)] = 1 + } + }) + + // ~6ms on a 1.6GHz Zeon. + checkLinear("float32", 10000, func(n int) { + m := map[float32]int{} + for i := 0; i < n; i++ { + m[float32(i)] = 1 + } + }) + + // ~6ms on a 1.6GHz Zeon. + checkLinear("float64", 10000, func(n int) { + m := map[float64]int{} + for i := 0; i < n; i++ { + m[float64(i)] = 1 + } + }) + + // ~22ms on a 1.6GHz Zeon. + checkLinear("complex64", 10000, func(n int) { + m := map[complex64]int{} + for i := 0; i < n; i++ { + m[complex(float32(i), float32(i))] = 1 + } + }) + + // ~32ms on a 1.6GHz Zeon. + checkLinear("complex128", 10000, func(n int) { + m := map[complex128]int{} + for i := 0; i < n; i++ { + m[complex(float64(i), float64(i))] = 1 + } + }) + + // ~70ms on a 1.6GHz Zeon. + // The iterate/delete idiom currently takes expected + // O(n lg n) time. Fortunately, the checkLinear test + // leaves enough wiggle room to include n lg n time + // (it actually tests for O(n^log_2(3)). + // To prevent false positives, average away variation + // by doing multiple rounds within a single run. + checkLinear("iterdelete", 2500, func(n int) { + for round := 0; round < 4; round++ { + m := map[int]int{} + for i := 0; i < n; i++ { + m[i] = i + } + for i := 0; i < n; i++ { + for k := range m { + delete(m, k) + break + } + } + } + }) +} |