test/maplinear.go

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