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

Question

通常我使用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在他的回答中所写，算术版本现在更快。我还将使用较新的编译器版本进行测试。

Answer 1

如果是，即使现在不是。
您的方法存在一些问题:

您正在使用go1.6.2，它是发布的over 4 years ago

您正在运行的二进制文件会执行其他操作，并且只运行一次

您是，期望对有符号整数的位移位和算术运算是相同的，但它们不是

将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

即使那样，所有这些也必须花很多精力:生成的代码将在很大程度上取决于其他情况以及如何使用结果。
但是基本规则适用:在执行算术运算时，类型很重要。位移位运算符不关心符号。