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