From 30f0d5c388b623a4d6052f28c221b57ba988aa29 Mon Sep 17 00:00:00 2001 From: Alan Donovan Date: Wed, 6 Aug 2014 17:02:55 -0400 Subject: test/mapnan.go: add regression test for non-empty interfaces. LGTM=rsc, khr R=rsc, khr, bradfitz CC=golang-codereviews https://codereview.appspot.com/126720043 --- test/map.go | 2 +- test/maplinear.go | 143 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ test/mapnan.go | 56 --------------------- 3 files changed, 144 insertions(+), 57 deletions(-) create mode 100644 test/maplinear.go delete mode 100644 test/mapnan.go (limited to 'test') diff --git a/test/map.go b/test/map.go index 485e743fe..2c1cf8a14 100644 --- a/test/map.go +++ b/test/map.go @@ -5,7 +5,7 @@ // license that can be found in the LICENSE file. // Test maps, almost exhaustively. -// NaN complexity test is in mapnan.go. +// Complexity (linearity) test is in maplinear.go. package main diff --git a/test/maplinear.go b/test/maplinear.go new file mode 100644 index 000000000..56e50951a --- /dev/null +++ b/test/maplinear.go @@ -0,0 +1,143 @@ +// +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 + } + fails++ + if fails == 6 { + panic(fmt.Sprintf("%s: too slow: %d inserts: %v; %d inserts: %v\n", + typ, n, t1, 2*n, t2)) + } + if fails < 4 { + n *= 2 + } + } +} + +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 + } + }) +} diff --git a/test/mapnan.go b/test/mapnan.go deleted file mode 100644 index f081cab01..000000000 --- a/test/mapnan.go +++ /dev/null @@ -1,56 +0,0 @@ -// +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 NaNs in maps don't go quadratic. - -package main - -import ( - "fmt" - "math" - "time" -) - -func main() { - - // Test that NaNs in maps don't go quadratic. - t := func(n int) time.Duration { - t1 := time.Now() - 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") - } - return time.Since(t1) - } - - // 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. - - n := 30000 // ~8ms user time on a Mid 2011 MacBook Air (1.8 GHz Core i7) - fails := 0 - for { - t1 := t(n) - t2 := t(2 * n) - // should be 2x (linear); allow up to 3x - if t2 < 3*t1 { - return - } - fails++ - if fails == 6 { - panic(fmt.Sprintf("too slow: %d inserts: %v; %d inserts: %v\n", n, t1, 2*n, t2)) - } - if fails < 4 { - n *= 2 - } - } -} -- cgit v1.2.1