text: // +build darwin linux
  // run
  
  // Copyright 2013 The Go Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style
  // license that can be found in the LICENSE file.
  
  // Test that maps don't go quadratic for NaNs and other values.
  
  package main
  
  import (
  	"fmt"
  	"math"
  	"time"
  )
  
  // checkLinear asserts that the running time of f(n) is in O(n).
  // tries is the initial number of iterations.
  func checkLinear(typ string, tries int, f func(n int)) {
  	// Depending on the machine and OS, this test might be too fast
  	// to measure with accurate enough granularity. On failure,
  	// make it run longer, hoping that the timing granularity
  	// is eventually sufficient.
  
  	timeF := func(n int) time.Duration {
  		t1 := time.Now()
  		f(n)
  		return time.Since(t1)
  	}
  
  	t0 := time.Now()
  
  	n := tries
  	fails := 0
  	for {
  		t1 := timeF(n)
  		t2 := timeF(2 * n)
  
  		// should be 2x (linear); allow up to 3x
  		if t2 < 3*t1 {
  			if false {
  				fmt.Println(typ, "\t", time.Since(t0))
  			}
  			return
  		}
  		// If n ops run in under a second and the ratio
  		// doesn't work out, make n bigger, trying to reduce
  		// the effect that a constant amount of overhead has
  		// on the computed ratio.
  		if t1 < 1*time.Second {
  			n *= 2
  			continue
  		}
  		// Once the test runs long enough for n ops,
  		// try to get the right ratio at least once.
  		// If five in a row all fail, give up.
  		if fails++; fails >= 5 {
  			panic(fmt.Sprintf("%s: too slow: %d inserts: %v; %d inserts: %v\n",
  				typ, n, t1, 2*n, t2))
  		}
  	}
  }
  
  type I interface {
  	f()
  }
  
  type C int
  
  func (C) f() {}
  
  func main() {
  	// NaNs. ~31ms on a 1.6GHz Zeon.
  	checkLinear("NaN", 30000, func(n int) {
  		m := map[float64]int{}
  		nan := math.NaN()
  		for i := 0; i < n; i++ {
  			m[nan] = 1
  		}
  		if len(m) != n {
  			panic("wrong size map after nan insertion")
  		}
  	})
  
  	// ~6ms on a 1.6GHz Zeon.
  	checkLinear("eface", 10000, func(n int) {
  		m := map[interface{}]int{}
  		for i := 0; i < n; i++ {
  			m[i] = 1
  		}
  	})
  
  	// ~7ms on a 1.6GHz Zeon.
  	// Regression test for CL 119360043.
  	checkLinear("iface", 10000, func(n int) {
  		m := map[I]int{}
  		for i := 0; i < n; i++ {
  			m[C(i)] = 1
  		}
  	})
  
  	// ~6ms on a 1.6GHz Zeon.
  	checkLinear("int", 10000, func(n int) {
  		m := map[int]int{}
  		for i := 0; i < n; i++ {
  			m[i] = 1
  		}
  	})
  
  	// ~18ms on a 1.6GHz Zeon.
  	checkLinear("string", 10000, func(n int) {
  		m := map[string]int{}
  		for i := 0; i < n; i++ {
  			m[fmt.Sprint(i)] = 1
  		}
  	})
  
  	// ~6ms on a 1.6GHz Zeon.
  	checkLinear("float32", 10000, func(n int) {
  		m := map[float32]int{}
  		for i := 0; i < n; i++ {
  			m[float32(i)] = 1
  		}
  	})
  
  	// ~6ms on a 1.6GHz Zeon.
  	checkLinear("float64", 10000, func(n int) {
  		m := map[float64]int{}
  		for i := 0; i < n; i++ {
  			m[float64(i)] = 1
  		}
  	})
  
  	// ~22ms on a 1.6GHz Zeon.
  	checkLinear("complex64", 10000, func(n int) {
  		m := map[complex64]int{}
  		for i := 0; i < n; i++ {
  			m[complex(float32(i), float32(i))] = 1
  		}
  	})
  
  	// ~32ms on a 1.6GHz Zeon.
  	checkLinear("complex128", 10000, func(n int) {
  		m := map[complex128]int{}
  		for i := 0; i < n; i++ {
  			m[complex(float64(i), float64(i))] = 1
  		}
  	})
  
  	// ~70ms on a 1.6GHz Zeon.
  	// The iterate/delete idiom currently takes expected
  	// O(n lg n) time.  Fortunately, the checkLinear test
  	// leaves enough wiggle room to include n lg n time
  	// (it actually tests for O(n^log_2(3)).
  	// To prevent false positives, average away variation
  	// by doing multiple rounds within a single run.
  	checkLinear("iterdelete", 2500, func(n int) {
  		for round := 0; round < 4; round++ {
  			m := map[int]int{}
  			for i := 0; i < n; i++ {
  				m[i] = i
  			}
  			for i := 0; i < n; i++ {
  				for k := range m {
  					delete(m, k)
  					break
  				}
  			}
  		}
  	})
  }
  