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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
// Usage: go test -run=TestCalibrate -calibrate
package bigfft
import (
"flag"
"fmt"
"testing"
"time"
)
var calibrate = flag.Bool("calibrate", false, "run calibration test")
// measureMul benchmarks math/big versus FFT for a given input size
// (in bits).
func measureMul(th int) (tBig, tFFT time.Duration) {
bigLoad := func(b *testing.B) { benchmarkMulBig(b, th, th) }
fftLoad := func(b *testing.B) { benchmarkMulFFT(b, th, th) }
res1 := testing.Benchmark(bigLoad)
res2 := testing.Benchmark(fftLoad)
tBig = time.Duration(res1.NsPerOp())
tFFT = time.Duration(res2.NsPerOp())
return
}
func TestCalibrateThreshold(t *testing.T) {
if !*calibrate {
t.Log("not calibrating, use -calibrate to do so.")
return
}
lower := int(1e3) // math/big is faster at this size.
upper := int(300e3) // FFT is faster at this size.
big, fft := measureMul(lower)
lowerX := float64(big) / float64(fft)
fmt.Printf("speedup at size %d: %.2f\n", lower, lowerX)
big, fft = measureMul(upper)
upperX := float64(big) / float64(fft)
fmt.Printf("speedup at size %d: %.2f\n", upper, upperX)
for {
mid := (lower + upper) / 2
big, fft := measureMul(mid)
X := float64(big) / float64(fft)
fmt.Printf("speedup at size %d: %.2f\n", mid, X)
switch {
case X < 0.98:
lower = mid
lowerX = X
case X > 1.02:
upper = mid
upperX = X
default:
fmt.Printf("speedup at size %d: %.2f\n", lower, lowerX)
fmt.Printf("speedup at size %d: %.2f\n", upper, upperX)
return
}
}
}
func measureFFTSize(w int, k uint) time.Duration {
load := func(b *testing.B) {
x := rndNat(w)
y := rndNat(w)
for i := 0; i < b.N; i++ {
m := (w+w)>>k + 1
xp := polyFromNat(x, k, m)
yp := polyFromNat(y, k, m)
rp := xp.Mul(&yp)
_ = rp.Int()
}
}
res := testing.Benchmark(load)
return time.Duration(res.NsPerOp())
}
func TestCalibrateFFT(t *testing.T) {
if !*calibrate {
t.Log("not calibrating, use -calibrate to do so.")
return
}
K:
for k := uint(3); k < 16; k++ {
// Measure the speedup between k and k+1
low := 10 << k
hi := 500 << k
low1, low2 := measureFFTSize(low, k), measureFFTSize(low, k+1)
lowX := float64(low1) / float64(low2) // less than 1
fmt.Printf("speedup of %d vs %d at size %d words: %.2f\n", k+1, k, low, lowX)
hi1, hi2 := measureFFTSize(hi, k), measureFFTSize(hi, k+1)
hiX := float64(hi1) / float64(hi2) // larger than 1
fmt.Printf("speedup of %d vs %d at size %d words: %.2f\n", k+1, k, hi, hiX)
for i := 0; i < 10; i++ {
mid := (low + hi) / 2
mid1, mid2 := measureFFTSize(mid, k), measureFFTSize(mid, k+1)
midX := float64(mid1) / float64(mid2)
fmt.Printf("speedup of %d vs %d at size %d words: %.2f\n", k+1, k, mid, midX)
switch {
case midX < 0.98:
low = mid
lowX = midX
case midX > 1.02:
hi = mid
hiX = midX
default:
fmt.Printf("speedup of %d vs %d at size %d words: %.2f\n", k+1, k, low, lowX)
fmt.Printf("speedup of %d vs %d at size %d words: %.2f\n", k+1, k, hi, hiX)
continue K
}
}
}
}
|
