Source file test/chanlinear.go

     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  
    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  

View as plain text