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                 fails++
  48                 if fails == 6 {
  49                         panic(fmt.Sprintf("%s: too slow: %d inserts: %v; %d inserts: %v\n",
  50                                 typ, n, t1, 2*n, t2))
  51                 }
  52                 if fails < 4 {
  53                         n *= 2
  54                 }
  55         }
  56 }
  57
  58 type I interface {
  59         f()
  60 }
  61
  62 type C int
  63
  64 func (C) f() {}
  65
  66 func main() {
  67         // NaNs. ~31ms on a 1.6GHz Zeon.
  68         checkLinear("NaN", 30000, func(n int) {
  69                 m := map[float64]int{}
  70                 nan := math.NaN()
  71                 for i := 0; i < n; i++ {
  72                         m[nan] = 1
  73                 }
  74                 if len(m) != n {
  75                         panic("wrong size map after nan insertion")
  76                 }
  77         })
  78
  79         // ~6ms on a 1.6GHz Zeon.
  80         checkLinear("eface", 10000, func(n int) {
  81                 m := map[interface{}]int{}
  82                 for i := 0; i < n; i++ {
  83                         m[i] = 1
  84                 }
  85         })
  86
  87         // ~7ms on a 1.6GHz Zeon.
  88         // Regression test for CL 119360043.
  89         checkLinear("iface", 10000, func(n int) {
  90                 m := map[I]int{}
  91                 for i := 0; i < n; i++ {
  92                         m[C(i)] = 1
  93                 }
  94         })
  95
  96         // ~6ms on a 1.6GHz Zeon.
  97         checkLinear("int", 10000, func(n int) {
  98                 m := map[int]int{}
  99                 for i := 0; i < n; i++ {
 100                         m[i] = 1
 101                 }
 102         })
 103
 104         // ~18ms on a 1.6GHz Zeon.
 105         checkLinear("string", 10000, func(n int) {
 106                 m := map[string]int{}
 107                 for i := 0; i < n; i++ {
 108                         m[fmt.Sprint(i)] = 1
 109                 }
 110         })
 111
 112         // ~6ms on a 1.6GHz Zeon.
 113         checkLinear("float32", 10000, func(n int) {
 114                 m := map[float32]int{}
 115                 for i := 0; i < n; i++ {
 116                         m[float32(i)] = 1
 117                 }
 118         })
 119
 120         // ~6ms on a 1.6GHz Zeon.
 121         checkLinear("float64", 10000, func(n int) {
 122                 m := map[float64]int{}
 123                 for i := 0; i < n; i++ {
 124                         m[float64(i)] = 1
 125                 }
 126         })
 127
 128         // ~22ms on a 1.6GHz Zeon.
 129         checkLinear("complex64", 10000, func(n int) {
 130                 m := map[complex64]int{}
 131                 for i := 0; i < n; i++ {
 132                         m[complex(float32(i), float32(i))] = 1
 133                 }
 134         })
 135
 136         // ~32ms on a 1.6GHz Zeon.
 137         checkLinear("complex128", 10000, func(n int) {
 138                 m := map[complex128]int{}
 139                 for i := 0; i < n; i++ {
 140                         m[complex(float64(i), float64(i))] = 1
 141                 }
 142         })
 143 }