边界检查消除

    从Go SDK 1.7开始，官方标准编译器使用了一个新的基于SSA（single-assignment form，静态单赋值形式）的后端。SSA使得Go编译器可以有效利用诸如BCE（bounds check elimination，边界检查消除）和（common subexpression elimination，公共子表达式消除）等优化。BCE可以避免很多不必要的边界检查，CSE可以避免很多重复表达式的计算，从而使得编译器编译出的程序执行效率更高。有时候这些优化的效果非常明显。

    本文将展示一些例子来解释边界检查消除在官方标准编译器1.7+中的表现。

    对于Go SDK 1.7+，我们可以运行来列出哪些代码行仍然需要边界检查。

    1. $ go build -gcflags="-d=ssa/check_bce/debug=1" example1.go
    2. ./example1.go:5: Found IsInBounds
    3. ./example1.go:6: Found IsInBounds
    4. ./example1.go:7: Found IsInBounds
    5. ./example1.go:11: Found IsInBounds
    6. ./example1.go:17: Found IsInBounds

    我们可以看到函数f2中的第12行和第13行不再需要边界检查了，因为第11行的检查确保了第12行和第13行中使用的下标肯定不会越界。

    但是，函数f1中的三行仍然都需要边界检查，因为第5行中的边界检查不能保证第6行和第7行中的下标没有越界，第6行中的边界检查也不能保证第第7行中的下标没有越界。

    在函数f3中，编译器知道如果第一个s[index]是安全的，则第二个s[index]是无需边界检查的。

    例子2

    1. // example2.go
    2. package main
    4. func f5(s []int) {
    5.     for i := range s {
    6.         _ = s[i]
    7.         _ = s[i:len(s)]
    8.         _ = s[:i+1]
    9.     }
    10. }
    12. func f6(s []int) {
    13.     for i := 0; i < len(s); i++ {
    14.         _ = s[i]
    15.         _ = s[i:len(s)]
    16.         _ = s[:i+1]
    17.     }
    18. }
    20. func f7(s []int) {
    21.     for i := len(s) - 1; i >= 0; i-- {
    22.         _ = s[i]
    23.         _ = s[i:len(s)]
    24.     }
    26. func f8(s []int, index int) {
    28.         _ = s[index]
    29.         _ = s[index:len(s)]
    30.     }
    31. }
    33. func f9(s []int) {
    34.     if len(s) > 2 {
    35.         _, _, _ = s[0], s[1], s[2]
    36.     }
    37. }
    39. func main() {}

    酷！官方标准编译器消除了上例程序中的所有边界检查。

    注意：在Go SDK 1.11之前，官方标准编译器没有足够聪明到认为第22行是不需要边界检查的。

    1. // example3.go
    2. package main
    4. import "math/rand"
    6. func fa() {
    7.     s := []int{0, 1, 2, 3, 4, 5, 6}
    8.     index := rand.Intn(7)
    9.     _ = s[:index] // 第9行： 需要边界检查
    10.     _ = s[index:] // 第10行： 边界检查消除了！
    11. }
    13. func fb(s []int, index int) {
    14.     _ = s[:index] // 第14行： 需要边界检查
    15.     _ = s[index:] // 第15行： 需要边界检查（不够智能？）
    16. }
    18. func fc() {
    19.     s := []int{0, 1, 2, 3, 4, 5, 6}
    20.     s = s[:4]
    21.     index := rand.Intn(7)
    22.     _ = s[:index] // 第22行： 需要边界检查
    23. }
    25. func main() {}
    1. $ go build -gcflags="-d=ssa/check_bce/debug=1" example3.go
    3. ./example3.go:14: Found IsSliceInBounds
    4. ./example3.go:15: Found IsSliceInBounds
    5. ./example3.go:22: Found IsSliceInBounds
    6. ./example3.go:23: Found IsSliceInBounds

    噢，仍然有这么多的边界检查！

    但是等等，为什么官方标准编译器认为第10行不需要边界检查，却认为第15和第23行仍旧需要边界检查呢？是标准编译器不够智能吗？

    事实上，这里标准编译器做得对！为什么呢？原因是一个子切片表达式中的起始下标可能会大于基础切片的长度。让我们先看一个简单的使用了子切片的例子：

    所以如果s[:index]是安全的则s[index:]是无需边界检查的这条论述只有在len(s)和cap(s)相等的情况下才正确。这就是为什么函数fb和fc中的代码仍旧需要边界检查的原因。

    例子4

    1. // example4.go
    2. package main
    4. import "math/rand"
    6. func fb2(s []int, index int) {
    7.     _ = s[index:] // 第7行： 需要边界检查
    8.     _ = s[:index] // 第8行： 边界检查消除了！
    9. }
    11. func fc2() {
    12.     s := []int{0, 1, 2, 3, 4, 5, 6}
    13.     s = s[:4]
    14.     index := rand.Intn(7)
    15.     _ = s[index:] // 第15行： 需要边界检查
    16.     _ = s[:index] // 第16行： 边界检查消除了！
    17. }
    19. func main() {}
    1. $ go build -gcflags="-d=ssa/check_bce/debug=1" example4.go
    2. ./example4.go:7:7: Found IsSliceInBounds
    3. ./example4.go:15:7: Found IsSliceInBounds

    在此例子中，标准编译器成功推断出：

    • 在函数fb2中，如果第7行是安全的，则第8行是无需边界检查的；
    • 在函数fc2中，如果第15行是安全的，则第16行是无需边界检查的。 注意：Go SDK 1.9之前中的标准编译器没有出推断出第8行不需要边界检查。

    当前版本的标准编译器并非足够智能到可以消除到一切应该消除的边界检查。有时候，我们需要给标准编译器一些暗示来帮助标准编译器将这些不必要的边界检查消除掉。

    1. $ go build -gcflags="-d=ssa/check_bce/debug=1" example5.go
    2. ./example5.go:7: Found IsInBounds

    总结

    本文上面列出的例子并没有涵盖标准编译器支持的所有边界检查消除的情形。本文列出的仅仅是一些常见的情形。

    尽管标准编译器中的边界检查消除特性依然不是100%完美，但是对很多常见的情形，它确实很有效。自从标准编译器支持此特性以来，在每个版本更新中，此特性都在不断地改进增强。无需质疑，在以后的版本中，标准编译器会更加得智能，以至于上面第5个例子中提供给编译器的暗示有可能将变得不再必要。谢谢Go语言开发团队出色的工作！

    Go语言101项目目前同时托管在Github和上。欢迎各位在这两个项目中通过提交bug和PR的方式来改进完善Go语言101中的各篇文章。

    本书微信公众号名称为"Go 101"。每个工作日此公众号将尽量发表一篇和Go语言相关的原创短文。各位如果感兴趣，可以搜索关注一下。