Source file test/chanlinear.go

     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  
    12  package main
    13  
    14  import (
    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.
    22  func 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  
    69  func 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  

View as plain text