Home | History | Annotate | Download | only in test 
      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 }
    173