1// run
2
3//go:build darwin || linux
4
5// Copyright 2014 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 dequeuing from a pending channel doesn't
10// take linear time.
11
12package main
13
14import (
15	"fmt"
16	"runtime"
17	"time"
18)
19
20// checkLinear asserts that the running time of f(n) is in O(n).
21// tries is the initial number of iterations.
22func checkLinear(typ string, tries int, f func(n int)) {
23	// Depending on the machine and OS, this test might be too fast
24	// to measure with accurate enough granularity. On failure,
25	// make it run longer, hoping that the timing granularity
26	// is eventually sufficient.
27
28	timeF := func(n int) time.Duration {
29		t1 := time.Now()
30		f(n)
31		return time.Since(t1)
32	}
33
34	t0 := time.Now()
35
36	n := tries
37	fails := 0
38	for {
39		runtime.GC()
40		t1 := timeF(n)
41		runtime.GC()
42		t2 := timeF(2 * n)
43
44		// should be 2x (linear); allow up to 3x
45		if t2 < 3*t1 {
46			if false {
47				fmt.Println(typ, "\t", time.Since(t0))
48			}
49			return
50		}
51		// If n ops run in under a second and the ratio
52		// doesn't work out, make n bigger, trying to reduce
53		// the effect that a constant amount of overhead has
54		// on the computed ratio.
55		if t1 < 1*time.Second {
56			n *= 2
57			continue
58		}
59		// Once the test runs long enough for n ops,
60		// try to get the right ratio at least once.
61		// If five in a row all fail, give up.
62		if fails++; fails >= 5 {
63			panic(fmt.Sprintf("%s: too slow: %d channels: %v; %d channels: %v\n",
64				typ, n, t1, 2*n, t2))
65		}
66	}
67}
68
69func main() {
70	checkLinear("chanSelect", 1000, func(n int) {
71		const messages = 10
72		c := make(chan bool) // global channel
73		var a []chan bool    // local channels for each goroutine
74		for i := 0; i < n; i++ {
75			d := make(chan bool)
76			a = append(a, d)
77			go func() {
78				for j := 0; j < messages; j++ {
79					// queue ourselves on the global channel
80					select {
81					case <-c:
82					case <-d:
83					}
84				}
85			}()
86		}
87		for i := 0; i < messages; i++ {
88			// wake each goroutine up, forcing it to dequeue and then enqueue
89			// on the global channel.
90			for _, d := range a {
91				d <- true
92			}
93		}
94	})
95}
96