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 }