Source file 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  }
   173  

View as plain text