[譯] Bounds Check Elimination 邊界檢查消除
Go 是一種內存安全的語言，在針對數組 (array) 或 Slice 做索引和切片操作時，Go 的運行時（runtime）會檢查所涉及的索引是否超出范圍。如果索引超出范圍，將產生一個 Panic，以防止無效索引造成的傷害。這就是邊界檢查（BCE）。邊界檢查使我們的代碼能夠安全地運行，但也會影響一定的性能。
原文鏈接：
Bounds Check Elimination
自從 Go Toolchain 1.7 以后，標準的 Go 編譯器采用了一個基于 SSA (靜態單賦值形式)的新的編譯器后端。SSA 幫助 Go 編譯器有效地進行代碼優化，比如 BCE (邊界檢查消除) 和 CSE (公共子表達式消除)。BCE 可以避免一些不必要的邊界檢查，CSE 可以避免一些重復的計算，如此使得標準的 Go 編譯器可以生成更高效的程序。有時這些優化的改進效果是顯而易見的。
本文將列出一些示例，說明 BCE 如何與標準的 Go 編譯器1.7 + 協同工作。
對于 Go Toolchain 1.7 + ，我們可以使用 -gcflags = “-d=ssa/check _ bce/debug=1”編譯器標志來顯示哪些代碼行仍然需要進行邊界檢查。
例 1
// example1.go
package mainfunc f1(s []int) {_ = s[0] // line 5: 需要邊界檢查_ = s[1] // line 6: 需要邊界檢查_ = s[2] // line 7: 需要邊界檢查
}func f2(s []int) {_ = s[2] // line 11: 需要邊界檢查_ = s[1] // line 12: 邊界檢查被消除_ = s[0] // line 13: 邊界檢查被消除
}func f3(s []int, index int) {_ = s[index] // line 17: 需要邊界檢查_ = s[index] // line 18: 邊界檢查被消除
}func f4(a [5]int) {_ = a[4] // line 22: 邊界檢查被消除
}func main() {}
$ go run -gcflags="-d=ssa/check_bce/debug=1" example1.go
./example1.go:5: Found IsInBounds
./example1.go:6: Found IsInBounds
./example1.go:7: Found IsInBounds
./example1.go:11: Found IsInBounds
./example1.go:17: Found IsInBounds
我們可以看到，沒有必要為函數 f2 中的第 12 行和第 13 行進行邊界檢查，因為第 11 行的邊界檢查確保了第 12 行和第 13 行的索引不會超出范圍。
但在函數 f1 中，必須對這三行都進行邊界檢查。因為第 5 行的邊界檢查不能保證第六行和第七行的安全，同樣第六行的檢查也不能保證第七行的安全。
而對于函數 f3，編譯器知道如果第一個 s [ index ] 是安全的，那么第二個 s [ index ] 就也是絕對安全的。
編譯器還能正確地判斷出 f4 中的唯一一行（22行）是安全的。
例 2
// example2.go
package mainfunc 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() {}
$ go run -gcflags="-d=ssa/check_bce/debug=1" example2.go
酷! 標準編譯器刪除程序中的所有綁定檢查。
注意: 在 Go Toolchain 1.11 版本之前，標準編譯器不夠智能，無法檢測到第22行是安全的。
例3
// example3.go
package mainimport "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/debug=1" example3.go
./example3.go:9: Found IsSliceInBounds
./example3.go:14: Found IsSliceInBounds
./example3.go:15: Found IsSliceInBounds
./example3.go:22: Found IsSliceInBounds
./example3.go:23: Found IsSliceInBounds
哦，這么多地方還需要做邊界檢查！
但是，為什么標準的 Go 編譯器認為第 10 行是安全的，而第 15 行和第 23 行卻不是呢？編譯器還不夠聰明嗎？
事實上，編譯器設計如此！為什么？原因是子切片表達式中的起始索引可能大于原始切片的長度。讓我們看一個簡單的例子:
package mainfunc main() {s0 := make([]int, 5, 10) // len(s0) == 5, cap(s0) == 10index := 8// 在 go 中，對于子切片語法 s[a:b] 必須保證 0 <= a <= b <= cap(s)// 否則會引起 panic_ = s0[:index]// 上面一行是安全的，但不能保證下面一行也是安全的// 事實上，下面一行將會導致 panic_ = s0[index:] // panic
}
因此，只有滿足 len(s) == cap(s) 時，才能根據 s[:index] 是安全的得出 s[index:] 也是安全地的結論，這就是為什么函數 fb 和 fc 中的代碼行仍然需要進行邊界檢查的原因。
標準 Go 編譯器成功地檢測到函數 fa 中的 len (s) 等于 cap (s) 干得好! Go團隊加油！
例4
// example4.go
package mainimport "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/debug=1" example4.go
./example4.go:7:7: Found IsSliceInBounds
./example4.go:15:7: Found IsSliceInBounds
在這個例子中，go 編譯器成功推斷出：
- 如果第 7 行是安全的，那么第 8 行也是安全地
- 如果第 15 行是安全的，那么第 16 行也是安全地
注意:在1.9版本之前的 Go Toolchain 中，標準的 Go 編譯器無法檢測到第 8 行不需要邊界檢查。
例 5
當前版本的標準 Go 編譯器不夠聰明，無法消除所有不必要的邊界檢查。有時，我們可以做一些提示來幫助編譯器消除一些不必要的邊界檢查.
// example5.go
package mainfunc 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 hintfor _, n := range bs {_ = is[n] // line 16: BCEed!}}
}func fe(isa []int, isb []int) {if len(isa) > 0xFFF {for _, n := range isb {_ = isa[n & 0xFFF] // line 24: bounds check}}
}func fe2(isa []int, isb []int) {if len(isa) > 0xFFF {isa = isa[:0xFFF+1] // line 31: a hintfor _, n := range isb {_ = isa[n & 0xFFF] // line 33: BCEed!}}
}func main() {}
$ go run -gcflags="-d=ssa/check_bce/debug=1" example5.go
./example5.go:7: Found IsInBounds
./example5.go:24: Found IsInBounds
核心的思想就是盡量消除在循環中的邊界檢查，這個例子有點奇怪，可以看下面這個：
// example4.go package mainfunc bad(a, b []int64, n int) {if len(a) >= n && len(b) >= n {for i, v := range b {a[i] = v}} }func good(a, b []int64, n int) {if len(a) >= n && len(b) >= n {a = a[:n]b = b[:n]for i, v := range b {a[i] = v}} }func main() {}$ go run -gcflags="-d=ssa/check_bce/debug=1" .\example2.go # command-line-arguments .\example2.go:7:5: Found IsInBounds .\example2.go:14:8: Found IsSliceInBounds通過 14 15 行的子切片操作，我們可以把邊界檢查放到循環之外，簡單跑一下 Benchmark 差距還是挺明顯的
cpu: Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz BenchmarkBCE BenchmarkBCE/good BenchmarkBCE/good-4 296671 4912 ns/op BenchmarkBCE/bad BenchmarkBCE/bad-4 182302 6136 ns/op PASS
摘要
標準的 Go 編譯器進行了更多的 BCE 優化。它們可能不像上面列出的那么明顯，所以本文不會全部展示。
盡管標準 Go 編譯器中的 BCE 特性仍然不夠完美，但對于許多常見情況來說，它確實做得很好。毫無疑問，標準的 Go 編譯器在以后的版本中會做得更好，這樣上面第5個例子中的提示可能就沒有必要了。謝謝團隊增加了這個美妙的功能！
參考文獻
- Bounds Check Elimination
- Utilizing the Go 1.7 SSA Compiler (and the second part)
