summaryrefslogtreecommitdiffstats
path: root/src/math/big/calibrate_test.go
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/math/big/calibrate_test.go173
1 files changed, 173 insertions, 0 deletions
diff --git a/src/math/big/calibrate_test.go b/src/math/big/calibrate_test.go
new file mode 100644
index 0000000..4fa663f
--- /dev/null
+++ b/src/math/big/calibrate_test.go
@@ -0,0 +1,173 @@
+// 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
+}