边界检查消除

Go是一个内存安全的语言。在数组和切片的索引和子切片操作中，Go运行时将检查操作中使用的下标是否越界。 如果下标越界，一个恐慌将产生，以防止这样的操作破坏内存安全。这样的检查称为边界检查。 边界检查使得我们的代码能够安全地运行；但是另一方面，也使得我们的代码运行效率略微降低。

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

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

对于Go官方工具链1.7+，我们可以使用编译器选项-gcflags="-d=ssa/check_bce/debug=1"来列出哪些代码行仍然需要边界检查。

例子1

  1. // example1.go
  2. package main
  4. func f1(s []int) {
  5.     _ = s[0] // 第5行： 需要边界检查
  6.     _ = s[1] // 第6行： 需要边界检查
  7.     _ = s[2] // 第7行： 需要边界检查
  8. }
  10. func f2(s []int) {
  11.     _ = s[2] // 第11行： 需要边界检查
  12.     _ = s[1] // 第12行： 边界检查消除了！
  13.     _ = s[0] // 第13行： 边界检查消除了！
  14. }
  16. func f3(s []int, index int) {
  17.     _ = s[index] // 第17行： 需要边界检查
  18.     _ = s[index] // 第18行： 边界检查消除了！
  19. }
  21. func f4(a [5]int) {
  22.     _ = a[4] // 第22行： 边界检查消除了！
  23. }
  25. func main() {}
  1. $ go run -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]是无需边界检查的。

编译器也正确地认为函数f4中的唯一一行（第22行）是无需边界检查的。

例子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.     }
  25. }
  27. func f8(s []int, index int) {
  28.     if index >= 0 && index < len(s) {
  29.         _ = s[index]
  30.         _ = s[index:len(s)]
  31.     }
  32. }
  34. func f9(s []int) {
  35.     if len(s) > 2 {
  36.         _, _, _ = s[0], s[1], s[2]
  37.     }
  38. }
  40. func main() {}
  1. $ go run -gcflags="-d=ssa/check_bce/debug=1" example2.go

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

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

例子3

  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.     _ = s[index:] // 第23行： 需要边界检查（不够智能？）
  24. }
  26. func main() {}
  1. $ go run -gcflags="-d=ssa/check_bce/debug=1" example3.go
  2. ./example3.go:9: Found IsSliceInBounds
  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行仍旧需要边界检查呢？ 是标准编译器不够智能吗？

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

  1. package main
  3. func main() {
  4.     s0 := make([]int, 5, 10)
  5.     // len(s0) == 5, cap(s0) == 10
  7.     index := 8
  9.     // 在Go中，对于一个子切片表达式s[a:b]，a和b须满足
  10.     // 0 <= a <= b <= cap(s);否则，将产生一个恐慌。
  12.     _ = s0[:index]
  13.     // 上一行是安全的不能保证下一行是无需边界检查的。
  14.     // 事实上，下一行将产生一个恐慌，因为起始下标
  15.     // index大于终止下标（即切片s0的长度）。
  16.     _ = s0[index:] // panic
  17. }

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

标准编译器成功地检测到在函数fa中len(s)和cap(s)是相等的。干得漂亮！Go语言开发团队！

例子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 run -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官方工具链1.9之前中的标准编译器没有出推断出第8行不需要边界检查。

例子5

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

  1. // example5.go
  2. package main
  4. func fd(is []int, bs []byte) {
  5.     if len(is) >= 256 {
  6.         for _, n := range bs {
  7.             _ = is[n] // 第7行： 需要边界检查
  8.         }
  9.     }
  10. }
  12. func fd2(is []int, bs []byte) {
  13.     if len(is) >= 256 {
  14.         is = is[:256] // 第14行： 一个暗示
  15.         for _, n := range bs {
  16.             _ = is[n] // 第16行： 边界检查消除了！
  17.         }
  18.     }
  19. }
  21. func fe(isa []int, isb []int) {
  22.     if len(isa) > 0xFFF {
  23.         for _, n := range isb {
  24.             _ = isa[n & 0xFFF] // 第24行： 需要边界检查
  25.         }
  26.     }
  27. }
  29. func fe2(isa []int, isb []int) {
  30.     if len(isa) > 0xFFF {
  31.         isa = isa[:0xFFF+1] // 第31行： 一个暗示
  32.         for _, n := range isb {
  33.             _ = isa[n & 0xFFF] // 第33行： 边界检查消除了！
  34.         }
  35.     }
  36. }
  38. func main() {}
  1. $ go run -gcflags="-d=ssa/check_bce/debug=1" example5.go
  2. ./example5.go:7: Found IsInBounds
  3. ./example5.go:24: Found IsInBounds

总结

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

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

参考：

  1. Bounds Check Elimination
  2. Utilizing the Go 1.7 SSA Compiler（第二部分）