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

View as plain text