test/maplinear.go

   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
  10 package main
  11
  12 import (
  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.
  20 func 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
  65 type I interface {
  66         f()
  67 }
  68
  69 type C int
  70
  71 func (C) f() {}
  72
  73 func 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 }