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 dequeuing from a pending channel doesn't
9// take linear time.
10
11package main
12
13import (
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.
21func 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
68func 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