Home | History | Annotate | Download | only in 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 func TestCalibrate(t *testing.T) {
     32 	if *calibrate {
     33 		computeKaratsubaThresholds()
     34 
     35 		// compute basicSqrThreshold where overhead becomes negligible
     36 		minSqr := computeSqrThreshold(10, 30, 1, 3)
     37 		// compute karatsubaSqrThreshold where karatsuba is faster
     38 		maxSqr := computeSqrThreshold(300, 500, 10, 3)
     39 		if minSqr != 0 {
     40 			fmt.Printf("found basicSqrThreshold = %d\n", minSqr)
     41 		} else {
     42 			fmt.Println("no basicSqrThreshold found")
     43 		}
     44 		if maxSqr != 0 {
     45 			fmt.Printf("found karatsubaSqrThreshold = %d\n", maxSqr)
     46 		} else {
     47 			fmt.Println("no karatsubaSqrThreshold found")
     48 		}
     49 	}
     50 }
     51 
     52 func karatsubaLoad(b *testing.B) {
     53 	BenchmarkMul(b)
     54 }
     55 
     56 // measureKaratsuba returns the time to run a Karatsuba-relevant benchmark
     57 // given Karatsuba threshold th.
     58 func measureKaratsuba(th int) time.Duration {
     59 	th, karatsubaThreshold = karatsubaThreshold, th
     60 	res := testing.Benchmark(karatsubaLoad)
     61 	karatsubaThreshold = th
     62 	return time.Duration(res.NsPerOp())
     63 }
     64 
     65 func computeKaratsubaThresholds() {
     66 	fmt.Printf("Multiplication times for varying Karatsuba thresholds\n")
     67 	fmt.Printf("(run repeatedly for good results)\n")
     68 
     69 	// determine Tk, the work load execution time using basic multiplication
     70 	Tb := measureKaratsuba(1e9) // th == 1e9 => Karatsuba multiplication disabled
     71 	fmt.Printf("Tb = %10s\n", Tb)
     72 
     73 	// thresholds
     74 	th := 4
     75 	th1 := -1
     76 	th2 := -1
     77 
     78 	var deltaOld time.Duration
     79 	for count := -1; count != 0 && th < 128; count-- {
     80 		// determine Tk, the work load execution time using Karatsuba multiplication
     81 		Tk := measureKaratsuba(th)
     82 
     83 		// improvement over Tb
     84 		delta := (Tb - Tk) * 100 / Tb
     85 
     86 		fmt.Printf("th = %3d  Tk = %10s  %4d%%", th, Tk, delta)
     87 
     88 		// determine break-even point
     89 		if Tk < Tb && th1 < 0 {
     90 			th1 = th
     91 			fmt.Print("  break-even point")
     92 		}
     93 
     94 		// determine diminishing return
     95 		if 0 < delta && delta < deltaOld && th2 < 0 {
     96 			th2 = th
     97 			fmt.Print("  diminishing return")
     98 		}
     99 		deltaOld = delta
    100 
    101 		fmt.Println()
    102 
    103 		// trigger counter
    104 		if th1 >= 0 && th2 >= 0 && count < 0 {
    105 			count = 10 // this many extra measurements after we got both thresholds
    106 		}
    107 
    108 		th++
    109 	}
    110 }
    111 
    112 func measureBasicSqr(words, nruns int, enable bool) time.Duration {
    113 	// more runs for better statistics
    114 	initBasicSqr, initKaratsubaSqr := basicSqrThreshold, karatsubaSqrThreshold
    115 
    116 	if enable {
    117 		// set thresholds to use basicSqr at this number of words
    118 		basicSqrThreshold, karatsubaSqrThreshold = words-1, words+1
    119 	} else {
    120 		// set thresholds to disable basicSqr for any number of words
    121 		basicSqrThreshold, karatsubaSqrThreshold = -1, -1
    122 	}
    123 
    124 	var testval int64
    125 	for i := 0; i < nruns; i++ {
    126 		res := testing.Benchmark(func(b *testing.B) { benchmarkNatSqr(b, words) })
    127 		testval += res.NsPerOp()
    128 	}
    129 	testval /= int64(nruns)
    130 
    131 	basicSqrThreshold, karatsubaSqrThreshold = initBasicSqr, initKaratsubaSqr
    132 
    133 	return time.Duration(testval)
    134 }
    135 
    136 func computeSqrThreshold(from, to, step, nruns int) int {
    137 	fmt.Println("Calibrating thresholds for basicSqr via benchmarks of z.mul(x,x)")
    138 	fmt.Printf("Looking for a timing difference for x between %d - %d words by %d step\n", from, to, step)
    139 	var initPos bool
    140 	var threshold int
    141 	for i := from; i <= to; i += step {
    142 		baseline := measureBasicSqr(i, nruns, false)
    143 		testval := measureBasicSqr(i, nruns, true)
    144 		pos := baseline > testval
    145 		delta := baseline - testval
    146 		percent := delta * 100 / baseline
    147 		fmt.Printf("words = %3d deltaT = %10s (%4d%%) is basicSqr better: %v", i, delta, percent, pos)
    148 		if i == from {
    149 			initPos = pos
    150 		}
    151 		if threshold == 0 && pos != initPos {
    152 			threshold = i
    153 			fmt.Printf("  threshold  found")
    154 		}
    155 		fmt.Println()
    156 
    157 	}
    158 	if threshold != 0 {
    159 		fmt.Printf("Found threshold = %d between %d - %d\n", threshold, from, to)
    160 	} else {
    161 		fmt.Printf("Found NO threshold between %d - %d\n", from, to)
    162 	}
    163 	return threshold
    164 }
    165