我最近在exercism.io上启动了Go跟踪,并很高兴优化“ n素数”计算。其实我遇到了一个有趣的事实,我无法解释。想象以下代码:
// Package prime provides ...
package prime
// Nth function checks for the prime number on position n
func Nth(n int) (int, bool) {
if n <= 0 {
return 0, false
}
if (n == 1) {
return 2, true
}
currentNumber := 1
primeCounter := 1
for n > primeCounter {
currentNumber+=2
if isPrime(currentNumber) {
primeCounter++
}
}
return currentNumber, primeCounter==n
}
// isPrime function checks if a number
// is a prime number
func isPrime(n int) bool {
//useless because never triggered but makes it faster??
if n < 2 {
println("n < 2")
return false
}
//useless because never triggered but makes it faster??
if n%2 == 0 {
println("n%2")
return n==2
}
for i := 3; i*i <= n; i+=2 {
if n%i == 0 {
return false
}
}
return true
}
在私有函数isPrime
中,我有两个从未触发的初始if语句,因为我只给出大于2的不均匀数。基准返回如下:
Running tool: /usr/bin/go test -benchmem -run=^$ -bench ^(BenchmarkNth)$
BenchmarkNth-8 100 18114825 ns/op 0 B/op 0
如果删除永不触发的if语句,则基准测试会变慢:
Running tool: /usr/bin/go test -benchmem -run=^$ -bench ^(BenchmarkNth)$
BenchmarkNth-8 50 21880749 ns/op 0 B/op 0
我已经多次运行基准测试来回更改代码,总是获得或多或少相同的数字,我想不出为什么这两个if语句应该使执行速度更快的原因。是的,它是微优化,但我想知道:为什么?
这里是来自练习的完整练习,并带有测试用例:nth-prime
我正在使用的Go版本是manjaro i3 linux上的1.12.1 linux / amd64
发生了什么,当添加那些if时,可以保证编译器具有一些关于输入的断言。如果取消了这些断言,则编译器必须自己添加它。它的实现方式是在每次迭代时对其进行验证。我们可以看一下汇编代码来证明这一点。 (通过将-gcflags=-S
传递到go test
命令)
带有if的:
0x004b 00075 (func.go:16) JMP 81
0x004d 00077 (func.go:16) LEAQ 2(BX), AX
0x0051 00081 (func.go:16) MOVQ AX, DX
0x0054 00084 (func.go:16) IMULQ AX, AX
0x0058 00088 (func.go:16) CMPQ AX, CX
0x005b 00091 (func.go:16) JGT 133
0x005d 00093 (func.go:17) TESTQ DX, DX
0x0060 00096 (func.go:17) JEQ 257
0x0066 00102 (func.go:17) MOVQ CX, AX
0x0069 00105 (func.go:17) MOVQ DX, BX
0x006c 00108 (func.go:17) CQO
0x006e 00110 (func.go:17) IDIVQ BX
0x0071 00113 (func.go:17) TESTQ DX, DX
0x0074 00116 (func.go:17) JNE 77
没有if的情况:
0x0016 00022 (func.go:16) JMP 28
0x0018 00024 (func.go:16) LEAQ 2(BX), AX
0x001c 00028 (func.go:16) MOVQ AX, DX
0x001f 00031 (func.go:16) IMULQ AX, AX
0x0023 00035 (func.go:16) CMPQ AX, CX
0x0026 00038 (func.go:16) JGT 88
0x0028 00040 (func.go:17) TESTQ DX, DX
0x002b 00043 (func.go:17) JEQ 102
0x002d 00045 (func.go:17) MOVQ CX, AX
0x0030 00048 (func.go:17) MOVQ DX, BX
0x0033 00051 (func.go:17) CMPQ BX, $-1
0x0037 00055 (func.go:17) JEQ 64
0x0039 00057 (func.go:17) CQO
0x003b 00059 (func.go:17) IDIVQ BX
0x003e 00062 (func.go:17) JMP 69
0x0040 00064 func.go:17) NEGQ AX
0x0043 00067 (func.go:17) XORL DX, DX
0x0045 00069 (func.go:17) TESTQ DX, DX
0x0048 00072 (func.go:17) JNE 24
汇编代码0x0033 00051 (func.go:17) CMPQ BX, $-1
中的第51行是罪魁祸首。
第16行,for i := 3; i*i <= n; i+=2
,在原始Go代码中,两种情况下的翻译相同。但是运行每个迭代的第17行if n%i == 0
会编译为更多指令,因此,CPU总共需要进行更多工作。
通过确保循环不会接收到encoding/base64
值,在nil
程序包中有些类似的东西。您可以在这里看看:https://go-review.googlesource.com/c/go/+/151158/3/src/encoding/base64/base64.go此检查是有意添加的。在您的情况下,您不小心对其进行了优化:)