calibrate_test.go

Documentation: math/big

		 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