blob: c6cd2e693b742e83aa5f1c366659dcb34b299496 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
// 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.
// 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.
// Usage: gotest -calibrate
package big
import (
"flag"
"fmt"
"testing"
"time"
)
var calibrate = flag.Bool("calibrate", false, "run calibration test")
// measure returns the time to run f
func measure(f func()) int64 {
const N = 100
start := time.Nanoseconds()
for i := N; i > 0; i-- {
f()
}
stop := time.Nanoseconds()
return (stop - start) / N
}
func computeThresholds() {
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
karatsubaThreshold = 1e9 // disable karatsuba
Tb := measure(benchmarkMulLoad)
fmt.Printf("Tb = %dns\n", Tb)
// thresholds
n := 8 // any lower values for the threshold lead to very slow multiplies
th1 := -1
th2 := -1
var deltaOld int64
for count := -1; count != 0; count-- {
// determine Tk, the work load execution time using Karatsuba multiplication
karatsubaThreshold = n // enable karatsuba
Tk := measure(benchmarkMulLoad)
// improvement over Tb
delta := (Tb - Tk) * 100 / Tb
fmt.Printf("n = %3d Tk = %8dns %4d%%", n, Tk, delta)
// determine break-even point
if Tk < Tb && th1 < 0 {
th1 = n
fmt.Print(" break-even point")
}
// determine diminishing return
if 0 < delta && delta < deltaOld && th2 < 0 {
th2 = n
fmt.Print(" diminishing return")
}
deltaOld = delta
fmt.Println()
// trigger counter
if th1 >= 0 && th2 >= 0 && count < 0 {
count = 20 // this many extra measurements after we got both thresholds
}
n++
}
}
func TestCalibrate(t *testing.T) {
if *calibrate {
computeThresholds()
}
}
|
