math.Pow(x,y)优化针对情况:常数整数y
。例如:
... math.Pow(length, 2)...
... math.Pow(length, 3.0)...
你在使用哪个版本的Go(go version
)?
$ go version
go version go1.11.4 linux/amd64
这个问题在最新版本中是否重现?
是的,对于go 1.6
你正在使用什么操作系统和处理器架构(go env
)?
go env
输出
$ go env
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/konstantin/.cache/go-build"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOOS="linux"
GOPATH="/home/konstantin/go"
GOPROXY=""
GORACE=""
GOROOT="/usr/local/go"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/linux_amd64"
GCCGO="gccgo"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build700464290=/tmp/go-build -gno-record-gcc-switches"
你做了什么?
package main
import (
"math"
"testing"
)
func BenchmarkMathPow(b *testing.B) {
x := 42.0
for i := 0; i < b.N; i++ {
_ = math.Pow(x, 2.0)
}
}
func BenchmarkInline(b *testing.B) {
x := 42.0
for i := 0; i < b.N; i++ {
_ = x * x
}
}
你期望看到什么?
两种情况下的性能相同或初步相同。
你看到了什么?
运行基准测试
> go test -bench=.
goos: linux
goarch: amd64
pkg: tmp
BenchmarkMathPow-4 30000000 49.6 ns/op
BenchmarkInline-4 2000000000 0.68 ns/op
PASS
ok tmp 2.992s
不同的多70倍。
注意
在math/pow.go中更改函数pow
对解决性能问题不够。
func BenchmarkPowModify(b *testing.B) {
x := 42.0
for i := 0; i < b.N; i++ {
_ = pow(x, 2.0)
}
}
func pow(x, y float64) float64 {
switch {
case y == 0 || x == 1:
return 1
// changes for cases with integer `y`.
case float64(int8(y)) == y:
if y < 0 {
return 1.0 / pow(x, -y)
}
n := int(y)
r := 1.0
for i := 0; i < n; i++ {
r *= x
}
return r
case math.IsNaN(x) || math.IsNaN(y):
return math.NaN()
... other like in file math/pow.go ....
结果更好,但仍不如the best
:
BenchmarkMathPow-4 30000000 49.6 ns/op
BenchmarkPowModify-4 200000000 7.56 ns/op
BenchmarkInline-4 2000000000 0.69 ns/op
PASS
ok tmp 5.268s
我们是否有优化的地方可以改变AST从参数math.Pow
= 2的函数表达式到表达式y
吗?(就像我理解的那样,ssa
不是正确的地方)。
9条答案
按热度按时间xqk2d5yq1#
https://golang.org/cl/155921提到了这个问题:
math: Pow(x,y) optimization for cases: constant integer
y.
ylamdve62#
请注意,对于:
较新的Go Gc编译器足够智能,可以推断出循环体计算从未使用过,并优化掉循环体。因此,这可能是对空循环的基准测试。
https://godbolt.org/z/ot9w2G
为了避免一些与死代码消除和常量折叠代码相关的问题,可以使用以下代码:
https://godbolt.org/z/Nt9OWg
有关优化的一些问题:
我认为在AST级别重写为
x*x
并不值得。我预计需要提高速度的程序员已经使用了更简单、更快的x*x
版本,而不是math.Pow。它还会产生一个不良副作用,即复制数学代码,导致速度变慢。通常,这些特定于包的重写优化应避免在编译器中进行,如果可能的话,应由与代码模式相匹配的一般优化来覆盖。或者,这些特殊情况可以通过函数中的if语句来覆盖,随着内联改进和常量传播的提高,将减少当前和未来的开销。3mpgtkmj3#
亲爱的@martisch,
在我笔记本电脑上将
BenchmarkInline
更改为go1.11.4
后,结果仍然是0.7...1.03 ns/op
。所以我进行了检查。关于您的问题:
y = 2
或y = 3
。在gonum
的实践中:y=7
...所以值不大,所以我检查了y=-127...127
-这对我的任务来说已经足够了。如果在我的任务中需要更多,那么在批准代码设计后,您可以修改更多的y
值。math.Pow
的实现和那个PR具有相同的结果。我同意您的观点,如果是
y > 3
,但对于y = 2
和y = 3
的情况,我自己是可以接受的。现在,我发现对于数学库中的常量没有优化,例如,如果我们有这样的代码:
就不需要在函数math.Max中进行所有的y检查。
az31mfrm4#
在我的笔记本电脑上,将BenchmarkInline更改为go1.11.4中您示例中的值后,结果相同。
当前math.Pow的实现和那个PR具有相同的结果。
感谢您的检查和澄清。
不需要在函数math.Max中检查所有y。
是的,编译器具有更好的内联支持,通常可以确定这一点(也超出了数学包的范围),并且只使用和内联相关的检查。这在字符串包中也有帮助,例如使用字符串计算长度为1的计数。在一般情况下,这可以更好地处理,而无需硬编码AST优化。
8aqjt8rx5#
我正在观察这里的变化。如果我们要这样做,我可以建议使用一个更简单的方法吗?背景是:
celeste:power7 mtj$ go test -v -bench=.
=== RUN TestSanityPowerM
--- PASS: TestSanityPowerM (0.03s)
=== RUN TestSanityPowerBinary
--- PASS: TestSanityPowerBinary (0.03s)
goos: darwin
goarch: amd64
pkg: power7
BenchmarkPowerMath-8 30000000 52.9 ns/op
BenchmarkPowerBinary-8 200000000 9.09 ns/op
BenchmarkPowerM-8 300000000 5.33 ns/op
BenchmarkPowerMathFixed-8 50000000 34.9 ns/op
BenchmarkPowerBinaryFixed-8 200000000 7.08 ns/op
BenchmarkPowerMFixed-8 300000000 4.95 ns/op
BenchmarkPowerMDirect124-8 1000000000 2.56 ns/op
数学库的方法,在我测试的一系列指数上平均为52.9纳秒/操作。
正在审查的迭代方法,对于x124和24-40纳秒的一般情况约为37秒。
众所周知的二进制幂法(如下),在一般情况下为9.09纳秒/操作,对于x124的情况为7.08纳秒/操作。
由我的程序生成的一组自动生成的神奇最优幂树(以及克努特斯、许多人的其他作品)。有了这个,你总体上得到5.33纳秒/操作,对于x124的特殊情况得到4.95纳秒/操作。(直接方法不适用于这里;它适用于你知道指数在编译时的情况并直接调用特定例程的情况。这只有在Go中将指数运算符作为运算符才可能发生。)
使用二进制幂算法进行幂运算的通用解决方案如下。我建议你将其纳入内部循环。
// 使用二进制幂算法计算ab
// 请参阅唐纳德·克努特斯的《计算机程序设计艺术》,第2卷,第4.6.3节
func PowerBinary(a float64, b int) (p float64) {
for p = 1; b > 0; b >>= 1 {
if b&1 != 0 {
p *= a
}
a *= a
}
return
}
这个技巧版本,早在很久以前就被决定为“问题的重要性和节省2-3纳秒/调用”,看起来像这样...
// PowerM124计算x124,需要9次乘法(版本311 of 315)
func PowerM124(x1 float64) float64 {
x2 := x1 * x1
x3 := x2 * x1
x6 := x3 * x3
x7 := x6 * x1
x12 := x6 * x6
x19 := x12 * x7
x31 := x19 * x12
x62 := x31 * x31
x124 := x62 * x62
return x124
}
...并有一个伴随调度器...
// PowerM计算xy使用最少的乘法运算
func PowerM(x float64, y int) float64 {
if 1 <= y && y <= 256 {
return callPowerM y
}
return math.Pow(x, float64(y))
}
var callPowerM = []func(float64) float64{
nil,
PowerM1,
PowerM2,
PowerM3,
PowerM4,
PowerM5,
PowerM6,
PowerM7,
PowerM8,
...
如果这个决定以后改变,我将拥有所有范围内的2到256次方的最佳代码和生成它们的程序。我在这里的建议只是精确地按照上面显示的方式使用二进制幂算法。它的舍入误差和其他方面都很好。
ulydmbyx6#
亲爱的@martisch,
是的,如果我们选择AST硬编码方式,那么对于其他
go
工具(如调试等)来说也是不清晰的。正如我所理解的,你也同意这一点:“我们没有那种优化的默认方式”。
亲爱的@MichaelTJones,
我同意任何优化。正如我所理解的,我们可以使用你的设计来为
[-256 , -1]
进行一些小的修改。如果你愿意的话,你可以准备一个带有你的设计的PR来进行详细的分析。关于当前函数
math.Pow
的设计,我们有这样一个部分:我认为我们也可以优化这个部分,例如在
switch
之后添加:但是我不知道如何将
n
转换为r
。0tdrvxhp7#
```
/cc @rsc (作为数学的所有者)
```
sh7euo9m8#
请注意,当前的
Pow(x, y)
实现(包括整数 y 输入)已经有一个开放的问题 #25270,因为它没有进行足够高精度的中间计算。标准库函数应该在优化速度之前确保准确性。此外,我认为大多数建议的速度提升是由于避免了Frexp
和Ldexp
调用,这些调用在原始代码中可能是不必要的。u0njafvf9#
大家好,
这个优化的当前状态是什么?
我的最后一条评论是在2019年,我不确定为什么Pow的不精确性证明了我们无法实际上提高其速度,而不影响其精度。
我复制了基准测试,似乎在1.21.4版本中,
a*a
和Pow(a, 2)
之间仍然存在巨大的差距。也许我做的基准测试是错误的,但我不明白为什么。