边界检查
大家都知道Golang是内存安全型语言,在根据索引获取数组/切片元素时,Golang runtime 会检查索引是否超出范围,如果索引超出了范围,程序就会 panic,这种机制叫做边界检查(bounds check)。边界检查保障了代码的安全运行,但是也会导致代码运行速度稍慢一些。
Golang从1.7开始,Go编译器引入了SSA(static single-assignment form式)特性,SSA帮助Go编译器有效地使用像BCE(bounds check elimination)和CSE(common subexpression elimination)这样的优化。BCE可以避免一些不必要的边界检查,CSE可以避免一些重复的计算,这样标准的Go编译器就可以编译出更高效的程序,在有些场景下这些优化效果提升十分明显。
编译程序时可以使用 -gcflags="-d=ssa/check_bce" 参数来显示哪行代码需要边界检查。
边界检查消除例1
先看个例子:
// main.go
package main
func f1(s []int) {
_ = s[0] // 第5行
_ = s[1] // 第6行
_ = s[2] // 第7行
}
func f2(s []int) {
_ = s[2] // 第11行
_ = s[1] // 第12行
_ = s[0] // 第13行
}
func f3(s []int, index int) {
_ = s[index] // 第17行
_ = s[index] // 第18行
}
func f4(a [5]int) {
_ = a[4] // 第22行
}
func main() {}
编译看下效果
$ go run -gcflags="-d=ssa/check_bce" main.go
# command-line-arguments
./main.go:4:7: Found IsInBounds
./main.go:5:7: Found IsInBounds
./main.go:6:7: Found IsInBounds
./main.go:10:7: Found IsInBounds
./main.go:16:7: Found IsInBounds
函数f1中三行都进行了边界检查,因为第5行的边界检查不能保证第6行和第7行是安全的,第6行的边界检查不能保证第7行是安全的。
函数f2中第12行和第13行不需要进行边界检查,因为第11行的边界检查确保了第12行和第13行的索引不会超出范围。
函数f3,如果第一个s[index]是安全的,编译器就知道第二个s[index]肯定是安全的。
函数f4中代码也不需要安全检查,因为数组长度是5,取索引为4的数据肯定是安全的。
如果泛型函数中的操作涉及类型参数,并且泛型函数从未实例化,编译器则不会执行边界检查。例如:
// main.go
package main
func foo[E any](s []E) {
_ = s[0] // line 5
_ = s[1] // line 6
_ = s[2] // line 7
}
// var _ = foo[bool]
func main() {
}
如果注释行打开的情况下,就会进行边界检查
$ go run -gcflags="-d=ssa/check_bce" main.go
./main.go:5:7: Found IsInBounds
./main.go:6:7: Found IsInBounds
./main.go:7:7: Found IsInBounds
./main.go:10:9: Found IsInBounds
边界检查消除例2
这个例子中都不会进行边界检查:
// main.go
package main
func f5(s []int) {
for i := range s {
_ = s[i]
_ = s[i:len(s)]
_ = s[:i+1]
}
}
func f6(s []int) {
for i := 0; i < len(s); i++ {
_ = s[i]
_ = s[i:len(s)]
_ = s[:i+1]
}
}
func f7(s []int) {
for i := len(s) - 1; i >= 0; i-- {
_ = s[i]
_ = s[i:len(s)]
}
}
func f8(s []int, index int) {
if index >= 0 && index < len(s) {
_ = s[index]
_ = s[index:len(s)]
}
}
func f9(s []int) {
if len(s) > 2 {
_, _, _ = s[0], s[1], s[2]
}
}
func main() {}
边界检查消除例3
// main.go
package main
import "math/rand"
func fa() {
s := []int{0, 1, 2, 3, 4, 5, 6}
index := rand.Intn(7)
_ = s[:index] // line 9: bounds check
_ = s[index:] // line 10: bounds check eliminated!
}
func fb(s []int, i int) {
_ = s[:i] // line 14: bounds check
_ = s[i:] // line 15: bounds check, not smart enough?
}
func fc() {
s := []int{0, 1, 2, 3, 4, 5, 6}
s = s[:4]
i := rand.Intn(7)
_ = s[:i] // line 22: bounds check
_ = s[i:] // line 23: bounds check, not smart enough?
}
func main() {}
编译看下效果
$ go run -gcflags="-d=ssa/check_bce" main.go
./main.go:9: Found IsSliceInBounds
./main.go:14: Found IsSliceInBounds
./main.go:15: Found IsSliceInBounds
./main.go:22: Found IsSliceInBounds
./main.go:23: Found IsSliceInBounds
为什么第10行是安全的,而第15行和第23行不是呢?是因为子切片表达式中的起始索引可能比切片的长度大。看一个简单的例子:
package main
func main() {
s0 := make([]int, 5, 10) // len(s0) == 5, cap(s0) == 10
index := 8
// In Go, for the subslice syntax s[a:b],
// the relations 0 <= a <= b <= cap(s) must
// be ensured to avoid panicking.
_ = s0[:index]
// The above line is safe can't ensure the
// following line is also safe. In fact, the
// following line will panic, for the starting
// index is larger than the end index.
_ = s0[index:] // panic
}
因此,如果s[:index]是安全的,那么s[index:]也是安全的,只有当len(s)等于cap(s)时才正确。这就是示例3中的函数fb和fc中的代码行仍然需要进行边界检查的原因。
边界检查消除例4
// main.go
package main
import "math/rand"
func fb2(s []int, index int) {
_ = s[index:] // line 7: bounds check
_ = s[:index] // line 8: bounds check eliminated!
}
func fc2() {
s := []int{0, 1, 2, 3, 4, 5, 6}
s = s[:4]
index := rand.Intn(7)
_ = s[index:] // line 15 bounds check
_ = s[:index] // line 16: bounds check eliminated!
}
func main() {}
编译看下效果
$ go run -gcflags="-d=ssa/check_bce" main.go
./main.go:7:7: Found IsSliceInBounds
./main.go:15:7: Found IsSliceInBounds
在这个例子中,如果函数fb2中第7行是安全的,会得出第8行也是安全的。如果函数fc2中第15行是安全的,那么第16行也是安全的。
边界检查消除例5
目前Go编译器还没有智能到可以消除所有不必要的边界检查。有时,可以做一些提示来帮助编译器消除一些不必要的边界检查。
// main.go
package main
func fd(is []int, bs []byte) {
if len(is) >= 256 {
for _, n := range bs {
_ = is[n] // line 7: bounds check
}
}
}
func fd2(is []int, bs []byte) {
if len(is) >= 256 {
is = is[:256] // line 14: a hint
for _, n := range bs {
_ = is[n] // line 16: BCEed!
}
}
}
func main() {}
编译看下效果
$ go run -gcflags="-d=ssa/check_bce" main.go
./main.go:7: Found IsInBounds
小结
Go编译器关于BCE优化不止上面几个示例展示这些,更多的需要自己去探索。
参考资料
Bounds Check Elimination https://go101.org/article/bounds-check-elimination.html