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

Question

通常我用 C 编程并经常使用按位运算符，因为它们速度更快。现在，我在使用按位运算符或除法和模运算时解决欧拉计划问题 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 在他的回答中所写，算术版本现在更快了。我还将使用较新的编译器版本进行测试。

Answer 1

如果他们曾经是，他们现在不是。

您的方法存在一些问题：

您使用的是 发布的 go1.6.2 over 4 years ago
你是运行一个可以做其他事情的 二进制文件运行它只做一次
您希望有符号整数的位移和算术运算相同，但它们不是

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

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

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

buf >>=1:

MOVQ AX, DX
SARQ , AX

buf /= 2 与 var buf int:

MOVQ AX, DX         
SHRQ , AX            
ADDQ DX, AX         
SARQ , AX

buf /= 2 与 var buf uint:

MOVQ CX, BX
SHRQ , CX

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

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

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

Why are bitwise operators slower than division and modulo in Go?

go

bitwise-operators