Source file test/locklinear.go

Documentation: test

     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  	if runtime.GOARCH == "arm" && os.Getenv("GOARM") == "5" {
   129  		// lockmany reliably fails on the linux-arm-arm5spacemonkey
   130  		// builder. See https://golang.org/issue/24221.
   131  		return
   132  	}
   133  
   134  	checkLinear("lockmany", 1000, func(n int) {
   135  		locks := make([]sync.RWMutex, n*offset+1)
   136  
   137  		var wg sync.WaitGroup
   138  		for i := 0; i < n; i++ {
   139  			wg.Add(1)
   140  			go func(i int) {
   141  				locks[(i+1)*offset].Lock()
   142  				wg.Done()
   143  				locks[(i+1)*offset].Lock()
   144  				locks[(i+1)*offset].Unlock()
   145  			}(i)
   146  		}
   147  		wg.Wait()
   148  
   149  		go func() {
   150  			for j := 0; j < n; j++ {
   151  				locks[1].Lock()
   152  				locks[0].Lock()
   153  				locks[1].Unlock()
   154  				runtime.Gosched()
   155  				locks[0].Unlock()
   156  			}
   157  		}()
   158  
   159  		for j := 0; j < n; j++ {
   160  			locks[1].Lock()
   161  			locks[0].Lock()
   162  			locks[1].Unlock()
   163  			runtime.Gosched()
   164  			locks[0].Unlock()
   165  		}
   166  
   167  		for i := 0; i < n; i++ {
   168  			locks[(i+1)*offset].Unlock()
   169  		}
   170  	})
   171  }
   172  

View as plain text