go 数学:Pow(x,y)优化情况:常数整数y,

9cbw7uwe  于 4个月前  发布在  Go
关注(0)|答案(9)|浏览(41)

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不是正确的地方)。

xqk2d5yq

xqk2d5yq1#

https://golang.org/cl/155921提到了这个问题:math: Pow(x,y) optimization for cases: constant integer y .

ylamdve6

ylamdve62#

请注意,对于:

func BenchmarkInline(b *testing.B) {
        x := 42.0
        for i := 0; i < b.N; i++ {
                _ = x * x
        }
}

较新的Go Gc编译器足够智能,可以推断出循环体计算从未使用过,并优化掉循环体。因此,这可能是对空循环的基准测试。
https://godbolt.org/z/ot9w2G
为了避免一些与死代码消除和常量折叠代码相关的问题,可以使用以下代码:

var Sink float64
var x = 42.0

func BenchmarkInline(b *testing.B) {
        for i := 0; i < b.N; i++ {
                Sink = x * x
        }
}

https://godbolt.org/z/Nt9OWg
有关优化的一些问题:

  • 对于较大的常数y,基准测试数字有何比较?
  • 对于较大的常数y与当前实现相比,是否有精度损失?

我认为在AST级别重写为 x*x 并不值得。我预计需要提高速度的程序员已经使用了更简单、更快的 x*x 版本,而不是math.Pow。它还会产生一个不良副作用,即复制数学代码,导致速度变慢。通常,这些特定于包的重写优化应避免在编译器中进行,如果可能的话,应由与代码模式相匹配的一般优化来覆盖。或者,这些特殊情况可以通过函数中的if语句来覆盖,随着内联改进和常量传播的提高,将减少当前和未来的开销。

3mpgtkmj

3mpgtkmj3#

亲爱的@martisch,

在我笔记本电脑上将BenchmarkInline更改为go1.11.4后,结果仍然是0.7...1.03 ns/op。所以我进行了检查。

关于您的问题:

  • 在我的有限元(FE)建模实践中,我使用y = 2y = 3。在gonum的实践中:y=7...所以值不大,所以我检查了y= -127...127 -这对我的任务来说已经足够了。如果在我的任务中需要更多,那么在批准代码设计后,您可以修改更多的y值。
  • 目前math.Pow的实现和那个PR具有相同的结果。

我同意您的观点,如果是y > 3,但对于y = 2y = 3的情况,我自己是可以接受的。
现在,我发现对于数学库中的常量没有优化,例如,如果我们有这样的代码:

a := math.Max(b,12.7)

就不需要在函数math.Max中进行所有的y检查。

az31mfrm

az31mfrm4#

在我的笔记本电脑上,将BenchmarkInline更改为go1.11.4中您示例中的值后,结果相同。
当前math.Pow的实现和那个PR具有相同的结果。
感谢您的检查和澄清。
不需要在函数math.Max中检查所有y。
是的,编译器具有更好的内联支持,通常可以确定这一点(也超出了数学包的范围),并且只使用和内联相关的检查。这在字符串包中也有帮助,例如使用字符串计算长度为1的计数。在一般情况下,这可以更好地处理,而无需硬编码AST优化。

8aqjt8rx

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纳秒/操作,对于x
124的情况为7.08纳秒/操作。
由我的程序生成的一组自动生成的神奇最优幂树(以及克努特斯、许多人的其他作品)。有了这个,你总体上得到5.33纳秒/操作,对于x124的特殊情况得到4.95纳秒/操作。(直接方法不适用于这里;它适用于你知道指数在编译时的情况并直接调用特定例程的情况。这只有在Go中将指数运算符作为运算符才可能发生。)
使用二进制幂算法进行幂运算的通用解决方案如下。我建议你将其纳入内部循环。
// 使用二进制幂算法计算a
b
// 请参阅唐纳德·克努特斯的《计算机程序设计艺术》,第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计算x
y使用最少的乘法运算
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次方的最佳代码和生成它们的程序。我在这里的建议只是精确地按照上面显示的方式使用二进制幂算法。它的舍入误差和其他方面都很好。

ulydmbyx

ulydmbyx6#

亲爱的@martisch,
是的,如果我们选择AST硬编码方式,那么对于其他go工具(如调试等)来说也是不清晰的。
正如我所理解的,你也同意这一点:“我们没有那种优化的默认方式”。
亲爱的@MichaelTJones,
我同意任何优化。正如我所理解的,我们可以使用你的设计来为[-256 , -1]进行一些小的修改。如果你愿意的话,你可以准备一个带有你的设计的PR来进行详细的分析。
关于当前函数math.Pow的设计,我们有这样一个部分:

...
 	case y == 0.5:
 		return Sqrt(x)
 	case y == -0.5:
 		return 1 / Sqrt(x)
...

我认为我们也可以优化这个部分,例如在switch之后添加:

// optimization for cases:
// y = 1/(2^r) , where integer value r = 1 ... 127 ...
if n := int8(1.0/y); n%2 == 0 && float64(n) == 1.0/y{
   // we have 
   // y = 0.5      n = 2
   // y = 0.25     n = 4
   // ...

   // convert `n` to `r` if possible. if not possible then default alorithm(example n = 6, y=0.16666... it is not 1/(2^r))

   // calculation
   result := x
   for i:= 0;i<r;i++{
      result = math.Sqrt(result)
   }
   return result
}

但是我不知道如何将n转换为r

0tdrvxhp

0tdrvxhp7#

```
/cc @rsc (作为数学的所有者)
```

sh7euo9m

sh7euo9m8#

请注意,当前的 Pow(x, y) 实现(包括整数 y 输入)已经有一个开放的问题 #25270,因为它没有进行足够高精度的中间计算。标准库函数应该在优化速度之前确保准确性。此外,我认为大多数建议的速度提升是由于避免了 FrexpLdexp 调用,这些调用在原始代码中可能是不必要的。

u0njafvf

u0njafvf9#

大家好,
这个优化的当前状态是什么?
我的最后一条评论是在2019年,我不确定为什么Pow的不精确性证明了我们无法实际上提高其速度,而不影响其精度。
我复制了基准测试,似乎在1.21.4版本中,a*aPow(a, 2)之间仍然存在巨大的差距。
也许我做的基准测试是错误的,但我不明白为什么。

package main

import (
	"fmt"
	"math"
	"time"
)

func compute_square_with_pow(a float64) float64 {
	return math.Pow(a, 2)
}

func compute_square(a float64) float64 {
	return a * a
}

func main() {
	length := 1000000000 // Adjust the length as needed for your benchmark

	// Benchmark compute_square_with_pow
	start := time.Now()
	for i := 0; i < length; i++ {
		compute_square_with_pow(2.5)
	}
	durationWithPow := time.Since(start)
	fmt.Printf("compute_square_with_pow took %v\n", durationWithPow)

	// Benchmark compute_square
	start = time.Now()
	for i := 0; i < length; i++ {
		compute_square(2.5)
	}
	duration := time.Since(start)
	fmt.Printf("compute_square took %v\n", duration)

	// Comparing the results and calculating relative difference
	var relativeDifference float64
	if duration < durationWithPow {
		absoluteDifference := durationWithPow - duration
		relativeDifference = (absoluteDifference.Seconds() / durationWithPow.Seconds()) * 100
		fmt.Printf("Direct multiplication is faster by %v (relative difference: %.2f%%)\n", absoluteDifference, relativeDifference)
	} else if duration > durationWithPow {
		absoluteDifference := duration - durationWithPow
		relativeDifference = (absoluteDifference.Seconds() / duration.Seconds()) * 100
		fmt.Printf("math.Pow is faster by %v (relative difference: %.2f%%)\n", absoluteDifference, relativeDifference)
	} else {
		fmt.Println("Both methods took the same amount of time")
	}
}
go run test/basics/power_optimisation.go 
compute_square_with_pow took 11.365080585s
compute_square took 193.561528ms
Direct multiplication is faster by 11.171519057s (relative difference: 98.30%)

相关问题