文档章节

Go1.7中的边界检查消除

漂泊尘埃
 漂泊尘埃
发布于 2017/04/14 18:18
字数 1644
阅读 102
收藏 0

Go1.7中的边界检查消除

原文链接:http://www.tapirgames.com/blog/golang-1.7-bce

最近发布的 Go 1.7 使用了一个新的基于静态单赋值(SSA)的编译器后端(不仅在amd64中可用)。SSA使得go编译器生成更高效的优化代码,比如 边界检查消除(BCE)常见的字表达式消除。 这篇文章将展示一些例子以说明BCE在官方的Go编译器1.7+中是怎样工作的。 在Go 1.7+,你可以运行 go build -gcflags="-d=ssa/check_bce/debug=1" 来展示哪些代码行需要检查边界。

Example 1

// example1.go
package main

func f1(s []int) {
	_ = s[0] // line 5: bounds check 
	_ = s[1] // line 6: bounds check 
	_ = s[2] // line 7: bounds check 
}

func f2(s []int) {
	_ = s[2] // line 11: bounds check 
	_ = s[1] // line 12: bounds check eliminatd!
	_ = s[0] // line 13: bounds check eliminatd!
}

func f3(s []int, index int) {
	_ = s[index] // line 17: bounds check 
	_ = s[index] // line 18: bounds check eliminatd!
}

func f4(a [5]int) {
	_ = a[4] // line 22: bounds check eliminatd!
}

func main() {}
$ go build -gcflags="-d=ssa/check_bce/debug=1" example1.go
# command-line-arguments
./11.go:5: Found IsInBounds
./11.go:6: Found IsInBounds
./11.go:7: Found IsInBounds
./11.go:11: Found IsInBounds
./11.go:17: Found IsInBounds

可以看到在函数 f2 中的 line 12 和 line 13 不需要检查边界了,在 line 11 的边界检查保证了 line 12 和 line 13 的索引不会越界。 但是在函数 f1 中,全部的3行代码都执行了边界检查。line 5 的边界检查不能保证 line 6 和 line 7 是安全的,line 6 的边界检查也不能保证 line 7 是安全的。 对于函数 f3 来说,如果第一个 s[index] 是安全的,Go 1.7+ 编译器就能知道第二个 s[index] 绝对是安全的。 Go 1.7+ 编译器也能准确的知道函数 f4 中唯一的一行(line 22) 也是安全的。

Example 2

// example2.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] // line 22: bounds check 
		_ = 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 build -gcflags="-d=ssa/check_bce/debug=1" example2.go
# command-line-arguments
./11.go:22: Found IsInBounds

可以看到在 example2.go 中只有一行代码需要边界检查。 Go 1.7+ 编译器可以聪明地做出结论:在函数 f5, f6, f8 和 f9 中的所有行都是安全的。 啊哈,看起来它还没有像人类那样聪明,line 22 看起来也是安全的。

Example 3

// example3.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 eliminatd!
}

func fb(s []int, index int) {
	_ = s[:index] // line 14: bounds check 
	_ = s[index:] // line 15: bounds check, not smart enough?
}

func fc() {
	s := []int{0, 1, 2, 3, 4, 5, 6}
	s = s[:4]
	index := rand.Intn(7)
	_ = s[:index] // line 22: bounds check 
	_ = s[index:] // line 23: bounds check, not smart enough?
}

func main() {}
$ go build -gcflags="-d=ssa/check_bce/debug=1" example3.go
# command-line-arguments
./11.go:9: Found IsSliceInBounds
./11.go:14: Found IsSliceInBounds
./11.go:15: Found IsSliceInBounds
./11.go:22: Found IsSliceInBounds
./11.go:23: Found IsSliceInBounds

Oh,还有这么多地方需要边界检查! 但是等等,为什么 Go 1.7+ 编译器认为 line 10 是安全的但是 line 15 和 line 23 却不是呢?是编译器不够聪明还是有bug? 事实上,编译器是正确的!为什么?原因是子切片的长度可能比原来的切片长。例如:

package main

func main() {
	s0 := make([]int, 5, 10) // len(s0) == 5, cap(s0) == 10

	index := 8

	// In golang, for the subslice syntax s[a:b],
	// the valid rage for a is [0, len(s)],
	// the valid rage for b is [a, cap(s)].
	
	// So, this line is no problem.
	_ = s0[:index]
	// But, above line is safe can't assure the following line is also safe.
	// In fact, it will panic.
	_ = s0[index:] // panic: runtime error: slice bounds out of range
}

所以 如果s[:index]是安全的那么s[index:]也是安全的 只有在 len(s)==cap(s) 的情况才成立。这就是为什么 example 3 中函数 fb 和 fc 的代码行仍需要做边界检查。 Go 1.7+ 编译器成功地在函数 fa 中检查到 len(s) == cap(s) 。做得好,Golang team! 然而,如果s[index:]是安全的那么s[:index]也是安全的 这句话看起来总是成立的。(译者注:注意index的位置,和前面是相反的)

Example 4

// example4.go
package main

import "math/rand"

func fa2() {
	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 eliminatd!
}

func fb2(s []int, index int) {
	_ = s[index:] // line 14: bounds check
	_ = s[:index] // line 15: bounds check // not smart enough?
}

func fc2() {
	s := []int{0, 1, 2, 3, 4, 5, 6}
	s = s[:4]
	index := rand.Intn(7)
	_ = s[index:] // line 22: bounds check 
	_ = s[:index] // line 23: bounds check eliminatd!
}

func main() {}
$ go build -gcflags="-d=ssa/check_bce/debug=1" example4.go
# command-line-arguments
./11.go:9: Found IsSliceInBounds
./11.go:14: Found IsSliceInBounds
./11.go:15: Found IsSliceInBounds
./11.go:22: Found IsSliceInBounds

在这个例子中,Go 1.7(和1.8)成功地判断出函数 fc2 中当 line 22 是安全的那么 line 23 也是安全的,但是在函数 fb2 中当 line 14 是安全的时没有判断出 line 15 也是安全的。

Example 5

虽然当前的编译器(Go 1.7.1 amd64 和 Go 1.8)没有足够聪明到消除一些不必要的边界检查,但是我们可以给编译器一些提示来帮助编译器消除这些不必要的边界检查。

// example5.go
package main

func fd(is []int, bs []byte) {
	if len(is) >= 256 {
		for _, n := range bs {
			_ = is[n] // line 7: bounds check, not smart enough.
		}
	}
}

func fd2(is []int, bs []byte) {
	if len(is) >= 256 {
		is = is[:256] // line 14: bounds check. A hint for the compiler.
		for _, n := range bs {
			_ = is[n] // line 16: bounds check eliminatd! 
		}
	}
}

func fe(isa []int, isb []int) {
	if len(isa) > 0xFFF {
		for _, n := range isb {
			_ = isa[n & 0xFFF] // line 24: bounds check, not smart enough.
		}
	}
}

func fe2(isa []int, isb []int) {
	if len(isa) > 0xFFF {
		isa = isa[:0xFFF+1] // line 31: bounds check. A hint for the compiler.
		for _, n := range isb {
			_ = isa[n & 0xFFF] // line 33: bounds check eliminatd! 
		}
	}
}

func ff(s []int) []int {
	s2 := make([]int, len(s))
	for i := range s {
		s2[i] = -s[i] // line 41: bounds check, not smart enough.
	}
	return s2
}

func ff2(s []int) []int {
	s2 := make([]int, len(s))
	s2 = s2[:len(s)] // line 48: bounds check. A hint for the compiler.
	for i := range s {
		s2[i] = -s[i] // line 50: bounds check eliminatd! 
	}
	return s2
}

func main() {}
$ go build -gcflags="-d=ssa/check_bce/debug=1" example5.go
# command-line-arguments
./11.go:7: Found IsInBounds
./11.go:14: Found IsSliceInBounds
./11.go:24: Found IsInBounds
./11.go:31: Found IsSliceInBounds
./11.go:41: Found IsInBounds
./11.go:48: Found IsSliceInBounds

总结

虽然官方的 Go 1.7(和1.8)编译器的 BCE 特性还不是很完美,但在很多常见的场景中它已经做得很好。毫无疑问地,Go 编译器在之后的版本会做得更好。感谢 Go 团队添加了这个漂亮的特性!

引用

  1. Bounds Checking Elimination - Google 文档
  2. Utilizing the Go 1.7 SSA Compiler

© 著作权归作者所有

上一篇: Go笔记-类型
漂泊尘埃

漂泊尘埃

粉丝 6
博文 38
码字总数 76552
作品 0
朝阳
私信 提问
Go 1.7 更新日志草案

这是Go1.7发行说明的草案,供Go1.7测试版准备。Go1.7尚未公布。通过我们的预期期,它将在2016年八月的某个发布时候发布。 语言变化 在此版本中一个很小的语言变化 Ports Go 1.7 adds an exp...

oschina
2016/06/02
11.1K
42
Go1.7将支持二进制包分发

Go1.7将支持二进制包分发 不出意外的话,Go1.7将在8月份发布。Go1.7最大的变化是引入SSA优化技术,号称有到的性能提升。 对于Windows用户,还有一个迟来的特性:就是生成C静态库(补充: Go1.7...

chai2010
2016/04/26
1K
8
LiteIDE X30 发布,Go 语言开发工具

Go 语言开发工具 LiteIDE X30 发布,新版本修复了BUG,支持Go1.7,编辑器增加了 FakeVim模式,支持快速文件打开(Ctrl+P)和快速编辑器打开(Ctrl+Alt+P)操作。...

七叶
2016/07/04
4K
29
DevExpress v18.1新版亮点——ASP.NET篇(四)

用户界面套包DevExpress v18.1日前终于正式发布,本站将以连载的形式为大家介绍各版本新增内容。本文将介绍了DevExpress ASP.NET v18.1 的新功能,快来下载试用新版本!点击下载>> Spreadsh...

Miss_Hello_World
2018/08/29
0
0
LiteIDE X30.2 发布,Go 语言开发工具

Go语言开发工具 LiteIDE X30.2发布,新版本修复BUG,在Go1.7 rc1下编译测试。 2016.7.12 Ver X30.2 * LiteApp * add new vs-dard css, thanks [tupunco](https://github.com/tupunco) * fix ......

七叶
2016/07/12
3.7K
33

没有更多内容

加载失败,请刷新页面

加载更多

Java8

package com.shi.lambda;import java.util.Arrays;import java.util.List;import org.junit.Test;import com.shi.model.Employee;/** * 初始化案例 * @author xiaosh......

小小小施爷
17分钟前
1
0
c# 动态编译代码

有时候做计算一些东西时候,算法一直变更,写在程序需要一直调整,因此算法写在cs文件,然后动态调用内部的方法去计算判断,只需变更cs文件即可。 static void Main() { Stopwatch watch = n...

朝如青丝暮成雪
18分钟前
2
0
好程序员技术分享html5和JavaScript的区别

好程序员技术分享html5和JavaScript的区别,HTML5广义上讲是前端开发学科的代名词,包含HTML5、CSS3及JavaScript三个重要的部分,是运行在浏览器上应用的统称。如PC端网站、管理系统、手机网...

好程序员IT
20分钟前
1
0
tomcat 与 spring boot 设置虚拟路径

tomcat 设置虚拟路径 <Context path="/uploadDir" docBase="/data"/>path是请求访问的路径docBase是服务器存储文件的路径,Linux 根目录下 data spring boot 虚拟路径设置 registry.addRe......

kdy1994
23分钟前
1
0
var ,let ,const 的区别和共同点

一、let和var区别 1.关于变量提升,var能变量提升,let不能 // 关于var 如下所示console.log(a); //输出undefined,此时就是变量提升var a = 2; console.log(a); //2 //相当于下面...

MrBoyce
28分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部