1 // run 2 3 // Copyright 2017 The Go Authors. All rights reserved. 4 // Use of this source code is governed by a BSD-style 5 // license that can be found in the LICENSE file. 6 7 // Test that locks don't go quadratic due to runtime hash table collisions. 8 9 package main 10 11 import ( 12 "bytes" 13 "fmt" 14 "log" 15 "os" 16 "runtime" 17 "runtime/pprof" 18 "sync" 19 "time" 20 ) 21 22 const debug = false 23 24 // checkLinear asserts that the running time of f(n) is at least linear but sub-quadratic. 25 // tries is the initial number of iterations. 26 func checkLinear(typ string, tries int, f func(n int)) { 27 // Depending on the machine and OS, this test might be too fast 28 // to measure with accurate enough granularity. On failure, 29 // make it run longer, hoping that the timing granularity 30 // is eventually sufficient. 31 32 timeF := func(n int) time.Duration { 33 t1 := time.Now() 34 f(n) 35 return time.Since(t1) 36 } 37 38 n := tries 39 fails := 0 40 var buf bytes.Buffer 41 inversions := 0 42 for { 43 t1 := timeF(n) 44 t2 := timeF(2 * n) 45 if debug { 46 println(n, t1.String(), 2*n, t2.String()) 47 } 48 fmt.Fprintf(&buf, "%d %v %d %v (%.1fX)\n", n, t1, 2*n, t2, float64(t2)/float64(t1)) 49 // should be 2x (linear); allow up to 3x 50 if t1*3/2 < t2 && t2 < t1*3 { 51 return 52 } 53 if t2 < t1 { 54 if inversions++; inversions >= 5 { 55 // The system must be overloaded (some builders). Give up. 56 return 57 } 58 continue // try again; don't increment fails 59 } 60 // Once the test runs long enough for n ops, 61 // try to get the right ratio at least once. 62 // If many in a row all fail, give up. 63 if fails++; fails >= 5 { 64 // If 2n ops run in under a second and the ratio 65 // doesn't work out, make n bigger, trying to reduce 66 // the effect that a constant amount of overhead has 67 // on the computed ratio. 68 if t2 < time.Second*4/10 { 69 fails = 0 70 n *= 2 71 continue 72 } 73 panic(fmt.Sprintf("%s: too slow: %d ops: %v; %d ops: %v\n\n%s", 74 typ, n, t1, 2*n, t2, buf.String())) 75 } 76 } 77 } 78 79 const offset = 251 // known size of runtime hash table 80 81 const profile = false 82 83 func main() { 84 if profile { 85 f, err := os.Create("lock.prof") 86 if err != nil { 87 log.Fatal(err) 88 } 89 pprof.StartCPUProfile(f) 90 defer pprof.StopCPUProfile() 91 } 92 93 checkLinear("lockone", 1000, func(n int) { 94 ch := make(chan int) 95 locks := make([]sync.RWMutex, offset+1) 96 for i := 0; i < n; i++ { 97 go func() { 98 locks[0].Lock() 99 ch <- 1 100 }() 101 } 102 time.Sleep(1 * time.Millisecond) 103 104 go func() { 105 for j := 0; j < n; j++ { 106 locks[1].Lock() 107 locks[offset].Lock() 108 locks[1].Unlock() 109 runtime.Gosched() 110 locks[offset].Unlock() 111 } 112 }() 113 114 for j := 0; j < n; j++ { 115 locks[1].Lock() 116 locks[offset].Lock() 117 locks[1].Unlock() 118 runtime.Gosched() 119 locks[offset].Unlock() 120 } 121 122 for i := 0; i < n; i++ { 123 <-ch 124 locks[0].Unlock() 125 } 126 }) 127 128 checkLinear("lockmany", 1000, func(n int) { 129 locks := make([]sync.RWMutex, n*offset+1) 130 131 var wg sync.WaitGroup 132 for i := 0; i < n; i++ { 133 wg.Add(1) 134 go func(i int) { 135 locks[(i+1)*offset].Lock() 136 wg.Done() 137 locks[(i+1)*offset].Lock() 138 locks[(i+1)*offset].Unlock() 139 }(i) 140 } 141 wg.Wait() 142 143 go func() { 144 for j := 0; j < n; j++ { 145 locks[1].Lock() 146 locks[0].Lock() 147 locks[1].Unlock() 148 runtime.Gosched() 149 locks[0].Unlock() 150 } 151 }() 152 153 for j := 0; j < n; j++ { 154 locks[1].Lock() 155 locks[0].Lock() 156 locks[1].Unlock() 157 runtime.Gosched() 158 locks[0].Unlock() 159 } 160 161 for i := 0; i < n; i++ { 162 locks[(i+1)*offset].Unlock() 163 } 164 }) 165 } 166
