...
Run Format

Source file test/locklinear.go

Documentation: test

  // run
  
  // Copyright 2017 The Go Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style
  // license that can be found in the LICENSE file.
  
  // Test that locks don't go quadratic due to runtime hash table collisions.
  
  package main
  
  import (
  	"bytes"
  	"fmt"
  	"log"
  	"os"
  	"runtime"
  	"runtime/pprof"
  	"sync"
  	"time"
  )
  
  const debug = false
  
  // checkLinear asserts that the running time of f(n) is at least linear but sub-quadratic.
  // tries is the initial number of iterations.
  func checkLinear(typ string, tries int, f func(n int)) {
  	// Depending on the machine and OS, this test might be too fast
  	// to measure with accurate enough granularity. On failure,
  	// make it run longer, hoping that the timing granularity
  	// is eventually sufficient.
  
  	timeF := func(n int) time.Duration {
  		t1 := time.Now()
  		f(n)
  		return time.Since(t1)
  	}
  
  	n := tries
  	fails := 0
  	var buf bytes.Buffer
  	inversions := 0
  	for {
  		t1 := timeF(n)
  		t2 := timeF(2 * n)
  		if debug {
  			println(n, t1.String(), 2*n, t2.String())
  		}
  		fmt.Fprintf(&buf, "%d %v %d %v (%.1fX)\n", n, t1, 2*n, t2, float64(t2)/float64(t1))
  		// should be 2x (linear); allow up to 3x
  		if t1*3/2 < t2 && t2 < t1*3 {
  			return
  		}
  		if t2 < t1 {
  			if inversions++; inversions >= 5 {
  				// The system must be overloaded (some builders). Give up.
  				return
  			}
  			continue // try again; don't increment fails
  		}
  		// Once the test runs long enough for n ops,
  		// try to get the right ratio at least once.
  		// If many in a row all fail, give up.
  		if fails++; fails >= 5 {
  			// If 2n ops run in under a second and the ratio
  			// doesn't work out, make n bigger, trying to reduce
  			// the effect that a constant amount of overhead has
  			// on the computed ratio.
  			if t2 < time.Second*4/10 {
  				fails = 0
  				n *= 2
  				continue
  			}
  			panic(fmt.Sprintf("%s: too slow: %d ops: %v; %d ops: %v\n\n%s",
  				typ, n, t1, 2*n, t2, buf.String()))
  		}
  	}
  }
  
  const offset = 251 // known size of runtime hash table
  
  const profile = false
  
  func main() {
  	if profile {
  		f, err := os.Create("lock.prof")
  		if err != nil {
  			log.Fatal(err)
  		}
  		pprof.StartCPUProfile(f)
  		defer pprof.StopCPUProfile()
  	}
  
  	checkLinear("lockone", 1000, func(n int) {
  		ch := make(chan int)
  		locks := make([]sync.RWMutex, offset+1)
  		for i := 0; i < n; i++ {
  			go func() {
  				locks[0].Lock()
  				ch <- 1
  			}()
  		}
  		time.Sleep(1 * time.Millisecond)
  
  		go func() {
  			for j := 0; j < n; j++ {
  				locks[1].Lock()
  				locks[offset].Lock()
  				locks[1].Unlock()
  				runtime.Gosched()
  				locks[offset].Unlock()
  			}
  		}()
  
  		for j := 0; j < n; j++ {
  			locks[1].Lock()
  			locks[offset].Lock()
  			locks[1].Unlock()
  			runtime.Gosched()
  			locks[offset].Unlock()
  		}
  
  		for i := 0; i < n; i++ {
  			<-ch
  			locks[0].Unlock()
  		}
  	})
  
  	checkLinear("lockmany", 1000, func(n int) {
  		locks := make([]sync.RWMutex, n*offset+1)
  
  		var wg sync.WaitGroup
  		for i := 0; i < n; i++ {
  			wg.Add(1)
  			go func(i int) {
  				locks[(i+1)*offset].Lock()
  				wg.Done()
  				locks[(i+1)*offset].Lock()
  				locks[(i+1)*offset].Unlock()
  			}(i)
  		}
  		wg.Wait()
  
  		go func() {
  			for j := 0; j < n; j++ {
  				locks[1].Lock()
  				locks[0].Lock()
  				locks[1].Unlock()
  				runtime.Gosched()
  				locks[0].Unlock()
  			}
  		}()
  
  		for j := 0; j < n; j++ {
  			locks[1].Lock()
  			locks[0].Lock()
  			locks[1].Unlock()
  			runtime.Gosched()
  			locks[0].Unlock()
  		}
  
  		for i := 0; i < n; i++ {
  			locks[(i+1)*offset].Unlock()
  		}
  	})
  }
  

View as plain text