为什么 Go 中的按位运算符比除法和取模慢？

Question

通常我用 C 语言编程并经常使用按位运算符，因为它们更快。现在，我在使用按位运算符或除法和取模解决 Project Euler Problem 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

正如马克在他的回答中所写，算术版本现在更快了。我还将使用较新的编译器版本进行测试。

Answer 1

如果曾经是的话，现在就不是了。

您的方法存在一些问题：

• 您正在使用4 年前发布的go1.6.2
• 你正在运行一个可执行其他操作的二进制文件，并且只运行一次
• 您期望有符号整数上的位移和算术运算相同，但它们不是

将 go1.15 与微基准一起使用将显示按位运算更快。这样做的主要原因是，对于有符号整数，按位移位和除以 2 绝对不同：按位移位不关心符号，但除法必须保留它。

如果您想要更接近等效的值，请使用无符号整数进行算术运算，编译器可能会将其优化为单个位移位。

在我的机器上的 go1.15 中，我看到每种类型的除以 2 生成了以下内容：

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

即便如此，所有这一切都必须持保留态度：生成的代码将在很大程度上取决于其他正在发生的事情以及结果的使用方式。

但基本规则适用：在执行算术运算时，类型非常重要。位移位运算符不关心符号。