Bounds Check Elimination

Since Go 1.7, the standard Go compiler has used a new compiler back end, which based on static single-assignment form (SSA). SSA makes go compiler generate more efficient code with optimizations like bounds check elimination (BCE) and common subexpression elimination (CSE).

This article will show some examples how BCE works in the standard Go compiler 1.7+.

In Go 1.7+, one can run go build -gcflags="-d=ssa/check_bce/debug=1" to show which code lines still need bounds checking.

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 eliminated!
	_ = s[0] // line 13: bounds check eliminated!
}

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

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

func main() {}
$ go build -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

We can see that there are no needs to do bounds checking for line 12 and line 13 in function f2, for the bounds check at line 11 ensures that the indexes in line 12 and line 13 will not be out of range.

But in function f1, bounds check must be performed for all three lines. The bounds check at line 5 can't ensure line 6 and line 7 are safe, and the bounds check at line 6 can't ensure line 7 is safe.

For function f3, Go 1.7+ compiler knows the second s[index] is absolutely safe if the first s[index] is safe.

Go 1.7+ compiler also correctly thinks the only line (line 22) in function f4 is safe.

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]
		_ = 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

Cool! The standard compiler removes all bound checking in this program.

Note: before Go 1.11, the standard compiler is not smart enough to detect line 22 is safe.

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 eliminated!
}

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
./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

Oh, so many places still need to do bounds check!

But wait, why does the Go standard compiler 1.7+ think line 10 is safe but line 15 and line 23 are not? Is the compiler still not smart enough or is it a bug?

In fact, the compiler is right here! Why? The reason is the length of a sub-slice may be larger than the original slice. For example:

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 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 ensure the following line is also safe.
	// In fact, it will panic.
	_ = s0[index:] // panic: runtime error: slice bounds out of range
}

So the statement if s[:index] is safe then s[index:] is also safe is only true when len(s) is equal to cap(s). This is why the code lines in function fb and fc of example 3 still need to do bounds checking.

Go standard compiler 1.7+ successfully detects len(s) is equal to cap(s) in function fa. Great work! Go team!

Example 4

// example4.go
package main

import "math/rand"

func fb2(s []int, index int) {
	_ = s[index:] // line 7: bounds check
	_ = s[:index] // line 8: 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 15 bounds check
	_ = s[:index] // line 16: bounds check eliminated!
}

func main() {}
$ go build -gcflags="-d=ssa/check_bce/debug=1" example4.go
./example4.go:7:7: Found IsSliceInBounds
./example4.go:15:7: Found IsSliceInBounds
In this example, The standard Go compiler successfully concludes

(Before Go SDK 1.9, the standard Go compiler failed to detect line 16 doesn't need bounds checking.)

Example 5

Although the current version of the standard Go compiler is still not smart enough to eliminate some unneccessary bounds checkings, but we can make some hints to help the compiler eliminate these unneccessary bounds checkings.
// 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: to avoid bounds check at line 16
		for _, n := range bs {
			_ = is[n] // line 16: bounds check eliminated!
		}
	}
}

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: to avoid bounds check at line 33
		for _, n := range isb {
			_ = isa[n & 0xFFF] // line 33: bounds check eliminated!
		}
	}
}

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: to avoid bounds check at line 50
	for i := range s {
		s2[i] = -s[i] // line 50: bounds check eliminated!
	}
	return s2
}

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

A Use Case Of BCE: Efficient Slice Comparison

(Note: as Erik Dubbelboer pointed out, the trick shown in this section to optimize slice comparisons is not needed any more since Go SDK 1.11. The standard Go compiler 1.11+ becomes even smarter so that this trick is not needed ay more. I will remove this section after some time.)

We all know that slice types don't support comparison in Go. To compare two slices, we must write custom comparison code, or use the DeepEqual function in the reflect standard package. But the reflect.DeepEqual function is too slow.

The following is a custom slice comparison function.
func CompareSlices_General(a, b []int) bool {
	if len(a) != len(b) {
		return false
	}

	if (a == nil) != (b == nil) {
		return false
	}

	for i, v := range a {
		if v != b[i] { // here bounds check is needed for b[i]
			return false
		}
	}

	return true
}
Bounds checking is still needed for the b[i] in the for-range loop block to avoid index i out of range. We can modify the function a bit to remove the bounds checking.
func CompareSlices_BCE(a, b []int) bool {
	if len(a) != len(b) {
		return false
	}

	if (a == nil) != (b == nil) {
		return false
	}

	b = b[:len(a)] // this line is the key.
	for i, v := range a {
		if v != b[i] { // no bounds check for b[i] now!
			return false
		}
	}

	return true
}
Let's benchmark the two functions. The result:
Benchmark_SliceComparison/General-4         	 5000000	       287 ns/op
Benchmark_SliceComparison/BCE-4             	 5000000	       251 ns/op

The BCE version is about 12.5% faster than the general version. Really not bad.

Summary

Although the BCE feature in the standard Go compiler is still not perfect, it really does well for many common cases. It is no doubt that Go compiler will do better in later versions. Thank Go team for adding this wonderful feature!

References:

  1. gBounds Checking Elimination
  2. Utilizing the Go 1.7 SSA Compiler

[edit@2016/09/22] added example 5 and refs.


The Go 101 project is hosted on both github and gitlab. Welcome to improve Go 101 articles by submitting corrections for all kinds of mistakes, such as typos, grammar errors, wording inaccuracies, description flaws, code bugs and broken links.

Support Go 101 by playing Tapir's games. Cryptocurrency donations are also welcome:
Bitcoin: 1xucQbv5jujFPPwhyg395ri5yV71hx9g9
Ethereum: 0x5dc4aa2c2bbfaadae373dadcfca11b3358912212