// 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
|
}
|
