From 43a123c1ae6613b3efeed291fa552ecd909d3acf Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Tue, 16 Apr 2024 21:23:18 +0200 Subject: Adding upstream version 1.20.14. Signed-off-by: Daniel Baumann --- src/math/big/calibrate_test.go | 173 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 173 insertions(+) create mode 100644 src/math/big/calibrate_test.go (limited to 'src/math/big/calibrate_test.go') 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 +} -- cgit v1.2.3