Home | History | Annotate | Download | only in test 
      1 // +build darwin linux
      2 // run
      3 
      4 // Copyright 2014 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 dequeueing from a pending channel doesn't
      9 // take linear time.
     10 
     11 package main
     12 
     13 import (
     14 	"fmt"
     15 	"runtime"
     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 		runtime.GC()
     39 		t1 := timeF(n)
     40 		runtime.GC()
     41 		t2 := timeF(2 * n)
     42 
     43 		// should be 2x (linear); allow up to 3x
     44 		if t2 < 3*t1 {
     45 			if false {
     46 				fmt.Println(typ, "\t", time.Since(t0))
     47 			}
     48 			return
     49 		}
     50 		// If n ops run in under a second and the ratio
     51 		// doesn't work out, make n bigger, trying to reduce
     52 		// the effect that a constant amount of overhead has
     53 		// on the computed ratio.
     54 		if t1 < 1*time.Second {
     55 			n *= 2
     56 			continue
     57 		}
     58 		// Once the test runs long enough for n ops,
     59 		// try to get the right ratio at least once.
     60 		// If five in a row all fail, give up.
     61 		if fails++; fails >= 5 {
     62 			panic(fmt.Sprintf("%s: too slow: %d channels: %v; %d channels: %v\n",
     63 				typ, n, t1, 2*n, t2))
     64 		}
     65 	}
     66 }
     67 
     68 func main() {
     69 	checkLinear("chanSelect", 1000, func(n int) {
     70 		const messages = 10
     71 		c := make(chan bool) // global channel
     72 		var a []chan bool    // local channels for each goroutine
     73 		for i := 0; i < n; i++ {
     74 			d := make(chan bool)
     75 			a = append(a, d)
     76 			go func() {
     77 				for j := 0; j < messages; j++ {
     78 					// queue ourselves on the global channel
     79 					select {
     80 					case <-c:
     81 					case <-d:
     82 					}
     83 				}
     84 			}()
     85 		}
     86 		for i := 0; i < messages; i++ {
     87 			// wake each goroutine up, forcing it to dequeue and then enqueue
     88 			// on the global channel.
     89 			for _, d := range a {
     90 				d <- true
     91 			}
     92 		}
     93 	})
     94 }
     95