math/big: update calibration tests and recalibrate
Refactor calibration tests to use the same logic for all.
Choosing thresholds that are broadly appropriate for all systems is part science
but also part guesswork and judgement. We could instead set per-GOOS/GOARCH
thresholds, but that seems like too much work, and even then there would be
variation between different chips within a GOOS/GOARCH.
(For example see the three linux/amd64 systems benchmarked below.)
The thresholds chosen in this CL are:
karatsubaThreshold = 40 // unchanged
basicSqrThreshold = 12 // was 20
karatsubaSqrThreshold = 80 // was 260
divRecursiveThreshold = 40 // was 100
The new file calibrate.md explains the calibration process and links to graphs
justifying those values. (The graphs are hosted on swtch.com to avoid adding
a megabyte of extra data to the Go repo and Go distributions.)
A rendered copy of calibrate.md is at https://swtch.com/math/big/calibrate.html.
goos: linux
goarch: amd64
pkg: math/big
cpu: Intel(R) Xeon(R) Platinum 8481C CPU @ 2.70GHz
│ old │ new │
│ sec/op │ sec/op vs base │
Div/20/10-88 13.13n ± 2% 13.14n ± 2% ~ (p=0.494 n=15)
Div/40/20-88 13.13n ± 2% 13.14n ± 2% ~ (p=0.137 n=15)
Div/100/50-88 25.50n ± 0% 25.51n ± 0% ~ (p=0.038 n=15)
Div/200/100-88 113.1n ± 1% 116.0n ± 3% +2.56% (p=0.000 n=15)
Div/400/200-88 135.3n ± 0% 137.1n ± 1% ~ (p=0.004 n=15)
Div/1000/500-88 259.9n ± 1% 259.0n ± 2% ~ (p=0.182 n=15)
Div/2000/1000-88 568.8n ± 1% 564.7n ± 3% ~ (p=0.927 n=15)
Div/20000/10000-88 25.79µ ± 1% 22.11µ ± 2% -14.26% (p=0.000 n=15)
Div/200000/100000-88 755.1µ ± 1% 737.6µ ± 1% -2.32% (p=0.000 n=15)
Div/
2000000/
1000000-88 31.30m ± 0% 31.20m ± 1% ~ (p=0.081 n=15)
Div/
20000000/
10000000-88 1.268 ± 0% 1.265 ± 0% ~ (p=0.011 n=15)
NatMul/10-88 142.6n ± 0% 142.9n ± 7% ~ (p=0.145 n=15)
NatMul/100-88 4.347µ ± 0% 4.350µ ± 3% ~ (p=0.430 n=15)
NatMul/1000-88 187.6µ ± 0% 188.4µ ± 2% ~ (p=0.004 n=15)
NatMul/10000-88 8.052m ± 0% 8.057m ± 1% ~ (p=0.148 n=15)
NatMul/100000-88 260.6m ± 0% 260.7m ± 0% ~ (p=0.512 n=15)
NatSqr/1-88 26.58n ± 5% 27.96n ± 8% ~ (p=0.574 n=15)
NatSqr/2-88 42.35n ± 7% 44.87n ± 6% ~ (p=0.690 n=15)
NatSqr/3-88 53.28n ± 4% 55.62n ± 5% ~ (p=0.151 n=15)
NatSqr/5-88 76.26n ± 6% 81.43n ± 6% +6.78% (p=0.000 n=15)
NatSqr/8-88 110.8n ± 5% 116.4n ± 6% ~ (p=0.040 n=15)
NatSqr/10-88 141.4n ± 4% 147.8n ± 4% ~ (p=0.011 n=15)
NatSqr/20-88 325.8n ± 3% 341.7n ± 4% +4.88% (p=0.000 n=15)
NatSqr/30-88 536.8n ± 3% 556.1n ± 4% ~ (p=0.027 n=15)
NatSqr/50-88 1.168µ ± 3% 1.197µ ± 3% ~ (p=0.442 n=15)
NatSqr/80-88 2.527µ ± 2% 2.480µ ± 2% -1.86% (p=0.000 n=15)
NatSqr/100-88 3.771µ ± 2% 3.535µ ± 2% -6.26% (p=0.000 n=15)
NatSqr/200-88 14.03µ ± 2% 10.57µ ± 3% -24.68% (p=0.000 n=15)
NatSqr/300-88 24.06µ ± 2% 20.57µ ± 2% -14.52% (p=0.000 n=15)
NatSqr/500-88 65.43µ ± 1% 45.45µ ± 1% -30.55% (p=0.000 n=15)
NatSqr/800-88 126.41µ ± 1% 94.13µ ± 2% -25.54% (p=0.000 n=15)
NatSqr/1000-88 196.4µ ± 1% 135.1µ ± 1% -31.18% (p=0.000 n=15)
NatSqr/10000-88 6.404m ± 0% 5.326m ± 1% -16.84% (p=0.000 n=15)
NatSqr/100000-88 267.2m ± 0% 198.7m ± 0% -25.64% (p=0.000 n=15)
geomean 7.318µ 6.948µ -5.06%
goos: linux
goarch: amd64
pkg: math/big
cpu: Intel(R) Xeon(R) CPU @ 3.10GHz
│ old │ new │
│ sec/op │ sec/op vs base │
Div/20/10-16 22.23n ± 0% 22.23n ± 0% ~ (p=0.973 n=15)
Div/40/20-16 22.23n ± 0% 22.23n ± 0% ~ (p=0.226 n=15)
Div/100/50-16 55.27n ± 1% 55.59n ± 0% ~ (p=0.004 n=15)
Div/200/100-16 174.7n ± 3% 175.9n ± 2% ~ (p=0.645 n=15)
Div/400/200-16 208.8n ± 1% 209.5n ± 2% ~ (p=0.169 n=15)
Div/1000/500-16 378.7n ± 2% 380.5n ± 2% ~ (p=0.091 n=15)
Div/2000/1000-16 778.4n ± 1% 781.1n ± 2% ~ (p=0.104 n=15)
Div/20000/10000-16 25.16µ ± 1% 24.93µ ± 1% -0.91% (p=0.000 n=15)
Div/200000/100000-16 926.4µ ± 0% 927.7µ ± 1% ~ (p=0.436 n=15)
Div/
2000000/
1000000-16 35.58m ± 0% 35.53m ± 0% ~ (p=0.267 n=15)
Div/
20000000/
10000000-16 1.333 ± 0% 1.330 ± 0% ~ (p=0.126 n=15)
NatMul/10-16 172.6n ± 0% 165.4n ± 0% -4.17% (p=0.000 n=15)
NatMul/100-16 5.706µ ± 0% 5.503µ ± 0% -3.56% (p=0.000 n=15)
NatMul/1000-16 220.8µ ± 0% 219.1µ ± 0% -0.76% (p=0.000 n=15)
NatMul/10000-16 8.688m ± 0% 8.621m ± 0% -0.77% (p=0.000 n=15)
NatMul/100000-16 333.3m ± 0% 333.5m ± 0% ~ (p=0.512 n=15)
NatSqr/1-16 28.66n ± 1% 28.42n ± 3% -0.84% (p=0.000 n=15)
NatSqr/2-16 48.29n ± 2% 48.19n ± 2% ~ (p=0.042 n=15)
NatSqr/3-16 59.93n ± 0% 59.64n ± 2% -0.48% (p=0.000 n=15)
NatSqr/5-16 88.05n ± 0% 87.89n ± 3% ~ (p=0.066 n=15)
NatSqr/8-16 127.7n ± 0% 126.9n ± 3% -0.63% (p=0.000 n=15)
NatSqr/10-16 170.4n ± 0% 169.7n ± 3% ~ (p=0.004 n=15)
NatSqr/20-16 388.8n ± 0% 392.9n ± 3% ~ (p=0.123 n=15)
NatSqr/30-16 635.2n ± 0% 641.7n ± 3% ~ (p=0.123 n=15)
NatSqr/50-16 1.304µ ± 1% 1.314µ ± 3% ~ (p=0.927 n=15)
NatSqr/80-16 2.709µ ± 1% 2.899µ ± 4% +7.01% (p=0.000 n=15)
NatSqr/100-16 3.885µ ± 0% 3.981µ ± 4% ~ (p=0.123 n=15)
NatSqr/200-16 13.29µ ± 2% 12.14µ ± 4% -8.67% (p=0.000 n=15)
NatSqr/300-16 23.39µ ± 0% 22.51µ ± 3% -3.78% (p=0.000 n=15)
NatSqr/500-16 58.13µ ± 1% 50.56µ ± 2% -13.02% (p=0.000 n=15)
NatSqr/800-16 118.4µ ± 1% 107.6µ ± 2% -9.11% (p=0.000 n=15)
NatSqr/1000-16 172.7µ ± 1% 151.8µ ± 2% -12.11% (p=0.000 n=15)
NatSqr/10000-16 6.065m ± 1% 5.757m ± 1% -5.08% (p=0.000 n=15)
NatSqr/100000-16 240.9m ± 0% 228.1m ± 0% -5.32% (p=0.000 n=15)
geomean 8.601µ 8.453µ -1.71%
goos: linux
goarch: amd64
pkg: math/big
cpu: AMD Ryzen 9 7950X 16-Core Processor
│ old │ new │
│ sec/op │ sec/op vs base │
Div/20/10-32 11.11n ± 0% 11.11n ± 1% ~ (p=0.532 n=15)
Div/40/20-32 11.08n ± 1% 11.11n ± 0% ~ (p=0.815 n=15)
Div/100/50-32 16.81n ± 0% 16.84n ± 29% ~ (p=0.020 n=15)
Div/200/100-32 73.91n ± 0% 76.85n ± 11% +3.98% (p=0.000 n=15)
Div/400/200-32 87.35n ± 0% 88.91n ± 34% +1.79% (p=0.000 n=15)
Div/1000/500-32 169.3n ± 1% 168.9n ± 1% ~ (p=0.049 n=15)
Div/2000/1000-32 369.3n ± 0% 369.0n ± 0% ~ (p=0.108 n=15)
Div/20000/10000-32 15.92µ ± 0% 13.55µ ± 2% -14.91% (p=0.000 n=15)
Div/200000/100000-32 491.4µ ± 0% 482.4µ ± 1% -1.84% (p=0.000 n=15)
Div/
2000000/
1000000-32 20.09m ± 0% 19.96m ± 0% -0.69% (p=0.000 n=15)
Div/
20000000/
10000000-32 756.5m ± 0% 755.5m ± 0% ~ (p=0.089 n=15)
NatMul/10-32 125.4n ± 5% 124.8n ± 1% ~ (p=0.588 n=15)
NatMul/100-32 2.952µ ± 3% 2.969µ ± 0% ~ (p=0.237 n=15)
NatMul/1000-32 120.7µ ± 0% 121.1µ ± 0% +0.30% (p=0.000 n=15)
NatMul/10000-32 4.845m ± 0% 4.839m ± 1% ~ (p=0.653 n=15)
NatMul/100000-32 173.3m ± 0% 173.3m ± 0% ~ (p=0.838 n=15)
NatSqr/1-32 31.18n ± 23% 32.08n ± 2% ~ (p=0.015 n=15)
NatSqr/2-32 57.22n ± 28% 58.88n ± 2% ~ (p=0.054 n=15)
NatSqr/3-32 61.34n ± 18% 64.33n ± 2% ~ (p=0.237 n=15)
NatSqr/5-32 72.47n ± 17% 79.81n ± 3% ~ (p=0.067 n=15)
NatSqr/8-32 83.26n ± 26% 100.10n ± 3% ~ (p=0.016 n=15)
NatSqr/10-32 87.31n ± 43% 125.50n ± 2% ~ (p=0.003 n=15)
NatSqr/20-32 193.5n ± 25% 244.4n ± 13% ~ (p=0.002 n=15)
NatSqr/30-32 323.9n ± 17% 380.9n ± 6% ~ (p=0.003 n=15)
NatSqr/50-32 713.4n ± 9% 761.7n ± 8% ~ (p=0.419 n=15)
NatSqr/80-32 1.486µ ± 7% 1.609µ ± 5% +8.28% (p=0.000 n=15)
NatSqr/100-32 2.115µ ± 9% 2.253µ ± 1% ~ (p=0.104 n=15)
NatSqr/200-32 7.201µ ± 4% 6.610µ ± 1% -8.21% (p=0.000 n=15)
NatSqr/300-32 13.08µ ± 2% 12.37µ ± 1% -5.41% (p=0.000 n=15)
NatSqr/500-32 32.56µ ± 2% 27.83µ ± 2% -14.52% (p=0.000 n=15)
NatSqr/800-32 66.83µ ± 3% 59.59µ ± 1% -10.83% (p=0.000 n=15)
NatSqr/1000-32 98.09µ ± 1% 83.59µ ± 1% -14.78% (p=0.000 n=15)
NatSqr/10000-32 3.445m ± 1% 3.245m ± 0% -5.81% (p=0.000 n=15)
NatSqr/100000-32 137.3m ± 0% 127.0m ± 0% -7.54% (p=0.000 n=15)
geomean 4.897µ 4.972µ +1.52%
goos: linux
goarch: arm64
pkg: math/big
│ old │ new │
│ sec/op │ sec/op vs base │
Div/20/10-16 15.26n ± 2% 15.14n ± 1% ~ (p=0.212 n=15)
Div/40/20-16 15.22n ± 1% 15.16n ± 0% ~ (p=0.190 n=15)
Div/100/50-16 26.53n ± 2% 26.42n ± 0% -0.41% (p=0.000 n=15)
Div/200/100-16 124.3n ± 0% 124.0n ± 0% ~ (p=0.704 n=15)
Div/400/200-16 142.4n ± 0% 141.8n ± 0% ~ (p=0.074 n=15)
Div/1000/500-16 262.0n ± 1% 261.3n ± 1% ~ (p=0.046 n=15)
Div/2000/1000-16 532.6n ± 0% 532.5n ± 1% ~ (p=0.798 n=15)
Div/20000/10000-16 22.27µ ± 0% 22.88µ ± 0% +2.73% (p=0.000 n=15)
Div/200000/100000-16 890.4µ ± 0% 902.8µ ± 0% +1.39% (p=0.000 n=15)
Div/
2000000/
1000000-16 35.03m ± 0% 35.10m ± 0% ~ (p=0.305 n=15)
Div/
20000000/
10000000-16 1.380 ± 0% 1.385 ± 0% ~ (p=0.019 n=15)
NatMul/10-16 177.6n ± 1% 175.6n ± 3% ~ (p=0.480 n=15)
NatMul/100-16 5.675µ ± 0% 5.669µ ± 1% ~ (p=0.705 n=15)
NatMul/1000-16 224.3µ ± 0% 224.6µ ± 0% ~ (p=0.653 n=15)
NatMul/10000-16 8.735m ± 0% 8.739m ± 0% ~ (p=0.567 n=15)
NatMul/100000-16 331.6m ± 0% 331.6m ± 1% ~ (p=0.412 n=15)
NatSqr/1-16 43.69n ± 2% 42.77n ± 6% ~ (p=0.383 n=15)
NatSqr/2-16 65.26n ± 2% 63.91n ± 5% ~ (p=0.285 n=15)
NatSqr/3-16 73.95n ± 1% 72.25n ± 6% ~ (p=0.198 n=15)
NatSqr/5-16 95.06n ± 1% 94.21n ± 3% ~ (p=0.721 n=15)
NatSqr/8-16 155.5n ± 1% 153.4n ± 4% ~ (p=0.170 n=15)
NatSqr/10-16 175.4n ± 1% 174.0n ± 2% ~ (p=0.271 n=15)
NatSqr/20-16 360.8n ± 0% 358.5n ± 2% ~ (p=0.170 n=15)
NatSqr/30-16 584.7n ± 0% 582.9n ± 1% ~ (p=0.170 n=15)
NatSqr/50-16 1.323µ ± 0% 1.322µ ± 0% ~ (p=0.627 n=15)
NatSqr/80-16 2.916µ ± 0% 2.674µ ± 0% -8.30% (p=0.000 n=15)
NatSqr/100-16 4.365µ ± 0% 3.802µ ± 0% -12.90% (p=0.000 n=15)
NatSqr/200-16 16.42µ ± 0% 11.29µ ± 0% -31.26% (p=0.000 n=15)
NatSqr/300-16 28.07µ ± 0% 22.83µ ± 0% -18.68% (p=0.000 n=15)
NatSqr/500-16 76.30µ ± 0% 50.06µ ± 0% -34.39% (p=0.000 n=15)
NatSqr/800-16 147.5µ ± 0% 101.2µ ± 1% -31.41% (p=0.000 n=15)
NatSqr/1000-16 228.6µ ± 0% 149.5µ ± 0% -34.61% (p=0.000 n=15)
NatSqr/10000-16 7.417m ± 0% 6.025m ± 0% -18.76% (p=0.000 n=15)
NatSqr/100000-16 309.2m ± 0% 214.9m ± 0% -30.50% (p=0.000 n=15)
geomean 8.559µ 7.906µ -7.63%
goos: darwin
goarch: arm64
pkg: math/big
cpu: Apple M3 Pro
│ old │ new │
│ sec/op │ sec/op vs base │
Div/20/10-12 9.577n ± 6% 9.473n ± 5% ~ (p=0.384 n=15)
Div/40/20-12 9.480n ± 1% 9.430n ± 1% ~ (p=0.019 n=15)
Div/100/50-12 14.82n ± 0% 14.82n ± 0% ~ (p=0.845 n=15)
Div/200/100-12 83.94n ± 1% 84.35n ± 4% ~ (p=0.512 n=15)
Div/400/200-12 102.7n ± 1% 102.9n ± 0% ~ (p=0.845 n=15)
Div/1000/500-12 185.3n ± 1% 181.9n ± 1% -1.83% (p=0.000 n=15)
Div/2000/1000-12 397.0n ± 1% 396.7n ± 0% ~ (p=0.959 n=15)
Div/20000/10000-12 14.05µ ± 0% 13.70µ ± 1% ~ (p=0.002 n=15)
Div/200000/100000-12 529.4µ ± 3% 526.7µ ± 2% ~ (p=0.967 n=15)
Div/
2000000/
1000000-12 20.05m ± 0% 20.05m ± 0% ~ (p=0.653 n=15)
Div/
20000000/
10000000-12 788.2m ± 1% 789.0m ± 1% ~ (p=0.412 n=15)
NatMul/10-12 79.95n ± 1% 80.87n ± 1% +1.15% (p=0.000 n=15)
NatMul/100-12 2.973µ ± 0% 2.986µ ± 2% ~ (p=0.051 n=15)
NatMul/1000-12 122.6µ ± 5% 123.0µ ± 1% ~ (p=0.783 n=15)
NatMul/10000-12 4.990m ± 1% 5.000m ± 1% ~ (p=0.653 n=15)
NatMul/100000-12 185.3m ± 3% 190.3m ± 1% ~ (p=0.089 n=15)
NatSqr/1-12 11.84n ± 1% 11.88n ± 1% ~ (p=0.735 n=15)
NatSqr/2-12 21.01n ± 1% 21.44n ± 6% ~ (p=0.039 n=15)
NatSqr/3-12 25.59n ± 0% 26.74n ± 9% +4.49% (p=0.000 n=15)
NatSqr/5-12 36.78n ± 0% 37.04n ± 1% +0.71% (p=0.000 n=15)
NatSqr/8-12 63.09n ± 3% 63.22n ± 1% ~ (p=0.846 n=15)
NatSqr/10-12 79.98n ± 0% 79.78n ± 0% ~ (p=0.100 n=15)
NatSqr/20-12 174.0n ± 0% 175.5n ± 1% ~ (p=0.361 n=15)
NatSqr/30-12 290.0n ± 0% 291.4n ± 0% ~ (p=0.002 n=15)
NatSqr/50-12 655.2n ± 4% 658.1n ± 0% ~ (p=0.060 n=15)
NatSqr/80-12 1.506µ ± 0% 1.397µ ± 5% -7.24% (p=0.000 n=15)
NatSqr/100-12 2.273µ ± 0% 2.005µ ± 5% -11.79% (p=0.000 n=15)
NatSqr/200-12 8.833µ ± 6% 6.109µ ± 0% -30.84% (p=0.000 n=15)
NatSqr/300-12 15.15µ ± 4% 12.37µ ± 0% -18.34% (p=0.000 n=15)
NatSqr/500-12 41.89µ ± 0% 27.70µ ± 1% -33.88% (p=0.000 n=15)
NatSqr/800-12 80.72µ ± 0% 56.40µ ± 0% -30.12% (p=0.000 n=15)
NatSqr/1000-12 127.06µ ± 1% 84.06µ ± 1% -33.84% (p=0.000 n=15)
NatSqr/10000-12 4.130m ± 0% 3.390m ± 0% -17.91% (p=0.000 n=15)
NatSqr/100000-12 173.2m ± 0% 131.2m ± 6% -24.25% (p=0.000 n=15)
geomean 4.489µ 4.189µ -6.68%
Change-Id: Iaf65fd85457b003ebf07a787c875cda321b40cc9
Reviewed-on: https://go-review.googlesource.com/c/go/+/652058
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Robert Griesemer <gri@google.com>
Reviewed-by: Alan Donovan <adonovan@google.com>
Auto-Submit: Russ Cox <rsc@golang.org>