calibrate_test.go

     1  // Copyright 2009 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Calibration used to determine thresholds for using
     6  // different algorithms.  Ideally, this would be converted
     7  // to go generate to create thresholds.go
     8  
     9  // This file prints execution times for the Mul benchmark
    10  // given different Karatsuba thresholds. The result may be
    11  // used to manually fine-tune the threshold constant. The
    12  // results are somewhat fragile; use repeated runs to get
    13  // a clear picture.
    14  
    15  // Calculates lower and upper thresholds for when basicSqr
    16  // is faster than standard multiplication.
    17  
    18  // Usage: go test -run='^TestCalibrate$' -v -calibrate
    19  
    20  package big
    21  
    22  import (
    23  	"flag"
    24  	"fmt"
    25  	"testing"
    26  	"time"
    27  )
    28  
    29  var calibrate = flag.Bool("calibrate", false, "run calibration test")
    30  
    31  const (
    32  	sqrModeMul       = "mul(x, x)"
    33  	sqrModeBasic     = "basicSqr(x)"
    34  	sqrModeKaratsuba = "karatsubaSqr(x)"
    35  )
    36  
    37  func TestCalibrate(t *testing.T) {
    38  	if !*calibrate {
    39  		return
    40  	}
    41  
    42  	computeKaratsubaThresholds()
    43  
    44  	// compute basicSqrThreshold where overhead becomes negligible
    45  	minSqr := computeSqrThreshold(10, 30, 1, 3, sqrModeMul, sqrModeBasic)
    46  	// compute karatsubaSqrThreshold where karatsuba is faster
    47  	maxSqr := computeSqrThreshold(200, 500, 10, 3, sqrModeBasic, sqrModeKaratsuba)
    48  	if minSqr != 0 {
    49  		fmt.Printf("found basicSqrThreshold = %d\n", minSqr)
    50  	} else {
    51  		fmt.Println("no basicSqrThreshold found")
    52  	}
    53  	if maxSqr != 0 {
    54  		fmt.Printf("found karatsubaSqrThreshold = %d\n", maxSqr)
    55  	} else {
    56  		fmt.Println("no karatsubaSqrThreshold found")
    57  	}
    58  }
    59  
    60  func karatsubaLoad(b *testing.B) {
    61  	BenchmarkMul(b)
    62  }
    63  
    64  // measureKaratsuba returns the time to run a Karatsuba-relevant benchmark
    65  // given Karatsuba threshold th.
    66  func measureKaratsuba(th int) time.Duration {
    67  	th, karatsubaThreshold = karatsubaThreshold, th
    68  	res := testing.Benchmark(karatsubaLoad)
    69  	karatsubaThreshold = th
    70  	return time.Duration(res.NsPerOp())
    71  }
    72  
    73  func computeKaratsubaThresholds() {
    74  	fmt.Printf("Multiplication times for varying Karatsuba thresholds\n")
    75  	fmt.Printf("(run repeatedly for good results)\n")
    76  
    77  	// determine Tk, the work load execution time using basic multiplication
    78  	Tb := measureKaratsuba(1e9) // th == 1e9 => Karatsuba multiplication disabled
    79  	fmt.Printf("Tb = %10s\n", Tb)
    80  
    81  	// thresholds
    82  	th := 4
    83  	th1 := -1
    84  	th2 := -1
    85  
    86  	var deltaOld time.Duration
    87  	for count := -1; count != 0 && th < 128; count-- {
    88  		// determine Tk, the work load execution time using Karatsuba multiplication
    89  		Tk := measureKaratsuba(th)
    90  
    91  		// improvement over Tb
    92  		delta := (Tb - Tk) * 100 / Tb
    93  
    94  		fmt.Printf("th = %3d  Tk = %10s  %4d%%", th, Tk, delta)
    95  
    96  		// determine break-even point
    97  		if Tk < Tb && th1 < 0 {
    98  			th1 = th
    99  			fmt.Print("  break-even point")
   100  		}
   101  
   102  		// determine diminishing return
   103  		if 0 < delta && delta < deltaOld && th2 < 0 {
   104  			th2 = th
   105  			fmt.Print("  diminishing return")
   106  		}
   107  		deltaOld = delta
   108  
   109  		fmt.Println()
   110  
   111  		// trigger counter
   112  		if th1 >= 0 && th2 >= 0 && count < 0 {
   113  			count = 10 // this many extra measurements after we got both thresholds
   114  		}
   115  
   116  		th++
   117  	}
   118  }
   119  
   120  func measureSqr(words, nruns int, mode string) time.Duration {
   121  	// more runs for better statistics
   122  	initBasicSqr, initKaratsubaSqr := basicSqrThreshold, karatsubaSqrThreshold
   123  
   124  	switch mode {
   125  	case sqrModeMul:
   126  		basicSqrThreshold = words + 1
   127  	case sqrModeBasic:
   128  		basicSqrThreshold, karatsubaSqrThreshold = words-1, words+1
   129  	case sqrModeKaratsuba:
   130  		karatsubaSqrThreshold = words - 1
   131  	}
   132  
   133  	var testval int64
   134  	for i := 0; i < nruns; i++ {
   135  		res := testing.Benchmark(func(b *testing.B) { benchmarkNatSqr(b, words) })
   136  		testval += res.NsPerOp()
   137  	}
   138  	testval /= int64(nruns)
   139  
   140  	basicSqrThreshold, karatsubaSqrThreshold = initBasicSqr, initKaratsubaSqr
   141  
   142  	return time.Duration(testval)
   143  }
   144  
   145  func computeSqrThreshold(from, to, step, nruns int, lower, upper string) int {
   146  	fmt.Printf("Calibrating threshold between %s and %s\n", lower, upper)
   147  	fmt.Printf("Looking for a timing difference for x between %d - %d words by %d step\n", from, to, step)
   148  	var initPos bool
   149  	var threshold int
   150  	for i := from; i <= to; i += step {
   151  		baseline := measureSqr(i, nruns, lower)
   152  		testval := measureSqr(i, nruns, upper)
   153  		pos := baseline > testval
   154  		delta := baseline - testval
   155  		percent := delta * 100 / baseline
   156  		fmt.Printf("words = %3d deltaT = %10s (%4d%%) is %s better: %v", i, delta, percent, upper, pos)
   157  		if i == from {
   158  			initPos = pos
   159  		}
   160  		if threshold == 0 && pos != initPos {
   161  			threshold = i
   162  			fmt.Printf("  threshold  found")
   163  		}
   164  		fmt.Println()
   165  
   166  	}
   167  	if threshold != 0 {
   168  		fmt.Printf("Found threshold = %d between %d - %d\n", threshold, from, to)
   169  	} else {
   170  		fmt.Printf("Found NO threshold between %d - %d\n", from, to)
   171  	}
   172  	return threshold
   173  }
   174
View as plain text