通常我使用C语言编程,并且经常使用按位运算符,因为它们速度更快。现在,我在使用按位运算符或除法和取模时解决了Euler问题14,从而遇到了这种时序差异。该程序使用go version go1.6.2
编译。
带按位运算符的版本:
package main
import (
"fmt"
)
func main() {
var buf, longest, cnt, longest_start int
for i:=2; i<1e6; i++ {
buf = i
cnt = 0
for buf > 1 {
if (buf & 0x01) == 0 {
buf >>= 1
} else {
buf = buf * 3 + 1
}
cnt++
}
if cnt > longest {
longest = cnt
longest_start = i
}
}
fmt.Println(longest_start)
}
执行程序:time ./prob14
837799
real 0m0.300s
user 0m0.301s
sys 0m0.000s
没有按位运算符的版本(用& 0x01
替换% 2
,用>>= 1
替换/=2
): for buf > 1 {
if (buf % 2) == 0 {
buf /= 2
} else {
buf = buf * 3 + 1
}
cnt++
}
执行程序:$ time ./prob14
837799
real 0m0.273s
user 0m0.274s
sys 0m0.000s
为什么Go中按位运算符的版本变慢?(我也用C语言创建了一个解决方案。这是具有按位运算符的版本,它没有优化标志就可以更快地运行(与-O3相等)。)
编辑
我做了评论中建议的基准测试。
package main
import (
"testing"
)
func Colatz(num int) {
cnt := 0
buf := num
for buf > 1 {
if (buf % 2) == 0 {
buf /= 2
} else {
buf = buf * 3 + 1
}
cnt++
}
}
func ColatzBitwise(num int) {
cnt := 0
buf := num
for buf > 1 {
if (buf & 0x01) == 0 {
buf >>= 1
} else {
buf = buf * 3 + 1
}
cnt++
}
}
func BenchmarkColatz(b *testing.B) {
for i:=0; i<b.N; i++ {
Colatz(837799)
}
}
func BenchmarkColatzBitwise(b *testing.B) {
for i:=0; i<b.N; i++ {
ColatzBitwise(837799)
}
}
以下是基准测试结果:go test -bench=.
PASS
BenchmarkColatz-8 2000000 650 ns/op
BenchmarkColatzBitwise-8 2000000 609 ns/op
事实证明,按位版本在基准测试中更快。编辑2
我将函数中所有变量的类型更改为
uint
。这是基准:go test -bench=.
PASS
BenchmarkColatz-8 3000000 516 ns/op
BenchmarkColatzBitwise-8 3000000 590 ns/op
正如Marc在他的回答中所写,算术版本现在更快。我还将使用较新的编译器版本进行测试。
最佳答案
如果是,即使现在不是。
您的方法存在一些问题:
将go1.15与微基准测试结合使用将显示按位运算的速度更快。这主要是因为有符号整数的逐位移位和除以绝对不相同:逐位移位并不关心符号,但除法必须保留它。
如果您想要更接近等效值,请对算术运算使用无符号整数,编译器可以将其优化为单个移位。
在我的机器上的go1.15中,我看到针对每种除法类型生成以下内容:
buf >>=1
:MOVQ AX, DX
SARQ $1, AX
带buf /= 2
的var buf int
:MOVQ AX, DX
SHRQ $63, AX
ADDQ DX, AX
SARQ $1, AX
带buf /= 2
的var buf uint
:MOVQ CX, BX
SHRQ $1, CX
即使那样,所有这些也必须花很多精力:生成的代码将在很大程度上取决于其他情况以及如何使用结果。但是基本规则适用:在执行算术运算时,类型很重要。位移位运算符不关心符号。
关于go - 为什么Go中的位运算符比除法和模运算慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63408688/