| // Copyright 2009 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. | |
| // Calibration used to determine thresholds for using | |
| // different algorithms. Ideally, this would be converted | |
| // to go generate to create thresholds.go | |
| // This file prints execution times for the Mul benchmark | |
| // given different Karatsuba thresholds. The result may be | |
| // used to manually fine-tune the threshold constant. The | |
| // results are somewhat fragile; use repeated runs to get | |
| // a clear picture. | |
| // Calculates lower and upper thresholds for when basicSqr | |
| // is faster than standard multiplication. | |
| // Usage: go test -run=TestCalibrate -v -calibrate | |
| package big | |
| import ( | |
| "flag" | |
| "fmt" | |
| "testing" | |
| "time" | |
| ) | |
| var calibrate = flag.Bool("calibrate", false, "run calibration test") | |
| const ( | |
| sqrModeMul = "mul(x, x)" | |
| sqrModeBasic = "basicSqr(x)" | |
| sqrModeKaratsuba = "karatsubaSqr(x)" | |
| ) | |
| func TestCalibrate(t *testing.T) { | |
| if !*calibrate { | |
| return | |
| } | |
| computeKaratsubaThresholds() | |
| // compute basicSqrThreshold where overhead becomes negligible | |
| minSqr := computeSqrThreshold(10, 30, 1, 3, sqrModeMul, sqrModeBasic) | |
| // compute karatsubaSqrThreshold where karatsuba is faster | |
| maxSqr := computeSqrThreshold(200, 500, 10, 3, sqrModeBasic, sqrModeKaratsuba) | |
| if minSqr != 0 { | |
| fmt.Printf("found basicSqrThreshold = %d\n", minSqr) | |
| } else { | |
| fmt.Println("no basicSqrThreshold found") | |
| } | |
| if maxSqr != 0 { | |
| fmt.Printf("found karatsubaSqrThreshold = %d\n", maxSqr) | |
| } else { | |
| fmt.Println("no karatsubaSqrThreshold found") | |
| } | |
| } | |
| func karatsubaLoad(b *testing.B) { | |
| BenchmarkMul(b) | |
| } | |
| // measureKaratsuba returns the time to run a Karatsuba-relevant benchmark | |
| // given Karatsuba threshold th. | |
| func measureKaratsuba(th int) time.Duration { | |
| th, karatsubaThreshold = karatsubaThreshold, th | |
| res := testing.Benchmark(karatsubaLoad) | |
| karatsubaThreshold = th | |
| return time.Duration(res.NsPerOp()) | |
| } | |
| func computeKaratsubaThresholds() { | |
| fmt.Printf("Multiplication times for varying Karatsuba thresholds\n") | |
| fmt.Printf("(run repeatedly for good results)\n") | |
| // determine Tk, the work load execution time using basic multiplication | |
| Tb := measureKaratsuba(1e9) // th == 1e9 => Karatsuba multiplication disabled | |
| fmt.Printf("Tb = %10s\n", Tb) | |
| // thresholds | |
| th := 4 | |
| th1 := -1 | |
| th2 := -1 | |
| var deltaOld time.Duration | |
| for count := -1; count != 0 && th < 128; count-- { | |
| // determine Tk, the work load execution time using Karatsuba multiplication | |
| Tk := measureKaratsuba(th) | |
| // improvement over Tb | |
| delta := (Tb - Tk) * 100 / Tb | |
| fmt.Printf("th = %3d Tk = %10s %4d%%", th, Tk, delta) | |
| // determine break-even point | |
| if Tk < Tb && th1 < 0 { | |
| th1 = th | |
| fmt.Print(" break-even point") | |
| } | |
| // determine diminishing return | |
| if 0 < delta && delta < deltaOld && th2 < 0 { | |
| th2 = th | |
| fmt.Print(" diminishing return") | |
| } | |
| deltaOld = delta | |
| fmt.Println() | |
| // trigger counter | |
| if th1 >= 0 && th2 >= 0 && count < 0 { | |
| count = 10 // this many extra measurements after we got both thresholds | |
| } | |
| th++ | |
| } | |
| } | |
| func measureSqr(words, nruns int, mode string) time.Duration { | |
| // more runs for better statistics | |
| initBasicSqr, initKaratsubaSqr := basicSqrThreshold, karatsubaSqrThreshold | |
| switch mode { | |
| case sqrModeMul: | |
| basicSqrThreshold = words + 1 | |
| case sqrModeBasic: | |
| basicSqrThreshold, karatsubaSqrThreshold = words-1, words+1 | |
| case sqrModeKaratsuba: | |
| karatsubaSqrThreshold = words - 1 | |
| } | |
| var testval int64 | |
| for i := 0; i < nruns; i++ { | |
| res := testing.Benchmark(func(b *testing.B) { benchmarkNatSqr(b, words) }) | |
| testval += res.NsPerOp() | |
| } | |
| testval /= int64(nruns) | |
| basicSqrThreshold, karatsubaSqrThreshold = initBasicSqr, initKaratsubaSqr | |
| return time.Duration(testval) | |
| } | |
| func computeSqrThreshold(from, to, step, nruns int, lower, upper string) int { | |
| fmt.Printf("Calibrating threshold between %s and %s\n", lower, upper) | |
| fmt.Printf("Looking for a timing difference for x between %d - %d words by %d step\n", from, to, step) | |
| var initPos bool | |
| var threshold int | |
| for i := from; i <= to; i += step { | |
| baseline := measureSqr(i, nruns, lower) | |
| testval := measureSqr(i, nruns, upper) | |
| pos := baseline > testval | |
| delta := baseline - testval | |
| percent := delta * 100 / baseline | |
| fmt.Printf("words = %3d deltaT = %10s (%4d%%) is %s better: %v", i, delta, percent, upper, pos) | |
| if i == from { | |
| initPos = pos | |
| } | |
| if threshold == 0 && pos != initPos { | |
| threshold = i | |
| fmt.Printf(" threshold found") | |
| } | |
| fmt.Println() | |
| } | |
| if threshold != 0 { | |
| fmt.Printf("Found threshold = %d between %d - %d\n", threshold, from, to) | |
| } else { | |
| fmt.Printf("Found NO threshold between %d - %d\n", from, to) | |
| } | |
| return threshold | |
| } |